Department of Mathematics - Seminar on Applied Mathematics - Accelerated Over-Relaxation Heavy-Ball Methods with Provable Acceleration and Global Convergence

10:00am - 11:00am
Room 2463 (Lifts 25/26)

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.

Event Format
Speakers / Performers:
Prof. Long CHEN
University of California, Irvine
Language
English
Recommended For
Faculty and staff
General public
PG students
UG students
Organizer
Department of Mathematics
Post an event
Campus organizations are invited to add their events to the calendar.