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

arXiv:2607.27073v1 Announce Type: new Abstract: 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 extbf{HT-PAder}, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, extbf{AdaGrad-Hedge}, which requires no moment conditions on meta-losses. For a domain of diameter D, Lipschitz constant G, noise level sigma, and comparator path length P_T, HT-PAder achieves an expected universal dynamic regret of [ widetilde Oleft( GDsqrt{T(1+P_T/D)} + sigma 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.

Source: arXiv cs.LG | 2026-07-30