Matrix Completion has No Spurious Local Minimum

Rong Ge; Jason D. Lee; Tengyu Ma

Source-linked AI summary

Matrix Completion has No Spurious Local Minimum

Rong Ge, Jason D. Lee, Tengyu Ma

arXiv:1605.07272v4May 24, 2016cs.LGcs.DSstat.ML

TL;DR

The paper asks why nonconvex matrix-completion algorithms can succeed from random or arbitrary initialization despite analyses often requiring careful initialization. It shows that the regularized objective has no spurious local minima and that gradient-based methods can reach global solutions from arbitrary starting points, while the proof strategy has scope and uniform-convergence limitations.

Problem
Existing analyses often require initialization near the optimum, although random initialization typically achieves robust and fast convergence in practice; explaining this gap matters for large-scale collaborative filtering.
Method
The paper analyzes the geometry of a regularized nonconvex matrix-completion objective, using concentration-based links between full- and partial-observation objectives and a regularizer for non-incoherent points.
Results
All local minima recover the target matrix, and stochastic gradient descent converges in polynomial time from any starting point with high probability, while random-start gradient descent converges with probability 1.
Takeaways & Limitations
The result provides guarantees for many basic optimization algorithms and suggests that this objective-geometry framework may apply to other problems with partial or noisy observations.
Takeaways & Limitations
Uniform-convergence arguments of the required form may hold only inside an incoherent ball, so handling non-incoherent points requires a separate regularizer-based argument.

Abstract

from arXiv · show

Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for \textit{positive semidefinite} matrix completion has no spurious local minima --- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve positive semidefinite matrix completion with \textit{arbitrary} initialization in polynomial time. The result can be generalized to the setting when the observed entries contain noise. We believe that our main proof strategy can be useful for understanding geometric properties of other statistical problems involving partial or noisy observations.

1 Introduction

Matrix completion methods trade the computational cost of convex relaxations for faster non-convex optimization, but their theory often requires careful initialization. This paper shows that, under stated positive-semidefinite and regularization assumptions, every local minimum is globally correct, enabling convergence from arbitrary starts.

Motivation: Matrix completion recovers a low-rank matrix from partial observations and supports applications including recommender systems, dimension reduction, and multiclass learning.Convex relaxations provide strong statistical guarantees but are computationally expensive in practice.
Motivation: Non-convex matrix completion algorithms are much faster than convex relaxations, which is crucial for large-scale collaborative filtering.
Open question: Most existing analyses require an initialization already close to the optimum, whereas practitioners typically use random initialization with robust and fast convergence.
Main results: Under symmetric positive-semidefinite modeling, independent entry sampling, bounded condition number, and row-norm regularization, the regularized objective has no spurious local minima.The target is modeled as M = ZZ^T, and the regularizer penalizes rows of X that are too large.
Main results: All local minima satisfy XX^T = Z Z^T = M when p ⩾ poly(κ, r, µ, log d)/d.
Algorithmic consequence: Stochastic gradient descent converges in polynomial time to a solution with XX^T = Z Z^T = M from any starting point, while gradient descent succeeds with probability 1 from random starts.
Robustness: The guarantee is robust to Gaussian observation noise, yielding ||XX^T − ZZ^T||_F ⩽ ε when the sampling probability is sufficiently large.The stated noise standard deviation is comparable to the magnitude of an entry.
Proof strategy: The proof analyzes first- and second-order optimality conditions, using the regularizer to exclude spurious minima and concentration inequalities to connect full and partial observations.Uniform convergence requires special handling outside the incoherent region, where the regularizer supplies a different argument.

2 Preliminaries

The preliminaries define the sampling operator, matrix norms, and first- and second-order optimality conditions used to analyze matrix completion objectives. A general theorem connects approximate first- and second-order stationarity to finding an approximate global minimum in polynomial time.

PΩ maps a matrix to one retaining observed entries on Ω and zeros elsewhere.
The analysis uses Frobenius, spectral, elementwise infinity, and induced p-to-q matrix norms, along with the shorthand ∥A∥Ω = ∥PΩA∥F.
A first-order necessary condition requires ∇f(x) = 0, while a second-order necessary condition requires ∇2f(x) ⪰ 0.
The relaxed second-order condition permits ∇2f(x) ⪰ −τI, making stationarity requirements more robust and compatible with efficient algorithms.
If approximate first- and second-order conditions imply ε^c-closeness to a global minimum, several optimization methods can find a δ-accurate global minimum in time polynomial in 1/δ, 1/τ0, and d.

3 Proof Strategy: “simple” proofs are more generalizable

