[2026年7月29日提交]

查看PDF HTML（实验性）

摘要：我们研究了在重尾噪声下的非平稳环境中的在线凸优化（OCO），其中随机梯度oracle仅具有有限的p阶中心矩（p ∈ (1, 2]）。尽管静态遗憾已被充分理解，但在无参数情况下实现通用动态遗憾仍是一个未解难题。我们通过提出\textbf{HT-PAder}算法解决了这一问题，该算法结合了几何块长度池上的重启AdaGrad专家与路径自适应元算法\textbf{AdaGrad-Hedge}，后者对元损失不需要矩条件。对于直径为D、Lipschitz常数为G、噪声水平为σ、比较路径长度为P_T的域，HT-PAder实现了期望通用动态遗憾为 \[ \widetilde O\left( GD\sqrt{T(1+P_T/D)} + \sigma D T^{1/p}(1+P_T/D)^{(p-1)/p} \right). \] 该算法不需要任何问题参数的先验知识。即使在有限方差（p=2）的特殊情况下，HT-PAder也提供了首个无参数极小极大通用动态遗憾保证。我们还证明了一个匹配的下界，确立了路径长度指数的最优性。

提交历史

来自: Vaneet Aggarwal [查看邮箱]
[v1] 2026年7月29日 周三 15:58:18 UTC (21 KB)