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 (50)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• A Simpler Approach to Matrix Completion
• Rank-Sparsity Incoherence for Matrix Decomposition
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• 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
• Guaranteed Matrix Completion via Non-convex Factorization
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Self-Calibration and Biconvex Compressive Sensing
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Matrix Completion from Noisy Entries
• Incoherence-Optimal Matrix Completion
• Matrix Completion has No Spurious Local Minimum
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• 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
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Non-convex Robust PCA
• Near-optimal bounds for phase synchronization
• ROP: Matrix recovery via rank-one projections
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Phaseless Rcovery using Gauss-Newton Method
• Phase Retrieval: An Overview of Recent Developments
• 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
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Fast, Robust and Non-convex Subspace Recovery
• Algorithmic stability and hypothesis complexity
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• A Selective Overview of Deep Learning
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Distributed Estimation of Principal Eigenspaces
• Phase Retrieval via Incremental Truncated Wirtinger Flow
• Convolutional Phase Retrieval via Gradient Descent
• A Convex Formulation for Mixed Regression with Two Components: Minimax Optimal Rates
• Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization
• 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 (90)

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