Guaranteed Matrix Completion via Non-Convex Factorization

By Ruoyu Sun, Zhi-Quan Tom Luo. 2014

480 citations recorded by the source corpus.

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Representation & Self-Supervised Learning

Citations in the corpus

Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “The PL inequality is a generalization of strong-convexity and is satisfied for matrix factorization [57] or when minimizing the logistic loss on a compact set [22].”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “With additional assumptions, RSI is satisﬁed by important non-convex models such as single hidden-layer neural networks [46, 41, 80], matrix completion [81] and phase retrieval [17].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “These include neural networks [18, 17, 35], matrix completion [36] and phase retrieval [6].”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Some notable examples satisfying RSI include two-layer neural networks [7], matrix completion [13], dictionary learning [2], and phase retrieval [3].”
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “First, in parallel with spectral initialization methods, the proposed orthogonality-promoting initialization can be applied for semidefinite optimization [37], matrix completion [47], [39], as well as blind deconvolution [38].”
Non-convex Optimization for Machine Learning (2017, background): “Another interesting line of work for matrix completion is that of [Ge et al., 2016, Sun and Lu, 2015] which shows that under certain regularization assumptions, the matrix completion problem does not have any non-optimal stationary points once one gets close-enough to the global minimum.”
How to Escape Saddle Points Efficiently (2017, background): “On the other hand, saddle points (and local maxima) can correspond to highly suboptimal solutions in many problems [see, e.g., Jain et al., 2015, Sun et al., 2016b].”
Dropping Convexity for Faster Semi-definite Optimization (2015, unknown): “While there are some recent and very interesting works that consider using such non-convex parametrization [42, 64, 71, 82, 69, 81], their results only apply to speciﬁc examples.”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “proximaterecoveryinthenoiseless/noisysettingthatareasgoodasorbetterthanknown results. In the noiseless setting (E= 0), our sample size requirement and contraction factor are sharperthanthoseinthepaper[57]byapolynomialfactorintherankr. Turningtothenoisysetting,supposethenoisematrixEhasindependentsub-”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Local convergence of (regularized) GD was later established for matrix completion (without resorting to Grassmann manifolds) [20], matrix sensing [24], [53], and blind deconvolution under subspace prior [23].”
The non-convex geometry of low-rank matrix optimization (2016, background): “A good initialization can lead to global convergence if the initial iterate lies in the attraction basin of the global optima [2, 4, 12, 51].”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, background): “To prevent this, additional balancing regularization is often added [Li et al., 2019b, Park et al., 2017, Tu et al., 2016, Sun and Luo, 2016], though empirically this has been shown to be unnecessary.”
A Geometric Analysis of Phase Retrieval (2016, methodology): “Besides GPR studied here, this line of work includes low-rank matrix recovery [35,52,53,59,60,63,77,89,98,99,107,113], tensor recovery [7–9,44, 61], structured element pursuit [55,85], dictionary learning [3,4,10–12,96], mixed regression [90,110], blind deconvolution [67–69], super resolution [40], ”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, methodology): “Therefore, the preceding modified TWF may add to recent literature in applying nonconvex schemes for low-rank matrix completion [27,30,31,46], robust principal component analysis (PCA) [37], or even a broader family of latent-variable models (e.”