The exact horizon-two queried-gradient worst case of Nesterov's fast gradient method is one-dimensional
Abstract
Let W_N be the worst-case value of min_(0 ≤ k ≤ N)norm(nabla f(xₖ))² over L-smooth convex functions with norm(x₀-xₛtar) ≤ R, where x₀,…,x_N are the points at which Nesterov's fast gradient method queries the gradient. Du (arXiv:2608.26719) proves W_N=L²R²/S_N for every N ≥ 7 in every dimension d ≥ N-4, with S_N=Σ_(k ≤ N)tₖ², and W₁=L²R²/4, and for 2 ≤ N ≤ 6 prints floating-point values while explicitly claiming no closed form, no uniqueness and no rank pattern. We settle the first of these horizons. Writing a for the coefficient of nabla f(x₁) in x₀-x₂ (for Nesterov's method a=1+(t₁-1)/t₂), we show that for every real a ∈ [5/4,13/10] the horizon-two worst case of the two-step scheme with coefficient a equals L²R²/(2+a)² exactly, is attained by a one-dimensional (rank-one) instance, and is certified by a dual multiplier vector that is a rational function of a. In particular W₂=L²R²/(3+(t₁-1)/(t₂))²=0.0928513193… · L²R², strictly below the Kim–Fessler bound L²R²/S₂. At horizon one we also give the exact post-gradient value 1/9, a number Taylor, Hendrickx and Glineur printed as LR/3.00 from a semidefinite solve and for which no certificate had been stated. Every theorem is stated over the finite interpolation data and is machine-checked in Lean 4 with Mathlib; no step rests on floating-point arithmetic or on an exhaustive search. The transfer to the function class, which rests on the cited interpolation theorem or on the source's explicit projection-envelope interpolant, is recorded separately and is not part of the formal development.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
5e2560570c4f57c58796b9fbf1133150cb951ad800f3d88dbfcb71751e45a258
Claim ledger
Stated results
FQ1known2026-09-03
the horizon-one queried PEP upper bound over the finite interpolation data: for every psd Gram of (x₀-x_*, grad f(x₀), grad f(x₁)) with ||x₀-x_*||² <= 1 satisfying the six Taylor-Hendrickx-Glineur inequalities of x₀, x₁, x_*, min(||g₀||², ||g₁||²) <= 1/4
FQ2known2026-09-03
attainment at horizon one, queried: 1/4 is the GREATEST value of minₖ ||grad f(xₖ)||² over the feasible interpolation data, attained by an explicit rank-one Gram (the one-dimensional Huber instance with c = 1/2)
FQ3known data2026-09-03
the horizon-one POST-GRADIENT upper bound: for feasible data of x₀, x₁ = y₁, y₂, x_*, min(||grad f(y₀)||², ||grad f(y₁)||², ||grad f(y₂)||²) <= 1/9
FQ4known data2026-09-03
the exact horizon-one post-gradient value: 1/9 is the GREATEST feasible value, attained by the rank-one instance x₀-x_* = e, grad f(x₀) = grad f(x₁) = grad f(y₂) = e/3, f = (5/18, 1/6, 1/18)
FQ5candidate2026-09-03
a one-parameter family the source does not consider: for EVERY real extrapolation coefficient a in [5/4, 13/10] (a = the coefficient of grad f(x₁) in x₀ - x₂), the horizon-two queried PEP value is at most 1/(2+a)², by an exact certificate whose multipliers are rational functions of a over Q(a)
FQ6candidate2026-09-03
the exact value of the one-parameter family: for every a in [5/4, 13/10] the horizon-two queried PEP value EQUALS 1/(2+a)², attained by a rank-one Gram – the horizon-two worst case is one-dimensional, with all three queried gradients equal to (x₀-x_*)/(2+a)
FQ7candidate2026-09-03
the exact horizon-two queried-gradient value of Nesterov's FGM, which the source declines to state: W₂ = 1/(3 + (t₁-1)/t₂)² with t₁ = (1+sqrt 5)/2 and t₂ = (1 + sqrt(7 + 2 sqrt 5))/2
FQ8routine2026-09-03
a rigorous decimal enclosure of the horizon-two value: 0.09285131 < W₂ < 0.09285133, from rational brackets on sqrt 5 and sqrt(7 + 2 sqrt 5)
FQ9routine2026-09-03
negative control: a smaller bound has no certificate – 9/100 is not an upper bound for the horizon-two feasible values, refuted by the extremal data itself
FQ10routine2026-09-03
negative control: a larger claim is refuted – every feasible horizon-two value is STRICTLY below the Kim-Fessler dimension-free bound 1/S₂, i.e. the source's numerical Delta₂ = -2.58e-2 as a theorem
FQ11routine2026-09-03
control that the extrapolation coefficient is load-bearing: the horizon-two exact value at coefficient 13/10 differs from FGM's, so the theorem is not an artefact of the certificate's shape
FQ12routine2026-09-03
non-vacuity: the horizon-two hypothesis set is satisfiable
FQ13routine2026-09-03
negative control at horizon one, queried: 1/5 is not an upper bound
FQ14routine2026-09-03
negative control at horizon one, post-gradient: 1/10 is not an upper bound
FQ15routine2026-09-03
hypothesis non-vacuity: the initial-condition hypothesis ||x₀-x_*||² <= 1 is load-bearing – the extremal data scaled by two satisfies the Gram positivity and every interpolation inequality and has metric value 1 > 1/4
FQ16routine2026-09-03
control that the metric is load-bearing: at horizon one the post-gradient worst case (1/9) is strictly below the queried one (1/4)
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Fix L > 0, R ≥ 0, d ≥ 1. F_(0,L)(Rᵈ) is the class of convex differentiable functions with L-Lipschitz gradient. Nesterov's fast gradient method (FGM), in the source's own normalisation (arXiv:2608.26719v1, equations (2.1)–(2.4)):
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7