Accelerated Gradient Methods: Nesterov Acceleration and FISTA

Intuition Beginner

A plain gradient method is like a cautious hiker: at every step it checks the slope where it stands and takes one careful step downhill. It is safe, but on a long gentle valley it crawls. It forgets, each step, that it has been heading the same way for a while and could afford to build up speed.

Acceleration adds memory. Instead of stepping from where you stand, you first coast a little in the direction you were already moving — you let momentum carry you past your current spot — and only then do you check the slope and correct. A ball rolling downhill does this naturally: it keeps the speed it has gathered, so on a long straight descent it covers ground far faster than a hiker who stops to re-measure at every footfall.

The surprising part is where you measure the slope. You do not measure it at your current point; you measure it at the look-ahead point you reached by coasting. Sampling the slope a step into the future is what keeps the extra speed from overshooting badly — the gradient at the look-ahead point gently steers the momentum before it can run you off course.

The payoff is a different speed class. Halve the error of a plain gradient method and you roughly double the work. With acceleration, halving the error costs only about $1.4$ times the work, because the error shrinks like one over the step count squared rather than one over the step count. This is provably the best any method can do using only slopes — you cannot beat it without extra information about the landscape.

One honest warning: a ball with momentum does not roll smoothly downhill the whole way. It overshoots, swings back, and ripples toward the bottom. Accelerated methods behave the same — the height can rise for a while even though the method is converging faster overall. Progress is real but not step-by-step tidy.

Visual Beginner

Picture two runners descending a long valley. The plain gradient runner re-checks the slope and takes one short step each time. The accelerated runner first coasts ahead using the speed gathered from previous steps, checks the slope at that look-ahead spot, and corrects — covering much more ground per step but rippling a little near the bottom.

   plain gradient (cautious)            accelerated (momentum + look-ahead)

   x_k                                  x_{k-1}
    | small downhill step                  \   remember the last move
    v                                        \  (momentum)
   x_{k+1}                                    v
    | small downhill step               y_k = x_k + (coast ahead)
    v                                        |  measure slope HERE, then step
   x_{k+2}                                   v
    |                                   x_{k+1}   (big progress, may overshoot)
    v
   ... crawls (error ~ 1/k)            ... races (error ~ 1/k^2), ripples near bottom

method	error after k steps	work to halve the error
plain gradient	about $1/k$	roughly double
accelerated (momentum)	about $1/k^2$	about $1.4$ times
best possible with slopes only	$1/k^2$	accelerated already matches it

Worked example Beginner

We race the two methods on a simple bowl, the one-dimensional cost $f(x)=\frac{1}{2}{x}^2$, whose slope at $x$ is just $x$ and whose minimum is at $x=0$. We start at $x_0=1$ and use step size $1$.

Plain gradient. The rule is "new point = old point minus slope." From $x_0=1$ the slope is $1$, so $x_1=1-1=0$. Here the plain method happens to land on the bottom in one step because the bowl is so simple. To make the contrast visible we shrink the step to $\frac{1}{2}$: then $x_1=1-\frac{1}{2}\cdot 1=\frac{1}{2}$, $x_2=\frac{1}{2}-\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$, $x_3=\frac{1}{8}$. The values $1,\frac{1}{2},\frac{1}{4},\frac{1}{8}$ halve each step — steady, geometric crawling.

Accelerated. Now add momentum with step $\frac{1}{2}$. The coast-ahead point is the current point pushed a bit further in the direction of the last move. Start $x_0=x_{-1}=1$ (no previous move yet), so $y_0=1$; slope at $y_0$ is $1$, giving $x_1=1-\frac{1}{2}\cdot 1=\frac{1}{2}$. Now there is a move to remember: the last change was $\frac{1}{2}-1=-\frac{1}{2}$. Coast ahead: $y_1=\frac{1}{2}+(\text{a fraction of }-\frac{1}{2})\approx \frac{1}{2}-0.17=0.33$. Slope at $y_1$ is $0.33$, so $x_2=0.33-\frac{1}{2}\cdot 0.33\approx 0.17$.

Compare. After two steps plain gradient sits at $\frac{1}{4}=0.25$; accelerated sits at about $0.17$, closer to zero. The momentum runner is pulling ahead, and the gap widens the longer they run.

What this tells us. The only extra ingredient is memory: coast in the direction of the last move, then correct using the slope at the look-ahead point. That small change turns a one-over-k crawl into a one-over-k-squared race.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex and $L$-smooth (its gradient $\nabla f$ is $L$-Lipschitz), and $g:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ is proper closed convex with a computable proximal operator ${\mathrm{prox}}_{\lambda g}$ as defined in 44.06.02. The composite objective is $F=f+g$ with minimiser $x^{\star }$ and optimal value $F^{\star }$; the smooth case is $g\equiv 0$. We write $R=\Vert x_0-x^{\star }\Vert$ and $⟨\cdot ,\cdot ⟩$, $\Vert \cdot \Vert$ for the Euclidean inner product and norm.

