We thank the reviewer for their positive and constructive feedback. We address your comments, suggestions and questions below.

Minor comments:

• In line 110, you are right it should be $T^{1-1/p}$, thank you for pointing this out!
• We will include a definition of “sign-invariant regularizer” in the final version.
• In Line 279, the phrasing we used was confusing. We meant the following: for $p>2$, the optimal rate in the low-dimensional setting is $O(\sqrt{Td^{1-2/p}})$ which is dimension-dependent. Proposition 4.5 shows that the regret guarantees do not improve for smaller dimensions, so are dimension-independent and therefore sub-optimal (so “provably dimension-independent and sub-optimal” in the sense that the optimal rate is dimension-dependent). We realise this phrasing is confusing and will amend it in the final version.

Questions:

Q1: Are you aware of any non-separable regularizers in the literature?

• There is for example the squared r-norm $\Vert x \Vert_r^2 = (\sum_{i=1}^d \|x_i\|^r)^{2/r}$ for $r\in(1,2]$ which is not separable and has been considered in the literature (e.g. see section 6.7 in [1]). It is however strongly convex with respect to the r-norm so Theorem 4.2 guarantees that it is sub-optimal in high dimension.

Q2: Could you provide any intuition or motivation behind the loss construction (Section E.1) used in the lower bound proof?

• For the first half of the rounds we successively use linear losses with gradient $\pm e_1$.
• For the second half we use a fixed linear loss with gradient a rescaled version of a point in the corner of the $\ell_p$-ball (so that competitor is this point in the corner which may be hard to reach).
• The different losses in the two halves of the rounds capture some sort of bias-variance trade-off of the algorithm: If the step-size is large then the algorithm will quickly reach the corner of the ball (the competitor) in the second half of the rounds but in the first it will suffer large regret because it moves too fast through the space and every other round it will get to close to $e_1$ which will make it suffer large loss in the next round (it has high “variance”).
• If the step-size is too small, it will not suffer much regret in the first half of the rounds but in the second half it will not be able to reach the corner of the ball (the competitor) sufficiently quickly and suffer large-regret (it has high “bias”).
• We chose this loss construction so that a large or small step-size does not benefit the algorithm: A perfectly tuned step-size reaches the correct balance between the regret suffered from both halves and corresponds to the optimal regret (both halves also correspond to the two terms that appear in the regret bounds of OMD/FTRL before tuning of the step-size). We will include this intuition in the corresponding appendix in the final version of the paper.

[1] Francesco Orabona. A modern introduction to online learning. 2019. Preprint, arXiv: 1912.13213.

We thank the reviewer for their positive, constructive and thorough feedback. We address your comments, suggestions and questions below.

Weaknesses:

Heavy technical machinery for simple switch

• While the proof of Theorem 3.1 in Appendix D is tedious and may obscure from the fact that it involves mostly algebraic computations, we attempted to make clear that the result consists of arguing with a sequence of elementary arguments (line 216: “The proof is in Appendix D and consists of a careful application of Theorem 2.3.” where Theorem 2.3 is just the general regret bound for FTRL).

The paper would also benefit from more intuition behind the proofs and sketches for some of the important building blocks that are relegated to the appendix (e.g. Lemma 4.7)

• This is a good point - we will include intuitions for some of these results/proofs in the final version - at least in the appendix and in the main text if space allows (see also answer to reviewer QhTE).

Bandit section is underdeveloped: Section 5 on bandit feedback feels somewhat disconnected from the main narrative and lacks the depth of analysis given to the full-information setting. The impossibility result for high-dimensional bandits is interesting but doesn't provide corresponding positive results or adaptive algorithms for the achievable regimes, leaving this part of the story incomplete.

• Our main results are for the full-information setting. We included the bandit results as an addition because we thought it was relevant to provide the separation with full-information that sub-linear regret is not possible in high-dimension. However, there are indeed still many unanswered questions including the optimal rate of regret in the low-dimensional setting (there is no matching lower-bound as far as we know) that leave open many possibilities for future work.

Assumptions on separability

• Resolving what result can be achieved for general regularizer that we leave open is of great importance to better understand the limitations and strengths of FTRL (see answer to reviewer vyFS). Also note that our result holds for non-separable regularizers that are a multiplicative constant away from a separable regularizer.

Questions:

Q1: What is the main technical issue with extending the present proofs to non-separable regularizers? Is it the analog of Lemma 4.7?

• Exactly, the difficulty is in extending Lemma 4.7 on the quadratic-growth of the regulariser beyond the 1-dimensional case. In fact having a general result on the necessity for quadratic growth or some form of strong convexity to achieve optimal regret in the low-dimensional setting could be of independent interest.

Q2: Could you explain a bit more about the prior work in this domain? Have negative results of the flavor presented in this work appeared before in the literature?

• As far as we are aware, results on the failure of fixed regularization are novel in online learning. Algorithmic specific lower bounds (like the ones we have for specific regularizers - Propositions 4.1 and 4.5) have appeared in prior work (e.g. Theorems 3&4 in [1]).

