[2026年7月29日提出]

PDF を表示 HTML（実験的）

要旨: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 $\sigma$, 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)} + \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.

投稿履歴

投稿者: Vaneet Aggarwal [メールを表示]
[v1] 2026年7月29日 水曜日 15:58:18 UTC (21 KB)