Theorem 3.14, p. 282 — some β-smooth convex f forces min_{s≤t} f(x_s) − f(x*) ≥ (3β/32)‖x₁ − x*‖²/(t + 1)² under (3.15)

Let $n,t$ be integers with $1\le t\le\frac{n-1}2$ and let $\beta>0$. There exist a $\beta$-smooth convex function $f:\mathbb R^n\to\mathbb R$ and a minimizer $x^*$ of $f$ such that for every black-box procedure satisfying (3.15) — $x_1=0$ and $x_{s+1}\in\mathrm{Span}(\nabla f(x_1),\dots,\nabla f(x_s))$ — one has

Together with the $O(\beta\|x_1-x^*\|^2/t^2)$ upper bound of Nesterov's accelerated gradient descent, this shows that the accelerated rate is optimal, up to a numerical constant, among first-order methods of the form (3.15) when the number of queries is at most about half the dimension.

Formalization Note The function $f$, its gradient map $g$ and the minimizer $x^*$ are chosen before the procedure (an $\exists\,\forall$ statement); $\beta$-smoothness means $g=\nabla f$ everywhere and $g$ is $\beta$-Lipschitz. The book writes $f(x^*)$ for a minimizer whose existence it always assumes; the hard function has many minimizers when $2t+1<n$, and the statement asserts the bound for one of them, as in the book's proof. The minimum over $1\le s\le t$ is written as the bound for every such $s$, and $t\ge1$ is added so that this minimum is over a nonempty range. The hypothesis $t\le(n-1)/2$ is written $2t+1\le n$.