Research map / Optimization / Implicit bias and generalization
Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime
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 SGD instead of GD with the same stepsize and iteration count | Multi-pass SGD for interpolating least squares · Interpolating least squares | excess risk | Hurt |
| Use optimally tuned SGD instead of optimally tuned GD | Multi-pass SGD for interpolating least squares · Polynomially decaying covariance spectrum | iteration complexity: SGD needs to take \tilde \cO(n^{\max\{0.5, \frac{r}{r+1}\}}) more iterations than GD | Hurt |
| Use optimally tuned SGD instead of optimally tuned GD | Multi-pass SGD for interpolating least squares · Polynomially decaying covariance spectrum | gradient complexity: SGD needs $\tilde \cO(n^{\max\{0.5, \frac{1}{r+1}\}})$ less stochastic gradient evaluations than GD | Helped |
Closest papers by meaning
- Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization (ICML 2025 · similarity 0.90)
- Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.90)
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.89)
- Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression (NeurIPS 2024 · similarity 0.88)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.88)
- A Precise Characterization of SGD Stability Using Loss Surface Geometry (ICLR 2024 · similarity 0.88)
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.