Trade-offs arise in ensuring reliable long-term prediction intervals online
The cost of enforcing long-run coverage: a phase transition in online conformal prediction
Machine Learning
Summary
When computers make predictions over time, they can give ranges that likely contain the true answer. This works well when data behaves consistently but struggles if data changes or is unpredictable. The authors study the balance between guaranteeing long-term accuracy and keeping predictions stable moment to moment. They find there is a clear boundary — for certain levels of strictness, it’s possible to have both stable and long-term reliable predictions, but beyond that boundary, trade-offs appear and you can’t have both.
What this means in practice
- •For data engineering teams: Design online prediction systems that balance long-term reliability and short-term stability under uncertain data conditions.
- •For financial algorithm developers: Build predictive models that maintain reliable coverage guarantees over time despite market shifts and unexpected data changes.
A theory result. No direct application yet.
Authors
Yu Gui, Rina Foygel Barber, Cong Ma
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 $\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.