← All setups

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 f:Rd→R with L-Lipschitz gradient, where d is a nonnegative integer and L>0. A given point x0∈Rd lies within Euclidean distance R>0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is a random output x¯∈Rd with integrable objective gap and EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness. The parameters satisfy the accuracy and dimension restrictions specified below.

The optimization problem is minx∈Rdf(x). Throughout, ∥⋅∥ denotes the Euclidean norm. The algorithm receives d, L, x0, R, and ε.

Our assumptions:

Assumption 1 (Parameter regime). The parameters satisfy d∈Z≥0 and L,R,ε>0, with 262144ε≤LR2,65536(⌊LR2/ε512⌋+1)5≤d.

Assumption 2 (Convexity and smoothness). The function f is differentiable everywhere on Rd. For every x,y∈Rd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 3 (Initial distance). There exists x⋆∈Rd such that f(x⋆)≤f(x)for every x∈Rd,∥x0−x⋆∥≤R.

Queries may be made at any point of Rd. After the allotted oracle calls, the output x¯ must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Proved result

⌊L⋅R2ε512⌋+

OracleTemplate.NonConvergence LongTails.Setups.SmoothAndConvexExpected.spec
  LongTails.Theorems.SmoothConvexExpectedLowerBound.budget

Relevant previous results

  • Jelena Diakonikolas and Cristóbal Guzmán. Lower Bounds for Parallel and Randomized Convex Optimization. 2020. Complexity: Ω(LR2/ε) sequential local-oracle calls for randomized algorithms achieving objective gap ε with probability at least 1−γ, for constant γ∈(0,1) and d=Ω((LR2/ε)3/2log⁡(LR2/ε)); the oracle can supply exact function values and gradients.