Nesterov's gradient acceleration

Definition

Nesterov's gradient acceleration refers to a general approach that can be used to modify a gradient descent-type method to improve its initial convergence.

The two-step iteration description

In this description, there are two intertwined sequences of iterates that constitute our guesses:

${\overrightarrow{x}}^{(0)},{\overrightarrow{x}}^{(1)},{\overrightarrow{x}}^{(2)},\dots$

${\overrightarrow{y}}^{(0)},{\overrightarrow{y}}^{(1)},{\overrightarrow{y}}^{(2)},\dots$

Explicitly, the sequences are intertwined as follows:

${\overrightarrow{x}}^{(0)},{\overrightarrow{y}}^{(0)},{\overrightarrow{x}}^{(1)},{\overrightarrow{y}}^{(1)},{\overrightarrow{x}}^{(2)},{\overrightarrow{y}}^{(2)},\dots$

We use parenthesized superscripts to denote the iteration stage, because the subscripts are reserved for use by the coordinates.

For the initialization, we set:

${\overrightarrow{x}}^{(0)}={\overrightarrow{y}}^{(0)}=\text{Initial guess}$

The two-step iteration is as follows:

• ${\overrightarrow{x}}^{(k+1)}=\text{Gradient descent-type method applied to }{\overrightarrow{y}}^{(k)}$
• ${\overrightarrow{y}}^{(k+1)}={\overrightarrow{x}}^{(k+1)}+m^{(k+1)}({\overrightarrow{x}}^{(k+1)}-{\overrightarrow{x}}^{(k)})$

Note that the sign on the right side is not a typographical error: ${\overrightarrow{y}}^{(k+1)}$ is a non-convex combination of ${\overrightarrow{x}}^{(k)}$ and ${\overrightarrow{x}}^{(k+1)}$. The value $m^{(k+1)}$ is a member of a predetermined sequence of real numbers in the interval $[0,1)$ that is independent of the specific problem. A typical expression is $m^{(k)}=(k-1)/(k+2)$ (so $m^{(k+1)}=k/(k+3)$).