# Online conformal prediction with decaying step sizes

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 2 Feb 2024.

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

- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Safe Planning in Dynamic Environments using Conformal Prediction](https://mlsanity.com/paper/2210.10254/) (2022)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [Sequential Predictive Conformal Inference for Time Series](https://mlsanity.com/paper/2212.03463/) (2022)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Improving Conditional Coverage via Orthogonal Quantile Regression](https://mlsanity.com/paper/2106.00394/) (2021)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Achieving Risk Control in Online Learning Settings](https://mlsanity.com/paper/2205.09095/) (2022)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Conformal Prediction with Temporal Quantile Adjustments](https://mlsanity.com/paper/2205.09940/) (2022)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Best of Both Worlds Policy Optimization](https://mlsanity.com/paper/2302.09408/) (2023)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [Methods to Compute Prediction Intervals: A Review and New Results](https://mlsanity.com/paper/2011.03065/) (2020)

## Built on by (most cited first, 30 of 56)

- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Localized Adaptive Risk Control](https://mlsanity.com/paper/2405.07976/) (2024)
- [Kernel-based Optimally Weighted Conformal Time-Series Prediction](https://mlsanity.com/paper/2405.16828/) (2024)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Error-quantified Conformal Inference for Time Series](https://mlsanity.com/paper/2502.00818/) (2025)
- [Conformal online model aggregation](https://mlsanity.com/paper/2403.15527/) (2024)
- [Conformalized Interactive Imitation Learning: Handling Expert Shift and Intermittent Feedback](https://mlsanity.com/paper/2410.08852/) (2024)
- [On Continuous Monitoring of Risk Violations under Unknown Shift](https://mlsanity.com/paper/2506.16416/) (2025)
- [Conformal Prediction and Human Decision Making](https://mlsanity.com/paper/2503.11709/) (2025)
- [Stochastic Online Conformal Prediction with Semi-Bandit Feedback](https://mlsanity.com/paper/2405.13268/) (2024)
- [Mirror Online Conformal Prediction with Intermittent Feedback](https://mlsanity.com/paper/2503.10345/) (2025)
- [Conformal Distributed Remote Inference in Sensor Networks Under Reliability and Communication Constraints](https://mlsanity.com/paper/2409.07902/) (2024)
- [Exploring the Noise Robustness of Online Conformal Prediction](https://mlsanity.com/paper/2501.18363/) (2025)
- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)
- [Conformal Prediction for Time-series Forecasting with Change Points](https://mlsanity.com/paper/2509.02844/) (2025)
- [Distributed Conformal Prediction via Message Passing](https://mlsanity.com/paper/2501.14544/) (2025)
- [Dynamic Estimation Loss Control in Variational Quantum Sensing via Online Conformal Inference](https://mlsanity.com/paper/2505.23389/) (2025)
- [Efficient Federated Conformal Prediction with Group-Conditional Guarantee](https://mlsanity.com/paper/2603.14198/) (2026)
- [Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization](https://mlsanity.com/paper/2604.17984/) (2026)
- [The Benefit of Being Bayesian in Online Conformal Prediction](https://mlsanity.com/paper/2410.02561/) (2024)
- [Online scalable Gaussian processes with conformal prediction for guaranteed coverage](https://mlsanity.com/paper/2410.05444/) (2024)
- [Multi-model Online Conformal Prediction with Graph-Structured Feedback](https://mlsanity.com/paper/2506.20898/) (2025)
- [Prediction-Powered Communication with Distortion Guarantees](https://mlsanity.com/paper/2509.24373/) (2025)
- [Conformal Inference for Open-Set and Imbalanced Classification](https://mlsanity.com/paper/2510.13037/) (2025)
- [Multi-Round Human-AI Collaboration with User-Specified Requirements](https://mlsanity.com/paper/2602.17646/) (2026)
- [Online Selective Conformal Prediction: Errors and Solutions](https://mlsanity.com/paper/2503.16809/) (2025)
- [CP2: Leveraging Geometry for Conformal Prediction via Canonicalization](https://mlsanity.com/paper/2506.16189/) (2025)
- [Extending Prediction-Powered Inference through Conformal Prediction](https://mlsanity.com/paper/2510.16166/) (2025)
- [Distribution-informed Online Conformal Prediction](https://mlsanity.com/paper/2512.07770/) (2025)
- [Certified Adaptive Refresh: Anytime-Valid Monitoring for Federated Conformal RAG](https://mlsanity.com/paper/2605.29139/) (2026)

## Abstract (arXiv)

We introduce a method for online conformal prediction with decaying step sizes. Like previous methods, ours possesses a retrospective guarantee of coverage for arbitrary sequences. However, unlike previous methods, we can simultaneously estimate a population quantile when it exists. Our theory and experiments indicate substantially improved practical properties: in particular, when the distribution is stable, the coverage is close to the desired level for every time point, not just on average over the observed sequence.