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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Smoothness). The function
Assumption 3 (Initial distance). There exists
Assumption 4 (Quadratic growth). For every
Our result is algorithm-specific: we analyze gradient descent. The
step-size sequence
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) UniversalSilverQuadraticGrowth
(Ours) |
|||
| (2) Restarted AGD (Fercoq and Qu 2017, Thm. 2, Sec. 3.4) | Includes restart tests; smooth unconstrained specialization in |
(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 |
| (3) Anytime GD (Zhang et al. 2025, Thm. 11, arXiv v2) | Special case: |
(1): Scope: QG instead of
strong convexity. Adaptivity: no |
(1): Extra |
| (4) Silver GD (Altschuler and Parrilo 2023, Thm. 1.1) | Special case: |
(1): Scope: QG instead of
strong convexity. Adaptivity: neither |
(1): Extra |
| (5) Restarted long-step GD (Grimmer et al. 2024, Remark 3) | Derived bound: convex PL restart in |
(1): No |
(1): Extra |
| (6) Constant-step GD,
|
QG/PL specialization of the classical proximal-gradient bound. |
(1): Rate: |
(1): Larger leading
constants and logarithmic overhead; savings require sufficiently large
|
Abbr: Costs count exact gradient calls.