mlsanityData to 14 Oct 2026

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

arXiv 2506.19752 ↗First posted 24 Jun 2025cs.LGcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

18 of 47 references.

References · 18

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2016Scale-Free Online Learningcited by 85
  3. 2020High-Dimensional Sparse Linear Banditscited by 61
  4. 2019Regret Bounds for Batched Banditscited by 49
  5. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 44
  6. 2020Online Learning with Imperfect Hintscited by 37
  7. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
  8. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  9. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21
  10. 2022Thompson Sampling for High-Dimensional Sparse Linear Contextual Banditscited by 16
  11. 2014Primal-dual subgradient methods for minimizing uniformly convex functionscited by 11
  12. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
6 more
  1. 2021Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Banditcited by 8
  2. 2021Linear Bandits on Uniformly Convex Setscited by 6
  3. 2023High-dimensional Contextual Bandit Problem without Sparsitycited by 5
  4. 2021Local and Global Uniform Convexity Conditionscited by 4
  5. 2024Computing Optimal Regularizers for Online Linear Optimizationcited by 4
  6. 2024Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimizationcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026When to use what Schatten-p norm in deep learning?cited by 2