Accelerated Convex Expected — Expected Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Expected Smooth Convex Minimization · Lean proof
Expected Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter regime). The parameters
satisfy
Assumption 2 (Convexity and smoothness). The
function
Assumption 3 (Initial distance). There exists
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.SmoothAndConvexExpected.spec
OracleTemplate.Gradient.AcceleratedConvexExpected.budgetRelevant previous results
- Yurii E. Nesterov. A method of
solving a convex programming problem with convergence rate O(1/k²).
1983. Complexity:
exact-gradient calls for objective gap at most , using Nesterov’s accelerated method with known ; no function-value calls are required.