← All setups

Backtracking Generalized Accelerated — Convex Minimization with Hidden Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Hidden Smoothness · Lean proof

Convex Minimization with Hidden Smoothness

We consider minimizing a convex function f:E→R on a real Hilbert space E. The function f is (L0,L1)-smooth with hidden constants L0>0 and L1≥0, and has a differentiable gradient. A given point x0∈E satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ for a global minimizer x⋆ and hidden bounds R,Δ>0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The algorithm receives only E, x0, and a scalar h0>0; the parameters L0,L1,R,Δ, and ε may enter the oracle-call budget but are not algorithm inputs.

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 (Generalized smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient ∇f:E→E is Fréchet differentiable everywhere. Its Hessian ∇2f(x):E→E satisfies ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈E.

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

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. The minimizer x⋆ is fixed independently of the algorithm’s randomness.

Proved result

2⋅⌈5+4⋅32⋅L0⋅R2ε+26⋅(1+L1⋅R)⋅log⁡(1+(2+13⋅L1⋅R)2⋅(2+1h0⋅(1L0⋅164)+16⋅L0⋅h0+5⋅L12⋅Δ4⋅L0+80⋅L12⋅Δ⋅h0))⌉+

OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothParameterFree.spec
  OracleTemplate.ParameterFreeGeneralized.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.