Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on ${\ell }_p$ Balls

Abstract

We study full-information online linear optimisation on the unit ${\ell }_p$ ball in ${\mathbb{R}}^d$, for fixed $2\le p<\infty$ and losses of dual norm at most one. Let ${\Delta }_T$ denote the cumulative loss of the best fixed action above each round's minimum. A follow-the-regularised-leader (FTRL) algorithm attains, on every loss sequence and without knowing $T$ or ${\Delta }_T$, regret $O_p(1+\min \{{\Delta }_T^{1-1/p},d^{1/2-1/p}\sqrt{{\Delta }_T}\})$. Matching lower bounds show that this rate is minimax for each fixed $p$, and its constant $(2+o(1))p/\log p$ is optimal as $p\to \infty$ among guarantees uniform in $d$ and $T$. The algorithm uses a bounded radial regulariser and switches at most once to its quadratic augmentation. On some paths where follow-the-leader (FTL) has regret one, its regret grows with $T$. A switching extension keeps the sharp constant and also guarantees ${\mathrm{Reg}}_T\le 2{\mathrm{Reg}}_T^{\mathrm{FTL}}$. For i.i.d. losses whose mean has no zero coordinates, we compute the exact $\log T$ coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.

arXiv comment49 pages