# The Relationship between No-Regret Learning and Online Conformal Prediction

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 16 Feb 2025.

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal Prediction With Conditional Guarantees](https://mlsanity.com/paper/2305.12616/) (2023)
- [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)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [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)
- [Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions](https://mlsanity.com/paper/2310.05921/) (2023)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [With Malice Towards None: Assessing Uncertainty via Equalized Coverage](https://mlsanity.com/paper/1908.05428/) (2019)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Achieving Risk Control in Online Learning Settings](https://mlsanity.com/paper/2205.09095/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Advancing subgroup fairness via sleeping experts](https://mlsanity.com/paper/1909.08375/) (2019)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Gradient Equilibrium in Online Learning: Theory and Applications](https://mlsanity.com/paper/2501.08330/) (2025)
- [Group-wise oracle-efficient algorithms for online multi-group learning](https://mlsanity.com/paper/2406.05287/) (2024)
- [Oracle Efficient Algorithms for Groupwise Regret](https://mlsanity.com/paper/2310.04652/) (2023)

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

- [When to Trust the Cheap Check: Weak and Strong Verification for Reasoning](https://mlsanity.com/paper/2602.17633/) (2026)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)
- [Multi-Round Human-AI Collaboration with User-Specified Requirements](https://mlsanity.com/paper/2602.17646/) (2026)
- [Distribution-informed Online Conformal Prediction](https://mlsanity.com/paper/2512.07770/) (2025)
- [ConformalShift: Targeted Event Reordering Against Adaptive ECG Monitoring](https://mlsanity.com/paper/2608.03628/) (2026)
- [Strategic Decision Support for AI Agents](https://mlsanity.com/paper/2606.12587/) (2026)
- [Online Conformal Prediction Beyond Feedback](https://mlsanity.com/paper/2608.07139/) (2026)
- [The Hidden Game Problem](https://mlsanity.com/paper/2510.03845/) (2025)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)
- [Parameter-Free and Group Conditional Online Conformal Prediction](https://mlsanity.com/paper/2606.00419/) (2026)
- [Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction](https://mlsanity.com/paper/2607.26577/) (2026)
- [Counterfactual Online Conformal Prediction Under Adaptive Logging](https://mlsanity.com/paper/2609.30811/) (2026)

## Abstract (arXiv)

Existing algorithms for online conformal prediction -- guaranteeing marginal coverage in adversarial settings -- are variants of online gradient descent (OGD), but their analyses of worst-case coverage do not follow from the regret guarantee of OGD. What is the relationship between no-regret learning and online conformal prediction? We observe that although standard regret guarantees imply marginal coverage in i.i.d. settings, this connection fails as soon as we either move to adversarial environments or ask for group conditional coverage. On the other hand, we show a tight connection between threshold calibrated coverage and swap-regret in adversarial settings, which extends to group-conditional (multi-valid) coverage. We also show that algorithms in the follow the perturbed leader family of no regret learning algorithms (which includes online gradient descent) can be used to give group-conditional coverage guarantees in adversarial settings for arbitrary grouping functions. Via this connection we analyze and conduct experiments using a multi-group generalization of the ACI algorithm of Gibbs & Candes [2021] (arXiv:2106.00170).