The Price of Hard Coverage Constraints in Online Conformal Prediction
Keeping prediction errors within a running budget requires larger prediction sets—even with perfect statistical knowledge.
The paper studies online prediction under a hard limit on cumulative miscoverages at every round. Under suitable regularity conditions, the minimum cumulative excess set size scales as Θ(log T) at a prespecified evaluation time, Θ(T⅓) for the largest expected cost across fixed times, and Θ(√T) for the expected worst realized cost evaluated in hindsight. These costs persist with independent, identically distributed data and a known score distribution. Methods using only past scores can attain the same rates without knowing that distribution.
ArXiv · AI/CL/LG's note
The paper studies online prediction under a hard limit on cumulative miscoverages at every round. Under suitable regularity conditions, the minimum cumulative excess set size scales as Θ(log T) at a prespecified evaluation time, Θ(T⅓) for the largest expected cost across fixed times, and Θ(√T) for the expected worst realized cost evaluated in hindsight. These costs persist with independent, identically distributed data and a known score distribution. Methods using only past scores can attain the same rates without knowing that distribution.
ArXiv · AI/CL/LG's note
score 4