← All setups

Continuized Similar Quasar — Similar Finite-Sum Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

Similar Finite-Sum Quasar Minimization · Lean proof

Similar Finite-Sum Quasar Minimization

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 and the functions fi:E→R are differentiable. The possibly nonconvex objective F has an L-Lipschitz gradient and is strongly quasar-convex with parameters 0<μ≤L and 0<γ≤1 relative to a global minimizer x⋆. Component-gradient deviations from ∇F satisfy a mean-square Lipschitz bound with constant δ≥0. A given point x0∈E satisfies F(x0)−F(x⋆)≤Δ, where Δ≥0. At (i,x), the oracle returns ∇fi(x). For ε>0, the goal is an output x¯∈E with integrable objective gap and EP[F(x¯)−F(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈EF(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, n, L, μ, γ, δ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Differentiability and smoothness). Each fi is Fréchet differentiable everywhere on E. The average gradient satisfies ∥∇F(x)−∇F(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Mean-square gradient similarity). Define di(x)=∇fi(x)−∇F(x). For every x,y∈E, 1n∑i=1n∥di(x)−di(y)∥2≤δ2∥x−y∥2.

Assumption 3 (Strong quasar-convexity and initial gap). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,F(x0)−F(x⋆)≤Δ. For this same minimizer and every x∈E, γF(x)+⟨∇F(x),x⋆−x⟩+γμ2∥x⋆−x∥2≤γF(x⋆).

Queries may use any component i∈{1,…,n} and any point x∈E. After the allotted component-gradient calls, the output must have an integrable objective gap and satisfy EP[|F(x¯)−F(x⋆)|]<∞,EP[F(x¯)−F(x⋆)]≤ε.

Proved result

(n+max{1,⌈8⋅Lμγ+4096⋅δ2γ3⋅μ2⌉+})⋅max{1,clog2(⌈1+2⋅Δγ⋅ε⌉+)}

OracleTemplate.Convergence LongTails.Setups.ContinuizedSimilarQuasar.spec OracleTemplate.ContinuizedSimilarQuasar.budget

Relevant previous results

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