{"id":"arxiv/2610.36097","url":"https://arxiv.org/abs/2610.36097","tags":["cs.LG","math.OC","stat.ML"],"score":0,"title":"Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\\ell_p$ Balls","domain":"cs.LG","source":"arxiv","authors":["Jack J. Mayo"],"reviews":0,"subject":"cs.LG","summary":"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 $Δ_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}\\sqrt{Δ_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$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}