= Nesterov accelerated gradient method
{c}
For a differentiable <convex function> $f$ on a <Euclidean space> with $L$-<Lipschitz gradient>, $L>0$, one form of the <Nesterov accelerated gradient method> uses
$$
\omega_k=\frac{k}{k+3},\qquad y_k=x_k+\omega_k(x_k-x_{k-1}),\qquad x_{k+1}=y_k-L^{-1}\nabla f(y_k),
$$
starting 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.<Proximal Algorithms by Neal Parikh and Stephen Boyd>[section4.3, extrapolation weight k/(k+3) and accelerated convergence, printed p152, smooth specialization]{ref}
If a <global minimizer> $x_*$ exists with $\|x_0-x_*\|\leq R$, the objective error is $O(LR^2/k^2)$. Reaching error $\delta>0$ therefore takes $O(\sqrt{LR^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.
Back to article page
