Universal Silver Quadratic Growth — Gradient Descent with Quadratic Growth
Descriptions may be stale. Consult the linked Lean sources.
Gradient Descent with Quadratic Growth · Lean proof
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
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothConvexQuadraticGrowth.spec
LongTails.Theorems.UniversalSilverQuadraticGrowth.budgetRelevant previous results
- Mingrui Liu and Tianbao Yang. Adaptive Accelerated Gradient
Converging Methods under Hölderian Error Bound Condition. 2017 (NIPS
publication; preprint first posted 2016, version used: May 2017).
Complexity:
exact-gradient calls for adaAGC to obtain , including initialization and gradient tests; , , initial error-bound estimate and doubling factor . - Olivier Fercoq and Zheng Qu. Adaptive restart of
accelerated gradient methods under local quadratic growth condition.
2019 (IMA Journal of Numerical Analysis; version used: September 2017
preprint). Complexity:
exact-gradient calls for AdaRES to obtain , including initialization and restart tests; , , initial normalized growth estimate .