2021

Private Prediction Sets

Angelopoulos, Anastasios N., Bates, Stephen, Zrnic, Tijana et al.

Understand

In real-world settings involving consequential decision-making, the deployment of machine learning systems generally requires both reliable uncertainty quantification and protection of individuals' privacy.

We present a framework that treats these two desiderata jointly.
Our framework is based on conformal prediction, a methodology that augments predictive models to return prediction sets that provide uncertainty quantification -- they provably cover the true response with a user-specified probability, such as 90%.
One might hope that when used with privately-trained models, conformal prediction would yield privacy guarantees for the resulting prediction sets; unfortunately, this is not the case.

Built on

S. S. Wilks, “Determination of sample sizes for setting tolerance limits,” Annals of Mathematical Statistics
1941
Earlier work this paper cites.
S. S. Wilks, “Statistical prediction with special reference to the problem of tolerance limits,” Annals of Mathematical Statistics
1942
Earlier work this paper cites.
A. Wald, “An extension of Wilks’ method for setting tolerance limits,” Annals of Mathematical Statistics
1943
Earlier work this paper cites.
J. W. Tukey, “Non-parametric estimation II. statistically equivalent blocks and tolerance regions—the continuous case,” Annals of Mathematical Statistics
1947
Earlier work this paper cites.
E. Grycko, “Classification with set-valued decision functions,” in Information and Classification
1993
Earlier work this paper cites.
V. Vovk, A. Gammerman, and C. Saunders, “Machine-learning applications of algorithmic randomness,” in International Conference on Machine Learning
1999
Earlier work this paper cites.
H. Papadopoulos, K. Proedrou, V. Vovk, and A. Gammerman, “Inductive confidence machines for regression,” in Machine Learning: European Conference on Machine Learning
2002
Earlier work this paper cites.
Springer, 2005
V. Vovk, A. Gammerman, and G. Shafer, Algorithmic Learning in a Random World · 2005
Earlier work this paper cites.
C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in Theory of Cryptography Conference
2006
Earlier work this paper cites.
F. McSherry and K. Talwar, “Mechanism design via differential privacy,” in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)
2007
Earlier work this paper cites.
G. Shafer and V. Vovk, “A tutorial on conformal prediction,” Journal of Machine Learning Research
2008
Earlier work this paper cites.
Wiley, 2009
K. Krishnamoorthy and T. Mathew, Statistical Tolerance Regions: Theory, Applications, and Computation · 2009
Earlier work this paper cites.
J. J. del Coz, J. Díez, and A. Bahamonde, “Learning nondeterministic classifiers,” Journal of Machine Learning Research
2009
Earlier work this paper cites.
A. Krizhevsky, G. Hinton, et al
2009
Earlier work this paper cites.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in 2009 IEEE conference on computer vision and pattern recognition
2009
Earlier work this paper cites.
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate, “Differentially private empirical risk minimization.,” Journal of Machine Learning Research
2011
Earlier work this paper cites.
J. Lei, “Differentially private m-estimators,” Advances in Neural Information Processing Systems
2011
Earlier work this paper cites.
A. Smith, “Privacy-preserving statistical estimation with optimal convergence rates,” in Proceedings of the forty-third annual ACM symposium on Theory of computing
2011
Earlier work this paper cites.
V. Vovk, “Conditional validity of inductive conformal predictors,” in Proceedings of the Asian Conference on Machine Learning
2012
Earlier work this paper cites.
J. Xu, Z. Zhang, X. Xiao, Y. Yang, G. Yu, and M. Winslett, “Differentially private histogram publication,” The VLDB Journal
2013
Earlier work this paper cites.
Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security
2014
Earlier work this paper cites.

Similar

R. Bassily, A. Smith, and A. Thakurta, “Private empirical risk minimization: Efficient algorithms and tight error bounds,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
2014
Cited alongside, same era.
J. Lei, “Classification with confidence,” Biometrika
2014
Cited alongside, same era.
C. Dwork and A. Roth, “The algorithmic foundations of differential privacy.,” Foundations and Trends in Theoretical Computer Science
2014
Cited alongside, same era.
J. Lei, A. Rinaldo, and L. Wasserman, “A conformal prediction approach to explore functional data,” Annals of Mathematics and Artificial Intelligence
2015
Cited alongside, same era.
V. Vovk, “Cross-conformal predictors,” Annals of Mathematics and Artificial Intelligence
2015
Cited alongside, same era.
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
2016
Cited alongside, same era.
A. Bittau, Ú. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” in Proceedings of the 26th Symposium on Operating Systems Principles
2017
Cited alongside, same era.
Differential Privacy Team Apple, “Learning with privacy at scale,” in Apple Machine Learning Research
2017
Cited alongside, same era.
B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in Advances in Neural Information Processing Systems
2017
Cited alongside, same era.
V. Feldman and T. Steinke, “Generalization for adaptively-chosen estimators via stable median,” in Conference on Learning Theory
2017
Cited alongside, same era.
V. Karwa and S. Vadhan, “Finite sample differentially private confidence intervals,” arXiv preprint arXiv:1711.03908
Original
2017
Cited alongside, same era.
O. Sheffet, “Differentially private ordinary least squares,” in International Conference on Machine Learning
2017
Cited alongside, same era.

Then

Y. Romano, E. Patterson, and E. Candès, “Conformalized quantile regression,” in Advances in Neural Information Processing Systems
2019
Later among the works it cites.
R. Izbicki, G. T. Shimizu, and R. B. Stern, “Flexible distribution-free conditional predictive bands using density estimators,” arXiv:1910.05575
Original
2019
Later among the works it cites.
L. Guan and R. Tibshirani, “Prediction and outlier detection in classification problems,” arXiv:1905.04396
Original
2019
Later among the works it cites.
R. J. Tibshirani, R. Foygel Barber, E. Candes, and A. Ramdas, “Conformal prediction under covariate shift,” in Advances in Neural Information Processing Systems 32
2019
Later among the works it cites.
J. C. Perez, C. de Blas Perez, F. L. Alvarez, and J. M. C. Contreras, “Databiology Lab CORONAHACK: Collection of public COVID-19 data,” bioRxiv
2020
Later among the works it cites.
S. Neel, A. Roth, G. Vietri, and S. Wu, “Oracle efficient private non-convex optimization,” in International Conference on Machine Learning
2020
Later among the works it cites.
S. Park, O. Bastani, N. Matni, and I. Lee, “PAC confidence sets for deep neural networks via calibrated prediction,” in International Conference on Learning Representations
2020
Later among the works it cites.
A. N. Angelopoulos, S. Bates, J. Malik, and M. I. Jordan, “Uncertainty sets for image classifiers using conformal prediction,” arXiv:2009.14193
Original
2020
Later among the works it cites.
Y. Romano, M. Sesia, and E. J. Candès, “Classification with valid and adaptive coverage,” arXiv:2006.02544
Original
2020
Later among the works it cites.
L. Guan, “Conformal prediction with localization,” arXiv:1908.08558
Original
2020
Later among the works it cites.
M. Cauchois, S. Gupta, and J. Duchi, “Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction,” arXiv:2004.10181
Original
2020
Later among the works it cites.
V. Vovk, I. Petej, P. Toccaceli, A. Gammerman, E. Ahlberg, and L. Carlsson, “Conformal calibrators,” in Conformal and Probabilistic Prediction and Applications
2020
Later among the works it cites.
M. Cauchois, S. Gupta, A. Ali, and J. C. Duchi, “Robust validation: Confident predictions even when distributions shift,” arXiv:2008.04267
Original
2020
Later among the works it cites.
X. Hu and J. Lei, “A distribution-free test of covariate shift using conformal prediction,” arXiv:2010.07147
Original
2020
Later among the works it cites.
L. Lei and E. J. Candès, “Conformal inference of counterfactuals and individual treatment effects,” arXiv:2006.06138
Original
2020
Later among the works it cites.
C. Jung, C. Lee, M. M. Pai, A. Roth, and R. Vohra, “Moment multicalibration for uncertainty estimation,” arXiv:2008.08037
Original
2020
Later among the works it cites.
T. Mortier, M. Wydmuch, K. Dembczyński, E. Hüllermeier, and W. Waegeman, “Efficient set-valued prediction in multi-class classification,” arXiv:1906.08129
Original
2020
Later among the works it cites.
R. F. Barber, E. J. Candes, A. Ramdas, R. J. Tibshirani, et al
2021
Closest in time.
S. Bates, A. Angelopoulos, L. Lei, J. Malik, and M. I. Jordan, “Distribution-free, risk-controlling prediction sets,” arXiv:2101.02703
Original
2021
Closest in time.
A. N. Angelopoulos and S. Bates, “A gentle introduction to conformal prediction and distribution-free uncertainty quantification,” arXiv preprint arXiv:2107.07511
Original
2021
Closest in time.
V. Gupta, C. Jung, G. Noarov, M. M. Pai, and A. Roth, “Online multivalid learning: Means, moments, and prediction intervals,” arXiv:2101.01739
Original
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…