The cost of enforcing long-run coverage: a phase transition in online conformal prediction
Organizations: Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · Department of Statistics, University of Chicago
Abstract
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 at each time . 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 by at most , for some . We prove that this family of conditions can be described with a phase transition. For , 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 , this type of condition comes at a cost, and does not achieve best-of-both-worlds behavior.
Figures & tables
Conformal Prediction
Conformal prediction wraps predictive models with calibrated sets or intervals that provide statistical coverage guarantees.
See all 395 papers