← All setups

High Dimensional Strong Quasar Upper Bound — High-Dimensional Strong Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Strong Quasar Minimization · Lean proof

High-Dimensional Strong Quasar Minimization

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R with an L-Lipschitz gradient, where d is the dimension and L>0. The function is strongly quasar-convex toward a global minimizer x⋆, with parameters μ>0 and 0<γ≤1/256. A given starting point x0∈Rd satisfies f(x0)−f(x⋆)≤Δ, where Δ≥0. The oracle returns ∇f(x) at x. For ε>0, the goal is an output x¯∈Rd with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s randomness.

The optimization problem is minx∈Rdf(x). We use the Euclidean inner product ⟨⋅,⋅⟩ and its induced norm ∥⋅∥. The algorithm receives d, L, x0, μ, γ, Δ, and ε.

Our assumptions:

Assumption 1 (Parameter and dimension regime). The dimension d is a nonnegative integer. In addition to the parameter ranges above, define κ=L/μ and require 870400μ≤L,4μ≤γ2L,1000γκε≤Δ,(κγ)5(Δ1000γκε)3≤d.

Assumption 2 (Smoothness). The function f is Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈Rd.

Assumption 3 (Strong quasar convexity and initial gap). There exists a global minimizer x⋆∈Rd satisfying the stated initial objective-gap bound such that, for every x∈Rd, f(x)−f(x⋆)≤1γ⟨∇f(x),x−x⋆⟩−μ2∥x−x⋆∥2.

Queries may be made at any point of Rd. After the allotted oracle calls, the output must have an integrable objective gap under P and satisfy EP[f(x¯)−f(x⋆)]≤ε.

Proved result

⌈32⋅Lμγ⌉+⋅clog2(⌈1+2⋅Δγ⋅ε⌉+)

OracleTemplate.Convergence LongTails.Setups.HighDimensionalStrongQuasar.spec
  LongTails.Theorems.HighDimensionalStrongQuasarUpperBound.budget

Relevant previous results