Optimization Online


Understanding the Acceleration Phenomenon via High-Resolution Differential Equations

Bin Shi (bshi001***at***cs.fiu.edu)
Simon Du (ssdu***at***cs.cmu.edu)
Michael Jordan (Correspondence) (jordan***at***cs.berkeley.edu)
Weijie Su (Correspondence) (suw***at***wharton.upenn.edu)

Abstract: Gradient-based optimization algorithms can be studied from the perspective of limiting or- dinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distin- guish between two fundamentally different algorithms—Nesterov’s accelerated gradient method for strongly convex functions (NAG-SC) and Polyak’s heavy-ball method—we study an alter- native limiting process that yields high-resolution ODEs. We show that these ODEs permit a general Lyapunov function framework for the analysis of convergence in both continuous and discrete time. We also show that these ODEs are more accurate surrogates for the underlying algorithms; in particular, they not only distinguish between NAG-SC and Polyak’s heavy-ball method, but they allow the identification of a term that we refer to as “gradient correction” that is present in NAG-SC but not in the heavy-ball method and is responsible for the qualitative difference in convergence of the two methods. We also use the high-resolution ODE framework to study Nesterov’s accelerated gradient method for (non-strongly) convex functions, uncover- ing a hitherto unknown result—that NAG-C minimizes the squared gradient norm at an inverse cubic rate. Finally, by modifying the high-resolution ODE of NAG-C, we obtain a family of new optimization methods that are shown to maintain the accelerated convergence rates of NAG-C for smooth convex functions.

Keywords: Convex optimization, first-order method, Polyak’s heavy ball method, Nesterov’s accelerated gradient methods, ordinary differential equation, Lyapunov function, gradient mini- mization, dimensional analysis, phase space representation, numerical stability

Category 1: Global Optimization (Theory )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Nonlinear Optimization (Unconstrained Optimization )


Download: [PDF]

Entry Submitted: 10/21/2018
Entry Accepted: 10/22/2018
Entry Last Modified: 12/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society