Parameter-Free Dynamic Regret under Heavy-Tailed Noise

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 LambdaT=1+PT/D. A single algorithm, using none of G,σ,p,PT, attains expected dynamic regret Opleft(minGD√TLambdaT+σ DT1/pLambdaT(p-1)/p,,GDTright) 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.