Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Optimisation P-constant-35a-gradient-descent-exponent

Gradient Descent Exponent

Let f be a convex function with 1-Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of _step size_ s: x_k+1 := x_k - s· ∇ f(x_k). In general, s can be chosen to vary with the step k.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-constant-35a-gradient-descent-exponent,
  title        = {Gradient Descent Exponent},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-35a-gradient-descent-exponent}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Description of constant

Let be a convex function with -Lipschitz gradient. We assume black-box access to the function and its gradient. Gradient descent will converge to a global minimum with an appropriate choice of _step size_ : . In general, can be chosen to vary with the step . The function gap , will then converge like for some exponent where is the iteration counter. While fixed step sizes achieve , time-varying patterns of increasing and decreasing step sizes can lead to improved rates of convergence, increasing the exponent.

The constant is the largest exponent such that there exists a step schedule so that vanilla gradient descent has a worst-case convergence of .

Known upper bounds

BoundReferenceComments
2FolkloreSee, e.g., [N2014]

Known lower bounds

BoundReferenceComments
1FolkloreAchieved by constant step sizes. See, e.g., [B2015].
1.0564[GSW23]Obtained by nonconstant, nonperiodic stepsize schedule. Appeared on arXiv concurrently with [AP24]
[AP24]Obtained by the "silver stepsize schedule". Conjecturally optimal. Appeared on arXiv concurrently with [GSW23].

References

  • [AP24] Jason M Altschuler and Pablo A Parrilo. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex optimization. Mathematical Programming, pages 1–14, 2024.
  • [B2015] Dimitri P. Bertsekas. Convex optimization algorithms. 2015.
  • [GSW23] Benjamin Grimmer, Kevin Shu, and Alex L. Wang. Accelerated Gradient Descent via Long Steps. arXiv:2309.09961
  • [N2014] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, 1 edition, 2014.

What counts as progress

  • A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
  • A formal proof (Lean) of a known bound, or a precise error in a claimed one.
  • New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.