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

Authors: Jingrong Wei, Long Chen
Primary area: optimization
Keywords: Optimization theory, heavy ball, momentum, acceleration, composite optimization, min-max, saddle point problem

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729717038619

thread_type:
official_review

<thread_object>
creator: reviewer_xljc

<content>
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.

strengths:
1. Compared to HB, the proposed approach achieves accelerated rates. 

2. 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.

2. Extensions to convex and stochastic problems are less straightforward.

3. The proposed approach only outperforms HB in numerical results. This indicates that it is not the most efficient momentum methods from a practical standpoint.

In sum, while the theoretical finding are impressive, the resultant approach occupies a ‘mid-point’ between momentum methods both theoretically and empirically.

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619260061

thread_type:
official_review

<thread_object>
creator: reviewer_c9is

<content>
summary:
The paper introduces Accelerated Over-Relaxation Heavy-Ball method which can converge at an accelerated rate for strongly-convex objective functions.

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).

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
$$
v_{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})] 
$$
$$
v_{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})
$$
So 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.

minor: line 373 typo double "that"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730651793130

thread_type:
official_review

<thread_object>
creator: reviewer_yqdx

<content>
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.

strengths:
1. The proposed method improves heavy-ball momentum, a well-known and widely applied method, to achieve acceleration for strongly convex functions.
2. 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.

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?
2. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730869674014

thread_type:
official_review

<thread_object>
creator: reviewer_1frv

<content>
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.

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. 
- 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." 
- 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.

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 
$$x_{k+1} = x_k - \gamma (\nabla f(x_k) - \theta \nabla f(x_{k-1}))+ \beta (x_k - x_{k-1}),$$
where $\gamma,\theta,\beta$ are some constants. A detailed comparison will be helpful. 

-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$.

---- 
Thekumparampil, Kiran K., Niao He, and Sewoong Oh. "Lifted primal-dual method for bilinearly coupled smooth minimax optimization." AISTATS 2022.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731981443943

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Rebuttal

comment:
We thank all the reviewers for carefully reading our work. We appreciate your insightful questions and constructive feedback. The manuscript has been revised to address these comments. To meet the page limit, we have slightly shortened the abstract.  

----

## Two primary concerns

The two primary concerns are 1) the advantages of AOR-HB over existing acceleration methods and 2) its extension to the convex case. Below, we provide a detailed response to these concerns.


---

**The advantage of the proposed algorithm compared to existing methods, particularly the Nesterov Accelerated Gradient (NAG) method**

For strongly convex optimization, acceleration can be viewed from various perspectives. AOR-HB can be interpreted as a parameter perturbation of NAG method, as noted by reviewer C9is. The convergence and performance of AOR-HB are thus comparable to those of NAG, though less precise than the triple momentum (TM) methods in the case of strongly convex optimization.

However, extending methods like NAG, TM, or high-resolution ODEs beyond convex optimization remains both rare and challenging. In contrast, AOR-HB demonstrates **superior generalization capability** as the true driving force of acceleration is through the $2 \times 2$ first-order ODE model. 

We give a unified framework for convex optimization, saddle-point problems, and monotone operator equations, represented as:  
$$\begin{bmatrix}  x'\\\  y'  \end{bmatrix}  =  \begin{bmatrix}    - I &  I \\\    I - \mu^{-1} A & - I - \mu^{-1} N  \end{bmatrix}  \begin{bmatrix}  x\\\  y  \end{bmatrix}.$$
- *Strongly convex optimization*: $A(x) = \nabla f(x), \ N = 0$. 
- *Composite convex optimization:* $A(x) = \nabla f(x), \  N(y) = \partial g(y)$.  
- *Saddle-point problem with bilinear coupling:*
  $A(x) = \begin{bmatrix}\nabla f(u) & 0 \\\ 0 & \nabla g(p)\end{bmatrix}, \ N = \begin{bmatrix}0 & B^{\top} \\\ B & 0 \end{bmatrix}$.  
- *Monotone operators*: $A(x) = \nabla F(x), \ N$ is linear and skew-symmetric.

Simplicity in design enables extension to broader problems, while methods like NAG, TM, and high-resolution ODEs are tailored for convex objectives, limiting their flexibility. For example, adapting Nesterov’s method to composite problems requires significant effort.

For saddle-point problems, our AOR-HB-saddle achieves accuracy in fewer iterations compared to other algorithms. Its single-loop structure and minimal parameter tuning also enhance practicality and ease of implementation.

In summary, **the primary strength of our approach lies in its generalization capability.** 


---

**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.**

Our approach extends to the non-strongly convex setting ($\mu = 0$) using the dynamic scaling technique introduced by Luo & Chen (2022). The resulting algorithm is:  
$$
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}),  
$$
which achieves an accelerated rate of $\mathcal{O}(1/k^2)$, comparable to NAG. Another approach involves using the perturbation form $f(x) + \frac{\epsilon}{2}\|x\|^2$, as discussed in Lessard et al. (2016, Section 5.4).  

The perturbation approach also extends to composite convex optimization and saddle-point problems. However, due to page limits, we focused on the simplest case to present the core ideas clearly.  

We have added a remark in the revision, immediately after Theorem 1.1 and Appendix D for the detailed proof.





---

## Major Improvement  

Theorem 1.2 has been modified to allow a larger step size for AOR-HB-saddle which further speeds up the convergence of our new methods.

