Research map / Optimization / Implicit bias and generalization
Learning Curves of Stochastic Gradient Descent in Kernel 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.
Analyzes single-pass SGD in kernel regression on the sphere under source condition (possibly misspecified), showing exponentially decaying step sizes achieve minimax rates without saturation, unlike KRR.
Problem
Excess risk learning curves of single-pass SGD for kernel regression in high-dimensional (n ~ d^gamma) and asymptotic (n >> d) regimes under source conditions, including misspecified settings, and how SGD compares with KRR, which suffers saturation.
Approach
Shows that single-pass SGD with an exponentially decaying step size schedule (piecewise-constant halving per stage) attains minimax-optimal excess risk for inner-product kernels on the sphere for all well-specified source smoothness, avoiding KRR's saturation; constant step with iterate averaging is used for misspecified cases, and its saturation is characterized.
Key results
- Under well-specified source conditions (s>=1), SGD with exponentially decaying step size attains minimax-optimal rates in high-dimensional and asymptotic settings, whereas KRR is suboptimal for s>1 (high-dim) and s>2 (asymptotic).
- For misspecified problems (0<s<1), SGD with averaged iterates achieves optimal rates in high-dimensional settings for all gamma>0, and in asymptotic settings for 1/(d+1) <= s <= 1.
- Simulations with NTK kernel on the sphere support the predicted convergence rates, showing no saturation for the exponentially decaying schedule.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use exponentially decaying step sizes | SGD for well-specified kernel regression · High-dimensional, n ≍ d^γ; s ≥ 1 | excess risk: d^{-γ+p}\log_2^2 d; d^{-(p+1)s} | Helped |
| use exponentially decaying step sizes | SGD for well-specified ReLU NTK kernel regression · Asymptotic, n ≫ d; s ≥ 1 | excess risk: \log_2^s n\cdot n^{-\frac{s(d+1)}{s(d+1)+d} } | Helped |
| use averaged iterates | SGD for misspecified kernel regression · High-dimensional, n ≍ d^γ; 0 < s < 1 | excess risk: d^{-γ+p}; d^{-(p+1)s} | Helped |
| use averaged iterates | SGD for misspecified ReLU NTK kernel regression · Asymptotic, n ≫ d; 1/(d+1) ≤ s ≤ 1 | excess risk: n^{-\frac{s(d+1)}{s(d+1)+d} } | Helped |
| use averaged iterates | SGD for highly misspecified ReLU NTK kernel regression · Asymptotic, n ≫ d; s < 1/(d+1) | excess risk | Hurt |
| replace exponentially decaying step sizes with constant step size and averaged iterates (ablation) | SGD for relatively smooth kernel regression · High-dimensional and asymptotic settings | excess risk: \frac{1}{n^2\eta_0^s} | Hurt |
| use exponentially decaying step sizes instead of constant step size with averaged iterates | SGD for relatively smooth kernel regression · High-dimensional and asymptotic settings | excess risk | Helped |
| use exponentially decaying step sizes instead of kernel ridge regression | Kernel regression for smooth targets · High-dimensional, n ≍ d^γ; s > 1 | excess risk: d^{-\min \left \{ \gamma-p,\frac{\gamma-p+p\tilde{s}+1 }{2} ,\tilde{s}\left ( p+1 \right ) \right \} } | Helped |
| use exponentially decaying step sizes instead of kernel ridge regression | ReLU NTK kernel regression for smooth targets · Asymptotic, n ≫ d; s > 2 | excess risk: n^{-\frac{2d+2}{3d+2} } | Helped |
Surprising findings
- Exponentially decaying step size SGD avoids saturation, while iterate-averaged SGD saturates for smooth targets (s>1 in high dimension, s>2 asymptotically).
- In the asymptotic regime, SGD is minimax optimal only for s >= 1/(d+1), i.e., it loses optimality for highly misspecified problems.
Limitations
- Analysis restricted to inner-product (dot-product) kernels on the sphere with uniform marginal distribution.
- Asymptotic regime misspecified case: SGD with averaged iterates not optimal for all s; optimization limits optimality to s >= 1/(d+1).
- Constants treated as fixed; assumption that Phi has positive Taylor coefficients up to floor(gamma)+3.
Experimental setup
Datasets: synthetic data sampled uniformly on the sphere with Gaussian noise
Benchmarks: synthetic kernel regression on the sphere with NTK kernel
Metrics: excess risk log excess risk decay
Baselines: kernel ridge regression ridgeless regression gradient descent with early stopping SGD with constant step size and averaged iterates
Builds on: kernel ridge regression saturation analysis SGD linear regression with exponentially decaying step size NTK theory
Closest papers by meaning
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes (NeurIPS 2018 · similarity 0.91)
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.89)
- The Benefits of Implicit Regularization from SGD in Least Squares Problems (NeurIPS 2021 · similarity 0.89)
- On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay (NeurIPS 2023 · similarity 0.89)
- Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.87)
- Generalization in Kernel Regression Under Realistic Assumptions (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.