← All setups

Generalized Gradient Sliding — Composite Generalized Smooth Minimization

Descriptions may be stale. Consult the linked Lean sources.

Composite Generalized Smooth Minimization · Lean proof

Composite Generalized Smooth Minimization

We minimize F=f+h over a convex set Q in a real Hilbert space E, where f,h:E→R. The function f is convex and (L0,L1)-smooth, with L0>0 and L1≥0; h admits bounded supporting subgradients on Q. A given point x0∈Q has bounded distance and objective gap to a minimizer x⋆, where the gradient of f is bounded. Oracles return exact gradients of f, bounded subgradients of h, and exact projections onto Q. For ε>0, the goal is x¯∈Q with F(x¯)−F(x⋆)≤ε almost surely under P, the joint law of algorithm and oracle randomness.

More precisely, define F(x)=f(x)+h(x) and consider minx∈QF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, x0, and all parameters L0,L1,M,R,Δ,G,ε, whose ranges are L0,R,Δ,ε>0,L1,M,G≥0. The functions and feasible set are accessed through the three oracles described below.

Our assumptions:

Assumption 1 (Convexity and feasibility). The set Q⊆E is convex and x0∈Q. 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, with continuous gradient. Its (L0,L1)-smoothness means that, for every x,y∈E and B∈R, ∥∇f(x+θ(y−x))∥≤Bfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1B)∥x−y∥.

Assumption 3 (Solution and initial bounds). There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,∥∇f(x⋆)∥≤G.

Assumption 4 (Oracle access). The gradient oracle returns ∇f(x) at x∈E. At each u∈Q, every reply s∈E of the subgradient oracle satisfies ∥s∥≤M,h(u)+⟨s,v−u⟩≤h(v)for every v∈Q. These conditions hold for every query history and every realization of oracle randomness. Subgradient queries outside Q carry no guarantee. At any w∈E, the projection oracle returns a point p∈Q satisfying ∥w−p∥≤∥w−u∥for every u∈Q.

Gradient, subgradient, and projection calls are counted separately. Oracle randomness may be dependent across calls, and subgradient replies may depend on the query history; the algorithm’s randomness is independent of the oracle’s randomness. After the allotted calls, the output must satisfy x¯∈Q,F(x¯)−F(x⋆)≤εP-a.s.

Proved result

Oracle 0:2⋅⌈20⋅(L0+L1⋅G)⋅R2ε+(6+320⋅L1⋅R)⋅log⁡(2+(3+240⋅L1⋅R)⋅ΔL0⋅R2)⌉+ Oracle 1:8⋅⌈20⋅(L0+L1⋅G)⋅R2ε+(6+320⋅L1⋅R)⋅log⁡(2+(3+240⋅L1⋅R)⋅ΔL0⋅R2)⌉++⌈768⋅M2⋅R2ε2⌉+ Oracle 2:8⋅⌈20⋅(L0+L1⋅G)⋅R2ε+(6+320⋅L1⋅R)⋅log⁡(2+(3+240⋅L1⋅R)⋅ΔL0⋅R2)⌉++⌈768⋅M2⋅R2ε2⌉+

OracleTemplate.Convergence LongTails.Setups.SlidingGeneralizedSmooth.spec OracleTemplate.GeneralizedSliding.budget

Relevant previous results

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