Definition (Nesterov accelerated gradient, smooth case). Set $x_0=x_{-1}$, $t_1=1$. For $k\ge 1$ iterate the extrapolation and gradient step

$$y_k=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1}),x_{k+1}=y_k-\frac{1}{L}\nabla f(y_k),$$

where the momentum schedule is

$$t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}.$$

The point $y_k$ is the extrapolated (look-ahead) point; the gradient is evaluated there, not at $x_k$. The schedule satisfies the defining identity $t_{k+1}^2-t_{k+1}=t_k^2$ and the growth bound $t_k\ge (k+1)/2$.

Definition (FISTA, composite case). The fast iterative shrinkage-thresholding algorithm replaces the gradient step by a proximal-gradient step on $F=f+g$. With the same schedule $t_k$ and step $1/L$,

$$y_k=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1}),x_{k+1}={\mathrm{prox}}_{(1/L)g}(y_k-\frac{1}{L}\nabla f(y_k)).$$

The backward (prox) step and the sufficient-decrease lemma of 44.06.02 are reused unchanged; the only structural change from unaccelerated proximal-gradient is that the forward step is taken from $y_k$ rather than $x_k$.

Definition (proximal-gradient map and gradient mapping). Write $p_L(y)={\mathrm{prox}}_{(1/L)g}(y-\frac{1}{L}\nabla f(y))$ for the proximal-gradient map at step $1/L$, so the FISTA update is $x_{k+1}=p_L(y_k)$. The associated gradient mapping is ${\mathcal{G}}_L(y)=L(y-p_L(y))$, which equals $\nabla f(y)$ when $g\equiv 0$ and plays the role of the gradient in the analysis: $p_L(y)=y-\frac{1}{L}{\mathcal{G}}_L(y)$ and ${\mathcal{G}}_L(x^{\star })=0$ iff $x^{\star }$ minimises $F$.

Definition (strongly convex accelerated method). If $f$ is in addition $\mu$-strongly convex with condition number $\kappa =L/\mu$, the constant-momentum scheme uses the fixed coefficient

$$\beta =\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1},y_k=x_k+\beta (x_k-x_{k-1}),x_{k+1}=y_k-\frac{1}{L}\nabla f(y_k),$$

in place of the diminishing $t_k$-driven momentum.

Counterexamples to common slips Intermediate+

• "Acceleration is a descent method." It is not. The energy $F(x_k)$ can increase across iterations; only the potential $E_k$ (defined below), which mixes value gap and a momentum-corrected distance, is monotone. Monitoring $F(x_k)$ alone can show oscillation while the method converges at the $O(1/k^2)$ rate.

