← All setups

Stochastic Constrained Quasar High Probability — Stochastic Constrained Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Constrained Quasar Minimization · Lean proof

Stochastic Constrained Quasar Minimization

We consider minimizing f:E→R over a compact convex set X in a finite-dimensional real Hilbert space E. On X, the function has an L-Lipschitz gradient, where L>0, and is γ-quasar-convex relative to a minimizer x⋆∈X, where 0<γ≤1. The oracles return unbiased stochastic gradients with bounded variance using independent, identically distributed samples, and exact Euclidean projections onto X. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying both x¯∈X and f(x¯)−f(x⋆)≤ε with probability at least 1−δ over sampling and algorithm randomness.

The optimization problem is minx∈Xf(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, the measurable sample space Ω, a starting point x0, and the parameters L,D>0, γ∈(0,1], σ≥0, ε>0, and δ∈(0,1); the objective, feasible set, minimizer, and sampling distribution are accessed through the oracles.

Our assumptions:

Assumption 1 (Feasible geometry). The set X⊆E is compact and convex, contains x0 and x⋆, and satisfies ∥x−y∥≤D,x,y∈X.

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

Assumption 3 (Stochastic gradient oracle). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈X, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. The oracle uses a sequence (ξk)k≥0 of measurable, mutually independent sample variables, each with law ν, independent of the algorithm’s randomness. At a stochastic gradient call with query x, it returns g(x,ξk) using the sample at that call’s index.

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

Both oracles accept queries throughout E; the gradient and moment conditions above apply on X. Stochastic gradient calls and projection calls have separate budgets. After these calls, the output x¯∈E must be measurable and satisfy P{x¯∉X or f(x¯)−f(x⋆)>ε}≤δ, where P is the joint law of the samples and the independent algorithm randomness.

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.StochasticConstrainedQuasar.spec OracleTemplate.StochasticQuasar.budget

Relevant previous results

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