Search papers, labs, and topics across Lattice.
This paper addresses the challenge of achieving universal dynamic regret in online convex optimization (OCO) under heavy-tailed noise without requiring parameter knowledge. The authors introduce HT-PAder, a novel algorithm that combines restarted AdaGrad experts with a pathwise meta-algorithm, AdaGrad-Hedge, allowing it to operate effectively even when the stochastic gradient oracle has only a finite p-th central moment. The key result is that HT-PAder achieves an expected universal dynamic regret that scales optimally with problem parameters, marking a significant advancement in parameter-free OCO methodologies.
Achieving universal dynamic regret in online convex optimization without any prior knowledge of problem parameters could redefine the landscape of adaptive algorithms 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 \textbf{HT-PAder}, a parameter-free algorithm combining restarted AdaGrad experts over a geometric pool of block lengths with a pathwise meta-algorithm, \textbf{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.