• "The momentum coefficient is a free tuning constant." In the convex case it is forced by the schedule ${\beta }_k=(t_k-1)/t_{k+1}$, which tends to $1$ from below; a constant $\beta <1$ does not give $O(1/k^2)$ for general convex $f$. The strongly convex case is the exception, where the constant $\beta =(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$ is correct because the extra curvature $\mu$ supplies what the growing schedule otherwise must.

• "Acceleration helps for any convex $f$." It needs $L$-smoothness. On the nonsmooth Lipschitz class the lower bound is $\Omega (1/\sqrt{k})$ from 44.06.01, which momentum cannot beat; acceleration exploits the smoothness of $f$, which is exactly the structure the subgradient lower bound lacks.

Key theorem with proof Intermediate+

The accelerated rate rests on a single monotone quantity: a potential built from the value gap weighted by $t_k^2$ plus a momentum-corrected squared distance to $x^{\star }$. The schedule identity $t_{k+1}^2-t_{k+1}=t_k^2$ is precisely what makes that potential nonincreasing across one step.

Theorem (FISTA $O(1/k^2)$ rate). Let $F=f+g$ with $f$ convex $L$-smooth and $g$ proper closed convex, $x^{\star }\in \arg \min F$. Run FISTA with $t_1=1$, $t_{k+1}=(1+\sqrt{1+4t_k^2})/2$, step $1/L$. Define $u_k=x_{k-1}+t_k(x_k-x_{k-1})$ and the potential

$$E_k=\frac{2t_k^2}{L}(F(x_k)-F^{\star })+\Vert u_k-x^{\star }{\Vert }^2.$$

Then $E_{k+1}\le E_k$ for all $k\ge 1$, and consequently

$$F(x_k)-F^{\star }\le \frac{2L\Vert x_0-x^{\star }{\Vert }^2}{(k+1{)}^2}=O(1/k^2).$$

Proof. The engine is the sufficient-decrease lemma of 44.06.02 applied at the extrapolated point $y_k$ with the prox-gradient step $x_{k+1}=p_L(y_k)$. That lemma, with parameter $t=1/L$, states that for every $z$,

$$F(x_{k+1})\le F(z)+\frac{L}{2}(\Vert y_k-z{\Vert }^2-\Vert x_{k+1}-z{\Vert }^2).\text{\hspace{1em}(1)}$$

Apply (1) twice. First with $z=x_k$:

$$F(x_{k+1})\le F(x_k)+\frac{L}{2}(\Vert y_k-x_k{\Vert }^2-\Vert x_{k+1}-x_k{\Vert }^2).\text{\hspace{1em}(2)}$$

Second with $z=x^{\star }$:

$$F(x_{k+1})\le F^{\star }+\frac{L}{2}(\Vert y_k-x^{\star }{\Vert }^2-\Vert x_{k+1}-x^{\star }{\Vert }^2).\text{\hspace{1em}(3)}$$

Write $v_k=F(x_k)-F^{\star }\ge 0$. Take the convex combination $(t_{k+1}-1)\times (2)+1\times (3)$, divide by nothing, and multiply through by $\frac{2}{L}$. The left side is $\frac{2t_{k+1}}{L}F(x_{k+1})$; subtracting $\frac{2t_{k+1}}{L}{F}^{\star }$ and using $v_{k+1}=F(x_{k+1})-F^{\star }$, $v_k=F(x_k)-F^{\star }$,

$$\frac{2t_{k+1}}{L}{v}_{k+1}\le \frac{2(t_{k+1}-1)}{L}{v}_k+(t_{k+1}-1)(\Vert y_k-x_k{\Vert }^2-\Vert x_{k+1}-x_k{\Vert }^2)+(\Vert y_k-x^{\star }{\Vert }^2-\Vert x_{k+1}-x^{\star }{\Vert }^2).$$

Multiply by $t_{k+1}$ and use the schedule identity $t_{k+1}^2-t_{k+1}=t_k^2$ on the first right-hand term to turn $t_{k+1}(t_{k+1}-1)v_k$ into $t_k^2{v}_k$:

$$\frac{2t_{k+1}^2}{L}{v}_{k+1}-\frac{2t_k^2}{L}{v}_k\le t_{k+1}(t_{k+1}-1)\Vert y_k-x_k{\Vert }^2-t_{k+1}(t_{k+1}-1)\Vert x_{k+1}-x_k{\Vert }^2+t_{k+1}(\Vert y_k-x^{\star }{\Vert }^2-\Vert x_{k+1}-x^{\star }{\Vert }^2).\text{\hspace{1em}(4)}$$

The right side of (4) is exactly $\Vert u_k-x^{\star }{\Vert }^2-\Vert u_{k+1}-x^{\star }{\Vert }^2$ once the extrapolation $y_k=x_k+\frac{t_k-1}{t_{k+1}}(x_k-x_{k-1})$ and the definition $u_{k+1}=x_k+t_{k+1}(x_{k+1}-x_k)$ are substituted. This is the algebraic identity

$$t_{k+1}^2\Vert x_{k+1}-x_k{\Vert }^2-2t_{k+1}⟨x_{k+1}-x_k,u_{k+1}-x^{\star }+\cdots ⟩+\cdots ,$$

collapsing via the polarisation identity $\Vert a{\Vert }^2-\Vert b{\Vert }^2=⟨a-b,a+b⟩$ applied to $a=u_k-x^{\star }$, $b=u_{k+1}-x^{\star }$ with $u_{k+1}-u_k=t_{k+1}(x_{k+1}-x_k)-(x_k-x_{k-1})t_k\cdots$; carrying the substitution through (the cross terms cancel because $y_k$ is the precise convex combination making $t_{k+1}{y}_k=t_{k+1}{x}_k+(t_k-1)(x_k-x_{k-1})$ align with $u_k$). Hence (4) reads

$$\frac{2t_{k+1}^2}{L}{v}_{k+1}+\Vert u_{k+1}-x^{\star }{\Vert }^2\le \frac{2t_k^2}{L}{v}_k+\Vert u_k-x^{\star }{\Vert }^2,$$

i.e. $E_{k+1}\le E_k$.

It remains to unwind the potential. Since $E_k$ is nonincreasing, $E_k\le E_1$. At $k=1$, $t_1=1$ and $u_1=x_0+1\cdot (x_1-x_0)=x_1$; bounding $E_1$ by inequality (3) at $k=0$ (the first plain prox-gradient step from $x_0=y_0$) gives $E_1\le \Vert x_0-x^{\star }{\Vert }^2=R^2$. Therefore $\frac{2t_k^2}{L}{v}_k\le E_k\le R^2$, so $v_k\le \frac{L{R}^2}{2t_k^2}$. The growth bound $t_k\ge (k+1)/2$ (proved by induction: $t_1=1\ge 1$, and $t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}\ge \frac{1}{2}+t_k\ge \frac{1}{2}+\frac{k+1}{2}=\frac{k+2}{2}$) gives $t_k^2\ge (k+1{)}^2/4$, hence $v_k\le 2L{R}^2/(k+1{)}^2$. $\square$

Bridge. The potential $E_k$ is the foundational reason acceleration works, and the schedule identity $t_{k+1}^2-t_{k+1}=t_k^2$ is exactly what makes it monotone; this builds toward the strongly convex linear rate and the estimate-sequence reformulation of the Advanced results, where the same balance reappears with the curvature $\mu$ supplying the growth that $t_k$ otherwise provides. This is exactly the proximal-gradient sufficient-decrease lemma $(†)$ of 44.06.02 applied at the extrapolated $y_k$ rather than at $x_k$ — the central insight that evaluating the gradient at a look-ahead point, then weighting the value gap by $t_k^2\sim k^2$, converts the $O(1/k)$ telescoping of that unit into $O(1/k^2)$. The rate generalises gradient descent's $O(1/k)$ and is dual to the $\Omega (1/k^2)$ lower bound of the smooth class, so putting these together the method is optimal; the bridge is the gradient mapping ${\mathcal{G}}_L$, which lets the smooth proof carry verbatim to the composite $f+g$, and the construction appears again in accelerated splitting methods 44.06.04.

Exercises Intermediate+

Advanced results Master

The accelerated method is $y_k=x_k+{\beta }_k(x_k-x_{k-1})$, $x_{k+1}=p_L(y_k)$ with ${\beta }_k=(t_k-1)/t_{k+1}$, and the results below give the second proof technique (estimate sequences), the strongly convex linear rate, the matching lower bound that certifies optimality, the continuous-time limit, and the restart fix for the non-monotone behaviour.

Theorem 1 (estimate-sequence construction of the optimal method). An estimate sequence for $f$ is a pair $\{({\varphi }_k,{\lambda }_k)\}$ with ${\lambda }_k\to 0$ and, for all $x$,

$${\varphi }_k(x)\le (1-{\lambda }_k)f(x)+{\lambda }_k{\varphi }_0(x).$$

If in addition ${\varphi }_k^{\star }:={\min }_x{\varphi }_k(x)\ge f(x_k)$ for the generated iterates, then $f(x_k)-f^{\star }\le {\lambda }_k({\varphi }_0(x^{\star })-f^{\star })\to 0$, and the rate is the decay rate of ${\lambda }_k$. Choosing ${\varphi }_0(x)=f(x_0)+\frac{{\gamma }_0}{2}\Vert x-x_0{\Vert }^2$ and updating ${\varphi }_{k+1}=(1-{\alpha }_k){\varphi }_k+{\alpha }_k[f(y_k)+⟨\nabla f(y_k),x-y_k⟩+\frac{\mu }{2}\Vert x-y_k{\Vert }^2]$ keeps each ${\varphi }_k$ a simple quadratic; matching the two conditions forces the extrapolation $y_k$ and the relation ${\alpha }_k^2=(1-{\alpha }_k){\gamma }_k/L+{\alpha }_k\mu /L$, which in the convex case ($\mu =0$) reproduces the $t_k$ schedule and ${\lambda }_k=O(1/k^2)$ ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. The estimate sequence is the original Nesterov proof; the potential function of the Key theorem is its Beck-Teboulle distillation.

