提出在线预测集构造新方法,应对部分反馈的对抗性环境。
Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization

- 将预测集选择建模为对抗性老虎机问题,通过最小化后悔来优化。
- 在独立同分布与非独立同分布数据下,误覆盖率可控且预测集合理大小。
- 适用于真实场景中标签仅在预测包含时才可获取的系统。
不确定性量化对安全关键系统至关重要,需在不确定性下做出决策。本文研究在线不确定性量化问题,数据点按序到达。在线合取预测是一种原则性方法,可在每一步动态构建预测集。现有方法虽无需分布假设即可保证长期覆盖率,但通常假设完整反馈(即始终观测真实标签)。本文提出一种新学习方法,适用于自适应对手的半老虎机部分反馈环境——仅当真实标签位于预测集中时才被观测。我们将在线合取预测建模为对抗性老虎机问题,将每个候选预测集视为一个动作。基于已有对抗性老虎机算法,本方法通过建立其与学习者后悔值的关联,实现长期覆盖率保证。实验表明,在独立同分布与非独立同分布设置下,该方法能有效控制误覆盖率,同时保持预测集合理大小。
原文摘要 · Abstract (English)
Uncertainty quantification is crucial in safety-critical systems, where decisions must be made under uncertainty. In particular, we consider the problem of online uncertainty quantification, where data points arrive sequentially. Online conformal prediction is a principled online uncertainty quantification method that dynamically constructs a prediction set at each time step. While existing methods for online conformal prediction provide long-run coverage guarantees without any distributional assumptions, they typically assume a full feedback setting in which the true label is always observed. In this paper, we propose a novel learning method for online conformal prediction with partial feedback from an adaptive adversary-a more challenging setup where the true label is revealed only when it lies inside the constructed prediction set. Specifically, we formulate online conformal prediction as an adversarial bandit problem by treating each candidate prediction set as an arm. Building on an existing algorithm for adversarial bandits, our method achieves a long-run coverage guarantee by explicitly establishing its connection to the regret of the learner. Finally, we empirically demonstrate the effectiveness of our method in both independent and identically distributed (i.i.d.) and non-i.i.d. settings, showing that it successfully controls the miscoverage rate while maintaining a reasonable size of the prediction set.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。