Sharp last-gradient bounds for constant-step convex gradient descent
Follow the latest progress by email.
For gradient descent with constant step h/L on a differentiable convex L-smooth function in a real Hilbert space, determine the sharp final-gradient bound after N≥0 steps for every h≥0. The proposed factor is max{1/(1+Nh),|1−h|^N} times L‖x₀−x*‖.
Why it matters and what counts as progress
Why it matters: It seeks an exact finite-horizon guarantee across all nonnegative step sizes, with Huber and quadratic witnesses identifying the competing worst cases.
What counts as progress: A matching worst-case bound and attaining examples for every step size and horizon; equality-trajectory classification or certified extensions to proximal residuals add further information.
How the problem developed
- 2017 · Conjecture [1]
A. B. Taylor, J. M. Hendrickx, and F. Glineur Posed the conjectured sharp worst-case final-gradient behavior for constant-step smooth convex gradient descent.
- 12 Sept 2026 · Partial result [2]
Salah Chikhi Proved the optimal constant step, value, and uniqueness for each finite horizon, without resolving the full worst-case curve.
JD Jones, with GPT-6 Astra and Codex assistance Established the full sharp final-gradient factor max{1/(1+Nh), |1−h|ᴺ} for every finite horizon and constant step, with one-dimensional sharpness examples.
AI contribution
GPT-assisted proof establishes the full last-gradient curve for smooth convex descent
For every N≥0 and h≥0, constant-step gradient descent xᵢ₊₁=xᵢ−(h/L)∇f(xᵢ) on a differentiable convex function with L-Lipschitz gradient in a real Hilbert space satisfies ‖∇f(xN)‖≤L‖x0−x*‖max{1/(1+Nh),|1−h|^N}. One-dimensional Huber and quadratic examples attain the two branches. The compared Lean contract also classifies sampled equality trajectories and proves the same sharp factor for the terminal residual of relaxed proximal minimization with actual minimizers.
Sources
- A. B. Taylor, J. M. Hendrickx, and F. Glineur, Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Salah Chikhi, Last-Iterate Performance of Gradient Descent and Relaxed Proximal Point via s-Composability
- Result and scope
- AIProofWatch, GPT-assisted proof establishes the full last-gradient curve
- Completed Lean proof
- Proof checking record
- Provenance and prior work
Website timeline
Publication dates and editorial changes.
GPT-assisted proof establishes the full last-gradient curve for smooth convex descent