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 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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.26719
curl -X POST /api/v1/records/arxiv/2608.26719/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.26719/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'