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.

講者/ 表演者:
Prof. Long CHEN
University of California, Irvine
語言
英文
適合對象
教職員
公眾
研究生
本科生
主辦單位
數學系
新增活動
請各校內團體將活動發布至大學活動日曆。