{"id":"arxiv/2608.26719","url":"https://arxiv.org/abs/2608.26719","tags":["math.OC"],"score":0,"title":"When a Relaxed PEP Is Exact: The Sharp Queried-Gradient Rate of Nesterov's Fast Gradient Method","domain":"math.OC","source":"arxiv","authors":["Yi Du"],"reviews":0,"subject":"math.OC","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}