Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Abstract
We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite p-th central moment, where p∈(1,2] is unknown. For a bounded convex domain of diameter D, subgradients bounded by G, noise scale σ, and comparator path length PT, let ΛT=1+PT/D. A single algorithm, using none of G,σ,p,PT, attains expected dynamic regret Op(min{GD√(TΛT)+σDT1/pΛT(p−1)/p, GDT}) against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent (p−1)/p, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in p; its logarithm-free form has noise coefficient O(1+log(p/(p−1))), while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.
Related
- Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
- Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
- TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise
BibTeX
@misc{aggarwal2026parameterfree,
title = {{Parameter-Free Dynamic Regret under Heavy-Tailed Noise}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.27073},
eprint = {2607.27073},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.27073},
}
RIS
TY - UNPB
TI - Parameter-Free Dynamic Regret under Heavy-Tailed Noise
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2607.27073
UR - https://arxiv.org/abs/2607.27073
AB - We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite p-th central moment, where p∈(1,2] is unknown. For a bounded convex domain of diameter D, subgradients bounded by G, noise scale σ, and comparator path length P_T, let Λ_T=1+P_T/D. A single algorithm, using none of G,σ,p,P_T, attains expected dynamic regret O_p(min{GD√(TΛ_T)+σDT^1/pΛ_T^(p−1)/p, GDT}) against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent (p−1)/p, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in p; its logarithm-free form has noise coefficient O(1+log(p/(p−1))), while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.
ER -