On the necessity of adaptive regularisation: Optimal anytime online learning on ℓ 𝒑 \boldsymbol{\ell_{p}} -balls
Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, Patrick Rebeschini · 2025
Read On the necessity of adaptive regularisation: Optimal anytime online learning on ℓ 𝒑 \boldsymbol{\ell_{p}} -balls by Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, Patrick Rebeschini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19752.txt.
Introduction
Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, and Patrick Rebeschini settle how online learning rules must adapt in a 2025 paper. An online learner bets round by round inside a rounded region, suffering regret when hindsight beats it. The best possible regret changes character depending on whether the region's dimension outnumbers the rounds.
A classic algorithm, Follow-the-Regularised-Leader, hits the best rate in both worlds only if its caution dial turns with time and dimension. The authors then prove the dial cannot stay fixed: any steady setting loses in one world or the other. Extra lower bounds close doors for the related bandit problem in high dimensions.
Catalog record
| CREATOR | Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, Patrick Rebeschini |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-19752
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the necessity of adaptive regularisation: Optimal anytime online learning on ℓ 𝒑 \boldsymbol{\ell_{p}} -balls Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke, Patrick Rebeschini Abstract We study online convex optimization on ℓ p \ell_{p} -balls in ℝ d \mathbb{R}^{d} for p > 2 p>2 . While always sub-linear, the optimal regret exhibits a shift between the high-dimensional setting ( d > T d>T ), when the dimension d d is greater than the time horizon T T and the low-dimensional setting ( d ≤ T d\leq 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 \ell_{p} -balls with p ≥ 1 p\geq 1 . 1 Introduction We study Online Convex Optimisation (OCO) [ 15 , 44 ] , a sequential game where in each round t=1,\dots,T , a learner selects a point x_{t} in a convex set V\subset\mathbb{R}^{d} and suffers a convex loss \ell_{t}(x_{t}) , the full loss \ell_{t} is then revealed to the learner before the next point x_{t+1} is selected. The learner competes against the best fixed point in hindsight and aims to minimise its regret against this competitor: R_{T}=\sum_{t=1}^{T}\ell_{t}(x_{t})-\min_{u\in V}\sum_{t=1}^{T}\ell_{t}(u) . Optimal performance is known to depend on parameters of the problem such as the geometry of the set V and constraints on the losses \ell_{t} [ 27 , 22 , 24 , 41 ] . We consider the setting where the action set V=\left\{x\in\mathbb{R}^{d}:\|x\|_{p}\leq 1\right\} is an \ell_{p} -ball in d -dimensional space with p>2 and losses are L -Lipschitz with respect to \|\cdot\|_{p} (ensuring R_{T}\leq 2LT ). The study of \ell_{p} -geometries with p>2 has been the focus of many works in optimisation [ 10 , 27 , 17 , 23 , 24 ] as it covers sets with varying levels of curvature, offering insights for more general spaces. In this work, we study the behaviour of the Follow-The-Regularised-Leader (FTRL) (and Online Mirror Descent (OMD)) family of algorithms in achieving anytime optimal regret guarantees. Anytime refers to the absence of knowledge of the time horizon T . We focus on two regimes: the high-dimensional setting where d>T and the low-dimensional setting where d\leq T . For \ell_{p} -balls with p>2 , the optimal regret exhibits a shift from the high-dimensional setting to the low-dimensional setting (see Table 1 ). If T is unknown, then so is the dimension regime when the game begins. We show that anytime optimality can be achieved with FTRL by using adaptive regularisation that in early high-dimensional rounds uses a uniformly-convex regulariser of degree p (see Definition 2.2 ) and switches to a strongly-convex regulariser in round t_{0}\approx d . Despite achieving the anytime optimal regret through adaptive regularisation, it remains an open question whether this can be achieved through OMD or FTRL with a single fixed regulariser. This would be desirable since it would provide algorithmic simplicity as well as an understanding of how to appropriately regularise \ell_{p} -balls across all dimension-regimes simultaneously. Therefore, we aim to answer the following question: Can OMD or FTRL with a fixed regulariser be anytime optimal for OCO on \ell_{p} -balls with p>2 ? To answer this question, it is natural to first consider the regularisers that are optimal in one of the dimension regimes. However, we give algorithmic-dependent lower bounds that show that these are not anytime optimal ( Proposition 4.1 , Proposition 4.5 ). More generally, we also show that any strongly-convex regulariser is provably sub-optimal in the high dimensional setting ( Theorem 4.2 ). We then turn to our main result which provides a negative answer to the above question for separable regularisers (that separate additively over dimension: \psi(x)=\sum_{i=1}^{d}g_{i}(x_{i}) ). The result ( Theorem 4.6 ) states that a separable regulariser (with OMD or FTRL) cannot be anytime optimal. This also establishes that the adaptive regularisation used in our procedure to achieve anytime optimality is necessary for separable regularisers. The class of separable regularisers covers a wide range of regularisers including all of the form \|x\|_{r}^{r} for any r\geq 1 which are commonly used in OMD and FTRL [ 10 , 27 , 42 ] . Moreover, the result holds for any separate coordinate-wise decreasing step-sizes, showing that the widely used diagonal versions of Adagrad-style algorithms [ 12 ] are also anytime sub-optimal and emphasising the relevance of this result on practical methods. For any online learning problem, the learner may not know if the game will end in low or high dimensions, and designing optimal procedures in both cases is important. Our results show that achieving this is not straightforward for \ell_{p} -balls, highlighting that this problem should not be overlooked in online learning more broadly and pointing out that the question on universality of mirror descent started in prior works [ 38 ] is not completely answered (see discussion in Section 4.3 ). We note that the \ell_{p} / \ell_{q} setting (i.e. V=\mathcal{B}_{p},\partial\ell_{t}(x)\subset\mathcal{B}_{q} ) is relevant in the literature, e.g., see the open problem in [ 16 ] . Our work highlights the difficulty of this setting for p=q>2 . Finally, we consider the linear bandit problem where only the loss evaluated at x_{t} is observed ( Section 5 ). We would like to approach this problem in the same way as the full-information problem by characterising the algorithms achieving optimal regret guarantees across all dimension regimes. However, while sub-linear regret bounds have been established in the low-dimensional setting by [ 24 ] , we show that the bandit setting is fundamentally different and much more difficult since sub-linear regret bounds become unachievable when the dimension is large enough ( Theorem 5.1 ). Table 1: Optimal regret rates for OCO on \ell_{p} -balls ( p>2 ) from known results. [ 27 ] show the regret bound of O(LT^{1/2}d^{1/2-1/p}) achieved by OMD using a strongly-convex regulariser is optimal for d=O(T) . When d\gg T this bound is vacuous since R_{T}\leq 2LT . For d>T , OMD with a uniformly-convex regulariser of degree p guarantees a regret of O(LT^{1-1/p}) [ 39 ] and is optimal [ 33 , 17 , 16 , 39 ] . These guarantees can also be achieved with FTRL using the same regularisers [ 35 , 4 ] . d\leq T (low-dim) d>T (high-dim) Optimal Regret Rate L\sqrt{Td^{1-2/p}} LT^{1-1/p} Regularisation (OMD or FTRL) Strongly-convex Uniformly-convex 1.1 Contributions We highlight our contributions for OCO on \ell_{p} -balls for p>2 below. Note that the case p\in[1,2] is already understood across all dimension regimes and does not present shifts in the rate of regret with respect to the time horizon T unlike in the p>2 case, see Remark 2.1 , [ 27 ] . We focus here on FTRL but the results also hold for OMD, and we include these in Appendix G . •