Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, Aaron Roth
arXiv 5 Jan 2021 · Machine Learning · 3 citations (OpenAlex)
arXiv:2101.01739 · PDF · DOI · OpenAlex · Extracted main text
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 \in G$ for any $G$ belonging to an arbitrary intersecting collection of groups $\mathcal{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.
appendix boundary found by appendix_command · 66% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum (2018) Multicalibration: Calibration for the (computationally-identifiable) masses | 0.977 | 15 | 5 | 93% |
| 2 | Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakes… (2020) Moment multicalibration for uncertainty estimation self | 0.974 | 13 | 6 | 92% |
| 3 | Drew Fudenberg and David K Levine (1999) An easier way to calibrate | 0.693 | 6 | 1 | 100% |
| 4 | Dean P Foster and Rakesh V Vohra (1998) Asymptotic calibration | 0.693 | 5 | 1 | 100% |
| 5 | Sergiu Hart (2020) Calibrated forecasts: The minimax proof | 0.511 | 2 | 1 | 100% |
| 6 | Glenn Shafer and Vladimir Vovk (2008) A tutorial on conformal prediction | 0.511 | 2 | 1 | 100% |
| 7 | A Philip Dawid (1982) The well-calibrated bayesian | 0.511 | 2 | 1 | 100% |
| 8 | Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Lar… (2018) Distribution-free predictive inference for regression | 0.511 | 2 | 1 | 100% |
| 9 | Michael P Kim, Amirata Ghorbani, and James Zou (2019) Multiaccuracy: Black-box post-processing for fairness in classification | 0.511 | 2 | 1 | 100% |
| 10 | Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra (2003) Calibration with many checking rules | 0.511 | 2 | 1 | 100% |
Showing the top 10 of 37 scored citations.