How many samples is a good initial point worth in Low-rank Matrix Recovery?

Jialun Zhang, Richard Y. ZhangNeurIPS 2020 · OpenReview

The Gap Between Global and Local Guarantees

Low-rank matrix recovery, such as matrix sensing, is a fundamental problem in data science with applications ranging from medical imaging to recommendation systems. Because the problem is naturally non-convex, its optimization landscape can theoretically be filled with "spurious" local minima—traps that prevent algorithms like gradient descent from finding the true solution.

Researchers have found that gathering enough data "smooths out" this landscape, eventually eliminating these traps. However, there is a massive gap between theory and practice. Global guarantees (which ensure successful recovery from any starting point) are extremely pessimistic, requiring an impractically huge amount of data to ensure no traps exist anywhere in the space. Conversely, local guarantees (which ensure success if you start "close enough" to the truth) are more realistic but have lacked a precise mathematical link to sample complexity.

This paper bridges that gap by asking a highly practical question: Exactly how many fewer samples do I need if my starting point is $X\%$ better?

Threshold RIP Constants and the First-Order Approximation

To quantify the value of a good initialization, the authors use the Restricted Isometry Property (RIP) constant ($\delta$) as a proxy for sample complexity. In simple terms, a smaller $\delta$ implies a more "perfect" measurement operator, which in practice requires a larger number of samples ($m$).

The core of their approach relies on introducing Threshold RIP Constants:

  • $\delta_{soc}(X)$: The maximum $\delta$ allowed before a specific point $X$ becomes a spurious local minimum (meaning it satisfies second-order conditions, including a positive semidefinite Hessian).
  • $\delta_{foc}(X)$: A simpler threshold based only on whether $X$ is a critical point (satisfying first-order conditions).

Because calculating exact second-order conditions for general rank-$r$ matrices is exceedingly difficult, the authors prove that $\delta_{foc}$ serves as a remarkably tight lower bound for $\delta_{soc}$.

Comparison of first-order and second-order threshold constants

One of the most surprising insights of the paper is that the second-order condition is often "inactive" near the solution. This means that simply ensuring a point isn't a critical point (first-order) is usually enough to ensure it isn't a local minimum.

The Geometry of Failure

By analyzing these thresholds, the authors uncover the "geometry of failure." They derive a closed-form geometric solution for $\delta_{foc}$ based on the "incidence angle" ($\theta$) between the current estimate and the ground truth error.

A point $X$ is most likely to become a trap if its column space is nearly orthogonal to the ground truth. Conversely, if $X$ is even slightly aligned with the truth, it requires significantly less data to prevent it from becoming a spurious local minimum.

Level sets of the optimization landscape

Key Results: The Linear Trade-off

The paper establishes a clear, quantifiable exchange rate between initialization quality and data requirements.

Through their geometric formula (Theorem 4), the authors show that the threshold for a point to be a spurious critical point is exactly $\cos \theta$. Building on this, Theorem 5 and Corollary 6 demonstrate that for an initial point with a relative error $\epsilon$, the required RIP constant scales as $\sqrt{1 - C\epsilon}$.

When translated back to real-world sample complexity, this means that a linear improvement in the quality of the initial guess ($\epsilon$) corresponds to a constant-factor reduction in the number of measurements ($m$) needed to guarantee success.

Limitations and Future Directions

While this paper provides a rigorous mathematical foundation for the value of initialization, the authors note a few limitations and areas for future work:

  • Problem Specificity: The current proofs rely heavily on the specific structure of the matrix sensing problem. It remains an open question whether this "incidence angle" logic maps perfectly to related problems like matrix completion or robust PCA.
  • The Cost of Initialization: The paper treats the initial point as a "given." In practice, finding a better initial point (e.g., via spectral initialization) also costs samples. Understanding the optimal trade-off between samples spent on initialization versus samples spent on the main optimization is a promising next step.
  • Neural Network Parallels: The authors suggest that these landscape-quantification techniques—measuring trap likelihood based on distance from the truth—could eventually help explain why highly non-convex neural networks reliably converge in practice.

Summary updated

Abstract

Given a sufficiently large amount of labeled data, the nonconvex low-rank matrix recovery problem contains no spurious local minima, so a local optimization algorithm is guaranteed to converge to a global minimum starting from any initial guess. However, the actual amount of data needed by this theoretical guarantee is very pessimistic, as it must prevent spurious local minima from existing anywhere, including at adversarial locations. In contrast, prior work based on good initial guesses have more realistic data requirements, because they allow spurious local minima to exist outside of a neighborhood of the solution. In this paper, we quantify the relationship between the quality of the initial guess and the corresponding reduction in data requirements. Using the restricted isometry constant as a surrogate for sample complexity, we compute a sharp “threshold” number of samples needed to prevent each specific point on the optimization landscape from becoming a spurious local minima. Optimizing the threshold over regions of the landscape, we see that, for initial points not too close to the ground truth, a linear improvement in the quality of the initial guess amounts to a constant factor improvement in the sample complexity.
BibTeX
@inproceedings{zhang2020how,
  author = {Jialun Zhang and Richard Y. Zhang},
  title = {{How many samples is a good initial point worth in Low-rank Matrix Recovery?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=zxdA0tJYW8a},
}
Figure