跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21542 · v1

The cost of enforcing long-run coverage: a phase transition in online conformal prediction

首次提交 2026-11-17 02:28
版本更新 2026-11-17 02:28
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

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 ≥1−α\geq 1-α at each time tt. 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−α1-α by at most O(T−β)\mathcal{O}(T^{-β}), for some β∈[0,1]β\in[0,1]. We prove that this family of conditions can be described with a phase transition. For β∈[0,12]β\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 β∈(12,1]β\in(\frac{1}{2},1], this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 02:28 · 最新观测版本

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 ≥1−α\geq 1-α at each time tt. 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−α1-α by at most O(T−β)\mathcal{O}(T^{-β}), for some β∈[0,1]β\in[0,1]. We prove that this family of conditions can be described with a phase transition. For β∈[0,12]β\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 β∈(12,1]β\in(\frac{1}{2},1], this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.

查看此版本解读 →查看此版本原文 ↗