Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise

We study online convex optimization (OCO) in non-stationary environments under heavy-tailed noise, where the stochastic gradient oracle admits only a finite p-th central moment for some p \in (1, 2]. While static regret is well-understood, achieving universal dynamic regret in a parameter-free manner remains an open challenge. We resolve this by proposing HT-PAder, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, AdaGrad-Hedge, which requires no moment conditions on meta-losses. For a domain of diameter D, Lipschitz constant G, noise level σ, and comparator path length P_T, HT-PAder achieves an expected universal dynamic regret of [ \widetilde O\left( GD\sqrt{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p} \right). ] The algorithm does not require prior knowledge of any of these problem parameters. Even in the special case of finite variance (p=2), HT-PAder provides the first parameter-free minimax universal dynamic regret guarantee. We also prove a matching lower bound, establishing the optimality of the path-length exponent.