Accelerated 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.AcceleratedConvex.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.