Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on ℓp Balls
Abstract
We study full-information online linear optimisation on the unit ℓp ball in ℝd, for fixed 2≤ p<∞ and losses of dual norm at most one. Let Δ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 ΔT, regret Op(1+min{ΔT1−1/p, d1/2−1/p√(Δ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→∞ 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 RegT≤ 2 RegTFTL. 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.
Related
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Lower Bounds for Linear-Oracle Online Learning
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
- Online Individualized Treatment Selection under Partial Feedback: False Discovery Control and Minimax Optimality
- High-Probability Minimax Lower Bounds
BibTeX
@misc{mayo2026minimaxoptimal,
title = {{Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls}},
author = {Jack J. Mayo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36097},
eprint = {2610.36097},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36097},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on ℓ_p Balls
AU - Jack J. Mayo
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36097
UR - https://arxiv.org/abs/2610.36097
AB - We study full-information online linear optimisation on the unit ℓ_p ball in ℝ^d, for fixed 2≤ p<∞ and losses of dual norm at most one. Let Δ_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 Δ_T, regret O_p(1+min{Δ_T^1−1/p, d^1/2−1/p√(Δ_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→∞ 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 Reg_T≤ 2 Reg_T^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.
ER -