← All setups

Dynamic Mirror Generalized Acceleration — Generalized Smooth Convex Mirror Geometry

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Convex Mirror Geometry · Lean proof

Generalized Smooth Convex Mirror Geometry

We minimize a differentiable convex function f:E→R on a finite-dimensional real normed space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A differentiable mirror function ψ:E→R induces a Bregman divergence Bψ dominating half the squared norm. A given point x0∈E satisfies Bψ(x⋆,x0)≤D and f(x0)−f(x⋆)≤Δ for a minimizer x⋆, where D,Δ>0. The oracle returns exact derivatives and Bregman proximal minimizers. For ε>0, the goal is f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). Write E∗ for the continuous dual of E. Derivatives ∇f(x) and ∇ψ(x) belong to E∗, and their norms are the induced operator norms ∥⋅∥op. Define Bψ(u,z)=ψ(u)−ψ(z)−∇ψ(z)[u−z]. The algorithm receives E, L0, L1, D, Δ, and x0; the tolerance ε may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is everywhere Fréchet differentiable, its derivative is continuous, and f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1]. Its (L0,L1)-smoothness means that, for every x,y∈E and M∈R, ∥∇f(x+θ(y−x))∥op≤Mfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥op≤(L0+L1M)∥x−y∥.

Assumption 2 (Mirror geometry and proximal access). The function ψ is everywhere Fréchet differentiable and satisfies Bψ(y,x)≥12∥y−x∥2,x,y∈E. For every z∈E and v∈E∗, a selected proximal minimizer exists: proxψ(z,v)∈argminu∈E⁡{v[u]+Bψ(u,z)}.

Assumption 3 (Initial bounds). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,Bψ(x⋆,x0)≤D,f(x0)−f(x⋆)≤Δ.

The oracle returns ∇f(x) at x. It also returns proxψ(z,v) on a query (z,v)∈E×E∗. Both types of queries are exact, may be made anywhere in their stated domains, and count toward a single total oracle-call budget.

After the allotted calls, the output x¯∈E must satisfy f(x¯)−f(x⋆)≤εP-a.s., where the global minimizer x⋆ is fixed independently of the algorithm’s randomness.

Proved result

3⋅⌈24576⋅(1+2⋅L0⋅Dε+(1+2⋅L1⋅D)⋅log⁡(2+2⋅Δε))⌉+

OracleTemplate.Convergence LongTails.Setups.MirrorGeneralizedSmooth.spec
  LongTails.Theorems.DynamicMirrorGeneralizedAcceleration.budget

Relevant previous results