The proof strategy starts from the rank-one fully observed case and transfers its geometric conclusions to partial observations through inequalities linear in the sampling indicators. Uniform concentration holds inside an incoherent domain, while regularization handles non-incoherent points.

Overview: The rank-one analysis first studies full observation, then generalizes the proof to random partial observation.
Rank-one setting: For rank one, incoherence assumes M = zz⊤ with ∥z∥ = 1 and bounded ∥z∥∞, while the sampling probability is chosen as p = poly(µ, log d)/(dε).
Partial observation: Within the incoherent domain B, the regularizer vanishes and the partial-observation objective has global minima z and −z with value 0.
Partial observation: All local minima in B are O(√ε)-close to ±z, and the formal result later establishes that the only local minima are ±z.
Full observation: In the full-observation rank-one case, the objective has exactly two local minima, {±z}.
Full observation: The eigenvector-based proof identifies critical points through ∇g(x) = Mx − ∥x∥2x = 0 and rejects non-top eigenvectors using a negative Hessian direction.
Partial observation: This proof does not generalize directly to partial observations because sampled critical points lack the eigenvector structure and make Hessian analysis difficult.
“Simple” proofs: The alternative proof uses inequalities linear in 1Ω, allowing the partial-observation argument to follow from the full-observation argument via concentration inequalities.

4 Warm-up: Rank-1 Case

The rank-1 analysis shows that first- and second-order optimality conditions, together with a regularizer, exclude spurious local minima both inside and outside the incoherent region.

General strategy: The regularizer penalizes coherent points while vanishing for incoherent x, enabling separate geometric arguments across the domain.Its fourth-power form also provides Lipschitz second-order derivatives.
Extension to general x: Outside the incoherent region, the regularizer changes the geometry so that candidate points have nonzero gradient or violate necessary optimality conditions.The proof partitions Rd into regions where different lemmas rule out local minima.
Handling incoherent x: Within the incoherent region, concentration inequalities relate partial-observation expressions to their fully observed counterparts.The regularizer is zero there, simplifying the first-order analysis.
Handling incoherent x: First-order optimality constrains x to align with z after scaling, while second-order optimality supplies a lower bound on its norm.These properties are combined to show xxT is close to zzT.

5 Rank-r case

The rank-r proof extends the rank-1 strategy by controlling row coherence, singular values, and the regularizer, then showing every local minimum recovers the target matrix.

Setup: The rank-r setting represents the target as M = ZZT and uses an objective with a row-based regularizer.The regularizer gradient has the form ∇R(X) = ΓX with diagonal Γ and nonnegative rowwise alignment.
Main theorem: With high probability, every local minimum satisfies f(X) = 0 and therefore XXT = ZZT.The theorem also states approximate-global-minimum guarantees for points satisfying approximate first- and second-order conditions.
First-order control: First-order optimality and the regularizer control the largest row norm of X, supplying an incoherence-like bound needed for concentration.The proof derives this through a rank-r analogue of the rank-1 argument.
Second-order control: Second-order optimality forces the smallest singular value of X to remain bounded below relative to Z.The argument uses a direction supported where the regularizer vanishes, eliminating its contribution to the second-order condition.
Closeness to the solution: The proof combines first- and second-order consequences to show that ZZᵀ and XXᵀ are close, including the bound ∥ZZT −XXT ∥F ⩽O(δ∥Z∥2/σmin(Z)3).It decomposes Z into components in and orthogonal to the column span of X.

6 Conclusions

The paper concludes that the non-convex matrix completion objective has no spurious local minima, while leaving robustness under broader model assumptions open.

Conclusion: The objective’s local minima are also global despite its non-convexity.The authors identify robustness to asymmetric completion, weighted observations, and alternative distance measures as open questions.
Conclusion: The proof framework is proposed as a way to study objective geometry in other problems involving partial or noisy observations.

A Omitted Proofs in Section 4

The appendix derives the first- and second-order optimality conditions and supplies supporting bounds used in the rank-1 proof.

Optimality conditions: The first-order condition follows from Taylor expansion and equates the sampled residual gradient with the regularizer gradient.The derived relation is 2PΩ(M −xx⊤)x = λ∇R(x).
Optimality conditions: The second-order condition requires the Hessian quadratic form, including the regularizer contribution, to be nonnegative in every direction.A τ-relaxed version permits a controlled negative curvature bounded by τ.
Supporting lemmas: For bounded incoherent x, the appendix shows the restricted target component has substantial norm, supporting the lower-bound argument.The proof establishes ∥zJ∥⩾1/2 under the stated assumptions.
Supporting lemmas: Combining the optimality relations yields alignment between x and z and then closeness between xxT and zzT.The decomposition z = ux + v bounds both the scaling error and the orthogonal component.

B Handling Noise

