Nesterov accelerated gradient method

For a differentiable convex function $f$ on a Euclidean space with $L$-Lipschitz gradient, $L>0$, one form of the Nesterov accelerated gradient method usesstarting with $x_{-1}=x_0$. The first extrapolation is zero. Each later step uses the previous displacement to form an extrapolated point $y_k$, then evaluates the gradient there.^[ref]

If a global minimizer $x_{\ast }$ exists with $\Vert x_0-x_{\ast }\Vert \le R$, the objective error is $O(L{R}^2/k^2)$. Reaching error $\delta >0$ therefore takes $O(\sqrt{L{R}^2/\delta })$ iterations. The parameter schedule and convex smoothness hypotheses are part of that guarantee.

The same extrapolation can be combined with a proximal gradient method step to handle an additional nonsmooth convex term.