We are grateful to Reviewer 1fRV for highlighting the lifted primal-dual (LPD) method proposed by Thekumparampil et al. (2022), which is tailored for min-max problems with bilinear coupling. With Thekumparampil’s help, we have included the LPD in our numerical comparisons. See the updated Figures 5 and 6. Our conclusion remains unchanged: "our AOR-HB-saddle methods consistently exhibit faster linear convergence compared to other algorithms."  

---

**Reference**
- Long Chen and Hao Luo. A unified convergence analysis of first order convex optimization methods via strong Lyapunov functions. *arXiv preprint arXiv:2108.00132*, 4(9):10, 2021.
- Hao Luo and Long Chen. From differential equation solvers to accelerated first-order methods for convex optimization. *Mathematical Programming*, 195(1):735–781, 2022.
- Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algorithms via integral quadratic constraints. *SIAM Journal on Optimization*, 26(1):57–95, 2016.
- Thekumparampil, Kiran K., Niao He, and Sewoong Oh. *Lifted primal-dual method for bilinearly coupled smooth minimax optimization.* International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732776261157

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
New contribution compare to Chen and Luo's approach

comment:
Reviewer 1fRV raised a follow-up question, and we believe it is important to include our response in the global rebuttal section to clarify our new contribution. This clarification has also been incorporated into the revised manuscript.

*The main machinery used in this paper, including the rotated gradient flow and strong Lyapunov property, has been previously introduced to design accelerated methods (Chen & Luo, 2021; Luo & Chen, 2022). Could the author briefly comment on what sets this paper apart from these prior works?*

Yes, while the algorithmic design and convergence analysis in this work follow the framework of the rotated gradient flow (for algorithm design) and strong Lyapunov property (for convergence analysis), our paper introduces significant contributions that set it apart from prior works. 


**Continuous Level**

In the framework of Chen and Luo, the rotated gradient flow is represented as:  
$$
\begin{bmatrix}  - I & \quad I \\\ 
I - \mu^{-1} \nabla f & \quad - I  
\end{bmatrix}.
$$
In contrast, our work introduces an additional term, resulting in the flow:  
$$
\begin{bmatrix}  - I & \quad I \\\ 
I - \mu^{-1} \nabla f & \quad - I   - \mu^{-1} N
\end{bmatrix}.
$$
The key contribution lies in the introduction of the $N$ term. Importantly, the strong Lyapunov property still holds for a broad class of $N$, significantly enhancing the generalization capability of the method.

For example, in composite convex optimization, the comparison is as follows:  
$$
\begin{bmatrix}  - I & \quad I \\\  
I - \mu^{-1} (\nabla f + \partial g) & \quad - I  
\end{bmatrix}  
\quad \text{vs.} \quad  
\begin{bmatrix}  - I & \quad I \\\  
I - \mu^{-1} \nabla f & \quad - I - \mu^{-1} \partial g  
\end{bmatrix}.
$$
More importantly, by selecting $N(x) = \begin{pmatrix} 0 & B^{\top} \\\ B & 0 \end{pmatrix}$, our approach extends to the min-max problem, which the original rotated gradient flow cannot handle.


**Discrete Level**

On the discrete level, we introduce the AOR (Accelerated Over-Relaxation) technique to approximate the gradient term as:   $$\nabla f(x) \approx 2\nabla f(x_{k+1}) - \nabla f(x_k),$$ 
whereas Chen and Luo use a simpler discretization, $\nabla f(x) \approx \nabla f(x_{k+1})$, and require an additional gradient step or carefully designed extrapolation scheme to achieve acceleration.

The AOR discretization is more faithful to the structure of the continuous flow. This fidelity not only simplifies convergence analysis but also significantly enhances generalization capabilities. For instance, beyond gradient terms, AOR can also be applied to bilinear couplings, such as   $$Bv \approx B (2v_{k+1} - v_k),$$  

resulting in accelerated first-order methods for min-max problems with bilinear coupling.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes an overrelaxation method, which effectively replaces $\nabla f(x_k)$ with $2\nabla f(x_k) - \nabla f(x_{k-1})$ to "fix" the convergence of the heavy-ball method in smooth strongly convex minimization methods. Namely, while the heavy ball is known to converge for strongly convex quadratics, it is also known to not converge in the worst case for smooth strongly convex minimization problems. The paper proves that the aforementioned strategy suffices to "fix" this issue for smooth strongly convex minimization. It further shows that the same strategy can be used to address convex composite problems and strongly convex-strongly concave min-max optimization problems. The main strengths of the paper lie in the elegance of the provided analysis and in the ability to apply the same approach to multiple settings. For this reason, I believe the paper would be a good addition to the conference.

I have some additional comments for the authors. What the authors call "over relaxation" is a special case of the "operator extrapolation" broadly used in the variational inequalities literature. The operator extrapolation boils down to replacing $F(x_k)$ with $F(x_k) + \theta (F(x_k) - F(x_{k-1})),$ which is the same as the "over relaxation" when $\theta = 1$ (and is, indeed, perhaps the most common choice). The paper does not cite this literature and I believe the authors may not be aware of this connection. The earliest reference is the method of Popov from 1980 when applied to unconstrained problems. It was rediscovered as the "optimistic method" or "optimistic mirror descent" in the more recent literature, starting with Daskalakis et al., 2017. The same idea appears in a paper by Kotsalis, Lan, and Li in SIOPT 2022 (which the authors should consult also in light of questions regarding stochastic settings). It was further used to obtain convergence results for cyclic methods in a line of work starting with Song and Diakonikolas, SIOPT 2023. 

While the algorithms and the results in the current paper are not the same as the results from the above line of work, the "operator extrapolation" idea is so closely related that there ought to be a detailed discussion of this line of work and an appropriate comparison to it.