arXiv:2607.26577cs.LGcs.DS2026-07

提出新方法同时保证在线预测的覆盖率与效率,克服传统方法三大缺陷。

Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction

  • 统一框架下同时控制覆盖误差与预测集大小,不依赖固定基准。
  • 在对抗设定中实现任意单调利普希茨效率目标的最优保证。
  • 适用于分布漂移场景,适合需要稳定可靠预测的研究者。

自适应共形推断(ACI)及其变体是分布漂移下在线共形预测的标准方法,但存在三个根本性局限:第一,其保证仅控制有符号长期覆盖误差,方向性持续误覆盖可能被后续补偿掩盖;第二,对预测集大小无约束,可通过过度放宽实现形式有效性;第三,现有效率保证对比的是事后固定的预测器,当数据分布漂移时该基准不再合理。本文提出统一在线学习框架,同时控制绝对非抵消覆盖偏差与针对动态变化基准的预测效率。在全对抗设定中,利用标准ACI更新等价于在pinball损失上的投影在线梯度下降,推导出任意单调利普希茨效率目标下的联合保证,无需分布假设或凸性条件。在具有完整评分反馈的随机设定中,设计滑动窗口分位数追踪器,并建立匹配的极小极大下界,证明算法率最优。在协变量相关随机设定中,开发分块式ACI算法以跟踪函数值型理想阈值,获得联合覆盖与效率保证。

原文摘要 · Abstract (English)

Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a \emph{fixed} predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.

在线学习共形预测覆盖率效率保证

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