Q3: Any insights on the algorithmic component to complement the impossibility results in Section 5?

• In the low-dimensional setting, the algorithm from [2] that achieves a regret bound of $\tilde{O}(T^{1-1/p} d^{1/p})$ is based on OMD with a carefully designed barrier regularizer. This result holds for all d but becomes loose as d increases. Our lower bound says that sub-linear regret is not possible in high enough dimension. It is unclear whether there are different optimal regret regimes within the low dimensional setting which would require an adaptive algorithm, it is even unclear if the regret bound of [2] is optimal in any dimension. As mentioned in the weakness section, there is still a lot to understand on the optimal rates of regret for the bandit setting.

[1] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50–69, 2018.

[2] Thomas Kerdreux, Christophe Roux, Alexandre d’Aspremont, and Sebastian Pokutta. Linear bandits on uniformly convex sets. Journal of Machine Learning Research, 22(284):1–23, 2021.

We thank the reviewer for their positive and insightful feedback. We address your comments, suggestions and questions below.

Weaknesses

While separable regularizers are indeed widely used, they are not a fundamentally necessary class. As a result, the negative result primarily highlights the need for more sophisticated fixed regularizers rather than a limitation of FTRL itself.

• This is correct. But in fact, we view this as one of the main messages of our work. Our results demonstrate that existing regularizers impose intrinsic limitations on FTRL and open up an interesting avenue of research to discover these more sophisticated alternatives that potentially give algorithms that are fundamentally different. Also note that our main result holds for non-separable regularizers that are a multiplicative constant away from being separable.

The negative result on linear bandits appears somewhat trivial, as it essentially demonstrates the dependence of regret on the dimensionality.

• Yes, it essentially demonstrates that the dependence of the low-dimensional regret on the dimensionality is maintained as the dimension increases but this is not always obvious. For example, in the full-information setting that we consider in most of our work, this is not the case. While it may be more expected that it is the case in the harder bandit feedback setting, proving it formally in the way that we do is not trivial.

Questions

Q1: Theorem 5.1 claims that linear regret is unavoidable in the high-dimensional setting. However, this conclusion would also follow from any dimension-dependent lower bound of the form $\Omega(d^a T^b)$. Does the lower bound instance presented in the paper yield any nontrivial results for norm balls that are stronger than those known for the multi-armed bandit setting? This is particularly relevant since, for $p \in [1,2]$, the regret bounds are already known to be the same.

• This conclusion would indeed also follow from any dimension-dependent lower bound of the form $\Omega(d^a T^b)$ but usually lower bounds of this form only hold in the low-dimensional setting (e.g. in [1], their lower bound Theorem 4 only holds for $T \geq d^{2/(1-q/2)}$ and does not give linear regret in high dimension). As far as we are aware, for $p \in [1,2]$, the regret bounds are known to be the same as for the multi-armed bandit setting only in the low-dimensional setting, making our results non-trivial in the high-dimensional setting. We will add a remark to clarify this in the final version.

Q2: Have the authors considered using fixed log-barrier regularizers, which are not part of the class of separable regularizers?

• We did not consider specific non-separable log-barrier regularizers but it is unclear how we could use it since they do not satisfy uniform convexity properties that allow us to obtain regret guarantees. However, we would be really happy to receive any pointer in this direction.

[1] Sébastien Bubeck, Michael Cohen, and Yuanzhi Li. Sparsity, variance and curvature in multi-armed bandits. In Proceedings of Algorithmic Learning Theory, Proceedings of Machine Learning Research, pages 111–127, 2018.

We thank the reviewer for their positive feedback. We address your questions below.

Q1: Whether the assumption that 0 is an interior point of the action set is fundamentally necessary for this paper?

• We could consider translating the lp-ball away from 0, then our results will hold for regularisers satisfying the conditions we need on this translated ball (e.g. reaches its minimum in the centre of the translated lp-ball). We will add a remark on this in the final version.

Q2: Do the authors have some intuition about whether the -ball structure can be generalized to certain more general convex sets to still have similar negative results for separable regularizers?

• This is an interesting question. What we need for Theorem 4.6 (our main result on the failure of separable regularization) to hold is

1. that in the 1-dimensional case, the optimal regret requires quadratic growth of the regularizer.
2. In the general d-dimensional case, quadratic growth of the regularizer leads to sub-optimal regret.

Point 1. will hold for any symmetric action set. The question then becomes whether we can show 2. for these more general convex sets, which is not clear We would also require that there is a similar shift in the optimal rate of regret between dimension-regimes, which is not necessarily obvious.

How general this phenomenon might be is likely related to the concept of quadratically convex sets [1] for which several results are known on the posibility of getting regret that grows as $\sqrt{T}$ in the low-dimensional case, while it is likely that the regret is better in the high dimensional case (when taking into account dependence on other quantities like dimension). This is an interesting direction of future research. We will also add a remark on this in the final version.

[1] Daniel Levy and John C Duchi. Necessary and sufficient geometries for gradient methods. In Advances in Neural Information Processing Systems, volume 32, 2019.