Understanding Alternating Minimization for Matrix Completion

By Moritz Hardt. 2013

272 citations recorded by the source corpus.

Alternating minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for alternating minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-convex in nature. We give a new algorithm based on alternating minimization that provably recovers an unknown low-rank matrix from a random subsample of its entries under a standard incoherence assumption. Our results reduce the sample size requirements of the alternating minimization approach by at least a quartic factor in the rank and the condition number of the unknown matrix. These improvements apply even if the matrix is only close to low-rank in the Frobenius norm. Our algorithm runs in nearly linear time in the dimension of the matrix and, in a broad range of parameters, gives the strongest sample bounds among all subquadratic time algorithms that we are aware of. Underlying our work is a new robust convergence analysis of the well-known Power Method for computing the dominant singular vectors of a matrix. This viewpoint leads to a conceptually simple understanding of alternating minimization. In addition, we contribute a new technique for controlling the coherence of intermediate solutions arising in iterative algorithms based on a smoothed analysis of the QR factorization. These techniques may be of interest beyond their application here.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “…random, which corresponds to (cid:16) (cid:17) Our assumption is also a generalization of the one in [Bhojanapalli and Jain, 2014], which requires W to be d -regular expander-like (i.e., to have a spectral gap) but is concerned only with matrix completion where the entries of W can be 0 or 1 only.”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “This direction is popular for many non-convex problems including matrix completion/sensing (Jain et al., 2013; Hardt, 2014; Sun & Luo, 2015; Balcan et al., 2017), mixed linear regression (Zhong et al., 2016), subspace recovery (Elhamifar & Vidal, 2009) and other latent models (Anandkumar et al.,…”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “Problem (4) is a non-convex fourth-order polynomial optimization problem, and can be solved to stationary points by standard nonlinear optimization algorithms such as gradient descent method, alternating minimization [1], [18], [19], [21] and SGD (stochastic gradient descent) [1], [16], [23], [24].”
Matrix Completion, Counterfactuals, and Factor Analysis of Missing Data (2019, background): “ Candes and Tao (2010, Theorem 1.7), Candes and Plan (2010, Theorem 2, p.929), Keshevan et al. (2010, Theorem 1.2, p.2982), Keshavan et al. (2010, p.2061), Candes et al. (2011) Jain et al. (2013) and Hardt (2014) put restrictions on σ r/σ1 and/or σ r+1/σ r in addition to incoherence conditions, to s”
Phase Retrieval Using Alternating Minimization (2013, background): “We would like to stress that not only does a natural variant of our proposed algorithm have rigorous theoretical guarantees, it also is eﬀective practically as each of its iterations is fast, has a closed form solution and does not require SVD computation.”
Non-convex Optimization for Machine Learning (2017, background): “Several works have furthered the alternating minimization approach itself by reducing its sample complexity [Hardt, 2014], giving recovery guarantees independent of the condition number of the problem [Hardt and Wootters, 2014, Jain and Netrapalli, 2015], designing universal sampling schemes for rec”
Complete dictionary recovery over the sphere (2015, result): “The particular geometry of this problem does not demand any clever initialization, in contrast with most recent approaches to analyzing nonconvex recovery of structured signals [9–11, 13, 18–30].”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, methodology): “For matrix sensing or matrix completion, the works [Keshavan et al., 2010a,b, Hardt and Wootters, 2014, Hardt, 2014, Jain et al., 2013, Chen and Wainwright, 2015, Sun and Luo, 2015, Zhao et al., 2015, Zheng and Lafferty, 2016, Tu et al., 2015] showed that given a good enough initialization, many…”
Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, background): “This adds to the recent literature on analyzing alternating minimization Jain et al. (2013); Hardt (2013); Netrapalli et al. (2013, 2014) but these work in a setting where there is a convex program that is known to work too, and in our setting, the only known convex program runs in time exponential…”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, methodology): “For example, both the approaches based on alternating minimization [56], [99], [100]”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, unknown): “This is consistent with empirical observations and theory, which states that over-parameterization is crucial to train neural networks successfully Hardt (2014); Soudry and Carmon (2016). In contrast, in this work we demonstrate that we can approximate the optimal parameters in the noisy case, and o”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow (2015, unknown): “See also [Har14, SL15].”
Matrix Completion has No Spurious Local Minimum (2016, background): “More recently, there has been growing interest in analyzing non-convex algorithms for matrix completion [KMO10, JNS13, Har14, HW14, SL15, ZWL15, CW15].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “matrix completion [29, 159, 160, 207] vanilla gradient descent [26] [1, 11, 13, 208–211] regularized Grassmanian GD [16, 65] projected / regularized GD [19, 21, 63] alternating minimization [17, 123, 124] blind deconvolution / demixing — vanilla GD [26, 62] [5, 6] (subspace model) regularized GD [22”