More Web Proxy on the site http://driver.im/

research-article

Public Access

Outcome indistinguishability

Authors:

Michael P. Kim,

Guy N. Rothblum,

Gal YonaAuthors Info & Claims

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

Pages 1095 - 1108

https://doi.org/10.1145/3406325.3451064

Published: 15 June 2021 Publication History

Abstract

Prediction algorithms assign numbers to individuals that are popularly understood as individual “probabilities”—what is the probability of 5-year survival after cancer diagnosis?—and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are Outcome Indistinguishable (OI) yield a generative model for outcomes that cannot be efficiently refuted on the basis of the real-life observations produced by .

We investigate a hierarchy of OI definitions, whose stringency increases with the degree to which distinguishers may access the predictor in question. Our findings reveal that OI behaves qualitatively differently than previously studied notions of indistinguishability. First, we provide constructions at all levels of the hierarchy. Then, leveraging recently-developed machinery for proving average-case fine-grained hardness, we obtain lower bounds on the complexity of the more stringent forms of OI. This hardness result provides the first scientific grounds for the political argument that, when inspecting algorithmic risk prediction instruments, auditors should be granted oracle access to the algorithm, not simply historical predictions.

References

[1]

Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant. 2019. Sample Amplification: Increasing Dataset Size even when Learning is Impossible. arXiv preprint arXiv:1904.12053 (2019).

[2]

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. 2017. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 483–496.

Digital Library

[3]

Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. 2018. Proofs of Work From Worst-Case Assumptions. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I (Lecture Notes in Computer Science), Hovav Shacham and Alexandra Boldyreva (Eds.), Vol. 10991. Springer, 789–819.

Digital Library

[4]

Avrim Blum and Thodoris Lykouris. 2019. Advancing subgroup fairness via sleeping experts. arXiv preprint arXiv:1909.08375 (2019).

[5]

Avrim Blum and Yishay Mansour. 2007. From external to internal regret. Journal of Machine Learning Research 8, Jun (2007), 1307–1324.

[6]

Kai-Min Chung, Edward Lui, and Rafael Pass. 2013. Can theories be tested?: a cryptographic treatment of forecast testing. In Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, Robert D. Kleinberg (Ed.). ACM, 47–56.

Digital Library

[7]

AP Dawid. 1982. Objective probability forecasts'. Technical Report. Research Report 14, Department of Statistical Science, University College London.

[8]

Philip Dawid. 2015. On individual risk. Synthese 194, 9 (Nov 2015), 3445–3474. issn:1573-0964

[9]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference. 214–226.

Digital Library

[10]

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. 2019. Learning from outcomes: Evidence-based rankings. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 106–125.

[11]

Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. 2020. Outcome Indistinguishability. arxiv:2011.13426 [cs.LG]

[12]

Cynthia Dwork and Moni Naor. 1992. Pricing via Processing or Combatting Junk Mail. In Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings (Lecture Notes in Computer Science), Ernest F. Brickell (Ed.), Vol. 740. Springer, 139–147.

[13]

Lance Fortnow and Rakesh V. Vohra. 2009. The Complexity of Forecast Testing. Econometrica 77, 1 (2009), 93–105. arxiv:https://onlinelibrary.wiley.com/doi/pdf/10.3982/ECTA7163

[14]

Dean P Foster and Rakesh V Vohra. 1998. Asymptotic calibration. Biometrika 85, 2 (1998), 379–390.

[15]

Yoav Freund and Robert E Schapire. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences 55, 1 (1997), 119–139.

Digital Library

[16]

Drew Fudenberg and David K Levine. 1999. An easier way to calibrate. Games and economic behavior 29, 1-2 (1999), 131–137.

[17]

Oded Goldreich. 2006. Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, USA.

Digital Library

[18]

Oded Goldreich. 2008. Computational Complexity: A Conceptual Perspective (1 ed.). Cambridge University Press, USA. isbn:052188473X

[19]

Oded Goldreich. 2009. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press.

Digital Library

[20]

Oded Goldreich and Leonid A Levin. 1989. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing. 25–32.

Digital Library

[21]

Oded Goldreich and Guy N. Rothblum. 2018. Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, Mikkel Thorup (Ed.). IEEE Computer Society, 77–88.

[22]

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2014. Generative adversarial nets. In Advances in neural information processing systems. 2672–2680.

[23]

Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of opportunity in supervised learning. In Advances in neural information processing systems. 3315–3323.

[24]

David Haussler. 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and computation 100, 1 (1992), 78–150.

[25]

\'Ursula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy Rothblum. 2018. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning. 1939–1948.

[26]

Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. 2020. Moment Multicalibration for Uncertainty Estimation. arXiv preprint arXiv:2008.08037 (2020).

[27]

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2018. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning. 2564–2572.

[28]

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. 2019. An empirical study of rich subgroup fairness for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency. 100–109.

Digital Library

[29]

Michael J Kearns and Robert E Schapire. 1994. Efficient distribution-free learning of probabilistic concepts. J. Comput. System Sci. 48, 3 (1994), 464–497.

Digital Library

[30]

Michael J Kearns, Robert E Schapire, and Linda M Sellie. 1994. Toward efficient agnostic learning. Machine Learning 17, 2-3 (1994), 115–141.

Digital Library

[31]

Michael P. Kim, Amirata Ghorbani, and James Zou. 2019. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society. 247–254.

