Accelerated Over-Relaxation Heavy-Ball Methods with Provable Acceleration and Global Convergence

The heavy-ball momentum method has gained widespread popularity for accelerating gradient descent by incorporating a momentum term. Recent studies have conclusively shown that the heavy-ball method cannot achieve an accelerated convergence rate for general smooth strongly convex optimization problems. This work introduces the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, a novel approach that represents the first heavy-ball method to demonstrate provable global and accelerated convergence for smooth strongly convex optimization. The key innovation of the AOR-HB method lies in the application of an over-relaxation technique to the gradient term. This novel approach enables the method to be applied to min-max problems and meet optimal lower complexity bounds. This breakthrough addresses a long-standing theoretical gap in heavy-ball momentum methods and paves the way for developing accelerated methods that transcend the boundaries of convex optimization to non-convex optimization. Numerical experiments validate the effectiveness of the proposed algorithms, with their performance matching that of other leading first-order optimization methods.