# Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 19 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Parameter-Free Dynamic Regret under Heavy-Tailed Noise](https://mlsanity.com/paper/2607.27073/) (2026)

## Abstract (arXiv)

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional pth noise moment, 1<p≤2. For every fixed interval I of length n and comparator path with LambdaI=1+PI/D, one learner achieves [ E[RegretI(u)]≤min(GDn, C[GD√n(LambdaI+log2(2T)) +σ Dn1/p(LambdaI+log2(2T))(p-1)/p]). ] The learner uses none of G,σ,p,I,PI, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes 1+log(T/n), including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.