Department of Mathematics - Seminar on Applied Mathematics - 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. We first revisit the acceleration phenomenon through A-stability theory for ODE solvers, explaining it by transforming the spectrum to the complex plane. We present the heavy-ball flow as an example of this transformation. Additionally, we introduce the Lyapunov framework for dynamical systems and the strong Lyapunov condition. We then introduce the Accelerated Over-Relaxation Heavy-Ball (AOR-HB) method, a novel approach that is 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 applying an overrelaxation technique to the gradient term. This novel approach enables the method to be applied to min-max problems and meet optimal lower complexity bounds. We extend the acceleration to a class of non-linear saddle point problems, presenting an accelerated transformed primal-dual (ATPD) method for saddle point systems and accelerated gradient and skew-symmetric splitting (AGSS) methods for a broader class of monotone operator equations. Numerical experiments validate the effectiveness of the proposed algorithms, with their performance matching that of other leading first-order optimization methods. This is joint work with my Ph.D student Jingrong Wei.