arXiv:2606.18527stat.MLcs.LG2026-06被引 2

提出一种新算法,让预测同时适应难易损失,实现最优后悔率。

Toward Simultaneously Optimal Regret in U-Calibration

  • 基于自协变噪声的扰动领袖跟踪法,直接在预测空间施加扰动
  • 对任意有界凸损失保持√T后悔率,对光滑损失降至log T
  • 适用于非Lipschitz损失,适合在线预测与鲁棒建模场景

U-校准研究一类在线预测算法,其输出可被任意未知下游代理使用,并保证对所有正则损失函数均实现次线性后悔。现有算法对每个有界正则损失均可达到最坏情况下的O(√T)后悔率,但无法适应更简单的损失:我们证明,即使对平方损失这类光滑损失,它们仍会带来Ω(√T)的后悔,而非最优的O(log T)。本文表明该限制并非本质缺陷。具体而言,我们设计了一种单一预测算法,能同时对所有有界正则损失实现˜O(√T)后悔率,并对所有有界光滑正则损失实现O(log T)后悔率。更一般地,该算法还可在损失相对于对数障碍光滑时实现对数后悔,涵盖多个非Lipschitz情形。方法基于一种新型的跟随扰动领袖(FTPL)变体,其中扰动直接作用于预测空间,采用自协变噪声。由此带来的分析也因该噪声的复杂性而显著区别于以往,可能具有独立研究价值。

原文摘要 · Abstract (English)

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal $O(\sqrt{T})$ regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur $Ω(\sqrt{T})$ regret instead of the optimal $O(\log T)$ regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves $\tilde O(\sqrt{T})$ regret for every bounded proper loss and $O(\log T)$ regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

在线学习后悔率优化预测算法FTPL

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。