Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization
Optimization theory;heavy ball;momentum;acceleration;composite optimization;min-max;saddle point problem
Yes
No ethics review needed.
- 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.
- 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.
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.
- 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.
Yes
No ethics review needed.
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?
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.
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.
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.
Yes
No ethics review needed.
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"
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.
The paper introduces Accelerated Over-Relaxation Heavy-Ball method which can converge at an accelerated rate for strongly-convex objective functions.
The AOR-HB method is very similar to Nesterov Acceleration (details in questions).
Yes
No ethics review needed.
See above.
1. Compared to HB, the proposed approach achieves accelerated rates. 

2. The design of ODEs and discretizing can be useful.
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.
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.
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.
@inproceedings{
anonymous2024accelerated,
title={Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=SWEqzy7IQB},
note={under review}
}
The heavy-ball momentum method is widely used to accelerate gradient descent by incorporating a momentum term. However, recent studies have shown it cannot achieve accelerated convergence for general smooth strongly convex problems. This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, the first heavy-ball variant with provable global and accelerated convergence for smooth strongly convex optimization. This breakthrough closes a long-standing theoretical gap and extends to composite convex optimization and min-max problems, achieving optimal complexity bounds and demonstrating broad generalization. The AOR-HB approach offers several advantages: (1) Generality: It applies to a wider range of optimization problems, (2) Impact: It introduces techniques that may reshape understanding of acceleration, and (3) Elegance: It is conceptually clearer and more intuitive than existing accelerated methods.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Optimization theory heavy ball momentum acceleration composite optimization min-max saddle point problem
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/433b33a691fea8d35c81786763aca513eb10239f.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission