← All setups

Cached 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 potentially nonconvex objective has a Lipschitz gradient, satisfies a quadratic lower model, and obeys strong quasar-convexity and quadratic growth relative to a global minimizer x⋆. Component-gradient deviations from the mean are Lipschitz with a restricted similarity constant. A given point x0∈E has bounded objective gap. The oracle returns ∇fi(x) at a queried pair (i,x). For ε>0, the goal is an output x¯∈E with F(x¯)−F(x⋆)≤ε almost surely under the algorithm’s randomness.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E. The parameters satisfy 0<μ≤L,0<γ≤1,δ≥0,384δ2≤γ3μ2,Δ≥0,ε>0. The algorithm receives E, n, L, μ, γ, δ, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Smoothness and component similarity). Each fi is Fréchet differentiable everywhere on E. For every x,y∈E and i∈{1,…,n}, ∥∇F(x)−∇F(y)∥≤L∥x−y∥,∥(∇fi(x)−∇F(x))−(∇fi(y)−∇F(y))∥≤δ∥x−y∥.

Assumption 2 (Quadratic lower model). For every x,y∈E, F(x)+⟨∇F(x),y−x⟩−γμ2μ/L∥y−x∥2≤F(y).

Assumption 3 (Strong quasar-convexity and quadratic growth). There exists a global minimizer x⋆∈E such that F(x0)−F(x⋆)≤Δ, and, for every x∈E, γF(x)+⟨∇F(x),x⋆−x⟩+γμ2∥x−x⋆∥2≤γF(x⋆),γμ2(2−γ)∥x−x⋆∥2≤F(x)−F(x⋆).

Queries may use any component index i∈{1,…,n} and any point x∈E. After the allotted component-gradient calls, the output must satisfy F(x¯)−F(x⋆)≤εP-a.s., where P is the law of the algorithm’s randomness.

Proved result

(n+⌈2⋅Lμγ⋅log⁡(1+148⋅δ2γ3⋅μ2+γ⋅ε16⋅(γ⋅ε+2⋅Δ))⌉+)⋅⌈log⁡(1+2⋅Δγ⋅ε)log⁡(148⋅δ2γ3⋅μ2+γ⋅ε16⋅(γ⋅ε+2⋅Δ)⋅12)⌉+

OracleTemplate.Convergence LongTails.Setups.SimilarFiniteSumQuasar.spec OracleTemplate.SimilarQuasar.budget

Relevant previous results

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