Research map / Optimization / Nonconvex and smooth optimization
Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization
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 AOR-HB, a heavy-ball variant with over-relaxed gradient term that achieves global accelerated linear convergence for smooth strongly convex minimization, extended to composite and bilinear saddle-point problems.
Problem
Heavy-ball momentum lacks global accelerated convergence for general smooth strongly convex optimization; extending acceleration to composite and saddle-point problems is also hard.
Approach
Discretize a first-order ODE system (a special HB flow) with an over-relaxation of the gradient term (2∇f(x_k) − ∇f(x_{k−1})) that symmetrizes the error equation, yielding a two-parameter heavy-ball update with a Lyapunov analysis giving rate 1/(1+√ρ/2).
Key results
- Theorem gives global linear rate 1/(1+sqrt(mu/L)/2) for AOR-HB, i.e., O(sqrt(kappa) log(1/eps)) iterations, matching the optimal first-order complexity.
- On a smooth piecewise objective with mu=1, L=1e4, HB plateaus while AOR-HB converges linearly at a rate comparable to NAG and ADR.
- For MSPBE saddle point problems, AOR-HB-saddle-I achieves the fastest convergence among compared accelerated methods, with iteration growth O(sqrt(kappa_g)) versus O(kappa_g) for EG.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the AOR gradient correction instead of the standard heavy-ball gradient term | AOR-HB · smooth multidimensional piecewise objective | convergence | Helped |
| use AOR-HB instead of NAG or ADR | smooth multidimensional piecewise objective · smooth multidimensional piecewise objective | convergence speed | No clear effect |
| use triple momentum instead of AOR-HB | smooth multidimensional piecewise objective · smooth multidimensional piecewise objective | convergence speed | Hurt |
| use AOR-HB instead of heavy-ball | logistic regression · logistic regression | convergence speed | Hurt |
| use AOR-HB-composite instead of FISTA or APG | non-convex $\ell_1-\ell_2$ minimization · $\ell_1-\ell_2$ minimization | relative $\ell_2$ error convergence | Helped |
| use AOR-HB-saddle instead of the other tested accelerated algorithms | saddle-point methods · MSPBE policy evaluation | iteration count to desired accuracy | Helped |
| treat the coupling implicitly instead of using the explicit coupling scheme (ablation) | AOR-HB-saddle · strongly-convex-strongly-concave saddle-point problems | convergence rate: 1-\mathcal O(\sqrt{\rho}) | Helped |
| add dynamic time rescaling for the non-strongly convex case (ablation) | AOR-HB · non-strongly convex minimization | convergence rate: \mathcal O(1/k^2) | Helped |
Surprising findings
- Heavy-ball converges on logistic regression and is fastest there, yet the paper notes such fast convergence lacks theoretical guarantees and can fail in other cases.
- The non-strongly-convex variant has an O(1/k^2) rate, comparable to NAG.
Limitations
- Requires knowledge of mu and L for parameter choice.
- Convergence rates in some theorems are not as tight as the triple momentum method.
- Stochastic performance not investigated.
Experimental setup
Datasets: synthetic smooth piecewise objective logistic regression synthetic data synthetic Lasso data synthetic MSPBE policy evaluation data
Benchmarks: synthetic smooth piecewise function logistic regression Lasso l1-l2 nonconvex regularized problem MSPBE policy evaluation saddle point
Metrics: log distance to optimum ||x_k - x*|| relative l2 error iterations to accuracy
Baselines: gradient descent Nesterov accelerated gradient heavy-ball method triple momentum ADR FISTA APG AG-OG APDG LPD EG
Builds on: Nesterov accelerated gradient triple momentum method extra-gradient method lifted primal-dual method
Closest papers by meaning
- Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise (ICLR 2024 · similarity 0.90)
- Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out (ICML 2022 · similarity 0.90)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.88)
- Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance (ICLR 2025 · similarity 0.87)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Optimal Acceleration for Minimax and Fixed-Point Problems is Not Unique (ICML 2024 · similarity 0.86)
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.