# Online Multivalid Learning: Means, Moments, and Prediction Intervals

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 5 Jan 2021.

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

- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [On Fairness and Calibration](https://mlsanity.com/paper/1709.02012/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [An Empirical Study of Rich Subgroup Fairness for Machine Learning](https://mlsanity.com/paper/1808.08166/) (2018)
- [Distribution-free binary classification: prediction sets, confidence intervals and calibration](https://mlsanity.com/paper/2006.10564/) (2020)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data](https://mlsanity.com/paper/1802.06300/) (2018)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Fairness Through Computationally-Bounded Awareness](https://mlsanity.com/paper/1803.03239/) (2018)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Sample Complexity of Uniform Convergence for Multicalibration](https://mlsanity.com/paper/2005.01757/) (2020)

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

- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Scalable Membership Inference Attacks via Quantile Regression](https://mlsanity.com/paper/2307.03694/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Sample-Efficient Safety Assurances using Conformal Prediction](https://mlsanity.com/paper/2109.14082/) (2021)
- [Oracle Efficient Online Multicalibration and Omniprediction](https://mlsanity.com/paper/2307.08999/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Simple and near-optimal algorithms for hidden stratification and multi-group learning](https://mlsanity.com/paper/2112.12181/) (2021)
- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [An Algorithmic Framework for Bias Bounties](https://mlsanity.com/paper/2201.10408/) (2022)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- [Private Prediction Sets](https://mlsanity.com/paper/2102.06202/) (2021)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Reconciling Individual Probability Forecasts](https://mlsanity.com/paper/2209.01687/) (2022)
- [Multicalibrated Regression for Downstream Fairness](https://mlsanity.com/paper/2209.07312/) (2022)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [Tractable Agreement Protocols](https://mlsanity.com/paper/2411.19791/) (2024)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Revisiting the Predictability of Performative, Social Events](https://mlsanity.com/paper/2503.11713/) (2025)
- [Scaffolding Sets](https://mlsanity.com/paper/2111.03135/) (2021)
- [Fair admission risk prediction with proportional multicalibration](https://mlsanity.com/paper/2209.14613/) (2022)
- [The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation](https://mlsanity.com/paper/2302.08507/) (2023)
- [Decision-Making under Miscalibration](https://mlsanity.com/paper/2203.09852/) (2022)
- [Three Types of Calibration with Properties and their Semantic and Formal Relationships](https://mlsanity.com/paper/2504.18395/) (2025)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)

## Abstract (arXiv)

We present a general, efficient technique for providing contextual predictions that are "multivalid" in various senses, against an online sequence of adversarially chosen examples (x,y). This means that the resulting estimates correctly predict various statistics of the labels y not just marginally -- as averaged over the sequence of examples -- but also conditionally on x ∈ G for any G belonging to an arbitrary intersecting collection of groups G. We provide three instantiations of this framework. The first is mean prediction, which corresponds to an online algorithm satisfying the notion of multicalibration from Hebert-Johnson et al. The second is variance and higher moment prediction, which corresponds to an online algorithm satisfying the notion of mean-conditioned moment multicalibration from Jung et al. Finally, we define a new notion of prediction interval multivalidity, and give an algorithm for finding prediction intervals which satisfy it. Because our algorithms handle adversarially chosen examples, they can equally well be used to predict statistics of the residuals of arbitrary point prediction methods, giving rise to very general techniques for quantifying the uncertainty of predictions of black box algorithms, even in an online adversarial setting. When instantiated for prediction intervals, this solves a similar problem as conformal prediction, but in an adversarial environment and with multivalidity guarantees stronger than simple marginal coverage guarantees.