Accepted

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

Jingrong Wei and Long Chen

ICLR, 2025

arXiv   Bibtex

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.