← All setups

Gradient Descent with Quadratic Growth

Descriptions may be stale. Consult the linked Lean sources.

Gradient Descent with Quadratic Growth

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E with norm ∥⋅∥. Its gradient is L-Lipschitz, with L>0. At each point, the objective gap is at least μ/2 times the squared distance to some global minimizer, where μ>0. A given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For ε>0, gradient descent with positive predetermined step sizes must return a last iterate x¯ satisfying f(x¯)−f(x⋆)≤ε almost surely.

The optimization problem is minx∈Ef(x). The norm is induced by the inner product on E. The algorithm receives only E, L, and x0; the parameters μ, R, and ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 4 (Quadratic growth). For every x∈E, there exists a global minimizer z∈E, possibly depending on x, such that μ2∥x−z∥2≤f(x)−f(z).

Our result is algorithm-specific: we analyze gradient descent. The step-size sequence (ηt)t≥0 is chosen from the algorithm inputs and satisfies ηt>0 for every t. Starting from the given x0, the iterates obey xt+1=xt−ηt∇f(xt),t=0,1,2,…. After K≥0 oracle calls, where K is an integer, the output is the last iterate x¯=xK. The required accuracy is f(x¯)−f(x⋆)≤εP-a.s., where P is the law of the algorithm’s randomness; the specified gradient descent method is deterministic.

Results

Convex f on a real Hilbert space has an exact L-Lipschitz gradient, L,μ,ε>0, and a minimizer x⋆ with ∥x0−x⋆∥≤R, R≥0. For every x, some minimizer z satisfies f(x)−f(z)≥μ2∥x−z∥2. The setup restricts algorithms to GD with predetermined positive stepsizes and current-iterate output. Target: f(xK)−f(x⋆)≤ε almost surely. In (1), updates use only L; μ,R,ε enter the stopping budget.

Smooth convex optimization with quadratic growth: SmoothConvexQuadraticGrowth.
Result Oracle complexity Novelty Limitations
(1) UniversalSilverQuadraticGrowth (Ours) (⋆⋆) (review) O((1+κ)pℓ
⋅[1+log⁡(1+κ)+log⁡ℓ])
(2) Restarted AGD (Fercoq and Qu 2017, Thm. 2, Sec. 3.4) O(1+κ[ℓ+log⁡(1+κ)])
Includes restart tests; smooth unconstrained specialization in Rd.
(1): Predetermined GD with anytime last-iterate accuracy; (2) adaptively restarts AGD and returns a stopped output. No complexity improvement; updates already need no μ. (1): Exponent p instead of 1/2, with extra logarithms; requires global QG instead of initial-sublevel QG.
(3) Anytime GD (Zhang et al. 2025, Thm. 11, arXiv v2) O(κqℓ)
Special case: μ-strong convexity in Rd.
(1): Scope: QG instead of strong convexity. Adaptivity: no μ. Rate on overlap: p≈0.786 instead of q≈0.893; total gain when κq−p≫1+log⁡κ+log⁡ℓ. (1): Extra 1+log⁡κ+log⁡ℓ factor. Crossover depends on unspecified constants; the unit-constant illustration exceeds κ≈1015.
(4) Silver GD (Altschuler and Parrilo 2023, Thm. 1.1) O(κpℓ)
Special case: μ-strong convexity; prescribed horizons. Distance contraction converted to objective gap.
(1): Scope: QG instead of strong convexity. Adaptivity: neither κ nor horizon needed; anytime last-iterate accuracy instead of prescribed-horizon accuracy. (1): Extra 1+log⁡κ+log⁡ℓ factor on the strongly convex overlap.
(5) Restarted long-step GD (Grimmer et al. 2024, Remark 3) O((1+κ)pℓ)
Derived bound: convex PL restart in Rd; QG implies PL up to universal factors. Block-end objective accuracy.
(1): No μ needed to choose block lengths; anytime last-iterate accuracy instead of block-end accuracy. Matches the condition-number exponent; no QG scope gain. (1): Extra 1+log⁡(1+κ)+log⁡ℓ factor.
(6) Constant-step GD, 1/L (Fercoq and Qu 2017, sec. 2.1) O((1+κ)ℓ)
QG/PL specialization of the classical proximal-gradient bound.
(1): Rate: κ0.786 instead of κ, up to logarithms; total gain when κ1−p≫1+log⁡κ+log⁡ℓ. No adaptivity gain: (6) is already anytime and μ-free. (1): Larger leading constants and logarithmic overhead; savings require sufficiently large κ.

Abbr: Costs count exact gradient calls. κ=L/μ, ℓ=1+log⁡(1+LR2/ε), p=log⁡2/log⁡(1+2), q=(1+p)/2. GD: gradient descent; AGD: accelerated gradient descent; QG: quadratic growth; PL: Polyak–Łojasiewicz inequality. Anytime: accuracy at every sufficiently large iteration; (1) exports the stated stopping budget.

Altschuler, Jason M., and Pablo A. Parrilo. 2023. Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule. https://doi.org/10.48550/arXiv.2309.07879.
Fercoq, Olivier, and Zheng Qu. 2017. Adaptive Restart of Accelerated Gradient Methods Under Local Quadratic Growth Condition. https://doi.org/10.48550/arXiv.1709.02300.
Grimmer, Benjamin, Kevin Shu, and Alex L. Wang. 2024. Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps. https://doi.org/10.48550/arXiv.2403.14045.
Zhang, Zihan, Jason D. Lee, Simon S. Du, and Yuxin Chen. 2025. “Anytime Acceleration of Gradient Descent.” Proceedings of Thirty Eighth Conference on Learning Theory, Proceedings of machine learning research, vol. 291: 5991–6013. https://proceedings.mlr.press/v291/zhang25a.html.

Lean setup