When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses

Thank you for taking the time to review our paper, for the positive feedback, and for recognizing our technical work. We address your points below.

Regarding the interpretability of Assumption 2.3. This assumption is intended to model environments that are not fully adversarial but have some underlying stochastic structure. Intuitively, $\Delta_{\min}$ represents the minimum performance gap between the best expert and any other expert, and the constant $C$ acts as a "corruption" budget, allowing for some adversarial deviations from this stochastic structure. In a purely i.i.d. setting, we would have $C = 0$. The question of whether $C$ can grow with $T$ or $K$ is a good one: In the literature (e.g., [5, 6]), $C$ is typically assumed to be a constant. However, like the algorithm of Zimmert and Seldin [5], our algorithm can also tolerate corruptions that are at most logarithmic and still have meaningful guarantees. To the best of our knowledge, it is an open problem whether it is possible to tolerate a linear amount of corruption (see, e.g., Section 5.2 of [5]). See also our answer to Reviewer ke8c for additional details on Assumption 2.3.

Regarding the motivation for the heavy-tailed setting. We refer to our answer to Reviewer fiH4 for a few motivating examples.

Regarding the squared loss. Indeed, our main motivation lies in scalar regression. This framework enables us to generalize the classical results of Vovk [1] to the more challenging setting where the outcomes $y_t$ can be heavy-tailed. This is an important setting with many applications, such as regression under heavy-tailed distributions, a topic surveyed by Lugosi and Mendelson [2, Section 5]. When we have different models to use but do not know which one is the best, our algorithm can learn (online) to perform nearly as well as this single best model, all without restrictive assumptions on problem parameters like knowledge of $\theta$.

(Q1) Regarding the lower bounds. Yes, this is a great question. The standard adversarial lower bounds for the experts problem apply directly to our setting because, as you pointed out, the setting with bounded losses is a special case of our Assumption 2.1. Therefore, the $\Omega(\sqrt{T \log K})$ lower bound (see, e.g., Theorem 3.6 from Cesa-Bianchi and Lugosi [3], or Theorem 3.22 from Haussler et al. [4]) holds. This implies that our regret bound of $\mathcal{O}(\sqrt{\theta T \log K})$ for the FTRL algorithm is optimal in both $T$ and $K$, and note we have $\theta \leq M^2$ (under Assumption 2.1).

(Q2) Regarding the plots. The $Y$-axis in the plots represents the mean ($\pm$std) cumulative loss over 40 repetitions of the experiments. In this case, by definition of the losses (see Appendix F), they are equivalent to the regrets.

We will add more clarifications in the next revision. Thank you again for your thoughtful feedback.

References

[1] Vovk, V. (2001). Competitive on‐line statistics. International Statistical Review, 69(2), 213-248.

[2] Lugosi, G., and Mendelson, S. (2019). Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19, 1145-1190.

[3] Cesa-Bianchi, N., and Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press.

[4] Haussler, D., Kivinen, J., and Warmuth, M. K. (1998). Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 44(5), 1906-1925.

[5] Zimmert, J., and Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.

[6] Amir, I., Attias, I., Koren, T., Mansour, Y., and Livni, R. (2020). Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 14315-14325.

We sincerely thank you for your detailed and constructive feedback. We are glad you found the problem important and our analysis insightful. We address the points you raised below.

(W.1.1, W.1.3) Regarding the typos and algorithm presentation. Thank you for pointing out unclear points and typos. We will fix these in the next version and take advantage of the additional content page to include the algorithms in the main body to improve readability.

(W.1.2) Regarding the i.i.d. assumption in the abstract. Our use of "i.i.d. losses" in the abstract was intended as a simple, concrete example of a scenario satisfying our more general assumption Assumption 2.3 (self-bounded environment). If losses are i.i.d. and there is a unique best expert $i^\star$, the gap to any other expert $i$, $\Delta_i$, is positive and lower-bounded by $\Delta_{\min}$. This implies Assumption 2.3 with a constant $C = 0$, since the regret satisfies $R_T = \mathbb{E} \left[ \sum_{t=1}^T \sum_{i \neq i^\star} p_t(i) \Delta_i \right] \geq \mathbb{E} \left[ \sum_{t=1}^T \sum_{i \neq i^\star} p_t(i) \Delta_{\min} \right] = \mathbb{E} \left[ \sum_{t=1}^T (1 - p_t(i^\star)) \Delta_{\min} \right].$ We will clarify that Assumption 2.3 is more general and covers non-i.i.d. settings (see, e.g., [1, 2]). See also our answer to Reviewer XFbG for a related discussion.

(W.1.4, Q.1) Regarding the regularizer in Algorithm 2. The reason for using the Bregman divergence $\varphi_t(\cdot) = D_t(\cdot \| p_1)$ rather than the multi-scale entropy $\psi_t$ for Algorithm 2 is essentially because we wanted a simplification in the analysis. The Bregman divergence is non-negative, which allows us to simplify some steps in the analysis that involve the decreasing learning rates $\eta_{t,i}$. As we comment at lines 282-290, using the Bregman divergence also guarantees monotonicity over $t$, which makes the FTRL analysis simpler by allowing us to remove the typical sum $\sum_t(\varphi_{t}(p_{t+1})-\varphi_{t+1}(p_{t+1})) \le 0$ from the stability term. On the other hand, monotonicity is not guaranteed for the multi-scale entropic regularizer $\psi_t$, and thus one would need to carefully analyze the corresponding sum $\sum_t(\psi_{t}(p_{t+1})-\psi_{t+1}(p_{t+1}))$ from the stability term of FTRL. We think that the analysis, although slightly more involved, could also lead to a meaningful result in our setting. However, due to the fact that the learning rates we employ depend on $i$ too, this could require the algorithm to tune the learning rates $\eta_{t,i}$ in a slightly different way than currently done by Algorithm 2.

