Timezone: »

A Differential Equation for Modeling Nesterov’s Accelerated Gradient Method: Theory and Insights
Weijie Su · Stephen Boyd · Emmanuel Candes

Tue Dec 09 07:10 AM -- 07:30 AM (PST) @ Level 2, room 210

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.

Author Information

Weijie Su (Stanford University)
Stephen Boyd (Stanford University)
Emmanuel Candes (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors