Research map / Optimization / Nonconvex and smooth optimization
Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Time
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.
Proposes randomized Hamiltonian flow (RHF) and its discretization RHGD for optimization, where velocity refreshes occur at exponentially distributed times, achieving accelerated convergence rates matching AGD for strongly and weakly convex smooth functions.
Problem
Accelerated optimization based on energy-conserving Hamiltonian dynamics; existing Hamiltonian-based optimizers are discretizations of damped accelerated gradient flow, and pure Hamiltonian flow for optimization lacked acceleration beyond quadratics.
Approach
Randomize the integration time of Hamiltonian flow for optimization (HF-opt) with exponential times whose rate depends on current time, refreshing velocity to zero at each event; discretize via a gradient-step approximation of the proximal Hamiltonian step (RHGD) to get accelerated rates without damping.
Key results
- RHF achieves rate O(exp(-sqrt(alpha/5) t)) for alpha-strongly convex functions, matching AGF up to constants.
- RHGD needs O(sqrt(kappa) log(1/eps)) iterations for strongly convex smooth functions and O(sqrt(L/eps)) for weakly convex, matching AGD's rates in expectation.
- In experiments RHGD is faster than GD and competitive with AGD and CAGD, outperforming them in some regimes such as misspecified strong convexity constant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RHGD instead of GD | Quadratic minimization, strongly convex with exact α · Quadratic minimization, κ=10^7 | convergence | Helped |
| Use RHGD instead of AGD or CAGD | Quadratic minimization, strongly convex with exact α · Quadratic minimization, κ=10^7 | convergence | Hurt |
| Use RHGD with overestimated α̂=0.01 instead of AGD or CAGD | Quadratic minimization with misspecified strong convexity · Quadratic minimization, κ=10^7, α̂=0.01 | convergence | Helped |
| Set α̂=0.01 instead of using the exact α (ablation) | AGD and CAGD · Quadratic minimization, κ=10^7 | convergence | Hurt |
| Use RHGD instead of AGD or CAGD | Quadratic minimization, weakly convex · Quadratic minimization, α=0 | convergence | Helped |
| Use RHGD instead of GD | Quadratic minimization, weakly convex · Quadratic minimization, α=0 | convergence | Helped |
| Use RHGD instead of GD | Logistic regression · Logistic regression, α=10^-4 | convergence | Helped |
| Use RHGD instead of AGD or CAGD | Logistic regression · Logistic regression, α=10^-4 | convergence | No clear effect |
| Set refreshment rate to γ_k=2√α instead of γ_k=√α (ablation) | RHGD · Logistic regression, α=10^-4 | convergence | Helped |
| Use RHGD instead of GD | Logistic regression, weakly convex · Logistic regression, α=0 | convergence | Helped |
| Use RHGD instead of AGD or CAGD | Logistic regression, weakly convex · Logistic regression, α=0 | convergence | No clear effect |
Surprising findings
- RHGD outperforms AGD and CAGD in the misspecified-alpha quadratic setting and in later iterations of the weakly convex quadratic setting.
Limitations
- Convergence guarantees hold only in expectation, not deterministically.
- Constants in the accelerated rates are larger than those of AGF and AGD.
- Analysis restricted to smooth convex-type settings (strong convexity, gradient domination, weak convexity); no stochastic variant.
Experimental setup
Datasets: synthetic quadratic functions synthetic logistic regression data
Benchmarks: quadratic minimization logistic regression
Metrics: objective suboptimality vs iterations
Baselines: GD AGD CAGD
Builds on: Hamiltonian Monte Carlo randomized Hamiltonian Monte Carlo Nesterov accelerated gradient descent continuized accelerated gradient descent
Closest papers by meaning
- On the Convergence of Hamiltonian Monte Carlo with Stochastic Gradients (ICML 2021 · similarity 0.89)
- Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows (AAAI 2022 · similarity 0.88)
- Stochastic Gradient Hamiltonian Monte Carlo Methods with Recursive Variance Reduction (NeurIPS 2019 · similarity 0.88)
- Stochastic Gradient Descent under Markovian Sampling Schemes (ICML 2023 · similarity 0.88)
- Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time (ICLR 2023 · similarity 0.87)
- Random Function Descent (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.