← All setups

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

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Constrained Quasar Minimization · Lean proof

High-Dimensional Constrained Quasar Minimization

We minimize a possibly nonconvex function f:Rd→R over a compact convex set X of diameter at most D>0. On X, its gradient is L-Lipschitz, with L>0, and f is γ-quasar-convex relative to a minimizer x⋆∈X, with 0<γ≤1. Two oracles return unbiased stochastic gradients with variance at most σ2, where σ≥0, using independent binary samples, and exact projections onto X. For ε>0 and 0<δ≤1/4, the goal is a measurable output x¯ satisfying x¯∈X and f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈Xf(x). We use the Euclidean inner product and norm on Rd. A starting point x0∈X is given. The algorithm receives d,x0,L,D,γ,σ,ε,δ and accesses the objective and feasible set through the two oracles.

The parameters satisfy d∈N,L,D,ε>0,σ≥0,0<γ≤1,0<δ≤14,108ε≤LD2,σ=0or64γε≤σD. To state the dimension requirement, define m=⌊LD2/ε10000γ+σ2D2log⁡(1/δ)8192γ2ε2⌋. The required regime is 234(m+1)5≤d.

Our assumptions:

Assumption 1 (Feasible set and minimizer). The set X⊆Rd is compact and convex, contains x0 and a fixed point x⋆, and satisfies ∥x−y∥≤Dfor all x,y∈X,f(x⋆)≤f(x)for all x∈X.

Assumption 2 (Smoothness and quasar convexity). The function f is Fréchet differentiable at every point of X. For all x,y∈X, ∥∇f(x)−∇f(y)∥≤L∥x−y∥. Its quasar-convexity condition is γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩,x∈X.

Assumption 3 (Stochastic gradient oracle). There is a probability distribution ν on {0,1} and a jointly measurable map g:Rd×{0,1}→Rd. For each x∈X, the vector g(x,ξ) is Bochner integrable and its squared error is integrable under ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. The samples ξ0,ξ1,… are measurable, mutually independent, have common law ν, and are independent of the algorithm’s randomness. At the kth oracle call, a stochastic gradient query at x returns g(x,ξk).

Assumption 4 (Projection oracle). The projection oracle returns ΠX(z) at z∈Rd, where ΠX(z)∈X,⟨z−ΠX(z),w−ΠX(z)⟩≤0,w∈X.

Both oracles accept queries anywhere in Rd; the gradient and moment conditions above apply on X. Stochastic gradient calls and projection calls are counted separately. After the allotted calls, the output x¯∈Rd must be measurable and satisfy PP(x¯∈X and f(x¯)−f(x⋆)≤ε)≥1−δ, where P is the joint law of the algorithm’s randomness and the independent oracle samples.

Proved result

Oracle 0:⌈296⋅(2+⌈8⋅log⁡(8δ)⌉+)⋅(1+clog2(⌈2+L⋅D2γ2⋅ε⌉+))2⋅(1+L⋅D2εγ+σ2⋅D2γ2⋅ε2)⌉+ Oracle 1:⌈296⋅(2+⌈8⋅log⁡(8δ)⌉+)⋅(1+clog2(⌈2+L⋅D2γ2⋅ε⌉+))2⋅(1+L⋅D2εγ+σ2⋅D2γ2⋅ε2)⌉+

OracleTemplate.Convergence LongTails.Setups.HighDimensionalConstrainedQuasar.spec
  LongTails.Theorems.HighDimensionalConstrainedQuasarUpperBound.budget

Relevant previous results

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