无需参数设定，可应对重尾噪声下的动态优化问题。
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
- 采用重启AdaGrad专家与路径元算法结合的自适应策略。
- 实现最优路径长度依赖的动态后悔界，不依赖任何先验参数。
- 适合噪声分布不满足方差条件的在线学习场景。
研究在非平稳环境和重尾噪声下的在线凸优化问题，其中随机梯度仅具有有限$p$阶中心矩（$p∈(1,2]$）。尽管静态后悔已充分理解，但实现无需参数设定的通用动态后悔仍是开放挑战。本文提出HT-PAder算法，结合重启AdaGrad专家与几何块长池的路径元算法AdaGrad-Hedge，无需对元损失施加矩条件。在直径$D$、Lipschitz常数$G$、噪声水平$σ$、比较路径长度$P_T$下，该算法实现期望通用动态后悔界：$ ilde Oig(GD oot{T(1+P_T/D)} + σD T^{1/p}(1+P_T/D)^{(p-1)/p}ig)$。算法无需预先知晓任何问题参数。即使在方差有限情形（$p=2$），HT-PAder也首次提供参数无关的极小极大最优动态后悔保证。我们还证明了匹配下界，确立路径长度指数的最优性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。