PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Optimality of Local Search for Low Rank Matrix Recovery

Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro

arXiv:1605.07221v2stat.MLcs.LGmath.OC

TL;DR

Low-rank matrix sensing uses a computationally efficient but non-convex factorized formulation, raising whether local search can recover the signal without favorable initialization. The paper proves global optimality under incoherent measurements, extends the guarantee to noisy settings, and combines saddle-point curvature with stochastic gradient descent to obtain polynomial-time convergence from random initialization.

  • Problem

    The paper asks whether practical factorized local optimization can globally recover low-rank signals without convex relaxation or initialization near the optimum.

  • Method

    The paper analyzes the factorized matrix-sensing objective under incoherence, characterizes local minima and saddle-point curvature, and applies a stochastic-gradient convergence result.

  • Results

    Noiseless problems have no spurious local minima, while noisy problems have local minima very close to a global optimum; SGD from random initialization converges in polynomially many iterations.

  • Takeaways & Limitations

    The results suggest SVD initialization is unnecessary for global convergence under the stated conditions, with random and SVD initialization showing no significant empirical recovery-probability difference.

Abstract

from arXiv · show

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent {\em from random initialization}.

1 Introduction

The paper studies practical non-convex factorized optimization for low-rank matrix sensing, addressing whether local search can recover the signal without convex relaxation or special initialization. It establishes global-optimality and convergence guarantees under incoherent measurements, extending beyond previously understood settings.

  • Low-rank matrix sensing recovers a positive semidefinite signal from linear measurements and supports applications including collaborative filtering, tomography, clustering, and multi-task learning.
  • Convex relaxations provide theoretical recovery guarantees, whereas earlier non-convex analyses commonly required SVD-based initialization near the optimum.
  • Factorized local optimization is widely used in practice because it scales with O(nr) variables rather than O(n^2), despite being non-convex and potentially having bad local minima.
  • The PSD assumption restricts the studied signal class, although the authors believe their techniques may extend to general matrices.
  • Under suitable incoherence, noiseless rank-r sensing has no spurious local minima, and all local minima recover X∗ exactly.
  • The work extends local-search guarantees to general rank-r matrix sensing, building on ideas from community detection and distinguishing its setting from PCA with full observations.

2 Formulation and Assumptions

The formulation models measurements as noisy linear inner products with sensing matrices and studies recovery in a high-dimensional regime. Identifiability depends on measurements being sufficiently spread out, formalized through restricted isometry.

  • The measurement operator maps X to inner products with sensing matrices, with observations y_i = ⟨A_i, X∗⟩ + w_i and i.i.d. Gaussian noise.
  • The high-dimensional regime has m measurements substantially smaller than the ambient matrix dimension n^2.
  • Measurements must be sufficiently spread across the matrix; otherwise unobserved blocks prevent recovery even when the target rank is known.
  • The restricted isometry property requires the measurement operator to preserve norms of matrices up to a specified rank.
  • δ2r < 1 ensures identifiability for rank-r targets, while i.i.d. Gaussian measurements achieve this with m = O(nr) measurements.

3 Main Results

Under RIP conditions, noiseless matrix sensing has only global local minima, while noisy and approximately low-rank settings keep local minima near global optima. Strict-saddle curvature then supports polynomial-time convergence from random initialization.

  • Noiseless matrix sensing has no spurious local minima: every local minimum satisfies UU^T = X* and is global.
  • Noisy measurements make exact recovery unavailable in general, but every local minimum remains close to a factorization of the true signal, with the radius decreasing as observations increase.
  • Noiseless first-order critical points that are not optimal have a direction of significant negative curvature.
  • Stochastic gradient descent from a random initialization converges to a global optimum in polynomially many iterations under the stated conditions.
  • The guarantees require (2r, 1/10)-RIP in the noisy case and (2r, 1/5)-RIP in the noiseless case.
  • The required spherical Gaussian measurement count is O(nr), up to a constant factor, under the paper’s milder RIP requirement.
  • For approximately low-rank signals, local-minimum error deteriorates gracefully and includes the best rank-r approximation error plus a nuclear-norm term scaled by δ2r.
  • In simulations, random and SVD initialization show no significant difference, with both methods transitioning near m = 2 · n · r.

4 Proof for the Noiseless Case

