Online Conformal Prediction with Efficiency Guarantees

We study the problem of conformal prediction in a novel online framework that directly optimizes efficiency. In our problem, we are given a target miscoverage rate \(\alpha \gt 0\), and a time horizon \(T\). On each day \(t \le T\) an algorithm must output an interval \(I_t \subseteq [0,1]\), then a point \(y_t \in [0,1]\) is revealed. The goal of the algorithm is to achieve coverage, that is, \(y_t \in I_t\) on (close to) a \((1-\alpha)\)-fraction of days, while maintaining efficiency, that is, minimizing the average volume (length) of the intervals played. This problem is an online analogue to the problem of constructing efficient confidence intervals.