Heavy-Tailed Convex Simplex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed Convex Simplex Optimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and attainment). For all
Assumption 2 (Smoothness in simplex geometry). The
function
Assumption 3 (Unbiased heavy-tailed oracle). Let
Queries are restricted to
Results
On
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdaptiveEntropicHeavyTailConvex
(Ours) |
|||
| (2) Clipped-SMD (Nguyen et al. 2023), Thm. 3.1 (known horizon); entropic specialization with global smoothness and pilot | (1): No |
(1): Stationary IID
rather than conditional moments; simplex rather than general Bregman
geometry. Large |
|
| (3) Clipped-ASMD (Nguyen et al.
2023), Thm. 4.1; globally smooth special case |
(1): Scope: arbitrary
constrained minimizers. Updates need neither |
(1): At fixed |
Abbr:
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (4)
Prox-clipped-SSTM-shift (Gorbunov et al. 2024),
Thm. 2.7, |
(1): Updates need neither
|
(1): Simplex only;
(4) covers composite objectives and unbounded domains.
Conversion gains need not hold when |
|
| (5) ASMD (Liu 2026),
Thm. 3.3, known- |
(1): Logarithmic instead
of polynomial confidence cost for the shared probability target; updates
need neither |
(1): Requires an ambient gradient and the simplex; (5) allows general composite Bregman problems. |
Abbr: