Gd Convex — Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Convex Minimization · Lean proof
Smooth Convex Minimization
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
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothAndConvex.spec OracleTemplate.Gradient.GdConvex.budgetRelevant previous results
- Yu. E. Nesterov. A method of solving a
convex programming problem with convergence rate O(1/k²). 1983.
Complexity:
fixed exact-gradient oracle calls for , using known- accelerated gradient in Hilbert space; no function-value calls. - Amir Beck and Marc Teboulle. A Fast Iterative
Shrinkage-Thresholding Algorithm for Linear Inverse Problems. 2009.
Complexity:
fixed exact-gradient oracle calls for in , using constant-step ISTA with (gradient descent); no function-value calls.