arXiv 论文证明在线保形预测存在相变现象
The cost of enforcing long-run coverage: a phase transition in online conformal prediction
保形预测圈子的理论好文:想在数据漂移时守住长程覆盖率,iid 场景下瞬时覆盖会跟着抖。作者算出了分界线 β=1/2,超过这个阈值两头就顾不上。做时序预测或风控区间的人值得看看。
一篇 arXiv 论文研究了在线保形预测中的两难问题:在 i.i.d. 数据下追求瞬时 training-conditional coverage 的低累积误差,与在对抗性数据漂移下保证 long-run empirical coverage 之间难以兼得。
作者设定长程经验覆盖率偏离目标水平 1-α 不超过 O(T^{-β}) 的约束族,β∈[0,1],并证明了该约束存在相变结构。当 β∈[0,1/2] 时,可以构造算法在对抗性设定下满足该约束,同时数据为 i.i.d. 时瞬时覆盖性能与 split conformal prediction 相同。
而当 β∈(1/2,1] 时,这类约束的代价显现,算法无法实现 best-of-both-worlds 行为。这一结果为在分布漂移场景下设计在线预测区间算法划定了可行边界,对需要处理 changepoint 或漂移数据的从业者具有直接的算法选择指导意义。
The cost of enforcing long-run coverage: a phase transition in online conformal prediction
Consider an online prediction setting, where at each time, we are given a new feature vector and asked to provide a prediction interval or prediction set that will likely contain the corresponding response. In this setting, if the data points are i.i.d. (or more generally, exchangeable), conformal prediction provides a mechanism for building valid prediction sets around the output of any trained model, offering coverage probability $\geq 1-α$ at each time $t$. In practice, however, issues such as distribution drift, changepoints, or other challenges may cause violations of the i.i.d. assumption. In this adversarial setting, online conformal prediction methods can still offer guarantees on long-run empirical coverage. However, there is a trade-off between these two types of goals: enforcing tight constraints on long-run empirical coverage to protect against the adversarial setting can lead to unstable oscillations in the instantaneous training-conditional coverage in the i.i.d. setting. In this work, we seek best-of-both-worlds algorithms that aim to minimize cumulative error in instantaneous training-conditional coverage when in the i.i.d. setting, while also offering long-run empirical coverage guarantees in the adversarial setting. Specifically, consider a condition that requires long-run empirical coverage to deviate from the target level $1-α$ by at most $\mathcal{O}(T^{-β})$, for some $β\in[0,1]$. We prove that this family of conditions can be described with a phase transition. For $β\in[0,\frac{1}{2}]$, it is possible to construct algorithms satisfying such a constraint in the adversarial setting, while offering the same instantaneous coverage performance as split conformal prediction if the data is in fact i.i.d. On the other hand, for $β\in(\frac{1}{2},1]$, this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include conformal prediction, online learning, phase change.
Source attribution: curated from arXiv cs.LG (@Yu Gui, Rina Foygel Barber, Cong Ma).