CoChat
Sign Up
PreprintCited by 1

Loss Minimization Yields Multicalibration for Large Neural Networks

Błasiok, Jarosław, Gopalan, Parikshit, Hu, Lunjia, Kalai, Adam Tauman, Nakkiran, Preetum·2023·arXiv
DOI 10.48550/arxiv.2304.09424arXiv 2304.09424
Open this paper in CoChat — free account

Abstract

Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be a distinct goal than loss minimization, even for simple predictors such as linear functions. In this work, we consider the setting where the protected groups can be represented by neural networks of size $k$, and the predictors are neural networks of size $n > k$. We show that minimizing the squared loss over all neural nets of size $n$ implies multicalibration for all but a bounded number of unlucky values of $n$. We also give evidence that our bound on the number of unlucky values is tight, given our proof technique. Previously, results of the flavor that loss minimization yields multicalibration were known only for predictors that were near the ground truth, hence were rather limited in applicability. Unlike these, our results rely on the expressivity of neural nets and utilize the representation of the predictor.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2304.09424

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 46

  1. Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. arXiv preprint arXiv:2304.01373 , 2023. 10 · arXiv
  2. Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. When does optimizing a proper loss yield calibration? arXiv preprint arXiv:2305.18764 , 2023a. 2, 3, 6, 8, 18, 19, 20 · arXiv
  3. Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, page 1727-1740, New York, NY, USA, 2023b. Association for Computing Machinery. ISBN 9781450399135. doi: 10.1145/3564246.3585182. URL https://doi.org/10.1145/3564246.3585182 . 6 · DOI
  4. Mathieu Blondel, Andr´ e F. T. Martins, and Vlad Niculae. Learning with Fenchel-Young losses. Journal of Machine Learning Research , 21(35):1-69, 2020. URL http://jmlr.org/papers/v21/ 19-021.html . 19
  5. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, …, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems , volume 33, pages 1877-1901. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/ 1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf . 10
  6. Annabelle Carrell, Neil Mallinar, James Lucas, and Preetum Nakkiran. The calibration generalization gap. arXiv preprint arXiv:2210.01964 , 2022. 6 · arXiv
  7. Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap : A generalized multicalibration method. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA , volume 251 of LIPIcs , pages 41:1-41:23. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023. doi: 10.4230/LIPIcs.ITCS.2023.41. URL https: //doi.org/10.4230/LIPIcs.ITCS.2023.41 . 2 · DOI
  8. Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 295-302, 2020. 6
  9. John Duchi, Khashayar Khosravi, and Feng Ruan. Multiclass classification, information, divergence and surrogate risk. The Annals of Statistics , 46(6B):3246 - 3275, 2018. doi: 10.1214/17-AOS1657. URL https: //doi.org/10.1214/17-AOS1657 . 19 · DOI
  10. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishability. In ACM Symposium on Theory of Computing (STOC'21) , 2021. URL https://arxiv. org/abs/2011.13426 . 6
  11. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature. In The 33rd International Conference on Algorithmic Learning Theory , 2022. 2
  12. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences , 68(4):753-787, 2004. URL https://www.sciencedirect.com/ science/article/pii/S0022000003001831 . Special Issue on FOCS 2002. 10
  13. Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth. Oracle efficient online multicalibration and omniprediction. CoRR , abs/2307.08999, 2023. URL https://doi.org/10.48550/arXiv. 2307.08999 . 2, 6 · DOI
  14. Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibration as boosting for regression. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research , pages 11459-11492. PMLR, 23-29 Jul 2023. URL https://proceedings.mlr.press/v202/globus-harris23a.html . 2, 8
  15. Parikshit Gopalan, Adam Tauman Kalai, and Adam R. Klivans. Agnostically learning decision trees. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , STOC '08, page 527-536, 2008. 11, 17
  16. Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In Innovations in Theoretical Computer Science (ITCS'2022) , 2022a. URL https://arxiv.org/ abs/2109.05389 . 2, 3, 6 · arXiv
  17. Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao. Low-degree multicalibration. In Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learning Research , pages 3193-3234. PMLR, 2022b. 2
  18. Parikshit Gopalan, Omer Reingold, Vatsal Sharan, and Udi Wieder. Multicalibrated partitions for importance weights. In International Conference on Algorithmic Learning Theory, 29-1 April 2022, Paris, France , volume 167 of Proceedings of Machine Learning Research , pages 408-435. PMLR, 2022c. 2, 6
  19. Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss Minimization Through the Lens Of Outcome Indistinguishability. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 60:1-60:20, Dagstuhl, Germany, 2023a. Schloss Dagstuhl - LeibnizZentrum f¨ ur Informatik. ISBN 978-3-95977-263-1. doi: 10.4230/LIPIcs.ITCS.2023.60. URL https: //drops.dagstuhl.de/opus/volltexte/2023/17563 . 2, 6 · DOI
  20. Parikshit Gopalan, Michael Kim, and Omer Reingold. Characterizing notions of omniprediction via multicalibration. In under submission , 2023b. URL https://arxiv.org/abs/2302.06726 . 2, 6 · arXiv
  21. ´ Ursula H´ ebert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In Proceedings of the 35th International Conference on Machine Learning, ICML , 2018. 1, 2, 3, 5, 6, 8, 10
  22. Dan Hendrycks*, Norman Mu*, Ekin Dogus Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshminarayanan. Augmix: A simple method to improve robustness and uncertainty under data shift. In International Conference on Learning Representations , 2020. URL https://openreview.net/ forum?id=S1gmrxHFvB . 6
  23. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks , 2(5):359-366, 1989a. 7
  24. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks , 2(5):359-366, 1989b. ISSN 0893-6080. doi: https://doi.org/10.1016/
  25. Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, and Chutong Yang. Omnipredictors for constrained optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning , volume 202 of Proceedings of Machine Learning Research , pages 13497-13527. PMLR, 23-29 Jul 2023. URL https://proceedings.mlr.press/v202/hu23b.html . 2, 6
  26. Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. arXiv preprint arXiv:2008.08037 , 2020. 7 · arXiv
  27. Sham M. Kakade and Dean P. Foster. Deterministic calibration and Nash equilibrium. In John ShaweTaylor and Yoram Singer, editors, Learning Theory , pages 33-48, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-27819-1. 6
  28. Archit Karandikar, Nicholas Cain, Dustin Tran, Balaji Lakshminarayanan, Jonathon Shlens, Michael C Mozer, and Becca Roelofs. Soft calibration objectives for neural networks. Advances in Neural Information Processing Systems , 34:29768-29779, 2021. 6
  29. Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. arXiv preprint arXiv:1711.05144 , 2017. 1, 6 · arXiv
  30. Michael P. Kim and Juan C. Perdomo. Making Decisions Under Outcome Performativity. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 79:1-79:15, Dagstuhl, Germany, 2023. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik. ISBN 978-3-95977-263-1. doi: 10.4230/LIPIcs.ITCS. 2023.79. URL https://drops.dagstuhl.de/opus/volltexte/2023/17582 . 6 · DOI
  31. Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society , pages 247254, 2019. 6, 7
  32. Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences , 119(4), 2022. 1, 2, 6
  33. Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS , 2017. 1, 6
  34. Lydia T Liu, Max Simchowitz, and Moritz Hardt. The implicit fairness criterion of unconstrained learning. In International Conference on Machine Learning , pages 4051-4060. PMLR, 2019. 2
  35. Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic. Revisiting the calibration of modern neural networks. Advances in Neural Information Processing Systems , 34:15682-15694, 2021. 6
  36. Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning functions of k relevant variables. Journal of Computer and System Sciences , 69(3):421-434, 2004. ISSN 0022-0000. doi: https://doi.org/10.1016/ j.jcss.2004.04.002. URL https://www.sciencedirect.com/science/article/pii/ S0022000004000418 . Special Issue on STOC 2003. 10
  37. Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems , 32, 2019. 7, 10
  38. Preetum Nakkiran, Behnam Neyshabur, and Hanie Sedghi. The deep bootstrap framework: Good online learners are good offline generalizers. In International Conference on Learning Representations , 2021. URL https://openreview.net/forum?id=guetrIHLFGI . 10
  39. Ryan O'Donnell. Analysis of boolean functions . Cambridge University Press, 2014. 5, 11, 18
  40. Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research , 11(83):2387-2422, 2010. URL http://jmlr.org/papers/v11/reid10a.html . 19
  41. Leonard J. Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association , 66(336):783-801, 1971. doi: 10.1080/01621459.1971.10482346. URL https: //www.tandfonline.com/doi/abs/10.1080/01621459.1971.10482346 . 19 · DOI
  42. Mark J. Schervish. A general method for comparing probability assessors. The Annals of Statistics , 17 (4):1856 - 1879, 1989. doi: 10.1214/aos/1176347398. URL https://doi.org/10.1214/aos/ 1176347398 . 19 · DOI
  43. Emir H. Shuford, Arthur Albert, and H. Edward Massengill. Admissible probability measurement procedures. Psychometrika , 31(2):125-145, 1966. doi: 10.1007/BF02289503. URL https://doi.org/10. 1007/BF02289503 . 19 · DOI
  44. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM , 51(3):385-463, may 2004. ISSN 0004-5411. doi: 10.1145/990308. 990310. URL https://doi.org/10.1145/990308.990310 . 5 · DOI
  45. Robert C Titsworth. Correlation properties of cyclic sequences . PhD thesis, California Institute of Technology, 1962. 18
  46. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM , 64(3):107-115, 2021. 7, 10

Cited by

Sorted by citations

Authors
Błasiok, J., Gopalan, P., Hu, L., Kalai, A. T., & Nakkiran, P.
Venue
arXiv
Publisher
arXiv
Published
2023
DOI
10.48550/arxiv.2304.09424
arXiv
2304.09424
References
0
Type
Preprint
Licence
creativecommons.org/licenses/by/4.0/legalcode

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review