arXiv：cs.LG· Vaneet Aggarwal·· 3 小时前AI 评分32
重尾噪声下无参数区间动态遗憾界
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
AI 导读
研究者在每轮仅有一个无偏随机次梯度、且条件 p 阶噪声矩未知（1<p≤2）的在线凸优化中，提出一种无需 G、σ、p、I、P_I 等参数的学习器，对任意长度 n 的固定区间 I 取得区间遗憾上界，并同时保留均值梯度与噪声两个独立指数。区间自适应仅增加比较器复杂度，其代价为 1+log(T/n)，涵盖最优全时域静态速率；一项测度变换下界在显式条件下刻画出保留全时域最优保证时该对数项的噪声幂次。
正文
Abstract:We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves
\[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \]
The learner uses none of $G,\sigma,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.
| Subjects: | Machine Learning (cs.LG); Information Theory (cs.IT); Optimization and Control (math.OC) |
| Cite as: | arXiv:2610.02258 [cs.LG] |
| (or arXiv:2610.02258v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02258 arXiv-issued DOI via DataCite |
Submission history
From: Vaneet Aggarwal [view email]
[v1]
Wed, 30 Sep 2026 21:03:03 UTC (26 KB)
来源：arXiv：cs.LG · arxiv.org