Many fundamental problems in machine learning and signal processing involve recovering a low-rank matrix or tensor from incomplete observations. Traditionally, researchers relied on convex relaxations—such as replacing a rank constraint with a nuclear norm. While convex problems offer global convergence guarantees, they scale poorly to high-dimensional datasets because they require expensive operations like Singular Value Decomposition (SVD) at every iteration.
To bypass this computational bottleneck, a common strategy is direct factorization (e.g., the Burer-Monteiro approach, which parameterizes a low-rank matrix $X$ as $UU^\top$ or $UV^\top$). This eliminates the need for full-scale SVDs, but it introduces a major theoretical challenge: the resulting optimization landscape is inherently non-convex. Symmetries in the factorization mean there are multiple equivalent global minima, along with potential saddle points and spurious local minima.
Yet, empirical evidence consistently shows that simple first-order methods like gradient descent solve these non-convex problems with remarkable ease. The key to resolving this paradox lies in understanding the local geometry of the optimization landscape.
The Geometry of the Basin of Attraction
While the global landscape of these factored recovery problems is non-convex, the region immediately surrounding the true solution behaves entirely differently. Once an algorithm enters a specific neighborhood around the ground truth—often called the basin of attraction—the objective function exhibits properties equivalent to strong convexity.
In a classical convex setting, strong convexity guarantees that the objective function is bounded below by a quadratic bowl, ensuring that gradient steps consistently move toward the unique minimum at an exponential rate. In non-convex optimization, local strong convexity means that within the basin of attraction, the Hessian matrix of the loss function remains positive definite and well-conditioned.
As shown by John D. Lafferty in A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements, exploiting this local structure allows gradient descent to achieve linear convergence (also known as geometric convergence), where the reconstruction error drops exponentially over time. Instead of getting trapped in suboptimal local minima, the algorithm treats the non-convex problem as if it were convex once it is inside this safe zone.
The Two-Stage Paradigm: Warm Start and Polishing
To turn this geometric insight into a provable algorithm, researchers developed a powerful two-stage framework:
- Initialization (Warm Start): Use a computationally cheap, coarse estimation method (such as a spectral method or a convex relaxation) to land directly inside the local basin of attraction.
- Local Polishing: Run vanilla gradient descent to rapidly converge to the exact global optimum.
For instance, Zhaoran Wang et al. demonstrated this in Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time by combining a convex relaxation for initialization with a fast non-convex polishing stage to achieve minimax-optimal accuracy in polynomial time. Similarly, Stephen Tu et al. introduced Procrustes Flow in Low-rank Solutions of Linear Matrix Equations via Procrustes Flow, which pairs a smart spectral initialization with gradient descent on factored matrices to achieve geometric convergence independent of the matrix's condition number.
Generalizing Across Matrix and Tensor Problems
This local geometric tractability is not unique to standard matrix recovery; it spans a wide variety of structured optimization problems:
- Matrix Completion: In Guaranteed Matrix Completion via Non-convex Factorization, Ruoyu Sun et al. proved that standard non-convex factorization algorithms can achieve perfect recovery without artificial resampling tricks, thanks to the relative strong convexity of the basin. Even under non-linear or thresholded observations, such as ReLU sampling, Huikang Liu et al. in Symmetric Matrix Completion with ReLU Sampling showed that the objective function exhibits geodesic strong convexity near the ground truth, ensuring convergence despite global spurious minima.
- Factored Matrix Optimization: Operating directly on the factors $U$ and $V$ rather than the full matrix provides massive computational speedups. Anastasios Kyrillidis et al. leveraged this in Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably to prove linear convergence for general smooth and strongly convex objectives. The authors extended this to constrained settings (e.g., quantum state tomography) in Provable non-convex projected gradient descent for a class of constrained matrix optimization problems, showing that non-convex approaches match the reliability of convex methods while outperforming them in speed.
- Structured and Non-linear Completion: For structured matrices, such as outlier-corrupted Hankel matrices, HanQin Cai et al. in Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion demonstrated exponential error reduction within the basin of attraction. For non-linear inductive matrix completion, Kai Zhong et al. in Provable Non-linear Inductive Matrix Completion proved that despite the inclusion of neural network layers, local strong convexity guarantees a linear convergence rate to the global optimum.
- Tensor Recovery: Moving from matrices to higher-order tensors, Botao Hao et al. in Sparse and Low-Rank Tensor Estimation via Cubic Sketchings used a method-of-moments initialization followed by thresholded gradient descent to achieve rapid error reduction. Furthermore, Shuang Li et al. in Local and Global Convergence of General Burer-Monteiro Tensor Optimizations established that general Burer-Monteiro tensor parameterizations converge linearly under a warm start.
Beyond Matrices: Regression and Neural Networks
The principle of local strong convexity extends beyond low-rank factorization into non-convex statistical estimation and machine learning architectures:
- Mixed Linear Regression (MLR): When data is generated from multiple latent linear models, the objective landscape is globally non-convex. However, Kai Zhong et al. in Mixed Linear Regression with Multiple Components proved that the Hessian of the loss function becomes positive definite in a neighborhood around the true parameters, enabling simple gradient descent to achieve exact recovery.
- Pairwise Preferences: In recommendation systems with sparse comparison data, Suryanarayana Sankagiri et al. in Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization showed that the local region around user preferences exhibits strong convexity, allowing exponential convergence from a good initial estimate.
- Neural Networks: Even in deep learning, the same geometric phenomenon applies. In Recovery Guarantees for One-hidden-layer Neural Networks, Kai Zhong et al. provided provable global optimality guarantees for training one-hidden-layer networks by identifying a local basin of attraction where the loss function is strongly convex.
Implicit Regularization and Basin Boundaries
Why doesn't gradient descent accidentally wander out of this well-behaved basin during optimization?
Cong Ma 0001 et al. addressed this in Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval and Matrix Completion. They discovered that vanilla gradient descent possesses an implicit regularization property: the algorithm naturally confines its trajectory to a region where the Hessian matrix remains well-conditioned, avoiding the need for explicit algorithmic constraints or "training wheels."
Understanding exactly how large this safe zone is remains a critical question. Jean-François Aujol et al. provided a rigorous geometric analysis of these boundaries in On Strong Basins of Attractions for Non-convex Sparse Spike Estimation: Upper and Lower Bounds, establishing upper and lower bounds on the radius of strong basins of attraction. Their work shows that the size of the region where linear convergence is guaranteed scales predictably with the number of measurements.
Even in physical imaging problems like 3D X-ray reconstruction with overlapping measurements, Maria Klodt et al. in 3D Image Reconstruction from X-Ray Measurements with Overlap demonstrated that while the global objective is non-convex, it exhibits partial convexity within physically meaningful density ranges, allowing first-order methods to reliably find the global minimum.
Key Foundational Work
A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements (2015) — contributed 2 concept elements to this direction.
Guaranteed Matrix Completion via Non-Convex Factorization (2014) — contributed 1 concept elements to this direction.
Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time (2014) — contributed 1 concept elements to this direction.