On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?

Jianhao Ma, Salar FattahiarXiv 2023 · OpenReview

Abstract

This paper investigates the optimization landscape of robust low-rank matrix recovery using Burer-Monteiro factorization under $\ell_1$-loss. Contrary to standard optimization intuition, the study reveals that the ground truth solution often manifests as a strict saddle point rather than a local minimum. This phenomenon occurs in specific sample size regimes and is influenced by rank imbalance and matrix coherence. The findings suggest that the success of first-order methods in robust recovery may rely on their inability to escape these "desirable" saddle points.

Introduction

In machine learning, nonconvex problems are frequently solved by factorizing a large matrix $X$ into smaller factors $W_1 W_2^\top$ via the Burer-Monteiro method. While the optimization landscape is typically well-behaved for "clean" data, "robust" recovery—employing an $\ell_1$-loss function to mitigate outliers and heavy noise—introduces significant nonsmoothness and complexity.

Prevailing theory suggests that first-order algorithms, such as sub-gradient descent, succeed because the ground truth manifests as a local or global minimum. This research challenges that assumption, investigating whether local optimality is a prerequisite for learning or if the ground truth $X^\star$ can exist as a non-optimal point in the robust setting.

Methodology

The authors conduct a rigorous mathematical analysis of the optimization landscape for Burer-Monteiro factorization under $\ell_1$-loss, focusing on two primary statistical models: Matrix Sensing (Gaussian linear measurements) and Matrix Completion (partial observations).

The analysis utilizes tools from variational analysis, specifically Clarke subdifferentials for nonsmooth functions, and random process theory, including Orlicz processes and Dudley entropy integrals, to characterize curvature around the ground truth. A novel technique involving "Parametric Perturbation Sets" is introduced to prove the existence of descent directions at points that might otherwise appear to be solutions. Empirical validation was performed using synthetic statistical models with matrices of dimension $d=20$ and rank $r=3$, corrupted by 10% gross outlier noise.

Theoretical Insights

Several key discoveries emerge regarding the geometry of the loss surface:

  • The "Saddle" Regime: In symmetric matrix sensing, there exists a regime of sample sizes ($dr \lesssim m \lesssim dk$) where the ground truth is a strict saddle point. Despite having strictly negative curvature in at least one direction—implying a better objective value exists nearby—it remains the correct physical solution.
  • Rank Imbalance: In asymmetric problems, if the factors $W_1$ and $W_2$ have different ranks, the ground truth may not even be a critical point.
  • The Curse of Coherence: For matrix completion, if the ground truth matrix is "coherent" (energy concentrated in few entries), the true solution is never a local optimum, regardless of data volume.
  • Challenging the "Escape" Dogma: While most research focuses on escaping strict saddle points, this paper shows that in robust recovery, escaping the saddle would mean moving away from the correct answer toward an over-fitted, sub-optimal solution.

Main Results

The theoretical findings regarding the nature of the ground truth across different sample size regimes are summarized in the table below.

Summary of the optimization landscape for robust matrix recovery across different sample size regimes.

Key theorems include:

  • Theorems 1 & 2 (Symmetric Sensing): With high probability, the ground truth is a strict saddle point when the number of measurements $m$ is proportional to the degrees of freedom but below the over-parameterization threshold.
  • Theorem 5 (Matrix Completion): The ground truth is not a local minimum if even a single diagonal entry is noisy.

Empirically, sub-gradient methods with decaying stepsizes demonstrate linear convergence to the ground truth in many trials, despite its saddle-point nature. This suggests that nonsmooth algorithms may lack the "saddle-escaping" properties of smooth gradient descent, which serves as a beneficial feature in this context.

Discussion and Future Work

The discovery that the ground truth is often a saddle point raises questions about why sub-gradient methods remain at these points. The authors propose two conjectures: either the solutions are "non-active strict saddle points" where nonsmoothness traps the algorithm, or sub-gradient methods inherently lack the geometry required to escape these specific saddles. Future research is needed to develop a complete convergence theory explaining how initialization and stepsize allow practitioners to reliably "land" on these desirable saddle points.

Summary updated

BibTeX
@misc{ma2023optimization,
  author = {Jianhao Ma and Salar Fattahi},
  title = {{On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?}},
  year = {2023},
  url = {https://openreview.net/forum?id=WEZNE8wCb_},
}
Figure