Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution

By Cong Ma, Kaizheng Wang, Yuejie Chi, Yuxin Chen. 2017

265 citations recorded by the source corpus.

Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require proper regularization (e.g., trimming, regularized cost, projection) in order to guarantee fast convergence. For vanilla procedures such as gradient descent, however, prior theory either recommends highly conservative learning rates to avoid overshooting, or completely lacks performance guarantees. This paper uncovers a striking phenomenon in nonconvex optimization: even in the absence of explicit regularization, gradient descent enforces proper regularization implicitly under various statistical models. In fact, gradient descent follows a trajectory staying within a basin that enjoys nice geometry, consisting of points incoherent with the sampling mechanism. This “implicit regularization” feature allows gradient descent to proceed in a far more aggressive fashion without overshooting, which in turn results in substantial computational savings. Focusing on three fundamental statistical estimation problems, i.e., phase retrieval, low-rank matrix completion, and blind deconvolution, we establish that gradient descent achieves near-optimal statistical and computational guarantees without explicit regularization. In particular, by marrying statistical modeling with generic optimization theory, we develop a general recipe for analyzing the trajectories of iterative algorithms via a leave-one-out perturbation argument. As a by-product, for noisy matrix completion, we demonstrate that gradient descent achieves near-optimal error control—measured entrywise and by the spectral norm—which might be of independent interest.

Subfields: Computational Mechanics, Mathematical Physics, Radiation, Optimization & Training, Statistical Learning Theory, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Radiation

In Optimization & Training

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Recent studies are on SGD for different tasks, such as logistic regression [27] and matrix factorization [11, 19, 16].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, methodology): “[26] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen.”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “[41] show that implicit regularization helps gradient descent avoid overshooting optima.”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, result): “Thirdly, while our results do not directly apply to settings where the population risk is not strongly convex, our results are still important for the following two-fold reasons: (1) while many learning problems are highly non-convex globally, they sometimes satisfy certain restricted strong convexi”
Lower bounds for non-convex stochastic optimization (2019, background): “Another growing body of work motivates this study by identifying sub-classes of non-convex problems for which all stationary (or second-order stationary) points are globally optimal [28, 29, 33, 45].”
On the Margin Theory of Feedforward Neural Networks (2018, background): “Ma et al. (2017) show that implicit regularization can help gradient descent avoid overshooting optima.”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, unknown): “dence intervals for Lasso (Javanmard and Montanari, 2015), likelihood ratio test (Sur, Chen and Candès, 2017), and nonconvex statistical learning (Ma et al., 2017; Chen et al., 2018).”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Using standard concentration inequalities for random matrices [55], [56], one derives the following strong convexity and smoothness bounds [27], [57], [58].”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “, 2015; Chen and Candes, 2015), blind deconvolution (Li et al., 2016; Ma et al., 2017; Huang and Hand, 2017), robust subspace recovery (Maunu et al.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “Other related works include [Ma et al., 2017, Gidel et al., 2019, Arora et al., 2019a, Suggala et al., 2018, Blanc et al., 2019, Banburski et al., 2019, Neyshabur et al., 2014, 2015].”
Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization (2018, background): “In particular, it has been argued that the optimization algorithms perform an implicit regularization , while optimizing the loss function, which is why the solution generalizes well (Neyshabur et al., 2017; Ma et al., 2017; Gunasekar et al., 2017; 2018; Soudry et al., 2018).”