# Improved Online Conformal Prediction via Strongly Adaptive Online Learning

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 78 references that are in the map.
- First posted on arXiv 15 Feb 2023.

## Builds on (most cited first, 30 of 41)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (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)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Using Trusted Data to Train Deep Networks on Labels Corrupted by Severe Noise](https://mlsanity.com/paper/1802.05300/) (2018)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [High-Quality Prediction Intervals for Deep Learning: A Distribution-Free, Ensembled Approach](https://mlsanity.com/paper/1802.07167/) (2018)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Image-to-Image Regression with Distribution-Free Uncertainty Quantification and Applications in Imaging](https://mlsanity.com/paper/2202.05265/) (2022)
- [Distribution-free uncertainty quantification for classification under label shift](https://mlsanity.com/paper/2103.03323/) (2021)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)

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

- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions](https://mlsanity.com/paper/2310.05921/) (2023)
- [Conformal Prediction Regions for Time Series using Linear Complementarity Programming](https://mlsanity.com/paper/2304.01075/) (2023)
- [Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them)](https://mlsanity.com/paper/2405.06627/) (2024)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [Conformal Prediction for Class-wise Coverage via Augmented Label Rank Calibration](https://mlsanity.com/paper/2406.06818/) (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)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [Error-quantified Conformal Inference for Time Series](https://mlsanity.com/paper/2502.00818/) (2025)
- [Conformalized Interactive Imitation Learning: Handling Expert Shift and Intermittent Feedback](https://mlsanity.com/paper/2410.08852/) (2024)
- [Conformal Prediction and Human Decision Making](https://mlsanity.com/paper/2503.11709/) (2025)
- [Empirically Validating Conformal Prediction on Modern Vision Architectures Under Distribution Shift and Long-tailed Data](https://mlsanity.com/paper/2307.01088/) (2023)
- [Stochastic Online Conformal Prediction with Semi-Bandit Feedback](https://mlsanity.com/paper/2405.13268/) (2024)
- [Multi-model Ensemble Conformal Prediction in Dynamic Environments](https://mlsanity.com/paper/2411.03678/) (2024)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Conformal Selective Acting: Anytime-Valid Risk Control for RLVR-Trained LLMs](https://mlsanity.com/paper/2605.20270/) (2026)
- [Mirror Online Conformal Prediction with Intermittent Feedback](https://mlsanity.com/paper/2503.10345/) (2025)
- [Conformal Policy Learning for Sensorimotor Control Under Distribution Shifts](https://mlsanity.com/paper/2311.01457/) (2023)
- [Adapting Prediction Sets to Distribution Shifts Without Labels](https://mlsanity.com/paper/2406.01416/) (2024)
- [Conformal Distributed Remote Inference in Sensor Networks Under Reliability and Communication Constraints](https://mlsanity.com/paper/2409.07902/) (2024)
- [Post-selection Inference for Conformal Prediction: Trading off Coverage for Precision](https://mlsanity.com/paper/2304.06158/) (2023)
- [CHAMP: Conformalized 3D Human Multi-Hypothesis Pose Estimators](https://mlsanity.com/paper/2407.06141/) (2024)
- [Exploring the Noise Robustness of Online Conformal Prediction](https://mlsanity.com/paper/2501.18363/) (2025)
- [WQLCP: Weighted Adaptive Conformal Prediction for Robust Uncertainty Quantification Under Distribution Shifts](https://mlsanity.com/paper/2505.19587/) (2025)
- [Valid Selection among Conformal Sets](https://mlsanity.com/paper/2506.20173/) (2025)
- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)

## Abstract (arXiv)

We study the problem of uncertainty quantification via prediction sets, in an online setting where the data distribution may vary arbitrarily over time. Recent work develops online conformal prediction techniques that leverage regret minimization algorithms from the online learning literature to learn prediction sets with approximately valid coverage and small regret. However, standard regret minimization could be insufficient for handling changing environments, where performance guarantees may be desired not only over the full time horizon but also in all (sub-)intervals of time. We develop new online conformal prediction methods that minimize the strongly adaptive regret, which measures the worst-case regret over all intervals of a fixed length. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously, and approximately valid coverage. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks, such as time series forecasting and image classification under distribution shift.