← All setups

Lipschitz Composite Generalized Accelerated — Generalized Smooth Composite Minimization

Descriptions may be stale. Consult the linked Lean sources.

Generalized Smooth Composite Minimization · Lean proof

Generalized Smooth Composite Minimization

We minimize F=f+ψ on a real Hilbert space E, where f:E→R is convex and continuously differentiable, and ψ:E→R is convex and M-Lipschitz, with M≥0. The function f is (L0,L1)-smooth, with L0,L1>0. A given point x0∈E satisfies ∥x0−x⋆∥≤R for some global minimizer x⋆ of F, where R>0. The oracle returns exact gradients, regularizer values, and proximal points. 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. The algorithm receives only E, L0, L1, M, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity and Lipschitz regularizer). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y). Moreover, for all x,y∈E, |ψ(x)−ψ(y)|≤M∥x−y∥.

Assumption 2 (Generalized smoothness). The function f is Fréchet differentiable everywhere on E, and ∇f:E→E is continuous. For every x,y∈E and S∈R, the implication ∥∇f(x+θ(y−x))∥≤Sfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1S)∥x−y∥ holds.

Assumption 3 (Exact proximal minimization). There is a map T:R×E×E→E such that, for every a>0 and z,v∈E, T(a,z,v)∈argminu∈E{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}.

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

The oracle returns ∇f(x) at x. It also returns ψ(x) for a value query at x, and T(a,z,v) for a proximal query (a,z,v)∈R×E×E. Each query counts as one call toward a shared oracle-call budget. All point queries may be made anywhere in E.

After the allotted calls, the output must satisfy F(x¯)−F(x⋆)≤εP-a.s. The minimizer in this requirement is fixed independently of the algorithm’s randomness.

Proved result

⌈184⋅(L0+L1⋅M)⋅R2ε+130000⋅(1+L1⋅R)⋅log⁡(2+L1⋅R)⌉+

OracleTemplate.Convergence LongTails.Setups.LipschitzCompositeGeneralizedSmooth.spec
  OracleTemplate.CompositeSherpa.budget

Relevant previous results

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