Stochastic Online Conformal Prediction with Semi-Bandit Feedback

• URL: http://arxiv.org/abs/2405.13268v2
• Date: Wed, 02 Oct 2024 21:46:53 GMT
• Title: Stochastic Online Conformal Prediction with Semi-Bandit Feedback
• Authors: Haosen Ge, Hamsa Bastani, Osbert Bastani,
• Abstract summary: We consider the online learning setting, where examples arrive over time, and the goal is to construct prediction sets dynamically. We propose a novel conformal prediction algorithm targeted at this setting, and prove that it obtains sublinear regret compared to the optimal conformal predictor.
• Score: 29.334511328067777
• License:
• Abstract: 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.

Related papers

• Multi-model Ensemble Conformal Prediction in Dynamic Environments [14.188004615463742]
  We introduce a novel adaptive conformal prediction framework, where the model used for creating prediction sets is selected on the fly from multiple candidate models. The proposed algorithm is proven to achieve strongly adaptive regret over all intervals while maintaining valid coverage.
  arXiv  Detail & Related papers  (2024-11-06T05:57:28Z)
• Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning [53.42244686183879]
  Conformal prediction provides model-agnostic and distribution-free uncertainty quantification. Yet, conformal prediction is not reliable under poisoning attacks where adversaries manipulate both training and calibration data. We propose reliable prediction sets (RPS): the first efficient method for constructing conformal prediction sets with provable reliability guarantees under poisoning.
  arXiv  Detail & Related papers  (2024-10-13T15:37:11Z)
• Conformal Structured Prediction [32.23920437534215]
  We propose a general framework for conformal prediction in the structured prediction setting. We show how our algorithm can be used to construct prediction sets that satisfy a desired coverage guarantee in several domains.
  arXiv  Detail & Related papers  (2024-10-08T18:56:15Z)
• Selecting informative conformal prediction sets with false coverage rate control [0.873811641236639]
  Conformal methods provide prediction sets for the outcome/label with finite sample coverage for any machine learning predictor. We consider both the classification and regression settings where the analyst may consider as informative only the sample with prediction sets small enough. We develop a unified framework for building such informative conformal prediction sets while controlling the false coverage rate (FCR) on the selected sample.
  arXiv  Detail & Related papers  (2024-03-18T22:35:43Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  Prediction sets capture uncertainty by predicting sets of labels rather than individual labels. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. We evaluate our approach on five datasets.
  arXiv  Detail & Related papers  (2023-10-19T17:57:57Z)
• Predictive Inference with Feature Conformal Prediction [80.77443423828315]
  We propose feature conformal prediction, which extends the scope of conformal prediction to semantic feature spaces. From a theoretical perspective, we demonstrate that feature conformal prediction provably outperforms regular conformal prediction under mild assumptions. Our approach could be combined with not only vanilla conformal prediction, but also other adaptive conformal prediction methods.
  arXiv  Detail & Related papers  (2022-10-01T02:57:37Z)
• Practical Adversarial Multivalid Conformal Prediction [27.179891682629183]
  We give a generic conformal prediction method for sequential prediction. It achieves target empirical coverage guarantees against adversarially chosen data. It is computationally lightweight -- comparable to split conformal prediction.
  arXiv  Detail & Related papers  (2022-06-02T14:33:00Z)
• Conformal prediction for the design problem [72.14982816083297]
  In many real-world deployments of machine learning, we use a prediction algorithm to choose what data to test next. In such settings, there is a distinct type of distribution shift between the training and test data. We introduce a method to quantify predictive uncertainty in such settings.
  arXiv  Detail & Related papers  (2022-02-08T02:59:12Z)
• Few-shot Conformal Prediction with Auxiliary Tasks [29.034390810078172]
  We develop a novel approach to conformal prediction when the target task has limited data available for training. We obtain substantially tighter prediction sets while maintaining desirable marginal guarantees by casting conformal prediction as a meta-learning paradigm. We demonstrate the effectiveness of this approach across a number of few-shot classification and regression tasks in natural language processing, computer vision, and computational chemistry for drug discovery.
  arXiv  Detail & Related papers  (2021-02-17T17:46:57Z)
• Private Prediction Sets [72.75711776601973]
  Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. We evaluate the method on large-scale computer vision datasets.
  arXiv  Detail & Related papers  (2021-02-11T18:59:11Z)
• AutoCP: Automated Pipelines for Accurate Prediction Intervals [84.16181066107984]
  This paper proposes an AutoML framework called Automatic Machine Learning for Conformal Prediction (AutoCP) Unlike the familiar AutoML frameworks that attempt to select the best prediction model, AutoCP constructs prediction intervals that achieve the user-specified target coverage rate. We tested AutoCP on a variety of datasets and found that it significantly outperforms benchmark algorithms.
  arXiv  Detail & Related papers  (2020-06-24T23:13:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.