The noiseless-case proof combines first- and second-order optimality conditions under RIP to show that every local minimum is globally optimal. The argument addresses factorization invariance and uses tailored directions because the Hessian can remain positive semidefinite far from the optimum.

  • Proof technique: Unlike related problems, the Hessian of f(U) can be positive semidefinite far from an optimum, so the proof requires new directions for applying second-order conditions.This distinguishes the argument from analyses where Hessian positivity is confined to points near the optimum.
  • Factor alignment: The proof must account for invariance under r×r orthonormal transformations when comparing a stationary point with a global optimum.Choosing the best alignment R allows the first- and second-order conditions to be combined without degrading the isometry constants.
  • First-order optimality: First-order stationarity controls the error within the column space of U but leaves the orthogonal-direction error potentially arbitrarily large.The stationary-point lemma is therefore insufficient by itself to establish global optimality.
  • Second-order optimality: Second-order optimality bounds the remaining orthogonal-direction error, complementing the first-order bound.The proof compares factor-space and matrix-space distances after aligning U with U∗ using an orthonormal matrix R.

5 Necessity of RIP

The paper shows that RIP is necessary for a general no-spurious-local-minima guarantee by constructing noiseless measurement objectives with non-global local minima. The construction extends to arbitrary rank and also demonstrates the issue when the factorization rank exceeds the solution rank.

  • Why RIP matters: The necessity question is motivated by the fact that matrix sensing can be NP-hard for general linear measurement operators without RIP.This rules out expecting a polynomial-time guarantee for every measurement operator.
  • Explicit counterexample: An explicit noiseless measurement operator with rank(X∗) = r yields a non-global local minimum, showing that unrestricted measurement operators do not guarantee benign optimization.The example has f(X∗) = 0 while another feasible rank-constrained point is locally minimizing.
  • Explicit counterexample: The rank-1 construction has a local minimum with f(X) = 1 despite an exact rank-1 solution.The objective is f(X) = (X11 + X22 − 1)^2 + (X11 − 1)^2.
  • Arbitrary rank: The counterexample extends to any rank r by adding diagonal quadratic terms and padding the global and local minima.Thus the obstruction is not limited to rank-1 instances.
  • Overparameterized rank: Non-global local minima can persist when the optimization rank exceeds rank(X∗), including cases where rank(X∗) = 1.The paper introduces a separate rank-2 example for this setting.

6 Conclusion

Under conditions comparable to convex-relaxation guarantees, the non-convex formulation avoids spurious local minima and supports global convergence from random initialization. The conclusion also reports no significant empirical recovery difference between random and SVD initialization and positions matrix recovery as a model for studying deep-network optimization.

  • Main conclusion: Under suitable conditions, matrix sensing has no spurious local minima, while noisy or approximately low-rank settings place all local minima within a small radius of a global minimum.The same framework yields theoretical guarantees for SGD from random initialization.
  • Optimization guarantee: SGD from random initialization has a theoretical polynomial-time global convergence guarantee under the paper’s measurement conditions.This contrasts with prior analyses that relied on initialization near the optimum.
  • Initialization: Figure 1 finds no significant difference in recovery probability between random and SVD initialization for random rank-k matrices.The comparison directly examines whether SVD initialization improves global convergence empirically.
  • Broader relevance: The factorized matrix-recovery problem is presented as a depth-two neural network with linear transfer and a possible model for understanding local search in deep networks.The authors frame matrix recovery as a guide toward conditions enabling efficient deep-network training.

A Numerical Simulations

The simulations compare standard and noisy gradient descent under random and SVD initialization. Across settings, recovery exhibits a phase transition near m = 2 · n · r with no significant performance differences.

  • Experimental setup: The experiments use 100 × 100 random positive semidefinite rank-r matrices with Frobenius norm 1, varying r from 1 to 20.Measurements are Gaussian with entries distributed as N(0, 1/m).
  • Experimental setup: Standard and noisy gradient descent are evaluated with random and SVD initialization until convergence, using a 1e −2 final-error success threshold.Each experiment is repeated 20 times, with noisy updates receiving noise of magnitude 1e −4.
  • Results: m = 2 · n · r marks the phase transition for all tested initialization and gradient-descent settings.This agrees with the claim that f(U) has no local minima once m ≥ 2 · n · r.
  • Results: Random initialization has the same performance as SVD initialization in the success-probability experiments.The figure compares standard and noisy gradient descent across both initialization schemes.
  • Results: The normalized recovery error shows no significant difference between random and SVD initialization, including the rank-10 phase transition comparison.The rightmost plot compares all tested methods for rank 10.

B Proof for the Noisy Case

