Stochastic Online Conformal Prediction with Semi-Bandit Feedback

Overview

• The paper introduces a new conformal prediction algorithm for the online learning setting with semi-bandit feedback.
• Conformal prediction is a technique that outputs prediction sets instead of single labels, with a guarantee that the true label is contained in the set with high probability.
• The semi-bandit feedback setting is where the true label is only revealed if it is contained in the prediction set, e.g. when calibrating a document retrieval model to a new domain.
• The proposed algorithm is shown to achieve sublinear regret compared to the optimal conformal predictor in this setting.

Plain English Explanation

In standard machine learning, models are typically trained to output a single predicted label for each input. However, this can be uncertain, especially when applying a model to a new domain. Conformal prediction is a technique that modifies models to instead output a

of possible labels. These prediction sets are designed to contain the true label with high probability.

This paper focuses on the

setting, where examples arrive over time, and the goal is to construct these prediction sets dynamically. The researchers assume a scenario, where the true label is only revealed if it is contained in the prediction set. This is like calibrating a document retrieval model - the user can only provide feedback if the target document is in the set of retrieved documents.

The researchers propose a new conformal prediction algorithm tailored to this semi-bandit setting. They prove that their algorithm achieves

, meaning it performs nearly as well as the best possible conformal predictor over time. They also demonstrate good empirical performance on retrieval and image classification tasks.

Technical Explanation

The key technical contribution of this paper is a novel conformal prediction algorithm designed for the online learning setting with

. In this setting, examples arrive sequentially, and the true label is only revealed if it is contained in the prediction set output by the model.

The algorithm works as follows: for each new example, it computes a

that measures how different the example is from the previous examples. It then uses these scores to construct a that is guaranteed to contain the true label with high probability, as in standard conformal prediction.

Crucially, the algorithm updates its internal model

based on the semi-bandit feedback received. That is, it only updates the model when the true label is revealed (i.e., when it is contained in the prediction set). The researchers prove that this approach achieves compared to the optimal conformal predictor, meaning it converges to the same performance as the optimal predictor over time.

The authors evaluate their algorithm on a document retrieval task and an image classification task. They show that it outperforms baselines that do not utilize the semi-bandit feedback, demonstrating the benefits of their adaptive approach.

Critical Analysis

The key strength of this work is its ability to handle the semi-bandit feedback setting, where the true label is only revealed when it is contained in the model's prediction set. This is a realistic scenario in many applications, such as calibrating a document retrieval model to a new domain.

That said, the paper does not address some important limitations. For example, the analysis assumes that the data is i.i.d. (independent and identically distributed), which may not hold in many real-world settings. Additionally, the algorithm requires storing all past examples, which may not be feasible for large-scale applications.

Furthermore, the paper does not discuss the

of the proposed algorithm, which is an important practical consideration. It would be helpful to understand the scalability of this approach compared to other conformal prediction methods.

Finally, the paper could benefit from a more thorough discussion of the implications of this work for the broader field of machine learning and uncertainty quantification. The potential applications and limitations of this approach could be explored in more depth.

Conclusion

This paper presents a novel conformal prediction algorithm for the online learning setting with semi-bandit feedback. By adaptively updating its internal model based on the limited feedback available, the algorithm is able to achieve strong performance guarantees compared to the optimal conformal predictor.

While the paper has some limitations, it represents an important step forward in developing effective uncertainty quantification techniques for real-world machine learning applications where full feedback may not be available. The researchers' work highlights the value of tailoring conformal prediction methods to specific feedback scenarios, and their algorithm could serve as a foundation for future developments in this area.