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

arXiv: https://arxiv.org/abs/2506.01722 · HTML: https://mlsanity.com/paper/2506.01722/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 43 references that are in the map.
- First posted on arXiv 2 Jun 2025.

## Builds on (most cited first, 22 of 22)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [Stochastic Online Convex Optimization. Application to probabilistic time series forecasting](https://mlsanity.com/paper/2102.00729/) (2021)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [Optimal Tracking in Prediction with Expert Advice](https://mlsanity.com/paper/2208.03708/) (2022)

## Built on by (most cited first, 2 of 2)

- [Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise](https://mlsanity.com/paper/2610.02258/) (2026)
- [Prediction with Expert Advice under Heavy-Tailed Losses](https://mlsanity.com/paper/2610.14904/) (2026)

## Abstract (arXiv)

We consider the problem setting of prediction with expert advice with possibly heavy-tailed losses, i.e. the only assumption on the losses is an upper bound on their second moments, denoted by θ. We develop adaptive algorithms that do not require any prior knowledge about the range or the second moment of the losses. Existing adaptive algorithms have what is typically considered a lower-order term in their regret guarantees. We show that this lower-order term, which is often the maximum of the losses, can actually dominate the regret bound in our setting. Specifically, we show that even with small constant θ, this lower-order term can scale as √KT, where K is the number of experts and T is the time horizon. We propose adaptive algorithms with improved regret bounds that avoid the dependence on such a lower-order term and guarantee O(√θ Tlog(K)) regret in the worst case, and O(θ log(KT)/Deltamin) regret when the losses are sampled i.i.d. from some fixed distribution, where Deltamin is the difference between the mean losses of the second best expert and the best expert. Additionally, when the loss function is the squared loss, our algorithm also guarantees improved regret bounds over prior results.