Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Abstract
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 ΛI=1+PI/D, one learner achieves E[RegretI(u)]≤min(GDn, C[GD√(n(ΛI+log2(2T))) +σDn1/p(ΛI+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.
Related
- Parameter-Free Dynamic Regret under Heavy-Tailed Noise
- On the Relation Between Interval Regret and Dynamic Regret
- Limit theory for a class of non-stationary linear processes with weakly dependent heavy-tailed innovations
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
- DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
BibTeX
@misc{aggarwal2026parameterfree,
title = {{Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02258},
eprint = {2610.02258},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02258},
}
RIS
TY - UNPB
TI - Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02258
UR - https://arxiv.org/abs/2610.02258
AB - 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 Λ_I=1+P_I/D, one learner achieves E[Regret_I(u)]≤min(GDn, C[GD√(n(Λ_I+log^2(2T))) +σDn^1/p(Λ_I+log^2(2T))^(p−1)/p]). The learner uses none of G,σ,p,I,P_I, 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.
ER -