Theorem 3.19, p. 294 — Nesterov's accelerated gradient descent on a convex β-smooth f satisfies f(y_t) − f(x*) ≤ 2β‖x₁ − x*‖²/t²

Let $f:\mathbb R^n\to\mathbb R$ be convex and $\beta$-smooth with $\beta>0$, and let $x^*$ be a minimizer of $f$. Let $\lambda_0=0$, $\lambda_t=\frac{1+\sqrt{1+4\lambda_{t-1}^2}}2$ and $\gamma_t=\frac{1-\lambda_t}{\lambda_{t+1}}$, and let $(x_t),(y_t)$ be generated from an arbitrary initial point $x_1=y_1$ by

Then for every $t\ge1$,

This is the accelerated $O(1/t^2)$ rate of Nesterov's method for smooth convex optimization, which improves on the $O(1/t)$ rate of plain gradient descent (Theorem 3.3) and matches, up to a constant factor, the black-box lower bound of Theorem 3.14.

Formalization Note The gradient is an explicit map $g$ with $g(x)=\nabla f(x)$; convexity is ConvexOn ℝ Set.univ f and $f$ is defined on all of $\mathbb R^n$ (the unconstrained setting of §3.7). That $x^*$ is a minimizer is the book's standing assumption (p. 242); $\beta>0$ is implicit in the step $1/\beta$ and is stated. The bound is asserted for every $t\ge1$: the page's proof covers $t\ge2$, and at $t=1$ the claim follows from the quadratic upper bound (3.4). The algorithm uses $\gamma_t$ in both coefficients of the $x$-update (the page's $\gamma_s$ is a misprint).