# Batch Multivalid Conformal Prediction

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 30 Sep 2022.

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [With Malice Towards None: Assessing Uncertainty via Equalized Coverage](https://mlsanity.com/paper/1908.05428/) (2019)
- [Bayes-optimal prediction with frequentist coverage control](https://mlsanity.com/paper/2105.14045/) (2021)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)

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

- [Scalable Membership Inference Attacks via Quantile Regression](https://mlsanity.com/paper/2307.03694/) (2023)
- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [E-Values Expand the Scope of Conformal Prediction](https://mlsanity.com/paper/2503.13050/) (2025)
- [Conformal Prediction with Learned Features](https://mlsanity.com/paper/2404.17487/) (2024)
- [Adaptive Bounding Box Uncertainties via Two-Step Conformal Prediction](https://mlsanity.com/paper/2403.07263/) (2024)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024)
- [Rectifying Conformity Scores for Better Conditional Coverage](https://mlsanity.com/paper/2502.16336/) (2025)
- [Self-Calibrating Conformal Prediction](https://mlsanity.com/paper/2402.07307/) (2024)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Automatically Adaptive Conformal Risk Control](https://mlsanity.com/paper/2406.17819/) (2024)
- [Wasserstein-regularized Conformal Prediction under General Distribution Shift](https://mlsanity.com/paper/2501.13430/) (2025)
- [Fortuna: A Library for Uncertainty Quantification in Deep Learning](https://mlsanity.com/paper/2302.04019/) (2023)
- [Multi-group Uncertainty Quantification for Long-form Text Generation](https://mlsanity.com/paper/2407.21057/) (2024)
- [Semi-Supervised Risk Control via Prediction-Powered Inference](https://mlsanity.com/paper/2412.11174/) (2024)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage](https://mlsanity.com/paper/2502.17264/) (2025)
- [Split Conformal Prediction under Data Contamination](https://mlsanity.com/paper/2407.07700/) (2024)
- [Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization](https://mlsanity.com/paper/2502.13030/) (2025)
- [Conformal Prediction Sets for Deep Generative Models via Reduction to Conformal Regression](https://mlsanity.com/paper/2503.10512/) (2025)
- [Conformal Prediction and Human Decision Making](https://mlsanity.com/paper/2503.11709/) (2025)
- [Synthetic-Powered Predictive Inference](https://mlsanity.com/paper/2505.13432/) (2025)
- [Empirically Validating Conformal Prediction on Modern Vision Architectures Under Distribution Shift and Long-tailed Data](https://mlsanity.com/paper/2307.01088/) (2023)
- [Training-Conditional Coverage Bounds under Covariate Shift](https://mlsanity.com/paper/2405.16594/) (2024)

## Abstract (arXiv)

We develop fast distribution-free conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. Multivalid coverage guarantees are stronger than marginal coverage guarantees in two ways: (1) They hold even conditional on group membership -- that is, the target coverage level 1-α holds conditionally on membership in each of an arbitrary (potentially intersecting) group in a finite collection G of regions in the feature space. (2) They hold even conditional on the value of the threshold used to produce the prediction set on a given example. In fact multivalid coverage guarantees hold even when conditioning on group membership and threshold value simultaneously. We give two algorithms: both take as input an arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups G, and then can equip arbitrary black-box predictors with prediction sets. Our first algorithm (BatchGCP) is a direct extension of quantile regression, needs to solve only a single convex minimization problem, and produces an estimator which has group-conditional guarantees for each group in G. Our second algorithm (BatchMVP) is iterative, and gives the full guarantees of multivalid conformal prediction: prediction sets that are valid conditionally both on group membership and non-conformity threshold. We evaluate the performance of both of our algorithms in an extensive set of experiments. Code to replicate all of our experiments can be found at https://github.com/ProgBelarus/BatchMultivalidConformal