← All setups

Convex Minimization with Unknown Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Unknown Smoothness

We consider minimizing a differentiable convex function f:E→R on a real Hilbert space E. Its gradient is L-Lipschitz for an unknown constant L>0, and a given starting point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns ∇f(x) at x. For a tolerance ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness. Only E and x0 are algorithm inputs.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The parameters L, R, and ε may enter the oracle-call budget but are not supplied to the algorithm.

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

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

Queries may be made at any point of E. After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s.

Results

    Lean setup