← All setups

Adaptive Entropic Heavy Tail Convex — Heavy-Tailed Convex Simplex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Heavy-Tailed Convex Simplex Optimization · Lean proof

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.

Proved result

⌈256⋅log⁡(100δ)+67108864⋅L⋅(log⁡(2⋅d)+log⁡(100δ))ε⋅(log⁡(100δ)+log⁡(2+L⋅(log⁡(2⋅d)+log⁡(100δ))ε))+4⋅(log⁡(2⋅d)+log⁡(100δ))⋅(274877906944⋅σε)pp−1⌉+

OracleTemplate.Convergence LongTails.Setups.AdaptiveHeavyTailSimplex.spec OracleTemplate.AdaptiveHeavyTailSimplex.budget

Relevant previous results

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