← All setups

High-Dimensional Constrained Quasar Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Compact convex X⊂Rd, x0,x⋆∈X, diam(X)≤D, and x⋆∈arg⁡minXf. On X, f is differentiable, ∇f is L-Lipschitz, and γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩. The jointly measurable gradient oracle uses IID Boolean samples, is unbiased on X, and has integrable squared error with variance at most σ2; the other channel gives exact Euclidean projections. No algorithm restriction is imposed; gradient replies outside X are unrestricted. Here L,D,ε>0, 0<γ≤1, σ≥0, 0<δ≤1/4, LD2/ε≥108, σ=0 or σD≥64γε, and d≥234(B+1)5. Target: P{x^∈X, f(x^)−f(x⋆)≤ε}≥1−δ under the IID execution law P. On this exact setup, (1) and (2) leave at most a factor O(log⁡(1/δ)ℓ2) between necessary and sufficient total calls.

High-dimensional constrained quasar-convex optimization: necessary and sufficient budgets for HighDimensionalConstrainedQuasar.
Result Oracle complexity Novelty Limitations
(1) HighDimensionalConstrainedQuasarLowerBound (Ours) (⋆⋆) (review) Ω(DL/εγ+σ2D2log⁡(1/δ)γ2ε2) total calls. Every randomized algorithm fails on some instance at every b≤(B,B); the hard instance can return zero outside X.
(2) HighDimensionalConstrainedQuasarUpperBound (Ours) (review) O(log⁡(1/δ)ℓ2[DL/εγ+σ2D2γ2ε2]) total gradient and projection calls, including all batches and trials.
(3) (Hinder et al. 2020), Theorem 3 Ω(RL/εγ) exact-gradient calls; deterministic algorithms, unconstrained objectives. Transfers to a ball with D=2R; requires LR2/ε≥1. (1): Same deterministic-term order for every randomized algorithm. The additional 1/γ information concerns γ<1/100; larger γ uses the convex chain. (1): Needs polynomially large dimension; allows uninformative exterior replies and establishes no randomized lower bound for the unconstrained oracle model.

Abbr: ℓ=log⁡(LD2/(γ2ε)); log+⁡t=max{1,log⁡t}; R bounds initial distance to a minimizer; H2 bounds the stochastic-gradient second moment; T is the noisy-gradient query count in (4). B=⌊DL/ε/(10000γ)+σ2D2log⁡(1/δ)/(8192γ2ε2)⌋; b is the vector of gradient/projection budgets, ordered componentwise.

HighDimensionalConstrainedQuasar (continued).
Result Oracle complexity Novelty Limitations
(4) (Saad et al. 2025), Theorem 3.4 Ω(σ2D2γ2ε2log⁡(2/γ)) noisy-gradient calls for expected gap ≤ε on a ball of diameter D; Gaussian oracle. (1): High-probability noise term has an algebraic factor log⁡(2/γ)log⁡(1/δ) increase. Expected-gap and probability lower bounds are incomparable without bounded gaps. (1): Much larger dimension; excludes 0<σD<64γε. (4) needs d≥log16/15⁡(4/γ2) and T≥120σ2L2D2log16/15⁡(2/γ).
(5) (LongTails 2026), StochasticConstrainedQuasarHighProbability O(log⁡(1/δ)ℓ2[DL/εγ+σ2D2γ2ε2]) total gradient and projection calls on the shared regime. (2): Matches known rate, oracle access and probability guarantee; obtained by restricting (5). (2): Boolean seeds, dimension floor, excluded small-noise band and δ≤1/4 narrow the class; (5) has none of these restrictions.
(6) (Martínez-Rubio 2026), Theorem 5; σ=0 O(DL/εγℓ2) value, gradient and projection calls; deterministic objective accuracy. (2): Gradient-and-projection access suffices without values; extends to finite-variance noise. At σ=0, matches the accuracy order up to confidence overhead; inherited from (5). (2): Extra log⁡(1/δ) factor at σ=0; probability guarantee instead of deterministic accuracy.
(7) QASGD (Fu et al. 2023), Corollary 3.3, μ=0; derived Markov bound O([RLεδ+H2R2γ2ε2δ2]log+LR2γεδ) value/component-gradient calls. Unconstrained smooth finite sums, E∥∇fi(x)∥2≤H2, ∇f(x⋆)=0. (2): Scope includes constrained boundary minimizers. On common unconstrained instances with R≤D, σ≤H, confidence is logarithmic instead of δ−2 in the noise term; inherited from (5). (2): Needs compact X and known D; dependence on D can lose when R≪D. Different moment bounds prevent identifying H with σ.

Abbr: ℓ=log⁡(LD2/(γ2ε)); log+⁡t=max{1,log⁡t}; R bounds initial distance to a minimizer; H2 bounds the stochastic-gradient second moment; T is the noisy-gradient query count in (4). B=⌊DL/ε/(10000γ)+σ2D2log⁡(1/δ)/(8192γ2ε2)⌋; b is the vector of gradient/projection budgets, ordered componentwise.

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.
Hinder, Oliver, Aaron Sidford, and Nimit Sohoni. 2020. “Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 1894–938. https://doi.org/10.48550/arXiv.1906.11985.
LongTails: StochasticConstrainedQuasarHighProbability. 2026. Repository convergence theorem and oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/StochasticConstrainedQuasarHighProbability.lean.
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.
Saad, El Mehdi, Wei-Cheng Lee, and Francesco Orabona. 2025. New Lower Bounds for Stochastic Non-Convex Optimization Through Divergence Decomposition. arXiv:2502.14060v2. https://doi.org/10.48550/arXiv.2502.14060.

Lean setup