With Gaussian noise, exact recovery is impossible, but the analysis still proves approximate recovery under sufficiently large noise. The proof adapts only a few concentration and optimality bounds.

Noise model: Gaussian perturbations make exact recovery impossible because distinct factors can produce the same noisy observation.The observed matrix is M = ZZT + N, with independent Gaussian noise entries.
Guarantee: σ√log d ⩽ µ2r/d is sufficient for the section’s conclusions to remain unchanged, even when noise is nearly as large as the maximum entry.Under the sampling and regularization conditions, local minima satisfy the stated approximation bound.
Proof changes: The proof changes in three places: the infinity-norm bound on M and the first- and second-order optimality conditions.These are the points where noise enters the arguments.
Proof changes: The required noise bounds control |M|∞ and the noise inner products appearing in the optimality inequalities.The stated bounds are established using Lemmas D.5 and D.6.

C Finding the Exact Factorization

The section constructs an exact factorization U aligned with a near-solution X and uses regularizer correlation plus concentration to show that first-order stationary points are global optima.

Proof strategy: The proof reduces exact recovery to showing that points satisfying first- and second-order conditions must equal the target matrix factorization.It first establishes closeness, then proves XXT = ZZT exactly.
Conclusion: Consequently, any point in the analyzed neighborhood satisfying the first-order condition is a global optimum, equivalently satisfying XXT = ZZT.The proof combines the objective decomposition, regularizer correlation, and bounds on the sampled terms.
Regularizer: The regularizer has nonnegative correlation with X − U, including strictly positive correlation for rows whose norms exceed the regularization threshold.The gradient aligns with Xi for sufficiently large row norms.
Factorization geometry: All factors U satisfying UUT = ZZT have the same row norms and Frobenius norm because they differ from Z by an orthonormal transformation.This symmetric-case observation replaces asymmetric row-norm bounds used in prior work.
Constructing U: If ||XXT − M||F = ε ⩽ σmin(Z)2/100, there exists U with UUT = M and ||X − U||F ⩽ 5ε√r/σmin(Z)2.The construction sets the lower block to zero and normalizes the upper block.
Stationarity argument: Concentration bounds make the sampled quadratic error small while preserving a large tangent-space component, enabling a positive gradient correlation away from the exact solution.The relevant tangent-space matrix has rank O(nr).

D Concentration inequality

The concentration section establishes that random sampling preserves inner products, spectral behavior, and key low-rank gradient terms, including under Gaussian noise.

Low-rank concentration: Random sampling preserves the inner product of two low-rank matrices with high probability.This result supports second-order optimality arguments.
Proof tools: The proof controls deviations using Bernstein bounds, truncation, ε-nets, and union bounds over low-rank matrices.The ε-net has size dO(dr), allowing uniform control.
Uniform bounds: For independent sampling, the relevant quadratic deviations are bounded by O(pν6r log2 d/d), which is below p2ε2 when p ⩾ Cν6r log1.5 d.The argument extends from the net to all matrices by approximation.
Symmetric sampling: The same concentration framework is adapted to symmetric sampling by pairing off-diagonal indicators and controlling diagonal contributions.Symmetry changes the indicators but only affects bounds up to constant factors.
Spectral approximation: Sampling also yields a spectral approximation used to control the sampled matrix term in the gradient.The proof applies matrix Bernstein inequalities.
Noise concentration: For Gaussian noise, analogous concentration lemmas bound sampled noise inner products and the spectral norm of the sampled noise matrix.Their proofs use the same or simpler concentration arguments than the noiseless case.

E Auxiliary Lemmas

The auxiliary lemmas provide the probabilistic discretization and moment bounds needed to obtain uniform concentration over low-rank matrices.

Probabilistic tools: Vector Bernstein’s inequality supplies concentration for sums of independent random vectors.It is used as a foundational probabilistic tool in the auxiliary arguments.
Moment bounds: Moment inequalities bound sums of powers of nonnegative quantities and control their maximum element.The resulting bound is max ai ⩽ Cr1/6 under the stated sixth-power condition.
Low-rank nets: For any ζ ∈ (0, 1), a finite rank-r net approximates every Frobenius-unit rank-r matrix within ζ and has size (d/ζ)O(dr).This cardinality supports union bounds in the concentration proofs.
ε-net construction: An ε-net for the unit Euclidean ball has size (d/ε)O(d), and the same construction applies to matrices under Frobenius norm.This converts uniform matrix control into finite-set control.
Low-rank nets: The proof constructs separate nets for matrix factors and diagonal singular-value matrices before combining them into a net Γ for rank-r matrices.The factors have Frobenius-radius bounds √r, while the diagonal net has radius 1.