# On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls

arXiv: https://arxiv.org/abs/2506.19752 · HTML: https://mlsanity.com/paper/2506.19752/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 24 Jun 2025.

## Builds on (most cited first, 18 of 18)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [Primal-dual subgradient methods for minimizing uniformly convex functions](https://mlsanity.com/paper/1401.1792/) (2014)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit](https://mlsanity.com/paper/2109.11612/) (2021)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [High-dimensional Contextual Bandit Problem without Sparsity](https://mlsanity.com/paper/2306.11017/) (2023)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Computing Optimal Regularizers for Online Linear Optimization](https://mlsanity.com/paper/2410.17336/) (2024)
- [Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization](https://mlsanity.com/paper/2412.15956/) (2024)

## Built on by (most cited first, 1 of 1)

- [When to use what Schatten-p norm in deep learning?](https://mlsanity.com/paper/2606.15268/) (2026)

## Abstract (arXiv)

We study online convex optimization on ℓp-balls in ℝd for p > 2. While always sub-linear, the optimal regret exhibits a shift between the high-dimensional setting (d > T), when the dimension d is greater than the time horizon T and the low-dimensional setting (d ≤ T). We show that Follow-the-Regularised-Leader (FTRL) with time-varying regularisation which is adaptive to the dimension regime is anytime optimal for all dimension regimes. Motivated by this, we ask whether it is possible to obtain anytime optimality of FTRL with fixed non-adaptive regularisation. Our main result establishes that for separable regularisers, adaptivity in the regulariser is necessary, and that any fixed regulariser will be sub-optimal in one of the two dimension regimes. Finally, we provide lower bounds which rule out sub-linear regret bounds for the linear bandit problem in sufficiently high-dimension for all ℓp-balls with p ≥ 1.