Yixing Du

When a Relaxed PEP Is Exact: The Sharp Queried-Gradient Rate of Nesterov's Fast Gradient Method

We determine the exact worst-case value, at every horizon $N\geq7$, of the smallest queried gradient norm generated by Nesterov's fast gradient method on smooth convex functions. Let $t_0=1$ and $t_{k+1}=(1+\sqrt{1+4t_k^2})/2$, and let $x_0,\ldots,x_N$ denote the points at which the method evaluates gradients. For ever...