Research map / Optimization / Implicit bias and generalization
The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms
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 exact deterministic ODE limits for risk and adaptive learning-rate curves of one-pass SGD with adaptive step sizes on high-dimensional linear composite problems, and applies them to idealized line search and AdaGrad-Norm on least squares.
Problem
Understanding the exact finite-horizon risk and learning-rate dynamics of adaptive learning rate methods (line search, AdaGrad-Norm) for stochastic optimization in high dimensions, beyond minimax worst-case rates.
Approach
Shows that in the high-dimensional limit with Gaussian data, the risk and adaptive learning rate of one-pass SGD concentrate around a deterministic solution of a system of ODEs (the "high line"), enabling exact comparison of adaptive stepsize strategies that depend on the covariance spectrum.
Key results
- Exact line search on noiseless least squares can converge to a learning rate of order lambda_min/(Tr(K^2)/d), which can be arbitrarily smaller than the optimal Polyak rate (Tr(K)/d)^{-1}.
- For noiseless targets, AdaGrad-Norm learning rate converges to a constant inversely proportional to (Tr(K)/d) times ||X_0-X*||^2 when lambda_min > C.
- For power-law spectra, a phase transition occurs at beta+delta=1: the AdaGrad-Norm learning rate stays constant when beta+delta<1 and decays when 1<beta+delta<2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact line search instead of the best fixed learning rate | Least-squares SGD with strongly anisotropic covariance · Least squares | convergence speed | Hurt |
| Use Polyak stepsize instead of exact line search | Least-squares SGD · Least squares with sufficiently anisotropic covariance | convergence speed: \gamma_t^{\mathrm{line}} \asymp \frac{\lambda_{\min}}{\text{Tr}(K^2)/d}; \quad \gamma_t = \frac{1}{\text{Tr}(K)/d} | Helped |
| Use AdaGrad-Norm with a warm start | Least-squares SGD · Noiseless least squares, λ_min > C | learning rate: \gamma_t = \frac{1}{\text{Tr}(K)/d} | Helped |
| Use AdaGrad-Norm on a power-law covariance with β + δ < 1 | Least-squares SGD · Power law, β + δ < 1 | learning rate: \gamma_t \asymp_{\delta, \beta} 1 | Helped |
| Use AdaGrad-Norm on a power-law covariance with β + δ = 1 | Least-squares SGD · Power law, β + δ = 1 | learning rate: \gamma_t \asymp_{\delta, \beta} \tfrac{1}{\log(t+1)} | Mixed |
| Use AdaGrad-Norm on a power-law covariance with 1 < β + δ < 2 | Least-squares SGD · Power law, 1 < β + δ < 2 | learning rate: \gamma_{t} \asymp_{\delta, \beta} t^{-1+\frac{1}{\beta+\delta}} | Hurt |
| Add AdaGrad-Norm's adaptive learning rate instead of using constant-step SGD | Least-squares SGD · Power law, β + δ > 1 | risk convergence rate: AdaGrad-Norm: {R}(t) \asymp_{\delta, \beta} t^{-\frac{2}{\beta +\delta} +1}; constant-step SGD: {R}(t)\asymp t^{\beta+\d | Mixed |
Surprising findings
- Exact line search, which greedily minimizes risk each step, can run arbitrarily slower than the best fixed SGD learning rate under strong anisotropy.
- AdaGrad-Norm can use overly pessimistic decaying schedules on hard power-law problems.
Limitations
- Theory limited to Gaussian data; extension beyond Gaussian is conjectured.
- Main ODE comparison requires Tr(K) on the order of dimension d.
- Analysis restricted to one-pass streaming methods; multi-pass only conjectured.
Experimental setup
Datasets: synthetic Gaussian data CIFAR-5m
Benchmarks: CIFAR-5m
Metrics: risk learning rate
Baselines: optimal fixed learning rate SGD Polyak stepsize exact line search
Builds on: AdaGrad-Norm Polyak stepsize DoG D-Adaptation
Closest papers by meaning
- Asymptotic theory of SGD with a general learning-rate (NeurIPS 2025 · similarity 0.89)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.89)
- High-dimensional Limit of SGD for Diagonal Linear Networks (NeurIPS 2026 · similarity 0.89)
- Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent (ICML 2025 · similarity 0.88)
- Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · similarity 0.87)
- Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares (NeurIPS 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.