← All setups

Stochastic Constrained Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

A finite-dimensional real Hilbert space; compact convex X of diameter at most D>0, with x0,x⋆∈X and x⋆∈arg⁡minXf. The differentiable objective has L-Lipschitz gradient on X, L>0, and γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for x∈X, 0<γ≤1. Access: exact projection and jointly measurable IID stochastic gradients, with ∫g(x,ω)dp=∇f(x) and ∫∥g(x,ω)−∇f(x)∥2dp≤σ2. Target: P{x^∈X, f(x^)−f(x⋆)≤ε}≥1−δ, ε>0, 0<δ<1.

Comparison for StochasticConstrainedQuasar.
Result Oracle complexity Novelty Limitations
(1) StochasticConstrainedQuasarHighProbability (Ours) (⋆⋆⋆) (review) O(hℓ2[1+LD2/εγ+σ2D2γ2ε2]) gradient-plus-projection calls.
(2) (Martínez-Rubio 2026), Thm. 5 O(ℓ2[1+γ−1LD2/ε]) value, gradient and projection calls; deterministic, σ=0. (1): Scope: finite-variance stochastic gradients. Oracle: removes function values. Matches deterministic polynomial rate at σ=0. (1): At σ=0, pays h and gives probability 1−δ rather than certainty.
(3) QASGD (Fu et al. 2023), Cor. 3.3 O([1+RL/ε+σ2R2γ2ε2]ℓR(ε)) component value/gradient calls; expected gap. Unconstrained; L-smooth components, bounded gradient second moment. (1): Scope: constrained boundary minimizers; variance instead of gradient-second-moment bound. Oracle: no component values. High-confidence guarantee. (1): Needs compact X, known D; D replaces R, potentially costly for R≪D.
(4) Derived bound: (Fu et al. 2023), Cor. 3.3 + Markov O([1+RL/(εδ)+σ2R2γ2ε2δ2]ℓR(εδ)) component value/gradient calls; confidence 1−δ. Restrictions of (3). (1): On overlap with R≍D, noise-term confidence dependence becomes hℓ2 instead of δ−2ℓR(εδ); improves when the latter dominates. (1): Requires a known compact feasible set containing a global minimizer; D may greatly exceed R.

Abbr: h=1+log⁡(1/δ); ℓ=1+log⁡(2+LD2/(γ2ε)); ℓR(a)=1+log⁡(1+LR2/(γa)); R bounds initial distance to a global minimizer. In (3), (4), σ2 bounds the stochastic gradient’s second moment. p is the sample law and P the IID sequence law. Costs include search and inner-solve calls.

Fu, Qiang, Dongchu Xu, and Ashia Camage Wilson. 2023. “Accelerated Stochastic Optimization Methods Under Quasar-Convexity.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 10431–60. https://proceedings.mlr.press/v202/fu23e.html.
Martínez-Rubio, David. 2026. “Fast Quasar-Convex Optimization with Constraints.” Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, Proceedings of machine learning research, vol. 300: 3340–48. https://proceedings.mlr.press/v300/martinez-rubio26a.html.

Lean setup