A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
This work provides theoretical insights into optimization algorithms, but it is incremental as it builds on existing Nesterov's method without introducing a fundamentally new paradigm.
The authors derived a second-order ordinary differential equation (ODE) as the continuous-time limit of Nesterov's accelerated gradient method to analyze and understand the scheme better, leading to a family of similar algorithms and a restarted version with proven linear convergence for strongly convex objectives.
We derive a second-order ordinary differential equation (ODE) which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.