A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing

We develop an efficient alternating framework for learning a generalized version of Factorization Machine (gFM) on steaming data with provable guarantees. When the instances are sampled from $d$ dimensional random Gaussian vectors and the target second order coefficient matrix in gFM is of rank $k$, our algorithm converges linearly, achieves $O(\epsilon)$ recovery error after retrieving $O(k^{3}d\log(1/\epsilon))$ training instances, consumes $O(kd)$ memory in one-pass of dataset and only requires matrix-vector product operations in each iteration. The key ingredient of our framework is a construction of an estimation sequence endowed with a so-called Conditionally Independent RIP condition (CI-RIP). As special cases of gFM, our framework can be applied to symmetric or asymmetric rank-one matrix sensing problems, such as inductive matrix completion and phase retrieval.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-08-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1608.05995
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Low-Rank Matrix Recovery

  2018cited by this paper
• An Overview of Low-Rank Matrix Recovery From Incomplete Observations

  2016cited by this paper
• Polynomial Networks and Factorization Machines: New Insights and Efficient Training Algorithms

  2016cited by this paper
• A Nonconvex Optimization Framework for Low Rank Matrix Estimation

  2015cited by this paper
• Nonconvex Low Rank Matrix Factorization via Inexact First Order Oracle

  2015cited by this paper
• Efficient Matrix Sensing Using Rank-1 Gaussian Measurements

  2015influential reference
• An Introduction to Matrix Concentration Inequalities

  2015cited by this paper
• Fast matrix completion without the condition number

  2014influential reference
• Convex recovery of a structured signal from independent random linear measurements

  2014cited by this paper
• Low rank matrix recovery from rank one measurements

  2014influential reference
• The Noisy Power Method: A Meta Algorithm with Applications

  2013cited by this paper
• Low-Rank Matrix Completion

  2013cited by this paper
• Near Optimal Compressed Sensing of Sparse Rank-One Matrices via Sparse Power Factorization

  2013cited by this paper
• Understanding Alternating Minimization for Matrix Completion

  2013cited by this paper
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming

  2013influential reference
• Provable Inductive Matrix Completion

  2013influential reference
• Phase Retrieval Using Alternating Minimization

  2013cited by this paper
• ROP: Matrix Recovery via Rank-One Projections

  2013influential reference
• Co-factorization machines: modeling user interests and predicting individual decisions in Twitter

  2013cited by this paper
• Angles between subspaces and their tangents

  2012cited by this paper
• Low-rank matrix completion using alternating minimization

  2012cited by this paper
• Oracle inequalities in empirical risk minimization and sparse recovery problems

  2011cited by this paper
• Phase Retrieval via Matrix Completion

  2011cited by this paper
• Fast context-aware recommendations with factorization machines

  2011cited by this paper
• Factorization Machines

  2010influential reference
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• Matrix Perturbation Theory

  1991cited by this paper

• Biologically inspired vision fusion: Central-peripheral synergy for medical image classification

  2026cites this paper
• Local feature enhancement transformer for image super-resolution

  2025cites this paper
• Near-optimal Reconfigurable Intelligent Surface Configuration: Blind Beamforming with Sensing

  2025cites this paper
• SPA: Self-Peripheral-Attention for central-peripheral interactions in endoscopic image classification and segmentation

  2023cites this paper
• What Limits the Performance of Local Self-attention?

  2023cites this paper
• ELSA: Enhanced Local Self-Attention for Vision Transformer

  2021cites this paper
• Learning Polynomial Neural Networks via Low Rank Tensor Recovery

  2020cites this paper
• Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex Optimization

  2020cites this paper
• Training Streaming Factorization Machines with Alternating Least Squares

  2019cites this paper
• Fast and Provable Algorithms for Learning Two-Layer Polynomial Neural Networks

  2019cites this paper
• Which Factorization Machine Modeling is Better: A Theoretical Answer with Optimal Guarantee

  2019influential citation
• Provable algorithms for nonlinear models in machine learning and signal processing

  2019cites this paper
• Provable Non-linear Inductive Matrix Completion

  2019cites this paper
• Towards Provable Learning of Polynomial Neural Networks Using Low-Rank Matrix Estimation

  2018influential citation
• Nonconvex Matrix Factorization From Rank-One Measurements

  2018cites this paper
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks

  2018cites this paper
• Symmetry. Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

  2018cites this paper
• Locally Linear Factorization Machines

  2017cites this paper
• Provable accelerated gradient method for nonconvex low rank optimization

  2017cites this paper
• Nonconvex One-bit Single-label Multi-label Learning

  2017cites this paper
• Improved Algorithms for Matrix Recovery from Rank-One Projections

  2017influential citation
• The Second Order Linear Model

  2017influential citation
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

  2016cites this paper
• Symmetry, Saddle Points, and Global Geometry of Nonconvex Matrix Factorization

  2016cites this paper