Nesterov accelerated gradient

Let $d\ge 1$ be an integer and let $F:{\mathbb{R}}^d\to \mathbb{R}$ be continuously Fréchet differentiable: at every $w$, $DF(w)$ is a linear first-order approximation with normwise remainder tending to zero, and $w\mapsto DF(w)$ is continuous. Write its coordinate gradient as $\mathrm{\nabla }F(w)=({\mathrm{\partial }}_{j}F(w){)}_{0\le j<d}$. Given an initial vector $w_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\in {\mathbb{R}}^d$, an integer horizon $T\ge 1$, and prescribed real parameter sequences $({\alpha }_t{)}_{1\le t<T}$ with ${\alpha }_t>0$ and $({\beta }_t{)}_{1\le t<T}$, initialize $w_0=w_1=w_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}$. For each integer $t=1,\dots ,T-1$, first set the look-ahead point

${\tilde{w}}_t:=w_t+{\beta }_t(w_t-w_{t-1}),$

then set

$w_{t+1}:={\tilde{w}}_t-{\alpha }_t\mathrm{\nabla }F({\tilde{w}}_t)\mathrm{.}$

Output $(w_0,w_1,\dots ,w_T)$. The gradient is evaluated after the look-ahead displacement. When ${\beta }_t=0$, that update is the fixed-step gradient-descent update at $w_t$ with step size ${\alpha }_t$.

Gradient descent

The total (Fréchet) derivative $Df(a)$ as the linear first-order approximation with $o(\mathrm{\parallel }h{\mathrm{\parallel }}_2)$ remainder

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case