MathDB

Gradient descent optimality conjecture for gradient-norm minimization

Let K>0K>0. Consider a method whose iterates have the form

xk=x0−∑i=0k−1βi,k∇f(xi),\boldsymbol{x}_k=\boldsymbol{x}_0-\sum_{i=0}^{k-1}\beta_{i,k}\nabla f(\boldsymbol{x}_i),

where x0∈Rd\boldsymbol{x}_0\in\mathbb{R}^d is the initial point, ff is a convex function accessed through a gradient oracle, and βi,k∈R\beta_{i,k}\in\mathbb{R} may depend on L>0L>0, ii, and kk, but is otherwise chosen independently of KK and the input function ff. Gradient descent optimality conjecture. There exists an LL-smooth convex function ff and an absolute constant C>0C>0 such that

∥∇f(xK)∥2≥CL(f(x0)−f(x∗))K.\|\nabla f(\boldsymbol{x}_K)\|^2\geq C\frac{L\bigl(f(\boldsymbol{x}_0)-f(\boldsymbol{x}^*)\bigr)}{K}.

This conjecture asserts that, in the stated class of methods, the gradient norm cannot generally decrease faster than order 1/K1/K relative to the initial optimality gap. The source presents it as a conjectured sense in which gradient descent is optimal; no resolution is supplied.

Sources & referencesView supporting material

Primary source

Jelena Diakonikolas and Puqian Wang, “Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization”, arXiv:2101.12101 (2021).

convex-optimizationgradient-methodslower-bounds

Progress summary

Refreshed
Open

No public proof or counterexample has been found for the conjecture in its full generality, although narrower gradient-descent results are known.

The conjecture asks whether every method formed from fixed linear combinations of earlier gradients must have some smooth convex instance whose final gradient norm decreases no faster than order 1/K1/K. The retrieved literature discusses related optimality questions, but does not resolve this full method class.

Known results

  • Long, specially chosen step-size schedules attain improved rates for gradient descent, including squared-gradient-norm rate O(N−1.2716…)\mathcal{O}(N^{-1.2716\ldots}), but only within step-size schedules (Altschuler and Parrilo, as discussed in 2024).
  • A variant concerning the minimax-optimal constant step size and final gradient norm was proved by Rotaru et al.; the exact conjecture here allows arbitrary coefficients βi,k\beta_{i,k}.
  • Exact worst-case rates are known for constant-step-size gradient descent in several smooth convex and nonconvex settings (2025).
  • In the anytime setting, the best reported squared-gradient-norm rate is O(n−1)\mathcal{O}(n^{-1}), with improvement left open (2026).

Current status (as of August 2026): The stated lower-bound conjecture for arbitrary coefficients βi,k\beta_{i,k} remains open; no proof, counterexample, or claimed resolution was found.

Sources

Solutions 0

No solutions have been posted yet.