Understanding the acceleration phenomenon via high-resolution differential equations

By Bin Shi, Simon Shaolei Du, Michael I. Jordan, Weijie Su. Mathematical programming, 2018

336 citations recorded by the source corpus.

Gradient-based optimization algorithms can be studied from the perspective of limiting ordinary differential equations (ODEs). Motivated by the fact that existing ODEs do not distinguish 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 alternative 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, uncovering 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.

Subfields: Computational Mechanics, Mathematical Physics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/d2ac83e42dca7879d55d2518a5430394fea1d8ff

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Numerical Analysis

Citations in the corpus

Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping (2021, background): “Due to the remarkable properties induced by the presence of the Hessiandriven damping, these inertial dynamics and algorithms have been the subject of active recent developments; see the work of [4] on a high resolution perspective, that of [5] for application to deep learning, the papers of [6,7] f”
Fast optimization via inertial dynamics with closed-loop damping (2020, methodology): “Time rescaling is a powerful tool to accelerate the inertial systems; see Attouch–Chbani– Riahi [24], Shi–Du–Jordan–Su [80] and references therein.”