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

In online convex optimization (OCO), standard algorithms like Online Gradient Descent (OGD) rely on the assumption that stochastic gradients have finite variance. However, in many real-world applications—such as deep learning and finance—gradients exhibit heavy-tailed noise, where only a finite p-th central moment exists for some p in (1, 2]. The research question is whether it is possible to achieve universal dynamic regret—which tracks the performance of an arbitrary comparator sequence—in a parameter-free manner (without knowing the Lipschitz constant, noise level, or tail index) under these heavy-tailed conditions.

The author proposes HT-PAder, an algorithm that combines two primary components to handle the challenges of non-stationarity and heavy-tailed noise:

1. Restarted AdaGrad Experts: The algorithm uses a geometric pool of block lengths, where each block runs an AdaGrad expert. Restarting the experts localizes the correction terms that typically arise from AdaGrad's variable stepsize, allowing the algorithm to adapt to unknown path lengths and gradient scales.
2. AdaGrad-Hedge: This is a pathwise meta-algorithm used to aggregate the experts. Unlike standard Hedge, which requires finite-variance assumptions on meta-losses, AdaGrad-Hedge provides a deterministic regret bound that holds for any realization of meta-losses, making it robust to heavy-tailed noise.

HT-PAder achieves a universal dynamic regret bound of O(GDsqrt(T(1+P_T/D)) + sigmaDT^(1/p)(1+P_T/D)^((p-1)/p)). This bound is minimax optimal, as confirmed by a matching lower bound established in the paper. Notably, the algorithm is parameter-free, meaning it does not require prior knowledge of the problem's parameters (G, sigma, p, or the path length P_T). When p=2, the algorithm recovers the first parameter-free minimax dynamic regret guarantee for standard finite-variance OCO.