Research map / Optimization / Optimizers
Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
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.
Gives the first rigorous convergence analysis of hypergradient descent (HDM) via online learning, proves local superlinear convergence, and proposes HDM with heavy-ball momentum (HDM-HB/HDM-Best) that rivals L-BFGS on deterministic convex problems.
Problem
Hypergradient descent is a 25-year-old heuristic for adaptive stepsize selection with no rigorous convergence theory, and vanilla HDM is unstable (objective spikes up to 1e30 early on).
Approach
Views the hypergradient stepsize/preconditioner update as online gradient descent on the hypergradient feedback h_x(P) = (f(x - P∇f(x)) - f(x))/||∇f(x)||^2, yielding global and local (superlinear) convergence guarantees; adds a null step, AdaGrad-based online learning, and heavy-ball momentum to fix instability.
Key results
- On 33 SVM problems, HDM-Best solves 32 (tied with BFGS), versus 26 for Adam and 31 for L-BFGS-M10.
- On 33 logistic regression problems, HDM-Best solves 21, versus 26 for BFGS and 16 for L-BFGS-M5.
- Theory proves local superlinear convergence of HDM under a Lipschitz Hessian assumption and convergence of the learned preconditioner to the inverse Hessian under uniform independence of gradient directions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HDM-Best instead of adaptive first-order methods | Deterministic convex optimization · SVM and Logistic Regression | solved problems | Helped |
| Use HDM-Best instead of L-BFGS-M10 | Deterministic convex optimization · SVM | solved problems: 31 -> 32 | Mixed |
| Use HDM-Best instead of L-BFGS-M10 | Deterministic convex optimization · Logistic Regression | solved problems: 18 -> 21 | Helped |
| Replace online gradient descent with AdaGrad for learning the preconditioner (ablation) | HDM · Optimization problems | convergence speed | Helped |
| Add a null step that skips an objective-increasing iterate (ablation) | HDM · Optimization problems | objective value | Helped |
| Remove the potential-function term from the heavy-ball feedback numerator (ablation) | HDM-Best · Deterministic convex problems | algorithm performance | No clear effect |
| Add the denominator term that smooths the momentum update (ablation) | HDM-Best · Deterministic convex problems | convergence | Helped |
Surprising findings
- Vanilla HDM's objective value can spike to about 1e30 in early iterations, but this is a warm-up phase of online learning rather than true divergence.
Limitations
- Analysis is limited to deterministic convex (and local strongly convex) problems; stochastic and nonconvex settings are left to future work.
- Vanilla HDM can blow up in objective value during warm-up; the fixes (null step, AdaGrad) are heuristic in practice and the sensitivity to stepsize parameters is notable.
- Global convergence of the momentum variant with the null step needs a warm start from vanilla AGD in the Nesterov case, which is only empirically unnecessary.
Experimental setup
Datasets: LIBSVM
Benchmarks: LIBSVM SVM problems (33) LIBSVM logistic regression problems (33)
Metrics: number of solved problems (grad norm <= 1e-4 within 1000 gra function value gap gradient norm
Baselines: GD GD-HB AGD-CVX AGD-SCVX Adam AdaGrad BFGS L-BFGS
Builds on: hypergradient descent (Baydin et al.) online-to-offline reduction (Gao et al.) AdaGrad heavy-ball method
Closest papers by meaning
- Online Learning Rate Adaptation with Hypergradient Descent (ICLR 2018 · similarity 0.91)
- The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 2024 · similarity 0.88)
- Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · similarity 0.88)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.88)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.87)
- Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality (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.