The Ω(1/t²) lower bound for first-order methods

Prove that for every first-order method whose iterates satisfy

$$x_t \in x_0 + \operatorname{span}\{\nabla f(x_0),\dots,\nabla f(x_{t-1})\},$$

and for every $t \le (d-1)/2$, there exists a convex $L$-smooth function $f$ on $\R^d$ with

$$f(x_t) - f^\star \ \ge\ \frac{3L\|x_0-x^\star\|_2^2}{32(t+1)^2}.$$

Conclude that Nesterov's method is optimal in this class up to a constant.