(W.2, Q.2) Regarding the novelty. While the ideas we use appear in some form or another in the literature, it is important to note that, as they appear in previous work, they still lead to the lower-order term that can force the regret bound to scale as $\sqrt{K T}$. For example, applying the clipping as proposed by Cutkosky [3] or Orseau and Hutter [4] also leads to the lower-order terms (see lines 126-135). Only when we overhaul these ideas and carefully combine them are we able to avoid the problematic lower-order term.

(Q2) On the choice of the learning rates $\eta_{t, i}$. Central to our results is not just the choice of the learning rates $\eta_{t, i}$ but also the clipping we use. At a high level, the choice of learning rate $\eta_{t, i}$ is driven by the need for stability in the analysis. For entropy-regularized OMD/FTRL, the term in the exponent must remain small, e.g. $|\eta_{t, i} \ell_t(i)| \leq 1$, to ensure the quadratic $1 - x + x^2$ is a good approximation of the exponential $\exp(-x)$, where we take $x = \eta_{t, i} \ell_t(i)$ (see, e.g., Section 11.4 of [5] for an argument specific to the Exponential Weights algorithm with rewards, which can be similarly extended to losses and entropy-regularized OMD/FTRL). A standard way to achieve this is to choose a global learning rate $\eta_t \propto 1 / \max_{s \leq t, j} |\ell_s(j)|$. However, this is too conservative: a single large loss from one expert makes the learning rate small for all experts, causing the problematic $\sqrt{K T}$ regret. This justifies setting the learning rate for each expert individually, based on their own observed history. We refer to Appendix A.3 for further details on the caveat of choosing a global learning rate.

The clipping mechanism is then linked to this choice of individual learning rates. For expert $i$ at time $t$, it is set to $1 / \eta_{t, i}$ and acts as follows. If an expert has been stable (i.e., low cumulative variance), its learning rate $\eta_{t, i}$ is large, making the clipping threshold $1 / \eta_{t, i}$ small. The algorithm becomes sensitive and clips even moderate losses, as they would appear as outliers for that expert. Conversely, if an expert has a high cumulative variance, its learning rate $\eta_{t, i}$ is small, making the threshold $1 / \eta_{t, i}$ large and the algorithm will tolerate larger losses since they are expected.

We will revise the paper to incorporate these clarifications. Thank you again for your thoughtful review.

References

[1] Zimmert, J., and Seldin, Y. (2021). Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28), 1-49.

[2] Amir, I., Attias, I., Koren, T., Mansour, Y., and Livni, R. (2020). Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 14315-14325.

[3] Cutkosky, A. (2019). Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory (pp. 874-894). PMLR.

[4] Orseau, L., and Hutter, M. (2021). Isotuning with applications to scale-free online learning. arXiv preprint arXiv:2112.14586.

[5] Lattimore, T., and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.

Thank you for taking the time to review our paper and for your positive feedback. We are pleased you found the paper well-written and conceptually relevant. We address the flagged weaknesses below.

Regarding the experimental evaluation. We would like to clarify that we did include experiments in Appendix F (pages 32-34). These experiments empirically validate our theoretical claims by comparing our proposed algorithms (LoOT-Free OMD and FTRL) against several established baselines on synthetic heavy-tailed data. The results, shown in Figures 1 and 2, illustrate the failure modes of existing methods that our work addresses, confirming the practical implications of our analysis.

Regarding practical motivation. Thank you for this suggestion. While our work is primarily theoretical, the assumption of heavy-tailed losses is motivated by several real-world scenarios where data is prone to infrequent, large-magnitude events. For instance:

• Financial markets: Asset returns are widely recognized as being heavy-tailed (see, e.g., [1]). Our framework can be applied to problems like online portfolio selection, where an investor aggregates the advice of different financial experts or trading strategies, and the daily losses (or negative returns) can exhibit large fluctuations.

• Energy forecasting: Forecasting electricity prices or demand is another key application. For instance, Li and Jones [2] observe that time series often feature sudden, large spikes due to unpredictable events (e.g., power plant outages, extreme weather). Aggregating different forecasting models as experts is a common approach in this domain [3].

• Online media and e-commerce: The popularity of items like news articles, videos, or products often follows a power-law distribution. In applications like ad placement or content recommendation, where the goal is to predict engagement, the observed outcomes (e.g., clicks, views, sales) can be heavy-tailed (see, e.g., [4]).

We will incorporate these examples in the final version of the paper to better motivate our contributions. We hope these clarifications address your concerns and are grateful for your supportive assessment.

References

[1] Bradley, B. O., and Taqqu, M. S. (2003). Financial risk and heavy tails. In Handbook of heavy tailed distributions in finance (pp. 35-103). North-Holland.

[2] Li, Y., and Jones, B. (2019). The use of extreme value theory for forecasting long-term substation maximum electricity demand. IEEE Transactions on Power Systems, 35(1), 128-139.

[3] Devaine, M., Gaillard, P., Goude, Y., and Stoltz, G. (2013). Forecasting electricity consumption by aggregating specialized experts: A review of the sequential aggregation of specialized experts, with an application to Slovakian and French country-wide one-day-ahead (half-) hourly predictions. Machine Learning, 90(2), 231-260.

[4] Cha, M., Kwak, H., Rodriguez, P., Ahn, Y. Y., and Moon, S. (2007, October). I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system. In Proceedings of the 7th ACM SIGCOMM Conference on Internet measurement (pp. 1-14).

Thank you for taking the time to review our paper and for the positive feedback. We are glad you found our paper well-written and recognized the relevance of our contributions. We are available to answer any questions that may arise during the discussion period.