揭示了无悔学习与在线推断预测间的深层联系，解决对抗环境下分组覆盖率难题。
The Relationship between No-Regret Learning and Online Conformal Prediction
- 用交换悔恨（swap-regret）建立对抗环境下的阈值校准覆盖关系
- 证明追随扰动领袖类算法可实现任意分组函数的分组条件覆盖率
- 提出并实验验证了ACI算法的多组推广版本，在对抗设置下保持覆盖率
现有的在线容错预测算法（保证对抗环境中边际覆盖率）均为在线梯度下降（OGD）的变体，但其最坏情况覆盖率分析无法从OGD的悔恨保证中推出。我们发现：尽管标准悔恨保证可导出独立同分布（i.i.d.）环境下的边际覆盖率，但一旦进入对抗环境或要求分组条件覆盖率，该联系即失效。另一方面，我们证明了在对抗环境中，阈值校准覆盖率与交换悔恨之间存在紧密联系，并可扩展至分组条件（多有效）覆盖率。我们还表明，属于“追随扰动领袖”类的无悔学习算法（包括OGD）可用于在对抗环境中对任意分组函数提供分组条件覆盖率保证。通过这一联系，我们分析并实验了Gibbs & Candes [2021]提出的ACI算法的多组推广版本（arXiv:2106.00170）。
原文摘要 · Abstract (English)
Existing algorithms for online conformal prediction -- guaranteeing marginal coverage in adversarial settings -- are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the perturbed leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes [2021] (arXiv:2106.00170).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。