Digital Library

[32]

Michael P. Kim, Omer Reingold, and Guy N. Rothblum. 2018. Fairness Through Computationally-Bounded Awareness. Advances in Neural Information Processing Systems (2018).

[33]

Diederik P Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. arxiv:1312.6114 [stat.ML]

[34]

Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2016. Inherent trade-offs in the fair determination of risk scores. arXiv preprint arXiv:1609.05807 (2016).

[35]

Richard J. Lipton. 1989. New Directions In Testing. In Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989 (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Joan Feigenbaum and Michael Merritt (Eds.), Vol. 2. DIMACS/AMS, 191–202.

[36]

Nick Littlestone and Manfred K Warmuth. 1994. The weighted majority algorithm. Information and computation 108, 2 (1994), 212–261.

[37]

Alvaro Sandroni. 2003. The reproducible properties of correct forecasts. International Journal of Game Theory 32, 1 (2003), 151–159.

Digital Library

[38]

Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra. 2003. Calibration with many checking rules. Mathematics of operations Research 28, 1 (2003), 141–153.

[39]

Eliran Shabat, Lee Cohen, and Yishay Mansour. 2020. Sample Complexity of Uniform Convergence for Multicalibration. arXiv preprint arXiv:2005.01757 (2020).

[40]

Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding machine learning: From theory to algorithms. Cambridge university press.

Digital Library

[41]

Luca Trevisan and Salil P. Vadhan. 2007. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Comput. Complex. 16, 4 (2007), 331–364.

Digital Library

[42]

Salil P. Vadhan. 2012. Pseudorandomness. Now Publishers Inc., Hanover, MA, USA. isbn:1601985940

[43]

Leslie G Valiant. 1984. A theory of the learnable. Commun. ACM 27, 11 (1984), 1134–1142.

Digital Library

[44]

Shengjia Zhao, Tengyu Ma, and Stefano Ermon. 2020. Individual Calibration with Randomized Forecasting. arXiv preprint arXiv:2006.10288 (2020).

Cited By

Zhang LRoth AZhang LSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Fair risk controlProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694541(59783-59805)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694541
Jain SCreel KWilson ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)PositionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692920(21148-21169)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692920
Deng SHsu DSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Multi-group learning for hierarchical groupsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692485(10440-10487)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692485
Show More Cited By

Index Terms

Outcome indistinguishability
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Pseudorandomness and derandomization
  2. Theory and algorithms for application domains
    1. Machine learning theory

Recommendations

Computational Indistinguishability Between Quantum States and Its Cryptographic Application

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is “secure” against any polynomial-time quantum adversary. Our problem, QSCD_ff, is to ...
How to use indistinguishability obfuscation: deniable encryption, and more
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems. We use this technique to carry out a systematic study of the applicability of indistinguishability obfuscation to a ...
Indistinguishability against Chosen Ciphertext Verification Attack Revisited: The Complete Picture
ProvSec 2013: Proceedings of the 7th International Conference on Provable Security - Volume 8209

The knowledge that whether a purported ciphertext is valid or not may leak sufficient information to mount practical attacks on public key cryptosystem, e.g., Bleichenbacher's attack on RSA-PKCS#1, Hall-Goldberg-Schneier's "reaction attack" on both ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 2021

1797 pages

ISBN:9781450380539

DOI:10.1145/3406325

General Chair:
Samir Khuller
Northwestern University, USA
,
Program Chair:
Virginia Vassilevska Williams
Massachusetts Institute of Technology, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '21

Sponsor:

SIGACT

STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing

June 21 - 25, 2021

Virtual, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
1,262
Total Downloads

Downloads (Last 12 months)451
Downloads (Last 6 weeks)75

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LRoth AZhang LSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Fair risk controlProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694541(59783-59805)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3694541
Jain SCreel KWilson ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)PositionProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692920(21148-21169)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692920
Deng SHsu DSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Multi-group learning for hierarchical groupsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692485(10440-10487)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692485
Hardt MKim M(2023)Is Your Model Predicting the Past?Proceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3617694.3623225(1-8)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3617694.3623225
Globus-Harris IGupta VJung CKearns MMorgenstern JRoth A(2023)Multicalibrated Regression for Downstream FairnessProceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society10.1145/3600211.3604683(259-286)Online publication date: 8-Aug-2023
https://dl.acm.org/doi/10.1145/3600211.3604683
Roth ATolbert AWeinstein S(2023)Reconciling Individual Probability Forecasts✱Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency10.1145/3593013.3593980(101-110)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3593013.3593980
Rothblum G(2023)Indistinguishable Predictions and Multi-group Fair LearningAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30545-0_1(3-21)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30545-0_1
Andrejevic MVolcic Z(2022)Biometric Re-bordering: Environmental Control During Pandemic TimesThe Viral Politics of Covid-1910.1007/978-981-19-3942-6_12(203-220)Online publication date: 21-Sep-2022
https://doi.org/10.1007/978-981-19-3942-6_12
Zhao SKim MSahoo RMa TErmon SRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Calibrating predictions to decisionsProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541970(22313-22324)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541970
Abebe RHardt MJin AMiller JSchmidt LWexler R(undefined)Adversarial Scrutiny of Evidentiary Statistical SoftwareSSRN Electronic Journal10.2139/ssrn.4107017
https://doi.org/10.2139/ssrn.4107017

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents