Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization (2025)

Jingrong Wei
Department of Mathematics
University of California, Irvine
Irvine, CA 92697
jingronw@uci.edu
&Long Chen
Department of Mathematics
University of California, Irvine
Irvine, CA 92697
chenlong@math.uci.edu
Corresponding author.

Abstract

The heavy-ball momentum method accelerates gradient descent with a momentum term but lacks accelerated convergence for general smooth strongly convex problems. This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, the first variant with provable global and accelerated convergence for such problems. AOR-HB closes a long-standing theoretical gap, extends to composite convex optimization and min-max problems, and achieves optimal complexity bounds. It offers three key advantages: (1) broad generalization ability, (2) potential to reshape acceleration techniques, and (3) conceptual clarity and elegance compared to existing methods.

1 Introduction

We first consider the convex optimization problem:

\min_{x\in\mathbb{R}^{d}}f(x),

(1)

where the objective function $f$ is $\mu$ -strongly convex and $L$ -smooth. Later on we consider extension to composite convex optimization $\min_{x}f(x)+g(x)$ with a non-smooth function $g$ , and a class of min-max problems $\min_{u\in\mathbb{R}^{m}}\max_{p\in\mathbb{R}^{n}}f(u)-g(p)+\langle Bu,p\rangle$ with bilinear coupling.

Notation.

$\mathbb{R}^{d}$ is $d$ -dimensional Euclidean space with standard $\ell_{2}$ -inner product $\langle\cdot,\cdot\rangle$ and the induced norm $\|\cdot\|$ . $f:\mathbb{R}^{d}\to\mathbb{R}$ is a differentiable function. We say $f$ is $\mu$ -strongly convex function when there exists $\mu>0$ such that

f(y)-f(x)-\langle\nabla f(x),y-x\rangle\geq\frac{\mu}{2}\|x-y\|^{2},\quad%\forall~{}x,y\in\mathbb{R}^{d}.

We say $f$ is $L$ -smooth with $L>0$ if its gradient is Lipschitz continuous:

Heavy-ball methods and flow.

Over the past two decades, first-order methods, which rely solely on gradient information rather than the Hessian as required by Newton’s method, have gained significant interest due to their efficiency and adaptability to large-scale data-driven applications and machine learning tasks(Bottou etal., 2018). Among these methods, the gradient descent method is the most straightforward and well-established algorithms. However, for ill-conditioned problems, where the condition number $\kappa\gg 1$ , the gradient descent method suffers from slow convergence.

In order to accelerate the gradient descent methods, a momentum term was introduced, encouraging the method to move along search directions that utilize not only current but also previously seen information. The heavy-ball (HB) method (also known as the momentum method(Polyak, 1964) was in the form of:

x_{k+1}=x_{k}-\gamma\nabla f(x_{k})+\beta(x_{k}-x_{k-1}),

(2)

where $\beta$ and $\gamma$ are constant parameters.Polyak motivated the method by an analogy to a “heavy ball” moving in a potential well defined by the objective function $f$ . The corresponding ordinary differential equation (ODE) model is commonly referred to as the heavy-ball flow(Polyak, 1964):

x^{\prime\prime}+\theta x^{\prime}+\eta\nabla f(x)=0,

(3)

where $x=x(t)$ , $x^{\prime}$ is taking the derivative of $t$ , and $\theta$ and $\eta$ are positive constant parameters.

Non-convergence and non-acceleration of the HB method.

Polyak (1964) showed that for (2) with $\beta=\left(\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}\right)^{2}$ , $\gamma=\frac{4}{(\sqrt{L}+\sqrt{\mu})^{2}}$ , andwhen $x_{k}$ is sufficiently close to the optimal solution $x^{*}$ , $\|x_{k}-x^{*}\|$ converges at rate $\frac{1-\sqrt{\rho}}{1+\sqrt{\rho}}$ , where $\rho=1/\kappa$ . Polyak’s choice relies on the spectral analysis of the linear system and thus the accelerated rate is only limited to the convex and quadratic objectives and is local for iterates near $x^{*}$ .IndeedLessard etal. (2016) designed a non-convergent example to show that the Polyak’s choice of parameters does not guarantee the global convergence for general strongly convex optimization. By changing the parameters, inGhadimi etal. (2015); Sun etal. (2019); SaabJr etal. (2022); Shi etal. (2022), the global linear convergence of the HB method has been established. However, the best rate is $1-\mathcal{O}(\rho)$ given byShi etal. (2022), which coincides with that of the gradient descent and not the accelerated rate $1-\mathcal{O}(\sqrt{\rho})$ .

The absence of acceleration is not due to a technical difficulty in the convergence analysis. Recently,Goujaud etal. (2023) have demonstrated that the HB method provably fails to achieve an accelerated convergence rate for smooth and strongly convex problems. Specifically, for any positive parameters $\beta$ and $\gamma$ in (2), either there exists an $L$ -smooth, $\mu$ -strongly convex function, and an initialization such that HB fails to converge; or even in the class of smooth and strongly convex quadratic function $f$ , the convergence rate is not accelerated: $1-\mathcal{O}(\rho)$ . For more related works on HB methods, see Appendix B.1.

Accelerated first-order methods.

To accelerate the HB method, one can introduce either an additional gradient step with adequate decay or an extrapolation step into the algorithm; seeWilson etal. (2021); Siegel (2019); Chen & Luo (2021).

Main contributions for smooth strongly convex optimization.

We propose a variant of the HB method in the form of

	$\displaystyle x_{k+1}$	$\displaystyle=x_{k}-\gamma(2\nabla f(x_{k})-\nabla f(x_{k-1}))+\beta(x_{k}-x_{%k-1}),$		(5)
	$\displaystyle\gamma$	$\displaystyle=\frac{1}{(\sqrt{L}+\sqrt{\mu})^{2}},\quad\quad\beta=\frac{L}{(%\sqrt{L}+\sqrt{\mu})^{2}}.$		(5)

The most notable yet simple change is using $2\nabla f(x_{k})-\nabla f(x_{k-1})$ not $\nabla f(x_{k})$ to approximate $\nabla f(x)$ . Namely an over-relaxation technique(Hadjidimos, 1978) is applied to the gradient term. Therefore, we name (5) accelerated over-relaxation heavy-ball (AOR-HB) method.

Rather than second-order ODEs, we consider a first-order ODE system proposed inChen & Luo (2021):

x^{\prime}=y-x,\quad y^{\prime}=x-y-\frac{1}{\mu}\nabla f(x),

(6)

which is a special case of the HB flow (3) with $\theta=2$ and $\eta=\frac{1}{\mu}$ when $y$ is eliminated. Although (6) is mathematically equivalent to an HB flow, the structure of this $2\times 2$ first-order ODE system is crucial for convergence analysis and algorithmic design. The same second-order ODE can correspond to different first-order systems. For example, another one equivalent to the HB flow (3) is

x^{\prime}=v,\quad v^{\prime}=-\theta v-\eta\nabla f(x),

(7)

where $v$ represents velocity, offering a physical interpretation. However, the convergence analysis is less transparent in the form (7) or the original second-order ODE (3).

We obtain AOR-HB by discretization of (6) with two iterates $(x_{k},y_{k})$ cf. (14). The AOR is used to symmetrize the error equation (19), which represents a novel contribution compared toLuo & Chen (2022) andChen & Luo (2021).The choice of parameters $\beta$ and $\gamma$ in (5) is derived from the time step-size $\alpha=\sqrt{\mu/L}$ . We rigorously prove that AOR-HB enjoys the global linear convergence with accelerated rate, which closes a long-standing theoretical gap in optimization theory.

Theorem 1.1 (Convergence of AOR-HB method).

Suppose $f$ is $\mu$ -strongly convex and $L$ -smooth. Let $(x_{k},y_{k})$ be generated by scheme (14) with initial value $(x_{0},y_{0})$ and step size $\alpha=\sqrt{\mu/L}$ . Then there exists a constant $C_{0}=C_{0}(x_{0},y_{0},\mu,L)$ so that we have the accelerated linear convergence

\displaystyle f(x_{k+1})-f(x^{*})+\frac{\mu}{2}\|y_{k+1}-x^{*}\|^{2}\leq C_{0}%\left(\frac{1}{1+\frac{1}{2}\sqrt{\mu/L}}\right)^{k},\quad k\geq 1.

(8)

Remark on non-strongly convex optimization.

When $\mu=0$ , we propose a variant of the AOR-HB method that incorporates the dynamic time rescaling introduced in (Luo & Chen, 2022):

x_{k+1}=x_{k}-\frac{k}{k+3}\frac{1}{L}\big{(}2\nabla f(x_{k})-\nabla f(x_{k-1}%)\big{)}+\frac{k}{k+3}(x_{k}-x_{k-1}),

(9)

which achieves an accelerated rate of $\mathcal{O}(1/k^{2})$ , comparable to NAG. We refer the details and the proofs to Appendix D. Another approach to extend the acceleration involves using the perturbed objective $f(x)+\frac{\epsilon}{2}\|x\|^{2}$ , as discussed in (Lessard etal., 2016, Section 5.4).

Relation to other acceleration methods.

The AOR term $2\nabla f(x_{k})-\nabla f(x_{k-1})$ can be treated as adding a gradient correction in the high resolution ODE model(Shi etal., 2022). AOR-HB (5) can be also rendered as a special case of the ‘SIE’ iteration described inZhang etal. (2021). However, the parameter choice ( $\sqrt{s}=\frac{1}{L}$ and $m=1$ ) recovering AOR-HB, does not satisfy the condition in their convergence analysis(Zhang etal., 2021, Theorem 3).

For strongly convex optimization, acceleration can be viewed from various perspectives, with the resulting three-term formulas differing only by a higher-order $\mathcal{O}(\rho)$ perturbation.With a proper change of variables, NAG (4) can be seen as a parameter perturbation of the AOR-HB in the form of (5). The performance of AOR-HB are thus comparable to NAG but less precise than triple momentum (TM) methods(VanScoy etal., 2017) for strongly convex optimization.

However, extending these methods (NAG, TM, SIE, and high-resolution ODEs) beyond the convex optimization is rare and challenging. In contrast, AOR-HB has a superior generalization capability as the true driving force of acceleration is better captured by the $2\times 2$ first-order ODE model (6).