Smooth Convex Expected Lower Bound — 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.NonConvergence LongTails.Setups.SmoothAndConvexExpected.spec
LongTails.Theorems.SmoothConvexExpectedLowerBound.budgetRelevant previous results
- Jelena Diakonikolas and Cristóbal Guzmán. Lower Bounds
for Parallel and Randomized Convex Optimization. 2020. Complexity:
sequential local-oracle calls for randomized algorithms achieving objective gap with probability at least , for constant and ; the oracle can supply exact function values and gradients.