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 over the
probability simplex , where . On this simplex, is convex and differentiable, attains
its minimum at , and has an
-Lipschitz gradient from the norm to the norm, with . The oracle returns unbiased
gradient estimates using independent, identically distributed samples,
with centered th moments in bounded by , where and . For and , the goal is a measurable
output
satisfying with
probability at least .
The optimization problem is We use the
Euclidean inner product to define gradients, and write The algorithm receives
only , , and ; the moment exponent , noise bound , and tolerance may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Convexity and attainment). For all
and , There
exists such that
Assumption 2 (Smoothness in simplex geometry). The
function is Fréchet
differentiable as a function on at every point of , and
Assumption 3 (Unbiased heavy-tailed oracle). Let
be a measurable space with
probability measure . The oracle
is specified by a jointly measurable map .
For each , the map
is Bochner integrable,
the random variable is integrable for , and At call , a
query receives , where are measurable, mutually
independent samples with common law . The algorithm’s randomness is
independent of the entire sample sequence.
Queries are restricted to . After the allotted oracle
calls, the algorithm must return a measurable -valued output satisfying
where is the joint law of the
oracle samples and the algorithm’s randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.AdaptiveHeavyTailSimplex.spec OracleTemplate.AdaptiveHeavyTailSimplex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.