Research map / Optimization / Implicit bias and generalization
Risk Bounds of Accelerated SGD for Overparameterized Linear Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives instance-dependent excess risk bounds for tail-averaged accelerated SGD in overparameterized linear regression, showing ASGD beats SGD on bias only in small-eigenvalue subspaces while its variance is always larger.
Problem
Existing optimization theory explains faster convergence of ASGD but not its generalization; prior excess-risk bounds for ASGD in least squares are limited to finite-dimensional regimes and cannot handle overparameterized settings where parameters exceed samples.
Approach
Uses eigen-subspace decomposition of the data covariance with explicit closed-form powers of the 2x2 ASGD transition blocks to get dimension-free, instance-dependent excess risk bounds for tail-averaged ASGD, then compares them with SGD bounds, with a new parameter choice avoiding dimension dependence.
Key results
- Theory: ASGD variance is always no smaller than SGD's, with effective variance O(min{1/N, N gamma^2 lambda_i^2}) vs O(min{1/N, N delta^2 lambda_i^2}) for SGD.
- Bias comparison: ASGD bias decays faster than SGD in subspaces with i > k-hat (small eigenvalues) and slower for large eigenvalues.
- Experiments on d=2000, lambda_i=i^-2: ASGD beats SGD when initialization error lies in small-eigenvalue subspace and is worse when it lies in large-eigenvalue subspace.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ASGD with tail averaging instead of SGD with tail averaging | Linear regression with signals mainly in small-eigenvalue directions · Overparameterized linear regression | excess risk: 0.996^s -> 0.9873^s | Helped |
| Use ASGD with tail averaging instead of SGD with tail averaging | Linear regression with initialization mainly in large-eigenvalue directions · Overparameterized linear regression | excess risk | Hurt |
| Use ASGD with tail averaging instead of SGD with tail averaging | Linear regression with initialization aligned to the \lambda_{\hat k} subspace · Overparameterized linear regression | excess risk | No clear effect |
| Use ASGD with tail averaging instead of SGD with tail averaging | Linear regression variance error · Overparameterized linear regression | variance error | Hurt |
| Use ASGD with tail averaging instead of SGD with tail averaging | Bias error in small-eigenvalue directions · Overparameterized linear regression | bias error | Helped |
| Use ASGD with tail averaging instead of SGD with tail averaging | Bias error in large-eigenvalue directions · Overparameterized linear regression | bias error | Hurt |
| Increase the free parameter \tilde\kappa (ablation) | ASGD · Smallest-eigenvalue subspace | bias decay rate | Helped |
| Increase the free parameter \tilde\kappa (ablation) | ASGD · Intermediate-eigenvalue subspace | bias decay rate | Hurt |
| Choose a small \tilde\kappa (ablation) | ASGD · Overparameterized linear regression | similarity to SGD | Helped |
Surprising findings
- ASGD's variance error is always larger than SGD's, so momentum does not help generalization in the variance term.
- Bias decay for ASGD is slower than SGD in large-eigenvalue subspaces, so ASGD underperforms SGD when the initialization error aligns with large eigen-directions.
Limitations
- Assumes diagonal Hessian and a fourth-moment condition with constant psi (Gaussian psi=3); one-hot case needs modifications.
- Excess risk bound contains an extra term relative to the classical fine-grained analysis.
- Experiments are limited to synthetic Gaussian data with a single spectrum setting in main text.
Experimental setup
Datasets: synthetic Gaussian linear regression data with eigenvalues lambda_i = i^-2
Benchmarks: synthetic overparameterized linear regression (d=2000)
Metrics: excess risk bias error variance error
Baselines: SGD with tail averaging stochastic heavy ball Jain et al. 2018 ASGD bound
Builds on: SGD overparameterized linear regression risk bounds (Zou et al. / Wu et al.) Jain et al. accelerated SGD for least squares stochastic heavy ball
Closest papers by meaning
- Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression (ICML 2022 · similarity 0.91)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.88)
- Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.88)
- Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization (ICML 2025 · similarity 0.88)
- Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression (NeurIPS 2024 · similarity 0.87)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · 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.