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

We study online convex optimisation on ℓ p -balls in R 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 sublinear regret bounds for the linear bandit problem in sufficiently high-dimension for all ℓ p -balls with p ≥ 1.

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 ≤ T . For ℓ 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 arXiv: 2506.19752v3 [cs.LG] 27 Nov 2025 (see Definition 2.2) and switches to a strongly-convex regulariser in round t 0 ≈ 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 ℓ 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 ℓ 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:

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 ≥ 1 which are commonly used in OMD and FTRL [10,28,43]. 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. As far as we are aware, results on the failure of fixed regularization are novel in online learning. However, algorithmic specific lower bounds (like the ones we have for specific regularizers in Proposition 4.1 and Proposition 4.5) have appeared in prior work (e.g. Theorems 3 & 4 in [37]).