The noisy-case proof analyzes local optima satisfying first- and second-order conditions for the factorized objective. It uses these conditions to constrain the recovery error under noisy measurements.

  • Setup: The noisy proof assumes y = A(X∗) + w, where X∗ has rank r and w has independent Gaussian noise.The noise is specified as i.i.d. N(0, σ2).
  • Optimality conditions: A local optimum is required to satisfy both ∇f(U) = 0 and nonnegative curvature in every direction.These conditions are then used to constrain UU ⊤ − U ∗U ∗⊤.

B.1 First order optimality

The first-order analysis uses stationarity, the measurement operator’s isometry property, and an orthonormal basis for U’s column space to bound in-subspace error. A remaining orthogonal component can still be large.

  • Stationarity: For any stationary point U, the condition ∇f(U) = 0 supplies the starting relation for the first-order analysis.The proof then tests this condition using matrices built from an orthonormal basis of U’s column space.
  • RIP-based bound: The isometry property of the measurement operators converts the stationary-point relation into the lemma’s error inequality.The argument invokes a Frobenius-norm duality identity to complete the bound.
  • Conclusion: Any first-order stationary point is close to a global optimum within the subspace spanned by U’s columns.The result is stated for measurement operators satisfying the (2r, δ)-RIP.
  • Limitation: The orthogonal error component ∥X∗Q⊥Q⊤∥F can remain large, so the full distance between X and X∗ may be arbitrarily big.Thus, the first-order result controls only the component represented in U’s column space.

B.2 Second order optimality

The second-order analysis evaluates the Hessian along a factor-alignment direction and uses local-minimum curvature conditions to control error outside U’s column space. Combined with the first-order result, it yields the theorem’s noisy-case bound.

  • Hessian direction: The Hessian is evaluated along vec(U − U ∗R), where R is an orthonormal r × r matrix aligning the factors.This directional evaluation avoids requiring the full n · r × n · r Hessian.
  • Curvature analysis: The second-order calculation derives a directional curvature expression from the Hessian and the first-order optimality condition.The resulting inequality follows by applying second-order optimality at a local minimum.
  • Second-order bound: At a local minimum, the second-order optimality corollary bounds the aligned-factor error under the stated probability guarantee.The corollary assumes a measurement operator satisfying the (2r, δ)-RIP.
  • Theorem: Combining the optimality conditions proves the theorem characterizing local minima in the noisy setting.The proof assumes a non-global factorization and obtains the theorem’s probability statement and error control.
  • Theorem: δ ≤ 1 10 yields ∥UU ⊤ − U ∗U ∗⊤∥F ≤ c q m σw, with c ≤ 17 and probability at least 1 − 2 n2.This is the stated noisy-case proximity bound.

C Proof for the High Rank Case

The high-rank proof analyzes first- and second-order optimality under the (2r, δ)-RIP, showing that stationary points are accurate within the span of their factors and controlling orthogonal error at local minima.

  • The proof treats the inexact case rank(X∗) ≥ r with measurements y = A(X∗).
  • First-order stationarity under the (2r, δ)-RIP yields a bound for any stationary point U, where Q spans U’s column space.
  • Any stationary point is close to a global optimum within the subspace spanned by U’s columns.
  • The orthogonal error ∥X∗Q⊥Q⊤∥F can remain large, so the full distance between X and X∗ may be arbitrarily large.
  • Combining the first- and second-order optimality conditions completes the proof of Theorem 3.4.
  • The second-order analysis evaluates the Hessian along the direction vec(U − U∗R) and bounds the orthogonal error at local minima.

D Proofs for Section 3

The proofs establish the regularity and geometric conditions needed for strict-saddle optimization, including boundedness, smoothness, Lipschitz Hessians, and local strong convexity. These properties are then combined with existing convergence results.

  • Proofs for Section 3: The convergence proof verifies strict saddles, local strong convexity, boundedness, smoothness, and Hessian Lipschitzness.
  • Regularity properties: The objective has smoothness constant β determined by the maximum Hessian eigenvalue over the bounded domain.
  • Regularity properties: The Hessian is shown to be ρ-Lipschitz, with ρ = O(b) under the bounded-domain analysis.
  • Strict saddle property: The strict-saddle argument extends a negative-curvature bound from saddle points to an ε-neighborhood using gradient smoothness and Hessian Lipschitzness.
  • Local strong convexity: For δ = 1/10, f is locally strongly convex within radius θ = σr(X∗) / (200σ1(X∗)σr(U∗R)) around the optimum.
  • Supporting results: The supporting lemmas relate factor and Gram-matrix errors, characterize the aligning orthonormal matrix R, and use Gaussian concentration in the probabilistic bounds.
Loading 1605.07221v2…