Stochastic Online Conformal Prediction with Semi-Bandit Feedback
This addresses the challenge of uncertainty quantification for online learning in scenarios like document retrieval where full feedback is unavailable, representing an incremental advance over existing conformal prediction methods.
The paper tackled the problem of constructing prediction sets with uncertainty guarantees in an online setting with semi-bandit feedback, where true labels are only observed if contained in the prediction set, and demonstrated that their algorithm achieves sublinear regret compared to the optimal conformal predictor.
Conformal prediction has emerged as an effective strategy for uncertainty quantification by modifying a model to output sets of labels instead of a single label. These prediction sets come with the guarantee that they contain the true label with high probability. However, conformal prediction typically requires a large calibration dataset of i.i.d. examples. We consider the online learning setting, where examples arrive over time, and the goal is to construct prediction sets dynamically. Departing from existing work, we assume semi-bandit feedback, where we only observe the true label if it is contained in the prediction set. For instance, consider calibrating a document retrieval model to a new domain; in this setting, a user would only be able to provide the true label if the target document is in the prediction set of retrieved documents. We propose a novel conformal prediction algorithm targeted at this setting, and prove that it obtains sublinear regret compared to the optimal conformal predictor. We evaluate our algorithm on a retrieval task, an image classification task, and an auction price-setting task, and demonstrate that it empirically achieves good performance compared to several baselines.