Online Conformal Prediction with Adversarial Feedback via Regret Minimization

Quantifying uncertainty is crucial in safety-critical learning systems where decisions are made based on uncertainty. Conformal prediction is one promising way to quantify uncertainty that comes with a theoretical guarantee. However, the theoretical guarantee comes with a price of the assumption on data generation process, including exchangeability or full feedback. In this paper, we propose a novel conformal prediction method with less data generation assumption, i.e., a learning method for online conformal prediction with partial feedback from an adaptive adversary. In particular, we leverage matured literatures in sequential prediction and adversarial bandits to design our online conformal prediction algorithm. The great benefit of the reliance on adversarial bandits is that we can exploit theoretical regret bounds for conformal prediction guarantees. Here, we explicitly connect the regret and a desired miscoverage guarantee in conformal prediction such that our algorithm via adversarial bandits can naturally provide a miscoverage guarantee from the regret bounds. Furthermore, we extend an existing adversarial bandit method to leverage the properties of conformal prediction, resulting in a bandit method with a tighter regret bound. We empirically demonstrate the efficacy of our conformal prediction method over various learning setups, including a stochastic setup and covariate shift setup, showing a controllability on a micoverage rate while achieving a reasonable conformal set size.