Implicit Regularization in Nonconvex Statistical Estimation
summary
Vanilla gradient descent on nonconvex statistical losses implicitly enforces incoherence and therefore converges much faster than worst-case theory predicts. Using spectral initialization and a leave-one-out sequence to get pointwise L∞ control, the analysis shows Gaussian designs yield implicit regularization that keeps iterates in an incoherent region and gives logarithmic iterations rather than O(n). Empirically n up to 1000 reaches five‑digit accuracy in ~200 iterations and the approach extends to matrix completion and blind deconvolution with optimal entrywise error.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:29Nonconvex estimation problems are everywhere
- 1:05Blessing of randomness
- 1:48Optimization-based methods: two-stage approach
- 4:05How about unregularized gradient methods?
- 7:57Phase retrieval / solving quadratic systems
- 9:37Gradient descent theory revisited
- 10:54What does this optimization theory say about WF?
- 14:17Numerical surprise with
- 15:09A second look at gradient descent theory
- 20:25Key ingredient: leave-one-out analysis
- 21:46Low-rank matrix completion
- 22:36Theoretical guarantees
- 24:06Blind deconvolution
- 24:52Summary
related talks
01h 23mImplicit Regularization II
11mOn Implicit Regularization in Deep Learning
01h 05mFirst-Order Optimization and Online Learning Techniques in the Design of Fast Spectral Algorithms
23mOn Implicit Regularization in Deep Learning
01h 17mImplicit Regularization I
01h 18mReconsidering Overfitting in the Age of Overparameterized Models
01h 01mRobustness, Stochastics, Uncertainty 2
46mLearning Functions and Sets with Spectral Regularization