SyncAI.news, a Varaisys broadcasting
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
VA

Vaneet Aggarwal

· 1 min read

ResearcharXiv cs.AI

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

arXiv:2607.27073v3 Announce Type: replace-cross Abstract: We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite $p$-th central moment, where $p\in(1,2]$ is unknown. For a bounded convex domain of diameter $D$, subgradients bounded by $G$, noise scale $\sigma$, and comparator path length $P_T$, let $\Lambda_T=1+P_T/D$. A single algorithm, using none of $G,\sigma,p,P_T$, attains expected dynamic regret $O_p\left(\min\{GD\sqrt{T\Lambda_T}+\sigma DT^{1/p}\Lambda_T^{(p-1)/p},\,GDT\}\right)$ against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent $(p-1)/p$, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in $p$; its logarithm-free form has noise coefficient $O(1+\log(p/(p-1)))$, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.

Original source

This story was published by arXiv cs.AI and written by Vaneet Aggarwal. SyncAI.news shows a preview; the complete article is on the publisher's site.

Read the full story on arxiv.org

Similar News