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

Abstract

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 every such $N$ and every dimension $d\geq N-4$, we prove \[ \sup_{\substack{f\in\F_{0,L}(\R^d),\ x_\star\in\arg\min f \norm{x_0-x_\star}\leq R}} \min_{0\leq k\leq N}\norm{\nabla f(x_k)}^2 =\frac{L^2R^2}{\sum_{k=0}^N t_k^2}. \] The relaxed-PEP upper bound is due to Kim and Fessler, who also reported tight numerical solutions of the exact-interpolation PEP at selected horizons. What remained missing was an analytic matching family valid uniformly over the horizon. For every $N\geq7$, we construct such a family using an FGM-specific spherical polytope $K_N$ and the standard projection-envelope function \[ f_N(x)=\max_{g\in K_N}\left\{\ip{x}{g}-\frac12\norm{g}^2\right\}, \qquad \nabla f_N(x)=\Proj_{K_N}(x). \] Every queried gradient has the same norm, and the vertices of $K_N$ are generated from a three-dimensional seed by a one-dimensional spherical cone lift. The lift preserves all projection inequalities and raises the adversary dimension by one at each horizon. The projection/Moreau-envelope template itself is classical; the new ingredients are the FGM-specific algebraic seed, the proof that it attains the relaxed bound, and the common-latitude lift that propagates this exactness to every $N\geq7$. We state precise hypotheses for that propagation and do not claim that every rank-one relaxed PEP admits such a seed.