← All setups

Backtracking Composite Generalized — Parameter-Free Composite Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Parameter-Free Composite Convex Minimization · Lean proof

Parameter-Free Composite Convex Minimization

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f:E→R is convex and continuously differentiable and ψ:E→R is convex on Q. The function f is (L0,L1)-smooth with hidden constants L0>0 and L1≥0. A given point x0∈Q has bounded distance and objective gap to a minimizer x⋆, whose smooth gradient is bounded. The oracle returns exact gradients and constrained proximal minimizers. For ε>0, the goal is x¯∈Q with F(x¯)−F(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

Write F(x)=f(x)+ψ(x). The optimization problem is minx∈QF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The algorithm receives only E, x0, and a scalar h0>0; the parameters L0>0, L1≥0, R>0, Δ>0, G≥0, and ε>0 may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Convexity). The set Q⊆E is convex, f is convex on E, and ψ is convex on Q. Thus, for t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y),x,y∈Q.

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 M∈R, the segment bound ∥∇f(x+t(y−x))∥≤Mfor every t∈[0,1] implies ∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥.

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

Assumption 4 (Initial point and minimizer). The given point satisfies x0∈Q. There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,∥∇f(x⋆)∥≤G.

The oracle returns ∇f(x) at x. A proximal query (a,z,v) returns P(a,z,v). Gradient queries may use any x∈E, and proximal queries may use any a∈R and z,v∈E; the proximal minimization condition applies when a>0. Both query types count toward a single total oracle-call budget.

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

Proved result

3⋅⌈4+61⋅(L0+L1⋅G)⋅R2ε+(35+1067⋅L1⋅R)⋅log⁡(1+(12+400⋅L1⋅R)⋅(1+1(L0+L1⋅G)⋅h0+L1⋅ΔL0+L1⋅G))+4⋅log⁡(52+1h0⋅(1L0+L1⋅G⋅116)+22⋅L12⋅ΔL0+L1⋅G)+2⋅log⁡(2⋅((1+h0⋅(40⋅(L0+L1⋅G)+400⋅L12⋅Δ))⋅(8⋅(1+32⋅L1⋅R)2+200⋅L12⋅R2)))⌉+

OracleTemplate.Convergence LongTails.Setups.CompositeGeneralizedParameterFree.spec
  OracleTemplate.CompositeParameterFree.budget

Relevant previous results

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