Research map / Optimization / Implicit bias and generalization
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval and Matrix Completion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use vanilla gradient descent with a large near-constant step size (about 1/log n) instead of the 1/n step size of prior WF theory, without explicit regularization | Wirtinger flow for phase retrieval · Phase retrieval, Gaussian design, m >= c0 n log n | iteration complexity to epsilon accuracy: O(n log(1/eps)) to O(log n log(1/eps)) | Helped |
| Implicit regularization: iterates and spectral init stay incoherent with sensing vectors (no trimming, regularized loss, or projection) | Vanilla gradient descent for phase retrieval · Phase retrieval, Gaussian design | max_j |a_j^T(x_t - x*)| / (sqrt(log n)||x*||) | No clear effect |
| Unregularized vanilla GD for noisy matrix completion with spectral initialization and constant step size | Vanilla gradient descent for matrix completion · Noisy low-rank matrix completion | linear convergence rate and entrywise/spectral/Frobenius error | Helped |
| Gradient descent with constant step size (ignoring explicit regularization) vs. prior regularized GD for matrix completion | Matrix completion · Noisy low-rank matrix completion, Table 1 comparison | sample complexity and iteration complexity | Mixed |
Closest papers by meaning
- Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction (NeurIPS 2021 · similarity 0.91)
- Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization (NeurIPS 2021 · similarity 0.90)
- Implicit Regularization for Optimal Sparse Recovery (NeurIPS 2019 · similarity 0.90)
- Implicit Sparse Regularization: The Impact of Depth and Early Stopping (NeurIPS 2021 · similarity 0.90)
- Implicit Regularization of Decentralized Gradient Descent for Sparse Regression (NeurIPS 2024 · similarity 0.87)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.