Papers

在线保形预测硬覆盖约束的代价被量化:最多需要 Θ(√T) 额外预测集规模

The Price of Hard Coverage Constraints in Online Conformal Prediction

Why we picked it

这篇理论论文把一个常被忽略的问题算清楚了:如果你要求保形预测在流式部署中全程不超失误预算,预测集要额外膨胀多少。结论很反直觉——就算数据分布完全已知,代价也躲不掉,最坏情况是 Θ(√T)。做风险控制、异常检测这类不能容忍覆盖失效的系统的人,选评估口径前应该先看这篇。

arXiv 论文《The Price of Hard Coverage Constraints in Online Conformal Prediction》研究了在线保形预测中的硬覆盖约束问题:预测集逐轮产出,累计失误次数必须在部署全程不超过给定预算。论文刻画了满足该约束的任何在线方法所必需的最小累计超额预测集规模。

Body

核心结论是三项复杂度下界:对预先固定的评估时点,期望代价为 Θ(log T);对所有不晚于 T 的固定时点取最大期望代价,为 Θ(T^{1/3});对事后选定时点的期望最坏实际代价,为 Θ(√T)。值得注意的是,即使数据是 i.i.d.、score 分布已知、且总体最优预测集完全可知,这一代价依然存在。

论文进一步证明这些速率可以仅凭历史 scores 达到,无需预先知道 score 分布。这对需要在流式场景中提供严格覆盖保证的开发者意味着:序列可靠性有不可消除的效率税,扩大预测集的规模预算应按对数到平方根量级提前规划。

Original · arXiv cs.LG

The Price of Hard Coverage Constraints in Online Conformal Prediction

Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over $T$ prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is $Θ(\log T)$ for expected cost at a fixed time known in advance, $Θ(T^{1/3})$ for the largest expected cost over all fixed times up to $T$, and $Θ(\sqrt{T})$ for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.

Industry Coordinates & Source Verification

This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include Conformal Prediction, uncertainty quantification, online learning.

Source attribution: curated from arXiv cs.LG (@Mingrui Liu).