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

Abstract

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 byproduct, 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.

accepted to Foundations of Computational Mathematics (FOCM)

References in corpus (20)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• The Complex Gradient Operator and the CR-Calculus
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Recovery Guarantees for One-hidden-layer Neural Networks
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• Non-convex Robust PCA
• Near-optimal bounds for phase synchronization
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• The Landscape of Empirical Risk for Non-convex Losses
• Fast matrix completion without the condition number
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• A Selective Overview of Deep Learning
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Convolutional Phase Retrieval via Gradient Descent
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• The Likelihood Ratio Test in High-Dimensional Logistic Regression Is Asymptotically a Rescaled Chi-Square

Cited by in corpus (89)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• The Numerics of Phase Retrieval
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Nonconvex Demixing From Bilinear Measurements
• A Priori Estimates of the Population Risk for Residual Networks
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Matrix completion with deterministic pattern - a geometric perspective
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Perturbed Amplitude Flow for Phase Retrieval
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependence
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Composite optimization for robust blind deconvolution
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Implicit competitive regularization in GANs
• Phase Retrieval via Smooth Amplitude Flow
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel Factorization
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Low-rank matrix completion and denoising under Poisson noise
• Tensor train completion: local recovery guarantees via Riemannian optimization
• Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
• Sparse Recovery Beyond Compressed Sensing: Separable Nonlinear Inverse Problems
• Blind Over-the-Air Computation and Data Fusion via Provable Wirtinger Flow
• Large-time asymptotics in deep learning
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Efficient Federated Low Rank Matrix Recovery via Alternating GD and Minimization: A Simple Proof
• Approximate Message Passing for Amplitude Based Optimization
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Inference for Heteroskedastic PCA with Missing Data
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Instance-dependent ${\ell }_{\infty }$-bounds for policy evaluation in tabular reinforcement learning
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: ${\ell }_{2,\infty }$ Statistical Guarantees
• Normal Approximation and Confidence Region of Singular Subspaces
• Learning Treatment Effects in Panels with General Intervention Patterns
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Confidence Region of Singular Subspaces for Low-rank Matrix Regression
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Short-and-Sparse Deconvolution -- A Geometric Approach
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps
• The nonsmooth landscape of blind deconvolution
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Sparse Tensor Additive Regression
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
• General Probabilistic Surface Optimization and Log Density Estimation
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Non-Convex Exact Community Recovery in Stochastic Block Model
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Exploiting Simultaneous Low-Rank and Sparsity in Delay-Angular Domain for Millimeter-Wave/Terahertz Wideband Massive Access
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• OMASGAN: Out-of-Distribution Minimum Anomaly Score GAN for Sample Generation on the Boundary
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries
• Non-Convex Structured Phase Retrieval
• Robust spectral compressive sensing via vanilla gradient descent
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Provable Low Rank Phase Retrieval
• Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise
• Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization
• Learning One-hidden-layer neural networks via Provable Gradient Descent with Random Initialization
• Good Classifiers are Abundant in the Interpolating Regime
• Learning Mixtures of Low-Rank Models
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective