Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization
Authors: Jingrong Wei
Long Chen
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization theory
heavy ball
momentum
acceleration
composite optimization
min-max
saddle point problem
Primary area: optimization
TL;DR: This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, the first heavy-ball variant with provable global and accelerated convergence for a large class of optimization problems.

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.

Published as a conference paper at ICLR 2025
ACCELERATED OVER-RELAXATION HEAVY-BALL METHOD: ACHIEVING GLOBAL ACCELERATED CON- VERGENCE WITH BROAD GENERALIZATION
Jingrong Wei
Long Chen
Department of Mathematics University of California, Irvine Irvine, CA 92697 Lnnrrowwuct edu
Department of Mathematics University of California, Irvine Irvine, CA 92697 chen chenlong@matio .du.
ABSTRACT
The heavy-ball momentum method accelerates gradient descent with a momentum term but lacks accelerated convergence for general smooth strongly convex prob- lems. This work introduces the Accelerated ever-Relaxation Heavy-Ball (AOR- HB) method, the first variant with provable global and accelerated convergence for such problems. AOR-HB closes long-standing theoretical gap, extends to com- posite convex optimization and min-max problems, and achieves optimal com- plexity bounds. It offers three key advantages: (I) broad generalization ability, (2) potential to reshape acceleration techniques, and (3) conceptual clarity and elegance compared to existing methods.
INTRODUCTION
We first consider the convex optimization problem:
min f(z), #E3
(1)
where the objective function f is j-stroogly convex and L-smooth. Later on we consider extension composite convex optimization min, [xx) + g(x) with non-smooth function g, and class of min-max problems min maXpeR" f(u) - g(p) + (Bu, p) with bilinear coupling.
Notation. Rd is d-dimensional Euclidean space with standard fn-inner product (..)) and the in- duced norm -1. f IRd IR is a differentiable function. We say is p-stronglyy convex function when there exists 0 such that
f(y) f(x) (V)()),
- - yll Vz,yER'.
We say L-smooth with if gradient is Lipschitz continuous:
[v] V S L||x - -lls Vx,y E Rd.
The condition number is defined
T./p.
When f is p-strongly convex and L-smooth, the optimization problem I has a unique global minimizer x=. We focus iterative methods find x= A useful measure of convergence is the Bregman divergence of f, defined as (y x) == f(y) f(x) (V [x)()) y æ). In particular, Dy(x, f(xx) - f(x*), ), since V Vf(x*) O. Various bounds and identities on the Bregman divergence can be found in Appendix A
Heavy-ball methods and flow. Over the past two decades, first-order methods, which rely solely on gradient information rather than the Hessian required by Newton's 's method, have gained sig- nificant interest due to their efficiency and adaptability to large-scale data-driven applications and
"Corresponding author.

---

Published as a conference paper at ICLR 2025
machine learning tasks (Bottou al. 2018 Among these methods, the gradient descent method the most straightforward and well-established algorithms. However, for ill col-coniiiioned problems, where the condition number > the gradient descent method suffers from slow convergence.
In order to accelerate the gradient descent methods, a momentum term was introduced, encouraging the method move along search directions that utilize not only current but also previously information. The heavy-ball (HB) method (also known as the momentum method (Polyak 1964) was in the form of:
#k+1 F.
[((x)) + B(ra TK-1),
where / and y are constant parameters. Polyak motivated the method by analogy to "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" + Ow! + [())
(3)
where x = xff), x' is taking the derivative of t, and and are positive constant parameters.
Non-convergence and non-acceleration of the HB method.
Polyak 1964) showed that for
with 3 (V- vL+VK)
(VL+vH)2* and when zg sufficiently close to the optimal solution 1-v0 xx, || x²1 converges rate T+VP' where p 1/k. 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 example to show that the Polyak's 's choice of parameters does not guarantee the global convergence Ghadimi al. (2015); for general strongly convex optimization. By changing the parameters, convergence of the HB Sun et al. (2019); Saab Jr et al. (022);; Shi et al.] (2022). the global linear O(p) given by Shi et al. (2022). which coincides with that of the gradient descent and not the accelerated rate - O(P)).
x². Indeed [essard et al. (2016) designed non-convergent
method has been established. However, the best rate
The absence of accelcration not due to technical difficulty in the convergence analysis. Re- cently, Goujaud et al.) (2023) have demonstrated that the HB method provably fails to achieve an accelerated convergence rate for smooth and strongly convex problems. Specifically, for any pos- itive parameters / and y in (2). either there exists an L-smooth, ju-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 Opp). For more related works on HB methods, see Appendix B.I
Accelerated first-order methods. To accelerate the HB method, one can introduce either an ad- ditional gradient step with adequate decay or an extrapolation step into the algorithm; see Wilson ett al. 1) Siegel (2019); Chen & Luo (022I)
Nesterov accelerated gradient (NAG) method (Nesterov) 1983, page 81) can viewed as an alter- native enhancement of the HB method. Nesterov's 's approach calculates the gradient at points that are extrapolated based on the inertial force:
VT- Vp VL vp
1
Tk+1 = =Ik + B(x - xx-1) Vx +3az - Ik-1)), with 3
7= (4)
Nesterov devised the method of estimate sequences (Nesterov 2013) to prove that achieves the accelerated linear convergence rate 1 vp.
Later on, numerous accelerated gradient methods have been developed for smooth strongly convex optimization problems (Lin et al. 2015 Drusvyatskiy et al. 2018 Bubeck et al. 2015 Aujol al.)
2022 Van Scoy et al., 2017; Cyrus et al.] 2018); to name just a few. However, little is known beyond convex optimization. One reason is that the techniques developed
often specialized on the convexity of the objective function, making them difficult to extend to non-convex cases. In machine learning terms, these approaches lack generalization ability.
2

---

Published as a conference paper at ICLR 2025
Main contributions for smooth strongly convex optimization. method in the form of
We propose variant of the HB
1k+1 24 (222 - vf((x-1)) + B(xx xk-1),
L
(5)
(VT+ Vu)²
(VT. + vP)2
The most notable yet simple change is using 2V f(r)))) V fx(=))) not V (z(x)) to approximate
fx)). 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 Chen & Luo 2021
x2 1/ ===-- y V(()), M
which is special case of the HB flow with A 2 and mathematically equivalent to HB flow, the structure of this 2 x 2 first-order ODE system is cru- cial 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
when y is eliminated. Although (6)
== v' -v fx),,
where u represents velocity, offering a physical interpretation. However, the convergence analysis less transparent in the form 7 or the original second-order ODE (3).
We obtain AOR-HB by discretization of (6) with two iterates (Ixx V&) cf. 14 The AOR is used to symmetrize the error equation (19,, which represents a novel contribution compared to Luo & Chen (022) and Chen Luo (2021). The choice of parameters 3 and y in (5) is derived from the time step-size a = v /// L. We rigorously prove that AOR-HB enjoys the global linear convergence with accelerated rate, which closes long-standing theoretical gap in optimization theory.
THEOREM 1.1 (Convergence of AOR-HB method). Suppose f is p-strongly convex and L-smooth.
Let (Iy, Du) be generated by scheme [4] with initial value (xo, yo) and step size a = 1/p/L. Then there exists constant Co Coo Yo M4 L) so that we have the accelerated linear convergence
k
((x+1)) - [xx)) + 11+1 - 12 Co
121.
(8)
1 2V
W/L
Remark on non-strongly convex optimization. When μr = O. we propose a variant of the AOR- HB method that incorporates the dynamic time rescaling introduced in (Luo & Chen 2022):
k 3 (2V (2V (((x=)))) k (3%k Ik-1),
k
Fk+1 Tk
which achieves an accelerated rate of (11kk²), comparable NAG. We refer the details and the proofs to Appendix D Another approach to extend the acceleration involves using the perturbed Section 5.4).
objective f(z) + $1 discussed in Lessard al. 2016
Relation to other acceleration methods. The AOR term f( - V f 1) can be treated as adding a gradient correction in the high resolution ODE model (Shi et al. 2022). AOR-HB (5) can be also rendered as a special case of the 'SIE' iteration described in ZZhng et al. (2221) However, the parameter choice (V8 = + and m = 1 recovering AOR-HB, does not satisfy the condition in their convergence analysis (Zhang et al. 2021 Theorem 3).
For strongly convex optimization, acceleration can viewed from various perspectives, with the resulting three-term formulas differing only by higher-order O(p) perturbation. With proper change of variables, NAG (4) can be seen as a parameter perturbation the AOR-HB in the form of (5). The performance of AOR-HB are thus comparable NAG but less precise than triple mo- mentum (TM) methods (Van Scoy et al. 2017) for strongly convex optimization.
However, extending these methods (NAG, TM. SIE, and high- nigh-resolution ODEs) beyond the convex optimization rare and challenging. contrast, AOR-HB has a superior generalization capability the true driving force of acceleration is better captured by the 2 x 2 first-order ODE model (6).
3

---

Published as a conference paper at ICLR 2025
Extension to composite convex minimization.
Consider the optimization problem:
min f() + g(x),
(10)
where is p-strongly convex and L-smooth, and g is convex but maybe non-smooth function. To handle this, we only need to split the gradient term in (6) into Vz(x) + dg(y) and use an implicit discretization scheme for y. This is equivalent to applying the proximal operator
1 2X x1|
prox (z) min g +
which we assume is available. The convergence analysis of the AOR-HB-composite Algorithm 2 directly follows from Theorem 1.1 Numerically, Algorithm also performs well for certain non- smooth and non-convex functions g when its proximal operator is available, further demonstrating the generalization capability of the AOR-HB method.
Extension to a class of saddle point problems. We extend the AOR-HB method (Algorithm to a stoonly--omecx-trooglyy-oocos saddle point system with bilinear coupling, defined as follows:
min C(u,p) f()) x(p) (Bu, "ER" pER
(11)
where B E Rexm is a matrix and B denotes its transpose, Rm + R and g R" - R are strongly convex functions with convexity constant [ and M4 respectively. Problem 11 has large number of applications, some of which we briefly introduce in Appendix B3.4
Only few optimal first-order algorithms for saddle point problems have been developed re- cently (Metelev et al. [2044] Thekumparampil et al. 2022; Kovalev al. 2022 Jin et al. (0022). In particular, Thrkkuparampil et al. (2022) introduced the Lifted Primal Dual (LPD) method, the first optimal algorithm for problem III. However, LPD involves five parameters, whereas AOR- HB-saddle requires only two parameters: l and L. Numerically,
achieves highly efficient performance while retaining the simplicity of the HB method. We state the convergence result below and refer to Appendix G.3 for a proof.
THEOREM 1.2 (Convergence of AOR-HB-saan saddle method). Suppose f is psy-strongly con- vex and sm-othhhh g is Pg-strongly convex and smooth.h Let (ug, Uk Pee qı.) be generated by Algorithm with initial value (ug. Uo. Po, 40) and step size a maxpe(0.1) min VB min stant Co Co(uo. 2o. Po. 90, Hs, LJ. Hgg Lg) so that we have the linear convergence
Hr 2
He J 3) suggu
3)>/ur ). Then there exists non-negative con-
[B
(1 ( )²
(y(u441, + D Dy(PktI,P") 1$ || w²11
Mg 2
11
p01 Co
Extension to a class of monotone operator equations. Our approach provides a unified frame- work for convex optimization, saddle-pon point problems, and monotone operator equations. Consider
- 1-
(
-1-
Strongly convex optimization: A(r) = (x(),, N 0.
This is the accelerated gradient flow
developed in Luo & Chen (2022) and Chen & Luo (2021).
Composite convex optimization: A(x) Vz(x), N(y) 0g(y).
BT B
Saddle-poin problem with bilinear coupling A(z)
Volp) N
0
0
A class of monotone operators: A(x) F N is linear and skew-symmetric.
In the discretization, AOR can be utilized to faithfully preserve the structure of the flow. The AOR term is also connected the extra- aita-ggradient methods originally proposed by (Korpelevich) 1976. Popoy 1980) for saddle point problems, which has only non-accelerated rate [x]]oog We refer Appendix B.3 for more discussion.
4

---

Published as a conference paper at ICLR 2025
2 AOR-HB METHOD FOR CONVEX OPTIMIZATION
Strong Lyapunov property. To simplify notation, introduce z (z. y) and z
x²)T_
Let (z) be vector field with ((z²) 0. For generic ODE z' = ((z), a Lyapunov function is non-negative function E() satisfying E (z), (x)) 2 0 for all z near z and E(z) = 0 if and only if = z². In order to get the exponential stability, Chen Luo (2021) introduce the so-called strong Lyapunov property: there exists such that
- (VVE2)) 2 cE(z) Vz E R
(12)
LEMMA 2.1.
Let z'
((z) with z(0) Zg- Assume there exists Lyapunov function Ez)
satisfying the strong Lyapunov property Then we have the exponential stability
((z) S E(zo).
Proof. By the chain rule and the strong Lyapunov property:
ह (x(()) = (VE(z), = x
(13)
and the exponential stability follows.
For the system 6), let E(r,y) = f(x) f(x*) + E1ly - x²1 By direct calculation and the j-convexity of f. obtain the strong Lyapunov property
- (VE(z.V). v)) = (x),, x - x²) - -m( - y. 1-y-22 x²)
(Vf(x), x²) #
2 (| -=1 || y/|² 11y x= x²11²²)
1 ly x= 1|? + | yl1 = E(r, y) + 1 - yl1
2 (1)))f(x>))) +
As shown above. the strong Lyapunov property and exponential stability can be established more straightforwardly using the first-order ODE system 3 or its equivalent form 7
(6) rather than the original second-order ODE
AOR-HB method for smooth strongly convex minimization problems. Based on discretization of 66. we propose an Accelerated weer-Relxxttion Heavy-Ball (BR-HBB method:
Tk+1
Tk
0 yk
Fk+1
(14a)
Mk+1
yk Ik+1
Wk++
1 - (2V (2V[(xx+1)
V (xx)).
(14b)
Setting a = VI/LT and eliminating yk leads to the formulation 5 which is summarized in Algo-
rithm 1
The gradient V (((*++1) be reused in the next iteration, essentially only one gradient
evaluation is required per iteration in Algorithm I
Algorithm Accelerated
Heavy-Bal Ball Method (AOR-HB)
Parameters: Zg. 21 E RRd L, μ. Set 7 (VT+ mma (VT++mma*
2: for k 1.2.... do
3: Tk+1 Ihk (2V - v f((x=1)) + 3(xx- - -xk-1)
4: end for
5: return 24+1
The convergence rate in Theorem 1.1
is global and accelerated, the sense that to obtain f(xx) need at most O (vkl log <l) iterations. The iteration complexity
f(**) and || x²ll is optimal for first-order methods (Nesterov) 2013). We give proof for Theorem [.] in Appendix and will outline the key steps using convex quadratic objectives here.
5

---

Published as a conference paper at ICLR 2025
Preliminaries for convergence analysis. For symmetric matrix A, introduce (x. v)
(Az, y) = (z, Ay) and || [1a == (.-)). Consider the quadratic and couvex function f(x) = E||z||2 - (6,z) r) + c for b E R2 c I and symmetric and positive definite (SPD) matrix with bound 0 < μ S. X(A) S L, where X(A) denotes generic eigenvalue of matrix A, and Amin (A) and Amax( ()) are minimal and maximal eigenvalues of A, respectively.
For two symmetric matrices D, A, denote A < D if A is SPD and A z Df D A is when
positive semi definite. One can easily verify that A N D is equivalent to Amax ( (D- (D-A) $ D is non-singular Amin (A-1D) 2 when A is non-singular.
A
0
(A
0
A
Denote by D
and A
Define two Lyapunov functions
0
pl)
0
1
(z)) =
2 211 2"1lz. and E" (z)
z zz
1-22lI0+aa D
By direct calculation, we have A(D A = =V A(A)/M / which implies
(1-a/v0) D D + aAFmmm (1 D/
p= P/LL..
(15)
Therefore for 0 5 vp.
0 5 (1 a/ E(2) S (2) S 28(2), Vz = (I.y) E Rddd
(16)
Convergence analysis for quadratic functions. The AOR-HB method
14 can be written
correction of the implicit Euler discrctization of the flow (6)
(
1) (2x+1 - -zz). LA
0
Zk+1 - ag(Zz+1)
(17)
As & is quadratic, De (z, the identity for the difference of the Lyapunov function & at consecutive steps:
f -- y yl So use the definition of Bregman divergence, we have
{(z++1) EZz)) = (VE(2x+1). Ze+1 - 24) 2 |2 26+1113
(18)
Substitute 17 into 18 and expand the cross term as:
(VE(Z)+1), Zk+1 z = a aVVE((z))) (zx+1)) - a2x++1 - zz, , ZzaaAmm..
(19)
The AOR Az x 2A ArR Arx+1 A( xx) is used to make the last term in associated to symmetric matrix A With such symmetrization, we can use identity of squares
19
(Z&+1 z², Zb+1 Ak) = (l|z*+1 zz 21 |z z 112
||z zz" 21133mmm))
Substitute back to (88 and rearrange terms, we obtain the following identity:
EdH (z Ed (zz) a (V ((zx+1))
| Z₁ Iit
(20)
which holds for arbitrary step size a.
Now take vp. Due to 15). the last term in (0 is non-positive.
Use the strong Lyapunov
property -(V)( 2 [z), and the bound E (z)
(z)
S 20(z)
z) in (16) to get
(7(2++1) (Z)) S - -08
- - a 8" (2x+1),
(21)
which implies the global linear convergence of Ea:
h+1
1
(Z(41)) 5 + ax/2
(Za) <
E (d(z),
k 0.
(22)
1+a/22
Moreover, 21 implies
1 (z()) < [1 ) 1 (E Edh (zx+1))
1 1
E(z++1)
(²))),
a
a
which implies 8 with Co = 18" (2o) 0. Note that Co = OlVR) is large. However, when
considering the Convergence of Ea in 222 this dependency is absent.

---

Published as a conference paper at ICLR 2025
AOR-HB method for composite convex optimization. For the composite optimization problem (O), AOR-HB can be seamlessly extended by using:
x' y I, my [1( (I- 3) Vf(x)) E ag(u):
(23)
where ag(-) denotes the set of subgradient. The strong Lyapunov property and exponential stability still hold (see Appendix E) as the modification only bring an additional monotone term.
We use implicit discretization in and apply AOR to f::
2k++1
/ Mk+1 yk [ Mk+1) (2V(((+)))- E ag(yx+1).
yv kk+1;
Given the proximal operator of g, an equivalent and computation-favorrt formulation is proposed in Algorithm 2 In the convergence analysis, since the non-smooth part is discretized implicitly, no difference arises in the error equation (17). Therefore, the convergence rate and proof are identical to those in Theorem 1.I Theorem E.1 In contrast, it requires considerable effort to generalize Nesterov's accelerated gradient method to the composite case Beck & Teboulle (2009).
Algorithm 2 Accelerated Over-Relaxation Heavy-Ball Method for Convex Composite Minimization (AOR- HBRR-BB-coo composssi
1: Parameters: zo, Yo IRd, L, Set a VL and X = (1+a)4
2: for k 1.2.... do
Tk+1 1+ a (Ik + aykk
4: yk++1 proxxg where = I4a (yk + 014+1) X(2V/(m=-1) - -V(((())))))((())
1
5: end for
6: return yk+1
3 AOR-HB METHOD FOR A CLASS OF SADDLE POINT PROBLEMS
In this section, we extend the flow 3 method for boongly-convex-strongge
to min-max problems and propose an accelerated first-order saddle-point problems with bilinear coupling.
The solution (u", (u") ) to the min-max problem g(p) + (Bu, p):
(11) is called saddle point of C(u. p) = f(u)
C(u", S L(u", .P)) S L(u,p"), V E , E IR...
As C(.pp) p) is strongly convex for any given p and L(u,,) is strongly concave for any given u, we called it -oteex-sool--y point (u", .p") exists uniquely and is necessarily a critical point L(u, p) satisfying:
saddle point problem. Under this setting, the saddle
VLl"", .p')
V
BT
u p"
00
(24)
B
-Vg
where (Vf.u) = fu) and (Vg.p) = Vg(p).
HB-saddle flow.
We propose the following HB-saddle flow for solving the min-max problem [1]
1 (Vf(u) + BB +Tq),
u' U, v'
(25)
1
p' P. df
(Vg(p) - Bu).
Mg
The HB-saddle flow 255 preserves the strong Lyapunov property (see Appendix G.2 and thus the exponential stability of [u" ,p*) for 25 follows.
For the gradient term, we use JVL instead of VL with = 9). When V and Vg are linear, VL is symmetric but not monotone JVL is non-symmetric but strongly monotone. Namely (JVL(z) - CV y) 2 min(ur, Soin(ur,,yylll Ha - yll2, Vz= = (u, p) = (c, T. The strong monotonicity has essential similarity to strongly convexity. Comparing to the convex optimization, one extra difficulty is the bilinear coupling (Bu, p) which can be again handled by the AOR technique in discretization.
7

---

Published as a conference paper at ICLR 2025
AOR-HB-saddle method. We propose Accelerated -ver-Relaxation Heavy-Ball (AOR-HB- saddle) Method for solving the min-max problem (IT) in Algorithm 3 Each iteration requires
matrix-vector products and 2 gradient evaluations if we store (f(ux) and Vg(ps).
Algorithm Accelerated over-relaxation Heavy-ball method for strongly-convex-stronglyyy saddle point problems with bilinear coupling (AOR-HB-saddle)
1: Parameters: do: to IR" Pus 90 E R", f. gs ps Mg:
B||
2: Set (E(o,) min VBmin { ps (V
1.g 33
VPrPo
||
3: for k 0, 1,
do
1
1
4: uk+1
[u av:):: Pk41 1+a (px taqs)
1 +
a (2V vf(uk)) + BT qi))
5: Uk+1 =
Uk: + a0u+1
1 + a
H$
6: (K+1 +
q/: + opk+1
(2Vg(pu+1) - -yppk)))))))())) B(20x+1 vk))
Hg
7: end for
8:
return Uk+1, 11 91++1
The convergence rate in Theorem 1.2 global and accelerated, meaning that ob- lain (ux. Pk) - "u",,")] I and [1 9x) (u)) S we need at most O (v / + Lg/ Mt + (11112/(991g)) log iterations. The iteration complexity is optimal for first-order methods for saddle point problems (Zhang et al. 2022).
Remark 3.1. We can treat the coupling implicitly: Line 5 and 6 Algorithm are replaced by
1
Uk+
Uk + 000441
(2V (2V((ux+1) [((u)) + B BT (Tax+t)
1 a
P
(26)
9k+1
1
ak app+1
(2Vg(Pk+1)
Vg(pk) Bok+t)
I + a
ig
((+
BT
Now (1841s (c+1) are coupled together and can be computed by inverting
a Mg (-2B
pr (1 (1+a)1
It is sufficient compute (11+ a) a BB BBT)
((++0) a² B
MyPe whichever is a relative small size matrix and can be further replaced by an inexact inner solver. We name the method
4/Pg
and the convergence rate can be improved to
1 O(vp) with min (u// / Ly Mg/ / Lg): see Appendix H for the formal results.
4 NUMERICAL RESULTS
In this section, we evaluate the performance of our AOR-HB methods on suite of optimization problems. All numerical experiments were conducted using MATLAB R2022a on desktop com- puter equipped with an Intel Core i7-6800K CPU operating at 3.4 GHz and 32GB RAM. We compare the results against several -ate-offtheeart optimization algorithms from the literature.
4.1 SMOOTH CONVEX MINIMIZATION
We test our AOR-HB method (Algorithm I and compare it with other first-order algorithms includ-
ing: (i) GD: gradient descent; (ii) NAG: Nesterov acceleration (Nesterov) 2013); (ii) HB: Polyak's
momentum method (Polyak 1964); (iv) TM: triple momentum method (Van Scoy et al. 2017) and
(v) ADR (Aujol et al. 2022
First, we test the algorithms using smooth multidimensional piecewise objective functions borrowed
from Van Scoy al. (017). Let
f(x) Σ
F
(a, x b.) |110| h(x)) = ( 1 2 1022--10
r/a
x > 0 x 5 0'
(27)
(0
8

---

Published as a conference paper at ICLR 2025
where A = [ai..... ap) E R and b I" with |||||| VL- μ. Then f is μ- strongly convex and L-smooth. We randomly generate the components of A and b from the normal distribution and then scale A so that ||||| vL μ. We set 1 L, 10 d 100, p 5 and r = 10
10t
Figure illustrates the logarithm of || x"1 for each algo- rithm's iterates. The HB method reaches plateau and fails to converge, while the other algorithms demonstrate global and lin- car convergence. As expected, GD, being non -oceeccee,,,,ed, con- verges slowly due to the large condition number. The AOR- HB method performs efficiently as NAG and ADR. The TM method achieves convergence rate of (1- vu/L)², slightly outpacing other accelerated algorithms. However, TM requires more parameter tuning and has not yet been extended beyond strongly smooth convex optimization.
10
MAG
10.10
KDR
Figure I: Simulation results for the objective function (27
Next, we report the numerical simulations on logistic regression problem with & regularizer:
min Σ log (1 exp (-b;a, x)) + ||
(28)
10
MAG
where (a,, b.) E Rd x {-1,1), 1.2. ..... m. For the logistic regression problem, l = X and L, Amax (Iit a;a, X. The data a; and 6; are generated by the normal distribution and Bernuuli distribution, respectively. We X 0.1, 1000, and 50. As illustrated by Figure this is an example where HB converges and it converges fastest. However, such fast con- vergence lacks theoretical guarantees and may fail in cases like the one depicted in Figure [ of robust theoretical convergence analysis rather than relying on empirical success alone.
ADM
10
10
2000
Figure 2: Simulation results for the logistic regression problem
This highlights the importance
28
4.2 COMPOSITE CONVEX AND NON-CONVEX MINIMIZATION
We test the performance of AOR-HiB-composit method (Algorithm non-smooth optimization problems and compare with two well-known methods: the Fast Iterative Shrinkage-Threen Thresholdihng Algorithm (FISTA) Beck & Teboulle (2009) and the Accelerated Proximal Gradient (APG) algo- rithm proposed in Li & Lin (2015).
We first consider the Lasso problem:
tot
min マ Ar - b12 + A||=||1,
which has wide applications compressed sensing, signal process- ing, and statistical learning, among other fields (Tibshirani, 1996). We generate the matrix A with size 1024 x 256 from Gaussian random matrices and ground-truth sparse vector of sparsity 5. The data vector obtained by matrix-vector multiplication b = Ar. We set À 0.8 and use the step size APG. We plot the decay of the relative &a error in Figure 3 All the methods cannot reach the accuracy of 10-3, This is because the ground-truth (sparse) solution may not be the minimizer of the corresponding minimization problem.
Figure 3: Comparison of & minimization methods.
1/L in FISTA and
AGB
10a
APG
Then we test the non-convex L by case where the l regular- izer is substituted by ||=||| - ||>||-- The proximal operator for g(x) := X(||=|I || is given in Yin et al. (2015). Using such non-smooth and non-convex function g will produce solution with better sparsity. The other settings remain the same the Lasso problem. FigureBladd4 show the convergence the relative la er- ror, where all methods converges but AOR-HB outperforms others.
Figure 4: Comparison of E lg minimization methods.

---

Published as a conference paper at ICLR 2025
4.3 SADDLE POINT PROBLEMS
We compare AOR-HB-saddle (Algorithm 3)
with the following algorithms: (i) AG-OG: accel-
erated gradient-optimistic gradient method with restarting regime (Li et al. 2023); (ii) APDG:
accelerated primal-dual gradient method (Kovalev et al. 2022]; (iii) LPD: lifted primal-dual
method [Thckumparampil et al. 2022; (iv) EG: variant of extra-gradient method (Mokhtari al. 2020a).
We consider policy evaluation problems in reinforcement learning (Du al. 2017 when finding minimum of the mean squared projected Bellman error (MSPBE):
arg min 2 |B - |lull
The corresponding saddle point problem (see Appendix B.4) is
aE PER 2 |u] _
min max
1
Illle - (b, + (Bu,p).
(29)
The saddle point formulation saves the computation cost of inverting C. In this example, μy Ls 1, Mg Amin (C') and Lg Amax (C). We generate random matrices B and C' such that
Mg = 1 and the condition number Kig = BB We set m 2500 and 50.
10a
We plot the convergence of eπror versus the number of itera- tions in Figure [5] Since each method has comparable per- iteration computational cost, the iteration count serves measure of efficiency. We only plot the case Ki = 10 but similar trends are observed for other condition numbers, where our -oadHee- methods consistently exhibit faster linear convergence compared to other algorithms.
AFDG
fair
10
10"10
Among the methods, MOR-HB-saddle-1 the semi-implicit scheme 26). achieves the fastest convergence and is overall the most time-efficient. is preferable when the coupling term || (1blg) exceeds vKy and Rig and the direct solver to compute ((1 a (I+a)uyp, the case 50) here. When the direct solver becomes com- putationally expensive, the explicit scheme AOR-H HRR-HB--addee is preferable, provided an optimized step size a is used.
Birnilion
Figure 5: Simulation results for MSPBE 29
a² BB ) is efficient, which is
AGCG
AFCO
Bleestion R
1nf
In Figure 6
we plot the iteration number K versus Kg such 10 In this log-log scale plot, we can ob- serve that the growth of iteration complexity is Ol for accelerated algorithms and ((kg) for EG, which matches the convergence analysis.
that | || <
10a
10
16a
10
Figure 6: Rate of convergence.
Among all accelerated algorithms we have tested, our AOR-HB-saddle method requires fewer iter- ation steps to achieve the desired accuracy. In addition, HB--dl- has single-loop structure and requires fewer parameters to tune, which is favorable for implementation.
5 CONCLUDING REMARKS
In conclusion, we have introduced the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) meth- ods, significant advancement of the accelerated first order optimization algorithms. This fills theoretical gap heavy-ball momentum methods and opens the door to developing provable accel- erated methods with potential forays into non-convex optimization scenarios.
AOR-HB comes with certain limitations. First, AOR-HB methods require the parameters j and L. While this is typical for accelerated methods, exploring adaptive strategies to reduce parameter dependence is an interesting direction for future research. Second, the convergence rates established not tight those achieved by the TM method (Van Scoy al. 2017 Taylor & Drori 2023). Finally, investigating the algorithm's 's performance under stochastic conditions is essential for assessing its robustness in real-world machine learning applications.
in some theorems
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The authors would like to thank Dr. Hao Luo and Professor Yurii Nesterov for their insightful discussions during the preparation of this work. We are also grateful to the anonymous reviewers for their constructive comments and suggestions, particularly for highlighting the Lifted Primal- Dual (LPD) method [Tekumparampil al. (2022), which helped improve the quality of the paper. We also thank Dr. Thekumparampil for generously providing the code for LPD. This work was supported by the National Science Foundation under grants RMS-2012465, DMS-2309777, and DMS-2309785.
REFERENCES
Hedy Attouch, Xavier Goudou, and Patrick Redont. The heavy ball with friction method, i. the continuous dynamical system: global exploration of the local minima real-valued function by asymptotic analysis of dissipative dynamical system. Communications in Contemporary Mathematics, 2(01))1-34, 2000.
J-F Aujol, Ch Dossal, and Aude Rondepierre. Convergence rates of the heavy ball method for quasi-strongly convex optimization. SIAM Journal Optimization, 32(3):1817-1842, 2022.
Amir Beck and Mare Teboulle. fast iterative ttrnkkaggg-treeehlniing algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2200 -0-202 2009.
Raghu Bollapragada, Tyler Chen, and Rachel Ward. On the fast convergence of minibatch heavy ball momentum. arXiv preprint arXiv:2206.06 07553, 2022.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, (0(2))223-311) 2018.
Felix E Browder and Wolodymyr V Petryshyn. Construction of fixed points of nonlinear mappings in Hilbert space. Journal of Mathematical Analysis and Applications, 20(2):197-228, 1967.
Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to Nesterov's 's accelerated gradient descent. arXiv preprint 1rXivv1566.000 150..08177, 2015.
Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120-145, 2011.
Gong Chen and Mare Teboulle. Convergence analysis of proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-544 1993.
Long Chen and Hao Luo. A unified convergence analysis of first order convex optimization methods strong Lyapunov functions. arXiv preprint arX1v:2108.00132, 409):10, 2021.
Shisheng Cui and Uday V Shanbhag. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In 2016 IEEE 55th conference on decision and control (CDC), pp. 4510-4515. IEFE, 2016.
Saman Cyrus, Bin Hu, Bryan Van Scoy, and Laurent Lessard. A robust accelerated optimization algorithm for strongly convex functions. In 2018 Annual American Control Conference (ACC), pp. 1376-1381. IERE, 2018
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint 1:X.v:17111.01444 2017.
Jelena Diakonikolas and Michael Jordan. Generalized momentum- based methods: Hamiltonian perspective. SIAM Journal on Optimization, 31(1):915 944, 2021.
Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM Journal on Optimization, 29(1):660-689, 2019.
Dmitriy Drusvyatskiy, Maryam Fazel, and Scott Roy. An optimal first order method based on optimal quadratic averaging. SIAM Journal on Optimization, 2811::25--211, 2018.

---

Published as a conference paper at ICLR 2025
Simon S Du and Wei Hu. Linear convergence of the primal-dual gradient method for convex- concave saddle point problems without strong convexity. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 196-205. PMLR, 2019.
Simon Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1049-1058. PMLR, 2017.
Euhanna Ghadimi, Iman Shames, and Mikael Johansson. Multi-step gradient methods for networked optimization. IEEE Transactions on Signal Processing, 61(21):5417-5422 2013.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pp. 310-315. IEEE, 2015.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint 1rXhv:1802.1055/1 2018.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gra- dient method for monotone variational inequalities. Advances in neural information processing systems, 35:21858-2111 -28700 2022.
Baptiste Goujaud, Adrien Taylor, and Aymeric Dieuleveut. Provable non-accelerations of the heavy- ball method. arXiv preprint arXhv:2307.1129) 2023.
Apostolos Hadjidimos. Accelerated overrelaxation method. Mathematics of Computation, 32(141): 159-157, 1978.
Yujia Jin, Aaron Sidford, and Kevin Tian. Sharper rates for separable minimax and finite sum op- timization via primal-dual extragradient methods. In Conference Learning Theory, pp. 4362- 4415. PMLR, 2022.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Georgios Kotsalis, Guanghui Lan, and Tianjiao Li. Simple and optimal methods for stochastic variational inequalities, i: operator extrapolation. SIAM Journal on Optimization, 32(3):2041- 2073, 2022.
Dmitry Kovalev, Alexander Gasnikov, and Peter Richtárik. Accelerated primal-dual gradient method for smooth and convex-concave saddle-poin problems with bilinear coupling. Advances in Neural Information Processing Systems, 35:21725-21177 2022.
Walid Krichene, Alexandre Bayen, and Peter I. Bartlett. Accelerated mirror descent in continuous and discrete time. Advances in neural information processing systems, 28, 2015.
Qi Lei, Ian En-Hsu Yen, Chao-yuan Wu, Inderjit $ Dhillon, and Pradeep Ravikumar. Doubly greedy primal-dual coordinate descent for sparse empirical risk minimization. In International Confer- ence on Machine Learning, pp. 2034-2042, PMLR, 2017.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algo- rithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
Chris Junchi Li, Huizhuo Yuan, Gauthier Gidel, Quanquan Gu, and Michael Jordan. Nesterov meets optimism: rate-optimal separable minimax optimization. In International Conference on Machine Learning, pp.
PMLR, 2023.
Huan Li and Zhouchen Lin. Accelcrated proximal gradient methods for nonconvex programming. Advances in neural information processing systems, 28, 2015.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimization. Advances in neural information processing systems, 28, 2015.
12

---

Published as a conference paper at ICLR 2025
Fengshan Liu and M Zuhair Nashed. Regularization of nonlinear ill-posed variational inequalities and convergence rates. Set- Valued Analysis, 6(4):313 13-344, 1998.
Hao Luo and Long Chen. From differential equation solvers accelerated first-order methods for convex optimization. Mathematical Programming, 195(1):735-78)) 2022.
Yu Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25(1):502-522 2015.
Dmitry Metelev, Alexander Rogozin, Alexander Gasnikov, and Dmitry Kovalev. Decentralized saddle-point problems with different constants of strong convexity and strong concavity. Compu- fational Management Science, 21(1):5, 2024.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra sttra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020a.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of (1) for op- timistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal on Optimization, 3034):3230-3251, 2020b.
Michael Muchlebach and Michael Jordan. A dynamical systems perspective on nesterov accelera- tion. In International Conference on Machine Learning, pp. 4656 4662. PMLR, 2019.
Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1)2229-251, 2004.
Yurii Nesterov. A method of solving convex programming problem with convergence rate O(1/k²). Doklady Akademii Nauk SSSR, 269(3):543, 1983.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-344, 2007.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Yurii Nesterov. Lectures on convex optimizaaion, volume 137. Springer, 2018.
Yurii Nesterov and Laura Scrimali. Solving strongly monotone variational and quasi- variiaiaaia inequalities. 2006.
Peter Ochs, Thomas Brox, and Thomas Pock. iPiasco: inertial proximal algorithm for strongly convex optimization. Journal of Mathematical Imaging and Vision, 53:171-181, 2015.
Rui Pan, Yuxing Liu, Xiaoyu Wang, and Tong Zhang. Accelerated convergence of stochastic heavy ball method under anisotropic gradient noise. arXiv preprint arXiv:2312. 14567, 2023.
Wei Peng. Yu-Hong Dai, Hui Zhang, and Lizhi Cheng. Training GANs with centripetal acceleration. Optimization Methods and Software, 35(5)95559973, 2020.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Leonid Denisovich Popov. modification the Arrow-Hurwizz method search for saddle points. Mat. Zametki, 2875)77777784, 1980.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.
Samer Saab Jr. Shashi Phoha, Minghui Zhu, and Asok Ray. An adaptive polyak heavy-ball method. Machine Learning, 111(9):245-3277) 2022. 2022.
13

---

Published as a conference paper at ICLR 2025
Jesús María Sanz Serna and Konstantinos C Zygalakis. The connections between Lyapunov fune- tions for some optimization algorithms and differential equations. SIAM Journal on Numerical Analysis, 5963):552--1655 2021.
Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' d'Apremmot. Integration methods and optimization algorithms. Advances in Neural Information Processing Systems, 30, 2017.
Bin Shi, Simon S Du, Michael I Jordan, and Weijie J Su. Understanding the acceleration phe- nomenon via high-resolution differential equations. Mathematical Programming, pp. 1-70, 2022.
Jonathan W Siegel. Accelerated oorder methods: Differential equations and Lyapunov functions.
arXiv preprint arXiv: 1rXhv:1903.0567,, 2019.
Chaobing Song and Jelena Diakonikolas. Cyclic coordinate dual averaging with extrapolation. SIAM
Journal on Optimization, 33(4):2935-2961, 2023.
Weijie Su, Stephen Boyd, and Emmanuel J Candes. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research, 17 (153):1-43) 1::3, 2016.
Boya Sun, Jemin George, and Solmaz Kia. High-resolution modeling of the fastest first-order opti- mization method for strongly convex functions. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 4237-4242. IEEE, 2020.
Tao Sun, Penghang Yin, Dongsheng Li, Chun Huang, Lei Guan, and Hao Jiang. Non-ergodic con- vergence analysis of heavy-bal algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp.
2019.
Iyy Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147, PMLR, 2013.
Adrien Taylor and Yoel Drori. An optimal gradient method for smooth strongly convex minimiza- tion. Mathematical Programming, 119(1)9:55)) 199(1):557-594 2023.
Adrien Taylor, Bryan Van Scoy, and Laurent Lessard. Lyapunov functions for first-order methods: Tight automated convergence guarantees. International Conference on Machine Learning, pp- 4897-4906. PMLR. 2018.
Kiran K Thekumparampil, Niao He, and Sewoong Oh. Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 4281-4308. PMLR, 2022.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):23,-25,, 1995.
Kansei Ushiyama, Shun Sato, and Takayasu Matsuo. A unified discretization framework for differ- ential equation approach with Lyapunov arguments for convex optimization. Advances in Neural Information Processing Systems, 36, 2024.
Bryan Van Scoy, Randy A Freeman, and Kevin M Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1): 49-54, 2017.
Hongbin Wang and Paul C Miller. Scaled heavy-ball acceleration of the Richardson-Lucy algorithm for 3D microscopy image restoration. IEEE Transactions on Image Processing, 23(2):848- 854, 2013.
Jun Kun Wang, Chi-Heng Lin, and Jacob D Abernethy. A modular analysis of provable acceler- ation via Polyak's momentum: Training wide ReLU network and a deep linear network. In International Conference Machine Learning, pp. 10816-10827. PMLR, 2021.
14

---

Published as a conference paper at ICLR 2025
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(47):E7351- E7358, 2016.
Ashia C Wilson, Ben Recht, and Michael Jordan. A Lyapunov analysis of accelerated methods in optimization. Journal of Machine Learning Research, 22(113):1-34 2021.
Hedi Xia, Vai Suliafu, Hangjie Ji, Tan Nguyen, Andrea Bertozzi, Stanley Osher, and Bao Wang.
Heavy ball neural ordinary differential equations. Advances in Neural Information Processing Systems, 34:1864 14:16666-1869, 2021.
Penghang Yin, Yifei Lou, Qi He, and Jack Xin. Minimization of 1 2 for compressed sensing. SIAM Journal on Scientific Computing, 37()):553-A563, 2015.
Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901-99)) 2022.
Peiyuan Zhang, Antonio Orvieto, Hadi Daneshmand, Thomas Hofmann, and Roy S Smith. Revisit- ing the role of euler numerical integration on acceleration and stability in convex optimization. In International Conference on Artificial Intelligence and Statistics, pp. 3979-3987. PMLR, 2021.
Yuchen Zhang and Lin Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization. Journal of Machine Learning Research, 18(84):1-42, 2017.
Dao Li Zhu and Patrice Marcotte. Co-coercivity and its role in the convergence of iterative schemes for solving variational incqualities. SIAM Journal on Optimization, 6(3):714-726, 1996.
A DEFINITIONS AND STANDARD RESULTS
We review some foundational results from the convex analysis.
Recall that the Bregman divergence of is defined as
(y x) := f(y) - f(x) ff((x),-=2) which is in general non-symmetrie, i.e., (y x) + (z v). A symmetrized Bregman divergence defined as
(v)()) V (v)), .) = Dy x) + Dy(
We have the following bounds on the Bregman divergence and the symmetrized Bregman diver- gence.
LEMMA A.1 (Section 2.1 in Nesterov 2018)). Suppose f RRd - is p-strongly corvex and T-smooth. For any x. y Rdd
P > 2ll s D) || y11
(30a)
2
1
1
Vf(x)
2 < x)(,,)) < /V((x) vf(r))?
(30b)
2L
2μ
μ|| - vl2 s (Vf(z)- - f(()), I - y) < L||x - -v12,
(30c)
7,
[V/(a) 1 < (V/(z) - vf(w), - x
|V](()) ((w)1
(30d)
The following threc-point identity on the Bregman divergence will be used to replace the identity of squares.
LEMMA A.2 (Bregman divergence identity (Chen & Teboulle 1993) differentiable, then for any z, V, E Rd it holds that
function Rd + R
is
(V - Vf(x).v 2) = Dy v) Dy(v. -D,(2,))
(31)
Proof. By definition,
Dy(2,u) f(z) f(v) (V)()), v),
Dy(,,x) = f(v) - f(x) - (V/(x). x),
Dy(2, f(=) - -(x) (V)(x), x).
Direct calculation gives the identity.
15

---

Published as a conference paper at ICLR 2025
B RELATED WORKS
B.1 EXTENSIONS/APPLICATOOSS HEAVY-BALL METHOSSS
While the acceleration guarantee has not yet proved rigorously, applications of heavy-ball methods including extension to constrained and distributed optimization problems have confirmed its perfor-
mance benefits over the standard gradient-basee methods (Wang & Miller 2013 Ochs et al. 2015
Ghadimi et al. 2013 Diakonikolas & Jordan 2021).
Sutskever et al. (2013) showed that stochastic gradient descent with momentum improves the train- ing of deep and recurrent neural networks. Also, using heavy-ball flow improves neural ODEs training and inference (Xia et al.] 202T). Recently, accelerated convergence of stochastic heavy- ball methods has been established in Pan et al.) (2023); [Bolapragada et al. (2022); [Wang et al. (202T) but only for quadratic objectives. get of the hyperparameters used in the heavy-ball methods, [Saab Jr et al. (2022) proposed adaptive heavy-ball that estimates the Polyak's s optimal at each iteration.
B.2 FIRST-ORDER METHODS AND DYNAMIC SYSTEM
One approach to better understand the mechanism the iterative method is the continuous time analysis: derive ordinary differential equation (ODE) model which coincides with the iterative method taking step size close to zero. Starting from the accelerated first-order methods for un- constrained optimization, important milestone in this direction is understand the acceleration from the variational perspective (Su et al.) 2016 Wibisono et al., 2016). While the iterative meth- ods are first-order, the continuous-tine or high-resolution ODEs (Shi et al. 2022] [unn et al. 2020; Muehlebach & Jordan 2019 Attouch al., 2000). With the continuous- time dynamic, novel accelerated methods are proposed by time discretization of the ODE model and usually the behaviour of the dynamic facilitates the conver-
dynamics proposed for accelerated methods are high-order
gence analysis of the iterative methods (Krichene et al. 2015 Luo & Chen 2022 Aujol al. 2022
Wilson et al. 202T Siegel 2019).
Due to the appealing results, systematic framework to draw connection between the dynamic system and the accelerated iterative method gains lots of interest (Scieur et al. [017 Ushiyama al. 2024 Taylor et al. 2018 Sanz Serna & Zygalakis| 202I). In fact, the theory and methods developed for other problem classes often build upon the work done in unconstrained optimization (Diakonikolas & Orecchia 2019).
B.3 EXTRA-GRADIENT METHODS BEYOND CONVEX OPTIMIZATION
The extra-gradient method, also known as optimistic gradient method can be formulated as:
Th-1 I 04 (2F())) (xx-1)))
where F()) is a (strongly) monotone and Liptschitz continuous operator. The origin of the extra- gradient method was proposed by (Popov. 1980 Korpelevich 1976) for saddle point problems, in an equivalent form
Fx Fg - -()+-1); Th+1 = Tb F(+x).
The anchoring of the gradient was introduced to circumvent the issue that the standard gradient method does not always converge. This algorithm was subsequently studied by. name just few among others, Chambolle & Pock (201T); Malitsky (2015); Nesterov] (2007) under various wild application in machine learning such as training generative adversarial networks (Gidel et al.) 2018 Daskalakis et al.) 2017 Cui
settings, and have recently attracted considerable interest
& Shanbhag 2016 Peng et al. 2020). The optimal rate convergence O(1/k) achieved by
(Korpelevich 1976 Nemirovski 2004 Gorbunov et al. 2022 Mokhtari et al.) 2020b). When the
operator is y-strongly monotone and L-Liptchitz continuous, the method was shown to exhibit a
geometric convergence rate Tseng (1995); Nesterov & Scrimali (2006); Kotsalis et al. (202);; Song & Diakonikolas (2023). However, the iteration complexity of O(L μu| log <l) i8 suboptimal when applied to convex optimization problems or saddle point problems.
16

---

Published as a conference paper at ICLR 2025
B.4 APPLICATIONS OF BERONGLY-CONVEX-STRONEE CONCAVE SADDLE POINT PROBLEMS WITH BILINEAR COUPLING
A classical upplication the regularized empirical risk minimization (ERM) with linear predictors, which is classical supervised learning problem. Given a data matrix B = [b1, b2. ... bnp] E Raxm where E RT is the feature vector of the i-th data entry, the ERM problem aims to solve
min (Bu) + f(u). wER
(32)
where g R + IR is some strongly convex loss function, f R - R. is strongly convex regularizer and u R is the linear predictor. Equivalently, we can solve the saddle point problem
min max {D" Bu g" g0(p) + f(u)).
(33)
NER PE
The saddle point formulation is favorable in many scenarios, for instance (Zhang & Xiao & Hu 2019 Lei et al. (017).
2017 7 Du
Another application is policy evaluation problems in reinforcement learning when finding minimum the mean squared projected Bellman error (Du et al. 2017
1 arg min 2 Bu b + Mul.:
where B, C are given matrices. The corresponding saddle point problem is
1 2 -
min max デ |u|l2 mE peR
-
- (b.p) + (Bu, p).
The saddle point formulation saves the computation cost of inverting C.
C PROOF OF THEOREM L.1
Consider the Lyapunov function
+ 11l- =1==== = Dy(e, x²) )+ + 1 1ly xv1, -1o
E(z) = E(x,)) : = and the modified Lyapunov function
(34)
8 (z) = Ex
(x. v)
E(x, v) + a - ( --
= =D((,, + -lu-~* "
(V - (f(""), - x²).
(35)
The novelty of EI(,, y) is the inclusion of the cross term a (V)()) - V V/<z"),v-r x²)) We denote the right-hand side of the accelerated gradient descent flow as
y - x, [V ((z) = ((x,)) = r y
LEMMA C.1 (Strong Lyapunov property (Luo & Chen 2022 )
- (VE(x, 9(x v)) 2 8(r, v) + " b x - vll Vx,y E Rd.
(36)
Proof. By direct calculation and the p-convexity of f, (VE (C( v)) (V)())
- xx) -1(z= y.y x²)
=V[()), 1 [| x
|| y/1² - 11y x }l)
2
2 f(x) ff()) ! I x-=1"1 x
H/ ||= v11 = E(x.8) v) 1/2 1| 2
+
2
17

---

Published as a conference paper at ICLR 2025
LEMMA C.2. Suppose f R - R is p-strongly convex and L-smooth. Denote by p L.L.
For any two vectors Zk: 2 R2dd and a > 0, we have the following inequality on the Bregman divergence of defined by 34
a
1-
(zk,
S De(zs, Zx+1) + ta Uk, vf(x++1) (((===1)-V(<xa)))
vp
a [ 5o D De
Proof. Using the identity of squares (for y) and Bregman divergence identity 331 the component form of
(for I), we have
De (Zk, Zb+1) (Zz, Tk+1)
(z
+ lyk yk+ 1ll.
By Cauchy-Schwarz inequality and bound (30b) in Lemma A.1
we have
avIp 11
a (y8+11 lk: V(((++1) - V[((x)))
V (ark) v((
Vk++1 11?
2/
Lv
Va Dy(0
11 yk+ill 11
2
M V # (D)(E)) (112)
llu 3k+2112)
By Lemma C.2 and E(z) (z(z, z²) where z" = (x)) is straightforward verify the following bounds for E, 8a Lyapunov functions. Assume 0 < v with p z. Then
0 (z) S (2(2), Vz (x, E 2
(37)
Now we are in the position to prove our first main result.
Proof of Theorem
I.1 We write 14) as a correction of Implicit Euler discretization of (6)
yk+1 ykk 7k+1 2 = og( a (V {((x)))
(38)
and substitude into the identity of
E(2++1) - E((2)) (VE(2++1), 26+1 2nd - (2t,,, 2k+1)
= =a(VE(ZZ+L) ((z++1)) - -a (H(V))((VV)))))) ( - f((x))) DE Zx+1).
yk+1 - 3/k
We write out the component form of the middle term and split it as
a (VV+(())1) vf(="), Mh+1 yk) + a( x", vf(x+41) vf(zx))
a(V/((x+1) Vf(x*), Me+1 - x²) a( - yk. VS(#++1) (xx)))
aayu =x", Vf(xx) vf(z))).
Substitute back to (8)) and rearrange terms, we obtain the following identity:
Ea (zu+1) E (zz) a (V
(39)
(2 2++1) - alyk+1 (s( - vf(xx));
By Lemma C we can drop the terms in the second line for 0 <as vp. Use the strong Lyapunov
property 36 and bound 37 we have
0 (Z6++1) (z(()) I -0E(24+1) < - 0 E" (z(+1))
(40)
18

---

Published as a conference paper at ICLR 2025
which implies the global linear convergence of E":
h+1
(Z6++)) v + a+/
(z)) -
{0())) 2 0.
1 1+ 1
Moreover, (40) implics
E(zx+1) - (E (E) - Ed (z++1))
1 (zi)) S 1
) (Z(Z),
1+ a/2
a
which coincides with (8) with Co
1 a
(zo) 2 0.
D AOR-HB METHOD FOR NON- STRONGLY CONVEX MINIMIZATION
In this section, present AOR-HB for non-strongly convex case, i.c., μ O. The convergence analysis is motivated by the Hessian-driven Nesterov accelerated gradient (HNAG) flow proposed in Chen & Luo 2021).
D.1
METHOD
Consider the rescaled rotated gradient flow
x' 8.
V/ 1 Vz(), ?
where y
a time rescaling parameter. This is the degenerated version of the rotated gradient flow Chen & Luo (2021) for non-strongly convex cases.
Using AOR technique to discretize, we get the update rule: given (I', 8k), compute
Tk+1
Fh
Uk
Tk+l,
Okk
(41)
1/++1
(2V
(2V((x++1) (s(x)))
Or 7k
We shall choose the parameters
2
7 a²L
0g
k+1
By eliminating yn ss get the AOR-HB-O method:
&
I6+1 I& k - 3L (2V (ani))-((((a- vf(xx-1))
+ k 3 (ok xk-1).
D.2 EQUIVALENCE HNAG
Introduce another parameter B% > 0 and change of variable
yk = 2/2 B& V f*x).
(42)
Substitute back yk
we obtain discretization in terms of (æy,
1b+1
Uk
Uk+1 - 3u V ((x))
(43)
0k+1
2k
1
BkB4+1
(f( +
vf(zx).
O
7k
akk
7
akk
Ol
at
Now we choose 3x
such that 04
We can further simplify (43) to
L.
7
7k
Jk+1
Uk
xk-
B& -&Vf((x))
(44a)
ak
Uk+1 1
Uk 1
Vf(x+t1)
(44b)
Ork 7k
19

---

Published as a conference paper at ICLR 2025
with
2
7hBB+11
OCk
k +
7k =
2
7 =
k nk.
Ork
It is straight forward to verity that Th satisfies
k +
h: +
0
1: +
(k 1)2
7++1
k + 7641
+1
7
7h
k(k + 3) 76
*/k-
k+1
aj
1 apk
which is equivalent to Therefore,
ik+1 7
71+1-
(45)
O
44
combining
45
is discretization of the following variant of the HNAG flow:
r' = - BV)(x).
1 - Vf(x),
= - 7
(46)
5
Notice that the flow for the dynamic coefficient is > = Chen & Luo (002)). We shall show
the convergence rate is accelerated for the scheme formulated in (44) The proofs turned out to be similar.
D.3 CONVERGENCE ANALYSIS
Define the Lyapunov function
7 -110 x²11..
f(x) +
2
We denote the right hand side of the flow 46 ((z v, 7). Direct computation gives
& || 1²1
- -(V u, G(x v,
(Vf(z) V
E(x, v, [z)
Hence E(.) satisfies strong Lyapunov property. THEOREM D.1 (Convergence rate for ntnnslrongly convex minimization). For (Ik: Un) generated by 440 with initial values (æ), U1, 71) = (Zo, up To) and
k
+
3x
a
k
1
+
0 T,'
k
have the convergence
6
E Uk41, Fk+1)
II
En <
Eo.
(47)
1 + aj
(k
k 3)
+ 2)
j=1
where E = E(oo, vo. 7o).
Proof. For short, we denote zy (xx, Uh 7x) and the right hand side of (46 by G(Z)) =
" GNT Let calculate the difference E(z++1) E(za) + la 13 with
E (IN+11 Uk m1) E(zx).
L = E (zb+1, Ukti, 76) E (Ik+1, Uk. 7k).
Ig E(z441) E (I Uk+1, k1).
We shall estimate the above three terms by one.
20

---

Published as a conference paper at ICLR 2025
As & is linear in terms of y, get
I3 & (I1++1, 1k41, 1 76+1 -m) = oz & (14+1; Me+1, f++1)) 1
Pkt1).
For the second item 12, the fact that (I1+1,'ss (5 is quadratic and equation (4hb) to get
7
12 (Vog (10+11 1 (k), 0h+11 us)
|luk-1
vx|l" 1
2
( (IR+1, 1 74+1) 9h+1)
|1u++1
uxll
2
where in the last step, switch the variable (I1+11, Ub41(()) to (2R+1, uk+1, (x+1) as the parameter fy is canceled in the product (V,E,""
Next for 1
the update formula 44a) and bound (30b).
I (V,ε (IR+1, Uk. 7x+1) 1) T6+1 T&) Dy(TRR Ix-1)
S ax ( (2++1), 9" (2k+1)) + ar [ (I++1) Vf (Ix+1) - V. (rxx))
(48)
1
+ or (V (I++1) Uk Uk+1)
[Vf
V
2L
In the first term, we can switch (I1+11 Uke 7k) 2 because 7,E V V(())) is independent of (u,7).
We use Cauchy-Schward inequality to bound the terms in 48 follows:
1
+ ag
ag V (#E+1)ll u0t1ll <
|V (m++1)
|| u 1 11
2L
2
and
ag (Vf (#++1), V (x++1) - Vf (xx))
343h | (=+)]1²+ 2
+ ag Bx
ax
|V/ 111
I1V (ax-1) -V (sx))l
2
2
2
Adding all together and applying strong Lyapunov property at 2 (but with Be not 3k- 1) yields that
1
onBE
E(2x+1) E(2x)
-04E(2++1)
(ire az. 110e -
|V (Ix))1
2
1
1
ax
| (Ix+1)ll
2
b
1
7.)
1
[V -T
2
By our choice of parameters:
0434 - =0, 36 > = =
we get
E(z++1) E(zx) & -
by throwing away negative terms. Rearrange terms and by induction we have the decay (4
The convergence rate
j +1
1
II 1=1
3+3 (k + 3) + = O
1
5=1
We conclude that for AOR-HB-0 method 9 f(x) - fx*) converges with complexity O(1/Ve).
17
21

---

Published as a conference paper at ICLR 2025
E
STRONGLY LYAPUNOV PROPERTY FOR AOR-HB-COMPOSHE FLOW
Consider the Lyapunov function
E(z, v) == xx(xxx))) + 211l
+ llv x=1l
where the Bregman divergence (x(xxx*) is generalization of f(x) f(x*) in the single convex function case.
We rewrite the flow
23 as
I' y 2,
y = x - - +))())++); E dg(y).
With this formulation, we denote the right- side as
y - 2, ((z) = gxx = y y--y- [(f(() ( -
+ e))
Using the first order optimality condition, G(z") = O for some 8r 0g(x").
We restate and prove the strong Lyapunov property in the following Lemma. The difference com- pared with the proof of Lemma C.1 is highlighted in blue.
LEMMA E.1 (Strong Lyapunov property for coomoBeeo flow (23
(VE(,,)). E(x, P 11 y/1 VEYERR
Proof. By direct calculation and the p-convexity of f.
-
-(=" x²))
-VVf(z) Vf(="), -( 2f y xx")
-Vf((z) V/(="),---))) 2 [|| x'12211
|| vll² 11y--11-1111 + v'y-x"
2 ()(x,x=)== + こー by 11 ~ 1| yl = E(x, + !ー ||= yll?:
2
where the inequality used the convexity of g:
(5 - n. y 20,
Vx,y E Rd and E Ag(v). E 0g(x).
THEOREM E.1 (Convergence rate of AOR-HB method for composite convex minimization). Sup- pose f is j-sstronlyy convex and L-smooth and is non-smooth and convex. Let (Æk, yk) be gen- erated by Algorithm 2 with initial value (Io, yo) and step size a = =V/LL. L. Then there exists non-negative constant Co Col2o, No: pb L) so that we have the accelerated linear convergence
H. 1 flla++ - x012 Co Dy(x,
K21.
(49)
1 V WH/L
Proof. See Appendix
22

---

Published as a conference paper at ICLR 2025
F EQUIVALENT FORMULATION OF AOR-HB-SADDLE
Algorithm is equivalent to the following discretization of the HB-saddle flow (56):
1 Uk Uk
uk+1+
(50a)
a
Pk++1 9k
Pk
ph+t,
(50b)
Uk+1
Uk
uk+1 - uk+1
(2V [(x+1))))))))))
Vf(uk) + BT (k),
(50c)
ax
P
9k+1 1 9k p
qo+1
1
(2Vg(pk+1)
Vg(pa) (2 uk))
(50d)
a
Pg
The discretization mixture implicit Fuler and explicit Fuler with time step size a. For both the gradient terms and Be term, we use the AOR technique, i.e., V = 2V (V - ("x),,
Vg(p) Re gV Vg(ps) and Bv z B(2u++1 - Uz). Algorithm 3 is implementation-frienee friendl
while 50 is convenient for deriving convergence analysis.
G PROOFS OF SECTION
G.1 A CLASS MONOTONE OPERATOR EQUATIONS
In fact, extend HB flow broad class of monotone operator equation A(x) with
A(x) FF + NNx
(51)
where F is strongly convex function and LF smooth, and A is linear and skew-symmetric opera- tor, NT -N. Then A is Lipschitz continuous with constant A S + Therefore . is
monotone and Lipschitz continuous which is also known inverse-strongly monotonicity (Browder
& Petryshyn 1967 Liu & Nashed 1998) or co-coercitivity (Zhu & Marcotte 1996). Consequently has unique solution (Rockafellar 1976).
equation A(x) 2
As special case, we recover
saddle point problems with bilinear
0
B
coupling when x == (u.p) F(x) = f(u) + g()) and N
B
0
We introduce an accelerated gradient flow
x = y I, V = x- - ( + WWy)
(52)
Comparing with the accelerated gradient flow (6) for convex optimization, the difference is the gradient and skew-symmetric splitting A(x) - VF(x) + NNy.
Denote the vector field on the right hand side of 52 by G(z, v). Then G(*",*") = 0 and thus (=",x") is an equilibrium point of (52).
We first show (x" x²" is exponentially stable. Consider the Lyapunov function:
E(x,y) (y(xx*))
H Ily 1=1
(53)
2
For u-strongly convex F, function DF(; E Sy. Then E(x, y) 2 0 and E(x, y) = iff x = x².
We then verify the strong Lyapunov property. The proof is similar to that Lemma
THEOREM G.1 (Strong Lyapunov Property). Assume function F is u-strongly convex. Then for the Lyapunov function (53) and the accelerated gradient flow vector field G asoociated to (52) the following strong Lyapunov property holds
-VE(x,)) v) g(x, y) 2 E(x. v) + 1 111 2113, VAYyEV.
(54)
23

---

Published as a conference paper at ICLR 2025
Proof. First of all, G(x x²)) 0,
-VV y), (z. v)) = - -VVE(E,)) - ,,"),")))
Direct computation gives
-(VE(z, (C(2,,),,gt (z, (VD ply - x², I - x²)
+ully [
x², ,Nu x²
(VF(2)
ply x² x²),
where we have used VDr(z, x²) = VF(x) - VF(x") and (y - x², Noy - -x")) = 0 since .N' is
skew-symmetric. We expand the last two term using the identity of squares:
2 11 x" 1|2 -")
x||
10 x" x²11?.
Using the bound (30a), we get
(v) -
x²) = Dr((x,²) + (p(x", Dr(x,x") + 211e - ==21
2
and obtain 14)_
The calculation is more clear when FF(x) Ax is linear with A v2F 2 pl. We denote by (I. and Ez)) 2/112 2" 11 with D
A
nz Then - -(VE v), ()x, xx)")x)))
0
is quadratic form (z =z'TT((< - z²). We calculate the matrix . as
A 0
-1
A (-wA+
A μI μ +N)
1+
ul
-I+
As U Mu T sym(M) where sym(-) is the symmetric part of matrix, direct computation gives
A
-AAN
A
-w1/2
sym
-pl
pl N A
-ul/2
ul
A/2
1
ul
-pl
0
pl
2
ul
ul
where in the last step we use the convexity A 2 pl. Then (54) follows.
G.2 EXPONENTIAL STABILITY OF HB-SADDLE FLOW
Return to the saddle point problems, we let z (xr,)) T with x (u,p) T , =vv.0) and denote by
E ERm T
0
BT
D2 = (vg
0
F(x) = f(u) + g(p), N=
-B 0
Ng
Consider the Lyapunov function
E(z) = (...))))) = DF(x, x²) )++ + 2/2 l1y - xx =²,1,,
(55)
= =Dy u²) + (p.r" pp) + 14 || - u²122
11--"11 + 14g l1q - p=11?,
2
2
As f.g g are strongly convex, E(z) 2 and Ezz) = iff u = v = u² and = q = p", Recall that the HB-saddle flow is
u' u,
p' P.
d' = u - V (Vf(u) + +B BT q).
(56)
Hf
1
d' -= p q (Vg(p) Bu).
Ng
Denoted the vector field on the right hand side of (56) by G(u, v, p. q). as a special case of Theorem G.1 obtain the following strong Lyapunov property.
24

---

Published as a conference paper at ICLR 2025
THEOREM G.2 (Strong Lyapunov property for HB HB-saddle flow). Suppose f is puy-strongly convex g is Ag -stonggy convex. The following strong Lyapunov property holds for all u, v E IR"', .P. q E RR.
- (VE(u, v.p. 9) G(u, u, u. 4)) 2 E(u, v. p. 9) + 1
2 1lu u112 + Pg 114 pll..
(57)
2
Consequently, for solutions (u(t), ut), p(t, (t)) of the HB-saddle flow (25 we have the exponen- tial stability:
((), D Do(p.'')=
H1 ||0 u112 Mg 11 p" p²11 S S (((((((() (0)),
t> 0.
2
G.3 PROOF OF THEOREM
Consider the modified Lyapunov function
8 2 = Ez) + a (VF(FF)) (x) - VF((=))))))))))))) ).y x²) -ally - B B
(58)
where Ez) is defined as 55 and B = (0 BT
B 0 Due to the bilinear coupling, additional
cross term ax y yn Brom 2a(B(v v²),9 9²) is included in E".
We shall split & Ill - x" 11 to f x² l/., +
- |y x=1
l to bound the two cross terms. The
cross term a(V Fx)) (F(x"),y- x") can be bounded using the vector form of Lemma Next
we focus on the ally - y" B
p
0 with P. > 0 and Beym
0
B
LEMMA G.1. Denoted by Dj =
For
/gg
B
0
any a C > O, we have
B (1- (1-G119
a||BI||
cD S cD 1 abyy
1+
cD Hu-
(59)
c/Pps
Proof. We first calculate the eigenvalues of Dj its eigenvalue is given by the 2 2 matrix 0 M (B)
Baym.
By choosing the SVD basis of B = UEV,
" "y (B)
where oBB) is a singular value
of B. So A(D;, (Bym) = + o(B) and consequently VKTHE
|BI
|B|
Amiu (D.-1 (Bemm
< Amax 1D=1Byyy S
(60)
VP
VPrflgg
Then write cDp + aB = DDD + B and apply the bound 66 to get the desired result.
LEMMA G.2. Suppose f Rm + IR is stronnlyy convex and L-mmoothh 9 R"
R is
Hg strongly convex and smooth. Let F(z) = f(u) + g(p). For any 3 E (0,1), 1). denoted by
{ {V min
Vp = min
mp=min
Mg Lg
(1 3)
L
B
Then for any a > 0 and & defined by 555 and any two vectors Zk, Ze+1 (2)++))
1- a {t)
D De(ZE, 2k+1)
< DE(us, 2k+1) + a(yk+1 uk. VF(* -F((x)) + a:llv 1111l
(61)
1 (1+ (1+// a vp)
DE(ZE, 2x+1).
In particular, for a S Vps we have the bound
0 (2) S (2(2)
2d
(62)
25

---

Published as a conference paper at ICLR 2025
Proof. For any B (0, 1), using the vector form of Lemma C.2
we have bound
vPF )
(D((E, vk+1) B
Ilax - ye+ 1lb,
(F 2
gllv - v2+1ll8, aauuut - Uk: VF(xx+1) VF((a))
(63)
1 a
vpF )
(To(,,,04111 3 Ilvx - uktillb,)
with pF = 3 min
MC. Fx Ley 5.
Use Lemma G.I we have the bound (1 [
B1I
1- B
1 1- 11y yk++1 11. + aalyy
yy
Vk++1
1l. 5
-/k 1l
(1 /uspo
2
2a B||
Σ +
luvk vk+1ll0,
(1 - /)
2
(64)
Adding 63 and 64 implies 61
Apply 61 with Z₁: z and Zk+1 zz to get (62)
In Lemma G.2
the optimal 8 such that
3 min {
14g
Pg
v
= (1 - (1)
Ly
V Lg
BBI
gives the largest step size
min / L5 V
No.
2
4u ut ||
min {V
H4 Lea
a² =
La
min (1 L
Hg
2y/py 233
Lg
2
min
{ (v
Mr
Px La
4prp B
min
Mx La
Lg
L
[B|
alternative simple choice check the order of convergence rate is to set B =3 3 2/2 and the consequent step size is
a v (V2 1) min
{
Pf
Pg
/PfPa
Lg
BB|
Now we are ready to prove the theorem.
Proof of Theorem
1.2 We write (50p as a correction of the implicit Euler method
0 D.-
0 1) (zu+1 zz) (D; (0..:aymmuu. - vn)) (65)
Zk+1 2x ag(zz
Use the definition of Bregman divergence, we have the identity for the difference of the Lyapunov function & at consecutive steps:
E(z++1) E(zx) (VE(Z++1), 2x) De(zk, 2k+1)
26

---

Published as a conference paper at ICLR 2025
Substitute (65
and expand the cross term:
(VE 2--1 k4) = ((x++1))))))))
a (VF(I=++)) (x²)), yk+1 yk) alyk++1 -x', x², VF(x++1) V (66)
a (3 y", g1++1 yk) 1oym
We split the gradient term as
a (VF(4t)+1) FF(x"); yk+1 yk) a(yx+1 x², VF(**+1) - VF((k))
= a (V - FF(x") Uk+1 - xx>> + afuct11 - yk, VF((x+1) - VF((x))
ayyk x. (F(()) VVFx"))))(x))
We can use identity of squares to expand
(yK+1 - 9" Mo+11 yk) Borm Borm
(11y++1 y" Ils -11++11 yk I
11ya
8n 811l (18em)))
Substitute back to (88) and rearrange terms, obtain the following identity:
Ed (z(++))) - Ed (zx) a aVVE(2e+)) ((zx+1))
(67)
Dee(Ze 21+1) + a(yu+1 1 Ma, VF(=++1) VF(xx)) - ox/lyx Mh++ 1
which holds for arbitrary step size a.
Now take < vp. The last term in 67 is non-positive. Use the strong Lyapunov property, and the bound -dh (z) S (z) to get
(7(4++1) (2,) - -0E(24+1) S - a cd(
(68)
2
which implies the global linear convergence:
A+1
1 8 (Z641)) S 1 a//2
(2x)) 1
{d(2) k 0.
Moreover, (68) implies
1 33 (zx 0d (2x+11) 5 a
1 [a((z) S 1/1 (1+a/2)
) (Z(Z)),
E(zx+1) S which coincides with
a
( with Co 8d 2 0.
H AOR-HB-SADDLES ALGORITHM AND CONVERGENCE ANALYSIS
We propose the AOR-HB -OR-HB-saddlee- algorithm in the following Algorithm Consider the modified Lyapunov function
0d (z) = E(z) a (V(()) - VF(x"), x²),
(69)
The following theorem show the convergence rate of AOR-HBB-saddle-I method. THEOREM H.1 (Convergence of A method). Suppose is stroongy conver and T-g-smooth, g pg-strongly convex and smy-shooth and let /p = min { Li Lg Let (ug, Ve, Pky qs) be generated by Algorithm with initial value (wo, Co, Po: 90) and step size a = vp. Then there exists a non-negative constant Co Coluo, vo, po, go, p&g, , Lss , Hgg Lg) that have the linear convergence
Dy(Me41, u²) + D2 (p p²)+ M$ |luu+1 x0 111 Mg 1h++1 11- =
1
1
(70)
27

---

Published as a conference paper at ICLR 2025
Algorithm 4 AOR-HBB-saddle- Algorithm
1: Parameters: ug: Uy
IR
Pu. qu E IR" y. L Mg B
2: Set min
Mr
Do
L
Lig
3: for k 0, 0,
do
1
1
4: uk+1 1+a
(u
av:):
Pk+1
(px aqqs)
1+a
5: Find (Uk+1: 9k+11) such that
(2V (2V Vf((u)) B au+1))
uk+1 + a
2k + +0u++1
a
(2Vg(Px+1) Vg(ps) Bun+t)
4k+1 + a
Uss opp+1
Pa
6: end for
7:
return Uk+1, Uk+ Pk-+1 1
Proof. AOR-HB-saddle-1 can be written as correction of the implicit Euler method
O
!)
Zk+1
(2(+++1)
VF
(Zx++1 Zz).
(71)
The proof follows the proof of Theorem I.] in Appendix @with f=P F.
28


Reviews:
[{"review_id": "mARSjeDXnH", "reviewer": "Reviewer_1fRV", "summary": "This paper proposes a variant of the classical heavy-ball method, where the key modification involves replacing $\\nabla f(x_k)$ with its over-relaxation $2 \\nabla f(x_k) - \\nabla f(x_{k-1})$. It can be regarded as a discretization of the rotated gradient flow introduced by (Chen & Luo, 2021). By employing a Lyapunov function, the authors prove that the proposed method achieves the optimal linear convergence rate for smooth strongly convex minimization problems. They further extended their results to the composite setting and strongly-convex-strongly-concave saddle point problems with bilinear coupling.", "questions": "- It appears that the proposed method resembles the accelerated method proposed by Thekumparampil et al. (2022), albeit from a different perspective. Specifically, they presented an accelerated method for strongly convex minimization problems in equation (11). If the variable $x_k$ is eliminated, the resulting update rule resembles \n$$x_{k+1} = x_k - \\gamma (\\nabla f(x_k) - \\theta \\nabla f(x_{k-1}))+ \\beta (x_k - x_{k-1}),$$\nwhere $\\gamma,\\theta,\\beta$ are some constants. A detailed comparison will be helpful. \n\n-The notation of $\\mathbf{x} = (x,y)^\\top$ could be confusing. I suggest the authors use a different symbol, such as $\\mathbf{z}$, to represent the concatenation of $x$ and $y$.\n\n---- \nThekumparampil, Kiran K., Niao He, and Sewoong Oh. \"Lifted primal-dual method for bilinearly coupled smooth minimax optimization.\" AISTATS 2022.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- It is known that the classical heavy-ball method cannot achieve the accelerated rate for general smooth strongly-convex optimization problems. The contribution of this paper is to show that, with a simple modification, a heavy-ball-like method can indeed achieve acceleration. \n- The proof technique is conceptually simpler than the standard approach used in accelerated gradient methods, such as the estimate sequence. Furthermore, this technique is adaptable to more general settings, as evidenced by the extensions provided in the paper.", "weaknesses": "- The main drawback is that other acceleration methods, such as Nesterov's accelerated gradient (NAG) and its extensions, are known to achieve similar convergence guarantees in the considered settings. As such, the advantage of the proposed algorithm over these existing methods remains unclear. This is further illustrated in the numerical experiments, where the proposed method exhibits comparable performance to NAG. Therefore, I have reservations about referring to the result as a \"breakthrough.\" \n- Another limitation is that the paper focuses solely on the strongly convex setting. It is unclear if an accelerated rate can also be achieved in the more general convex setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Y858FHtYB", "reviewer": "Reviewer_YQdx", "summary": "This paper proposes a variant of heavy-ball momentum acceleration that provably achieves the optimal linear convergence rate with the factor of $\\sqrt{\\kappa}$ for smooth strongly convex functions, amending the previous heavy-ball momentum method that does not accelerate in this setting. The proposed framework is further extended to composite optimization and saddle point optimization. Numerical results are provided to validate the theory.", "questions": "1. How are the convergence rate and practical performance of AOR-HB for non-strongly convex functions? Does the proposed modification also achieve the optimal $O(1/T^2)$ rate or is the method limited to strongly convex functions?\n2. In Figure 2, the HB method also achieves fast linear convergence, faster than all the other methods. Why is it the case and wouldn't this weaken the motivation of the paper? Are there more empirical evidence to demonstrate the contrast between HB and AOR-HB in terms of optimizing strongly convex functions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The proposed method improves heavy-ball momentum, a well-known and widely applied method, to achieve acceleration for strongly convex functions.\n2. Comprehensive extensions to composite optimization and saddle point optimization are also included.", "weaknesses": "1. The paper can be further improved if the authors could include some more intuitive discussion on why the over-relaxation is applied to approximate the gradient in line 110.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uwZfmiRmva", "reviewer": "Reviewer_C9is", "summary": "The paper introduces Accelerated Over-Relaxation Heavy-Ball method which can converge at an accelerated rate for strongly-convex objective functions.", "questions": "Nesterov Acceleration (NAG) can be defined as $v_k = w_k + \\beta (w_k - w_{k-1})$ and $w_{k+1} = v_k - \\gamma \\nabla f (v_k)$. We can eliminate term $w_k$ and achieve\n$$\nv_{k+1} = v_k - \\gamma \\nabla f (v_k) + \\beta (v_k - v_{k-1}) - \\gamma \\beta [ \\nabla f (v_k) - \\nabla f (v_{k-1})] \n$$\n$$\nv_{k+1} = v_k - \\gamma \\beta [ (1 + \\frac{1}{\\beta}) \\nabla f (v_k) - \\nabla f (v_{k-1})] + \\beta (v_k - v_{k-1})\n$$\nSo the only difference if 1 versus $\\frac{1}{\\beta}$ (where $\\beta$ is close to 1) as I understand, can you elaborate more on the differences between these two methods and when will AOR-HB is more prefer compare to NAG. In fig 1 and 2 the empirical performance of AOR-HB and NAG are also very similar.\n\nminor: line 373 typo double \"that\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors provide proofs for the convergence of their AOR-HB method for smooth, strongly-convex objective function. The method is also proved to achieve convergence for a class of non-smooth optimization and min-max problems.", "weaknesses": "The AOR-HB method is very similar to Nesterov Acceleration (details in questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8Wz3ulkJnQ", "reviewer": "Reviewer_XLjC", "summary": "This paper proposes a new momentum method AOR-HB. This method is motivated by discretizing an related ODE using over-relaxation. AOR-HB has accelerated rates compared to HB, and it is further extended to proximal and mini-max problems. Numerical results are provided.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Compared to HB, the proposed approach achieves accelerated rates. \n\n2. The design of ODEs and discretizing can be useful.", "weaknesses": "1. The constant $C_0$ in theorem 1.1 still depends on $\\kappa$, which implies that this approach remains slower than Nesterov's momentum. The author should make this dependence clear.\n\n2. Extensions to convex and stochastic problems are less straightforward.\n\n3. The proposed approach only outperforms HB in numerical results. This indicates that it is not the most efficient momentum methods from a practical standpoint.\n\nIn sum, while the theoretical finding are impressive, the resultant approach occupies a ‘mid-point’ between momentum methods both theoretically and empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)