← All setups

Heavy-Tailed Convex Simplex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Convex Simplex Optimization

We consider minimizing f:Rd→R over the probability simplex Δd={x∈Rd:xi≥0, ∑i=1dxi=1}, where d≥2. On this simplex, f is convex and differentiable, attains its minimum at x⋆, and has an L-Lipschitz gradient from the ℓ1 norm to the ℓ∞ norm, with L>0. The oracle returns unbiased gradient estimates using independent, identically distributed samples, with centered pth moments in ℓ∞ bounded by σp, where 1<p≤2 and σ≥0. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈Δd satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈Δdf(x). We use the Euclidean inner product to define gradients, and write ∥v∥1=∑i=1d|vi|,∥v∥∞=max1≤i≤d|vi|. The algorithm receives only d, L, and δ; the moment exponent p, noise bound σ, and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Convexity and attainment). For all x,y∈Δd and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There exists x⋆∈Δd such that f(x⋆)≤f(x),x∈Δd.

Assumption 2 (Smoothness in simplex geometry). The function f is Fréchet differentiable as a function on Rd at every point of Δd, and ∥∇f(x)−∇f(y)∥∞≤L∥x−y∥1,x,y∈Δd.

Assumption 3 (Unbiased heavy-tailed oracle). Let Ω be a measurable space with probability measure ν. The oracle is specified by a jointly measurable map g:Δd×Ω→Rd. For each x∈Δd, the map g(x,⋅) is Bochner integrable, the random variable ∥g(x,ξ)−∇f(x)∥∞p is integrable for ξ∼ν, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥∞p]≤σp. At call k, a query xk∈Δd receives g(xk,ξk), where (ξk)k≥0 are measurable, mutually independent samples with common law ν. The algorithm’s randomness is independent of the entire sample sequence.

Queries are restricted to Δd. After the allotted oracle calls, the algorithm must return a measurable Δd-valued output x¯ satisfying P(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the oracle samples and the algorithm’s randomness.

Results

On Δd={x∈Rd:xi≥0, ∑ixi=1}, d≥2, f is convex, has an ambient gradient at every feasible point, and satisfies ∥∇f(x)−∇f(y)∥∞≤L∥x−y∥1 for feasible x,y, with L>0. A constrained minimizer x⋆ exists. The jointly measurable oracle uses IID samples of law ν, with integrable replies and noise moments, ∫g(x,ω)dν=∇f(x) and ∫∥g(x,ω)−∇f(x)∥∞pdν≤σp, 1<p≤2, σ≥0. Target: a measurable feasible output with P{f(output)−f(x⋆)>ε}≤δ, ε>0, 0<δ<1. Public inputs are d,L,δ; the stopping budget also uses p,σ,ε.

Heavy-tailed stochastic convex optimization on the simplex: AdaptiveHeavyTailSimplex.
Result Oracle complexity Novelty Limitations
(1) AdaptiveEntropicHeavyTailConvex (Ours) (⋆⋆⋆) (review) O(γ+LHε[γ+log(2+LHε)]+H(238σε)q)
(2) Clipped-SMD (Nguyen et al. 2023), Thm. 3.1 (known horizon); entropic specialization with global smoothness and pilot O(γ+γ[LD+D(G0+σ)]ε+γ(σDε)q) (1): No p,σ in updates; smoothness term ε−1/2 up to logs instead of ε−1; removes G0. For fixed p<2,δ, stochastic dimension factor Dq/2→D. (1): Stationary IID rather than conditional moments; simplex rather than general Bregman geometry. Large 238q penalty: dimensional gain requires roughly Dq/2−1≫238q.
(3) Clipped-ASMD (Nguyen et al. 2023), Thm. 4.1; globally smooth special case ∇f(x⋆)=0 O(1+γLDε+γ(σDε)q) (1): Scope: arbitrary constrained minimizers. Updates need neither p nor σ. On the overlap, deterministic term improves when H[γ+log⁡(2+LH/ε)]≪γ2D; no improved accuracy exponent. (1): At fixed d,δ, deterministic term loses log⁡(L/ε) as L/ε→∞; larger noise constant. Stationary IID and simplex restriction; stopping still needs p,σ,ε.

Abbr: q=p/(p−1), D=log⁡d, γ=1+log⁡(1/δ), H=D+γ; x0=(1/d,…,1/d) and G0=∥∇f(x0)∥∞. Costs count individual stochastic-gradient replies, including the pilot in (2); prior entropic bounds use entropy radius at most log⁡d. In (4), L2 and σ2 are Euclidean smoothness and noise-moment constants, R≥∥x0−x⋆∥2, ζ⋆≥∥∇f(x⋆)∥2, and ℓ=1+log((2+L2R2/ε+Rζ⋆/ε+(σ2R/ε)q)/δ). Prior-work big-O constants may depend on fixed p; the explicit 238q in (1) is retained because it is nonuniform as p↓1.

AdaptiveHeavyTailSimplex (continued).
Result Oracle complexity Novelty Limitations
(4) Prox-clipped-SSTM-shift (Gorbunov et al. 2024), Thm. 2.7, n=1; Euclidean regularity on B52R(x⋆) O((1+L2R2ε)ℓ2+Rζ⋆εℓ3/2+(σ2Rε)qℓ) (1): Updates need neither p nor σ. Rates not comparable on the full setup. On a common regular extension, worst-case L2=dL, σ2=dσ, R≤2 give polynomial rather than logarithmic dimension factors. (1): Simplex only; (4) covers composite objectives and unbounded domains. Conversion gains need not hold when L2=L, σ2=σ; (1) retains its noise factor H.
(5) ASMD (Liu 2026), Thm. 3.3, known-p,σ,T tuning; Derived bound (Markov) O(1+δ−1/pLDε+δ−2/(p−1)(σDε)q) (1): Logarithmic instead of polynomial confidence cost for the shared probability target; updates need neither p nor σ. (5) derives from a bound on E[gapp/2]. (1): Requires an ambient gradient and the simplex; (5) allows general composite Bregman problems.

Abbr: q=p/(p−1), D=log⁡d, γ=1+log⁡(1/δ), H=D+γ; x0=(1/d,…,1/d) and G0=∥∇f(x0)∥∞. Costs count individual stochastic-gradient replies, including the pilot in (2); prior entropic bounds use entropy radius at most log⁡d. In (4), L2 and σ2 are Euclidean smoothness and noise-moment constants, R≥∥x0−x⋆∥2, ζ⋆≥∥∇f(x⋆)∥2, and ℓ=1+log((2+L2R2/ε+Rζ⋆/ε+(σ2R/ε)q)/δ). Prior-work big-O constants may depend on fixed p; the explicit 238q in (1) is retained because it is nonuniform as p↓1.

Gorbunov, Eduard, Abdurakhmon Sadiev, Marina Danilova, et al. 2024. “High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise.” Proceedings of the 41st International Conference on Machine Learning, Proceedings of machine learning research, vol. 235: 15951–6070. https://proceedings.mlr.press/v235/gorbunov24a.html.
Liu, Zijian. 2026. In-Expectation Convergence of Stochastic Gradient Methods Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2606.00520.
Nguyen, Ta Duy, Alina Ene, and Huy L. Nguyen. 2023. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails. https://doi.org/10.48550/arXiv.2304.01119.

Lean setup