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

View PDF HTML (experimental)

Abstract:We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves
\[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \]
The learner uses none of $G,\sigma,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.

Subjects:	Machine Learning (cs.LG); Information Theory (cs.IT); Optimization and Control (math.OC)
Cite as:	arXiv:2610.02258 [cs.LG]
	(or arXiv:2610.02258v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2610.02258 arXiv-issued DOI via DataCite

Submission history

From: Vaneet Aggarwal [view email]
[v1] Wed, 30 Sep 2026 21:03:03 UTC (26 KB)