A Differential Equation for Modeling Nesterov%26apos;s Accelerated Gradient Method: Theory and Insights

作者：Su Weijie; Boyd Stephen; Candes Emmanuel J

来源：Journal of Machine Learning Research, 2016, 17: 153.

• Nesterov's accelerated scheme
• convex optimization
• first-order methods
• differential equation
• restarting

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.

• 出版日期2016