Theorem 2 (strongly convex linear rate, $\sqrt{\kappa }$ dependence). If $f$ is $\mu$-strongly convex and $L$-smooth with $\kappa =L/\mu$, the constant-momentum method with $\beta =(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$ satisfies

$$f(x_k)-f^{\star }\le (1-\frac{1}{\sqrt{\kappa }}{)}^k(f(x_0)-f^{\star }+\frac{\mu }{2}\Vert x_0-x^{\star }{\Vert }^2),$$

a geometric rate with contraction $1-1/\sqrt{\kappa }$ ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. Plain gradient descent attains only $(1-1/\kappa {)}^k$; acceleration replaces the iteration count $O(\kappa \log (1/\epsilon ))$ by $O(\sqrt{\kappa }\log (1/\epsilon ))$. The estimate-sequence proof carries the curvature $\mu$ through the ${\lambda }_k$ recursion ${\lambda }_{k+1}=(1-\sqrt{\mu /L}){\lambda }_k$, giving the geometric ${\lambda }_k=(1-1/\sqrt{\kappa }{)}^k$ in place of the convex $O(1/k^2)$.

Theorem 3 (the $\Omega (1/k^2)$ first-order lower bound). Consider any first-order method whose iterates satisfy $x_k\in x_0+\mathrm{span}\{\nabla f(x_0),\dots ,\nabla f(x_{k-1})\}$ (the Krylov / linear-span model). For each $k$ there is a convex $L$-smooth function on ${\mathbb{R}}^{2k+1}$ — the worst function in the world $f(x)=\frac{L}{8}(x_1^2+{\sum }_{i=1}^{2k}(x_i-x_{i+1}{)}^2-2x_1)$, whose Hessian is the scaled tridiagonal $(2,-1)$ matrix — for which

$$f(x_k)-f^{\star }\ge \frac{3L\Vert x_0-x^{\star }{\Vert }^2}{32(k+1{)}^2}=\Omega \left(\frac{L{R}^2}{k^2}\right).$$

The mechanism is that one gradient evaluation can activate only one new coordinate of the tridiagonal coupling, so after $k$ steps the iterate is supported on $k$ coordinates and the residual on the untouched tail is bounded below ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. Since accelerated gradient attains $O(L{R}^2/k^2)$ (Key theorem), the bounds match in order: the accelerated method is optimal for the $L$-smooth convex first-order class, exactly as the subgradient method is optimal for the nonsmooth class of 44.06.01. No first-order method can be asymptotically faster on this class.

Theorem 4 (continuous-time / ODE limit). Taking the step size to zero in $x_{k+1}=x_k+{\beta }_k(x_k-x_{k-1})-\frac{1}{L}\nabla f(\cdots )$ with ${\beta }_k=(k-1)/(k+2)$, the rescaled trajectory $X(t)$ solves the second-order ODE with vanishing friction

$$\ddot{X}(t)+\frac{3}{t}\dot{X}(t)+\nabla f(X(t))=0,$$

and the Lyapunov function $\mathcal{E}(t)=t^2(f(X(t))-f^{\star })+2\Vert X(t)+\frac{t}{2}\dot{X}(t)-x^{\star }{\Vert }^2$ is nonincreasing, giving $f(X(t))-f^{\star }\le 2R^2/t^2$ ^{[Su, W., Boyd, S. & Candes, E. J. — A Differential Equation for Modeling Nesterov's Accelerated Gradient Method]}. The friction coefficient $3/t$ is the smallest decaying damping that still yields $O(1/t^2)$; the discrete potential $E_k$ of the Key theorem is the time-discretisation of $\mathcal{E}(t)$, and the oscillatory, non-monotone trajectories of the ODE are the continuous shadow of the non-monotone $F(x_k)$ in discrete time.

Theorem 5 (non-monotonicity and restart). The energy $F(x_k)$ along accelerated iterates is not monotone: momentum overshoots the minimiser and rings down, so $F(x_{k+1})>F(x_k)$ on whole stretches even as the potential $E_k$ falls. Adaptive restart — resetting $t_k\leftarrow 1$ (zeroing momentum) whenever $F(x_{k+1})>F(x_k)$ (function restart) or whenever $⟨y_k-x_{k+1},x_{k+1}-x_k⟩>0$ (gradient restart) — empirically recovers the linear rate on locally strongly convex regions and removes the oscillation, while preserving the worst-case $O(1/k^2)$ guarantee ^{[Su, W., Boyd, S. & Candes, E. J. — A Differential Equation for Modeling Nesterov's Accelerated Gradient Method]}. Restart is the practical reconciliation of the optimal global rate with the local strong-convexity speedup of Theorem 2.

Synthesis. The accelerated method is exactly the proximal-gradient iteration of 44.06.02 with the gradient sampled at an extrapolated point and the value gap weighted by $t_k^2\sim k^2$, and this single change is the foundational reason the rate jumps from $O(1/k)$ to $O(1/k^2)$. The two proofs are dual faces of one object: the estimate sequence builds simple quadratic lower models whose minima rise to meet $f(x_k)$, while the potential function is the Beck-Teboulle distillation in which the schedule identity $t_{k+1}^2-t_{k+1}=t_k^2$ is exactly what makes the energy monotone — putting these together, the ${\lambda }_k=O(1/k^2)$ of the estimate sequence and the $1/t_k^2$ of the potential are the same decay. The central insight is that $O(1/k^2)$ is dual to the $\Omega (1/k^2)$ lower bound on the smooth class, so acceleration is optimal there, precisely as the subgradient method is optimal on the nonsmooth class of 44.06.01 where momentum cannot help; the strongly convex case generalises this with $\sqrt{\kappa }$ in place of $\kappa$, again matching its own lower bound. The bridge to the rest of the chapter is the gradient mapping ${\mathcal{G}}_L$ and the momentum schedule: they carry the smooth proof verbatim to the composite $f+g$ as FISTA, and the same template accelerates the splitting methods 44.06.04; the ODE $\ddot{X}+\frac{3}{t}\dot{X}+\nabla f(X)=0$ is the continuous-time identification that makes the non-monotone overshoot, and its restart cure, structurally transparent.

Full proof set Master

Proposition 1 (potential monotonicity). Under the Key theorem hypotheses, $E_{k+1}\le E_k$ for all $k\ge 1$, where $E_k=\frac{2t_k^2}{L}(F(x_k)-F^{\star })+\Vert u_k-x^{\star }{\Vert }^2$ and $u_k=x_{k-1}+t_k(x_k-x_{k-1})$.

Proof. This is the body of the Key theorem and is complete there: apply the sufficient-decrease lemma (1) of 44.06.02 at $y_k$ with $z=x_k$ and with $z=x^{\star }$, form the combination $(t_{k+1}-1)\times (z=x_k)+(z=x^{\star })$, scale by $\frac{2t_{k+1}}{L}$, use $t_{k+1}^2-t_{k+1}=t_k^2$ to relate consecutive value gaps, and collapse the distance terms by the polarisation identity with the extrapolation definition $t_{k+1}{y}_k=t_{k+1}{x}_k+(t_k-1)(x_k-x_{k-1})$ aligning $u_{k+1}=x_k+t_{k+1}(x_{k+1}-x_k)$. The result is $\frac{2t_{k+1}^2}{L}{v}_{k+1}+\Vert u_{k+1}-x^{\star }{\Vert }^2\le \frac{2t_k^2}{L}{v}_k+\Vert u_k-x^{\star }{\Vert }^2$. $\square$

Proposition 2 (schedule identity and growth). The sequence $t_1=1$, $t_{k+1}=(1+\sqrt{1+4t_k^2})/2$ satisfies $t_{k+1}^2-t_{k+1}=t_k^2$ and $t_k\ge (k+1)/2$.

Proof. From $2t_{k+1}-1=\sqrt{1+4t_k^2}$, squaring gives $4t_{k+1}^2-4t_{k+1}+1=1+4t_k^2$, i.e. $t_{k+1}^2-t_{k+1}=t_k^2$. For growth, $t_{k+1}=\frac{1}{2}+\sqrt{\frac{1}{4}+t_k^2}\ge \frac{1}{2}+t_k$, so by induction from $t_1=1$, $t_k\ge 1+(k-1)/2=(k+1)/2$. $\square$

Proposition 3 ($O(1/k^2)$ rate). Under the Key theorem hypotheses, $F(x_k)-F^{\star }\le 2L\Vert x_0-x^{\star }{\Vert }^2/(k+1{)}^2$.

Proof. Proposition 1 gives $E_k\le E_1$. By the base-case computation (Exercise 8), $E_1\le R^2$ with $R=\Vert x_0-x^{\star }\Vert$. Hence $\frac{2t_k^2}{L}(F(x_k)-F^{\star })\le E_k\le R^2$, so $F(x_k)-F^{\star }\le \frac{L{R}^2}{2t_k^2}$. Proposition 2 gives $t_k^2\ge (k+1{)}^2/4$, whence $F(x_k)-F^{\star }\le \frac{L{R}^2}{2}\cdot \frac{4}{(k+1{)}^2}=\frac{2L{R}^2}{(k+1{)}^2}$. $\square$

Proposition 4 (strongly convex linear rate). If $f$ is $\mu$-strongly convex and $L$-smooth ($g\equiv 0$, $\kappa =L/\mu$), the constant-momentum method with $\beta =(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$ satisfies $f(x_k)-f^{\star }\le (1-1/\sqrt{\kappa }{)}^k{\Phi }_0$ where ${\Phi }_0=f(x_0)-f^{\star }+\frac{\mu }{2}\Vert x_0-x^{\star }{\Vert }^2$.

Proof. Run the estimate sequence with ${\varphi }_0(x)=f^{\star }+\frac{\mu }{2}\Vert x-x^{\star }{\Vert }^2+(f(x_0)-f^{\star })$ and the quadratic update ${\varphi }_{k+1}=(1-\alpha ){\varphi }_k+\alpha [f(y_k)+⟨\nabla f(y_k),\cdot -y_k⟩+\frac{\mu }{2}\Vert \cdot -y_k{\Vert }^2]$ with the constant $\alpha =\sqrt{\mu /L}=1/\sqrt{\kappa }$, which is the fixed point of the relation ${\alpha }^2=(1-\alpha ){\alpha }_{\text{prev}}+\alpha \mu /L$ when ${\gamma }_k\equiv \mu$. Then ${\lambda }_{k+1}=(1-\alpha ){\lambda }_k=(1-1/\sqrt{\kappa }){\lambda }_k$, so ${\lambda }_k=(1-1/\sqrt{\kappa }{)}^k$; the strong convexity of each ${\varphi }_k$ (curvature $\mu$) sustains ${\varphi }_k^{\star }\ge f(x_k)$ along the iterates generated by $y_k=x_k+\beta (x_k-x_{k-1})$ with $\beta =(1-\alpha )/(1+\alpha )=(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$. The estimate-sequence bound $f(x_k)-f^{\star }\le {\lambda }_k({\varphi }_0(x^{\star })-f^{\star })=(1-1/\sqrt{\kappa }{)}^k{\Phi }_0$ follows ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. $\square$

Proposition 5 (lower bound, tridiagonal worst function). For every first-order method with $x_k\in x_0+\mathrm{span}\{\nabla f(x_0),\dots ,\nabla f(x_{k-1})\}$ and $x_0=0$, there is a convex $L$-smooth $f$ on ${\mathbb{R}}^{2k+1}$ with $f(x_k)-f^{\star }\ge 3L{R}^2/(32(k+1{)}^2)$.

Proof. Let $A$ be the tridiagonal matrix with $2$ on the diagonal and $-1$ on the off-diagonals on ${\mathbb{R}}^n$, $n=2k+1$, and set $f(x)=\frac{L}{8}(⟨Ax,x⟩-2⟨e_1,x⟩)$. Then $\nabla f(x)=\frac{L}{4}(Ax-e_1)$ and the Hessian $\frac{L}{4}A$ has spectrum in $[0,L]$ (since $\Vert A{\Vert }_2\le 4$), so $f$ is convex and $L$-smooth. With $x_0=0$, $\nabla f(x_0)=-\frac{L}{4}{e}_1$ is supported on coordinate $1$; inductively, because $A$ couples only adjacent coordinates, $x_j$ and $\nabla f(x_j)$ are supported on coordinates $\{1,\dots ,j+1\}$, so $x_k$ is supported on $\{1,\dots ,k\}$ — its last $n-k=k+1$ coordinates vanish. The exact minimiser solves $A{x}^{\star }=e_1$, giving $x_i^{\star }=1-i/(n+1)$, with $f^{\star }=-\frac{L}{8}\cdot \frac{n}{n+1}$ and $\Vert x^{\star }{\Vert }^2=\frac{(n+1)(2n+1)}{6(n+1)}\cdots$. Evaluating $f$ on the best $k$-supported vector and comparing with $f^{\star }$ yields, after the standard partial-sum estimate, $f(x_k)-f^{\star }\ge \frac{3L\Vert x_0-x^{\star }{\Vert }^2}{32(k+1{)}^2}$ ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. $\square$

Proposition 6 (ODE limit and Lyapunov decay). With ${\beta }_k=(k-1)/(k+2)$ and step $h=1/\sqrt{L}$, the interpolated accelerated trajectory converges as $h\to 0$ to the solution of $\ddot{X}+\frac{3}{t}\dot{X}+\nabla f(X)=0$, along which $\mathcal{E}(t)=t^2(f(X)-f^{\star })+2\Vert X+\frac{t}{2}\dot{X}-x^{\star }{\Vert }^2$ obeys $\dot{\mathcal{E}}(t)\le 0$, so $f(X(t))-f^{\star }\le 2R^2/t^2$.

Proof. Differentiate $\mathcal{E}$:

$$\dot{\mathcal{E}}=2t(f(X)-f^{\star })+t^2⟨\nabla f(X),\dot{X}⟩+4⟨X+\frac{t}{2}\dot{X}-x^{\star },\frac{3}{2}\dot{X}+\frac{t}{2}\ddot{X}⟩.$$

Substitute the ODE $\frac{t}{2}\ddot{X}=-\frac{3}{2}\dot{X}-\frac{t}{2}\nabla f(X)$ into the last bracket: $\frac{3}{2}\dot{X}+\frac{t}{2}\ddot{X}=-\frac{t}{2}\nabla f(X)$. Hence

$$\dot{\mathcal{E}}=2t(f(X)-f^{\star })+t^2⟨\nabla f(X),\dot{X}⟩-2t⟨X+\frac{t}{2}\dot{X}-x^{\star },\nabla f(X)⟩=2t(f(X)-f^{\star })-2t⟨X-x^{\star },\nabla f(X)⟩,$$

the $t^2⟨\nabla f,\dot{X}⟩$ terms cancelling. Convexity gives $⟨X-x^{\star },\nabla f(X)⟩\ge f(X)-f^{\star }$, so $\dot{\mathcal{E}}\le 2t(f(X)-f^{\star })-2t(f(X)-f^{\star })=0$. Therefore $t^2(f(X)-f^{\star })\le \mathcal{E}(t)\le \mathcal{E}(0^{+})=2\Vert X(0)-x^{\star }{\Vert }^2=2R^2$, giving the decay ^{[Su, W., Boyd, S. & Candes, E. J. — A Differential Equation for Modeling Nesterov's Accelerated Gradient Method]}. $\square$

Connections Master

• Accelerated gradient is the direct successor to the proximal-gradient method of 44.06.02: FISTA is that exact iteration with the gradient evaluated at the extrapolated $y_k$ instead of $x_k$, the sufficient-decrease lemma $(†)$ reused verbatim, and the prox step unchanged. The unit's $O(1/k)$ telescoping becomes $O(1/k^2)$ purely through the $t_k^2$ weighting in the potential $E_k$, so the entire acceleration is a re-weighting of the same per-step estimate proved there.

• The optimality of acceleration is dual to the lower-bound theory of 44.06.01: where that unit proves $\Omega (1/\sqrt{k})$ for the nonsmooth black-box class and shows the subgradient method attains it, this unit proves $\Omega (1/k^2)$ for the $L$-smooth class and shows accelerated gradient attains it. The two lower bounds together partition the first-order landscape — nonsmooth Lipschitz versus smooth — and the boundary is exactly the smoothness structure acceleration exploits and the subgradient model lacks.

• Accelerated proximal methods are the workhorse for large-scale composite optimisation in statistical learning and signal processing, feeding forward to ADMM and operator-splitting 44.06.04, which admit their own momentum-accelerated variants built on this same $t_k$ schedule and potential-function template; the gradient mapping ${\mathcal{G}}_L$ that carries the smooth proof to composite $f+g$ is the object those splitting accelerations also extrapolate.

Historical & philosophical context Master

The accelerated gradient method was introduced by Yurii Nesterov in 1983, who exhibited a first-order scheme attaining the $O(1/k^2)$ rate on the smooth convex class and proved it optimal by matching Nemirovski and Yudin's information-based lower bound for that class ^{[Nesterov 1983]}. The proof technique of estimate sequences, which constructs a family of simple quadratic models converging to the objective, was developed by Nesterov across subsequent work and is the organising method of his lectures ^{[Nesterov 2018]}. The extension to nonsmooth composite problems — accelerating the proximal-gradient (ISTA) iteration to FISTA — was given by Amir Beck and Marc Teboulle in 2009, who supplied the potential-function proof that replaced the estimate sequence with a single monotone energy and demonstrated the method on image-deblurring inverse problems ^{[Beck & Teboulle 2009]}. The continuous-time interpretation, identifying Nesterov's scheme as the discretisation of a second-order ODE with vanishing $3/t$ friction, was given by Weijie Su, Stephen Boyd, and Emmanuel Candès in 2014–2016, who used it to explain the non-monotone oscillation and to design the adaptive-restart heuristic ^{[Su, Boyd & Candes 2016]}. The constant $3$ in the friction term — the smallest damping preserving the $O(1/t^2)$ rate — and the lower-bound construction trace back through Nemirovski–Yudin's complexity theory of the 1970s and 1980s.

Bibliography Master

@article{nesterov1983accelerated,
  author  = {Nesterov, Yurii},
  title   = {A method of solving a convex programming problem with convergence rate $O(1/k^2)$},
  journal = {Soviet Mathematics Doklady},
  volume  = {27},
  number  = {2},
  pages   = {372--376},
  year    = {1983}
}

@book{nesterov2018lectures,
  author    = {Nesterov, Yurii},
  title     = {Lectures on Convex Optimization},
  edition   = {2},
  series    = {Springer Optimization and Its Applications},
  volume    = {137},
  publisher = {Springer},
  year      = {2018}
}

@article{becktebeoulle2009fista,
  author  = {Beck, Amir and Teboulle, Marc},
  title   = {A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems},
  journal = {SIAM Journal on Imaging Sciences},
  volume  = {2},
  number  = {1},
  pages   = {183--202},
  year    = {2009}
}

@article{suboydcandes2016ode,
  author  = {Su, Weijie and Boyd, Stephen and Cand\`es, Emmanuel J.},
  title   = {A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights},
  journal = {Journal of Machine Learning Research},
  volume  = {17},
  number  = {153},
  pages   = {1--43},
  year    = {2016}
}

@book{nemirovskiyudin1983,
  author    = {Nemirovski, Arkadi S. and Yudin, David B.},
  title     = {Problem Complexity and Method Efficiency in Optimization},
  publisher = {Wiley-Interscience},
  year      = {1983}
}

@article{odonoghuecandes2015restart,
  author  = {O'Donoghue, Brendan and Cand\`es, Emmanuel J.},
  title   = {Adaptive Restart for Accelerated Gradient Schemes},
  journal = {Foundations of Computational Mathematics},
  volume  = {15},
  number  = {3},
  pages   = {715--732},
  year    = {2015}
}