# The Benefit of Being Bayesian in Online Conformal Prediction

arXiv: https://arxiv.org/abs/2410.02561 · HTML: https://mlsanity.com/paper/2410.02561/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 3 Oct 2024.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Conformal Bayesian Computation](https://mlsanity.com/paper/2106.06137/) (2021)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Optimal Multiclass U-Calibration Error and Beyond](https://mlsanity.com/paper/2405.19374/) (2024)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)

## Built on by (most cited first, 3 of 3)

- [Mirror Online Conformal Prediction with Intermittent Feedback](https://mlsanity.com/paper/2503.10345/) (2025)
- [Calibrated Multi-Level Quantile Forecasting](https://mlsanity.com/paper/2512.23671/) (2025)
- [Feature Fitted Online Conformal Prediction for Deep Time Series Forecasting Model](https://mlsanity.com/paper/2505.08158/) (2025)

## Abstract (arXiv)

Based on the framework of Conformal Prediction (CP), we study the online construction of confidence sets given a black-box machine learning model. By converting the target confidence levels into quantile levels, the problem can be reduced to predicting the quantiles (in hindsight) of a sequentially revealed data sequence. Two very different approaches have been studied previously: (i) Assuming the data sequence is iid or exchangeable, one could maintain the empirical distribution of the observed data as an algorithmic belief, and directly predict its quantiles. (ii) Due to the fragility of statistical assumptions, a recent trend is to consider the non-distributional, adversarial setting and apply first-order online optimization algorithms to moving quantile losses. However, it requires the oracle knowledge of the target quantile level, and suffers from a previously overlooked monotonicity issue due to the associated loss linearization. This paper presents an adaptive CP algorithm that combines their strengths. Without any statistical assumption, it is able to answer multiple arbitrary confidence level queries with low regret, while also overcoming the monotonicity issue suffered by first-order optimization baselines. Furthermore, if the data sequence is actually iid, then the same algorithm is automatically equipped with the "correct" coverage probability guarantee. To achieve such strengths, our key technical innovation is to regularize the aforementioned algorithmic belief (the empirical distribution) by a Bayesian prior, which robustifies it by simulating a non-linearized Follow the Regularized Leader (FTRL) algorithm on the output. Such a belief update backbone is shared by prediction heads targeting different confidence levels, bringing practical benefits analogous to the recently proposed concept of U-calibration (Kleinberg et al., 2023).