Research map / Optimization / Implicit bias and generalization
Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
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 multiple passes with t = Θ(n^{α/(2rα + 1)}) iterations | Averaged SGD for hard least-squares problems with μ α < 2rα + 1 < α · Hard least-squares problems | expected excess risk: O(n^{-2r}) -> O ( n^{-2rα/(2rα + 1)}) | Helped |
| Use multiple passes with t = Θ(n^{1/μ}~(log n)^{1/μ}) iterations | Averaged SGD for hard least-squares problems with μ α ≥ 2rα + 1 · Hard least-squares problems | expected excess risk: O(n^{-2r}) -> O ( n^{-2r / μ} ) | Helped |
| Use multiple passes instead of one pass | Averaged SGD on hard problems satisfying 2r ≥ μ · Non-parametric least-squares estimation | minimax excess risk rate: O(n^{-2r}) -> O(n^{\frac{-2rα}{2rα +1}} ) | Helped |
| Increase iterations with sample size according to t*(n) = Θ(n^{α/(2rα + 1)}) | Averaged SGD on synthetic hard spline-kernel problems · Synthetic spline-kernel experiments, α = 2.5 and α = 3 | test error | Helped |
| Use one pass rather than a growing number of passes | Averaged SGD on easy problems · Easy least-squares problems | statistical convergence rate | No clear effect |
| Increase the number of passes as sample size increases | Averaged SGD with linear least-squares regression · MNIST | test error | Helped |
| Replace sampling with replacement by sampling without replacement (ablation) | Averaged SGD · Synthetic spline-kernel experiments | iterations-to-sample-size scaling | No clear effect |
| Replace sampling with replacement by cycling through data in the same order (ablation) | Averaged SGD · Synthetic spline-kernel experiments | iterations-to-sample-size scaling | No clear effect |
Closest papers by meaning
- Learning Curves of Stochastic Gradient Descent in Kernel Regression (ICML 2025 · similarity 0.91)
- Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning (ICML 2026 · similarity 0.90)
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.90)
- Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime (NeurIPS 2022 · similarity 0.89)
- Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization (ICML 2025 · similarity 0.89)
- The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 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.