{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:12:27Z","timestamp":1762272747907,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451028","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"183-196","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sample-efficient proper PAC learning with approximate differential privacy"],"prefix":"10.1145","author":[{"given":"Badih","family":"Ghazi","sequence":"first","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noah","family":"Golowich","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Chansoo Lee, Audra McMillan, and Ambuj Tewari.","author":"Abernethy Jacob D.","year":"2019","unstructured":"Jacob D. Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari. 2019. Online Learning via the Differential Privacy Lens. In NeurIPS. Pages 8892\u20138902."},{"key":"e_1_3_2_1_2_1","unstructured":"Naman Agarwal and Karan Singh. 2017. The Price of Differential Privacy for Online Learning. In ICML. Pages 32\u201340."},{"key":"e_1_3_2_1_3_1","unstructured":"Noga Alon Amos Beimel Shay Moran and Uri Stemmer. 2020. Closure Properties for Private Classification and Online Prediction. In COLT. Pages 119\u2013152."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Omri Ben-Eliezer Yuval Dagan Shay Moran Moni Naor and Eylon Yogev. 2021. Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. In STOC.","DOI":"10.1145\/3406325.3451041"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Noga Alon Roi Livni Maryanthe Malliaris and Shay Moran. 2019. Private PAC Learning Implies Finite Littlestone Dimension. In STOC. Pages 852\u2013860.","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_6_1","first-page":"2003","article-title":"Rademacher and Gaussian Complexities","volume":"3","author":"Bartlett Peter L.","year":"2003","unstructured":"Peter L. Bartlett and Shahar Mendelson. 2003. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. JMLR, 3, 2003. Pages 463\u2013482.","journal-title":"Risk Bounds and Structural Results. JMLR"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5404-1"},{"key":"e_1_3_2_1_8_1","unstructured":"Amos Beimel Shay Moran Kobbi Nissim and Uri Stemmer. 2019. Private Center Points and Learning of Halfspaces. In COLT. Pages 269\u2013282."},{"key":"e_1_3_2_1_9_1","first-page":"7","article-title":"Private Learning and Sanitization: Pure vs. Approximate Differential Privacy","volume":"12","author":"Beimel Amos","year":"2014","unstructured":"Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2014. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. Theory of Computing, 12, 7, 2014.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Amos Beimel Kobbi Nissim and Uri Stemmer. 2015. Learning Privately with Labeled and Unlabeled Examples. In SODA. Pages 461\u2013477.","DOI":"10.1137\/1.9781611973730.32"},{"key":"e_1_3_2_1_11_1","first-page":"146","article-title":"Characterizing the Sample Complexity of Pure Private Learners","volume":"20","author":"Beimel Amos","year":"2019","unstructured":"Amos Beimel, Kobbi Nissim, and Uri Stemmer. 2019. Characterizing the Sample Complexity of Pure Private Learners. JMLR, 20, 146, 2019. Pages 1\u201333.","journal-title":"JMLR"},{"key":"e_1_3_2_1_12_1","volume-title":"2 Notes on Classes with Vapnik\u2013Chervonenkis Dimension 1. arXiv:1507.05307","author":"Ben-David Shai","year":"2015","unstructured":"Shai Ben-David. 2015. 2 Notes on Classes with Vapnik\u2013Chervonenkis Dimension 1. arXiv:1507.05307, 2015."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Shai Ben-David D\u00e1vid P\u00e1l and Shai Shalev-Shwartz. 2009. Agnostic Online Learning. In COLT.","DOI":"10.3817\/0609147077"},{"key":"e_1_3_2_1_14_1","volume-title":"arXiv:1702.03956","author":"Bhaskar Siddharth","year":"2017","unstructured":"Siddharth Bhaskar. 2017. Thicket Density. arXiv:1702.03956, 2017."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Aditya Bhaskara Daniel Dadush Ravishankar Krishnaswamy and Kunal Talwar. 2012. Unconditional Differentially Private Mechanisms for Linear Queries. In STOC. Pages 1269\u20131284.","DOI":"10.1145\/2213977.2214089"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Jaroslaw Blasiok Mark Bun Aleksandar Nikolov and Thomas Steinke. 2019. Towards Instance-Optimal Private Query Release. In SODA. Pages 2480\u20132497.","DOI":"10.1137\/1.9781611975482.152"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Avrim Blum Katrina Ligett and Aaron Roth. 2008. A Learning Theory Approach to Non-Interactive Database Privacy. In STOC. Pages 609\u2013618.","DOI":"10.1145\/1374376.1374464"},{"key":"e_1_3_2_1_18_1","unstructured":"Olivier Bousquet Roi Livni and Shay Moran. 2020. Synthetic Data Generators: Sequential and Private. In NeurIPS."},{"key":"e_1_3_2_1_19_1","unstructured":"Mark Bun. 2020. A Computational Separation between Private Learning and Online Learning. In NeurIPS."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Cynthia Dwork Guy N. Rothblum and Thomas Steinke. 2018. Composable and Versatile Privacy via Truncated CDP. In STOC. Pages 74\u201386.","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Roi Livni and Shay Moran. 2020. An equivalence between private classification and online prediction. In FOCS. Pages 389\u2013402.","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Kobbi Nissim and Uri Stemmer. 2016. Simultaneous Private Learning of Multiple Concepts. In ITCS. Pages 369\u2013380. isbn:9781450340571","DOI":"10.1145\/2840728.2840747"},{"key":"e_1_3_2_1_23_1","volume-title":"Vadhan","author":"Bun Mark","year":"2015","unstructured":"Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. 2015. Differentially Private Release and Learning of Threshold Functions. In FOCS. Pages 634\u2013649."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Mark Bun Jonathan Ullman and Salil Vadhan. 2014. Fingerprinting Codes and the Price of Approximate Differential Privacy. In STOC. Pages 1\u201310.","DOI":"10.1145\/2591796.2591877"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1914598117"},{"volume-title":"Uniform Central Limit Theorems","author":"Dudley Richard M.","key":"e_1_3_2_1_26_1","unstructured":"Richard M. Dudley. 1999. Uniform Central Limit Theorems. Cambridge University Press."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork. 2006. Differential privacy. In ICALP. Pages 1\u201312.","DOI":"10.1007\/11787006_1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Frank McSherry Kobbi Nissim and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC. Pages 265\u2013284.","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Moni Naor Omer Reingold Guy N. Rothblum and Salil Vadhan. 2009. On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results. In STOC. Pages 381\u2013390.","DOI":"10.1145\/1536414.1536467"},{"volume-title":"The Algorithmic Foundations of Differential Privacy","author":"Dwork Cynthia","key":"e_1_3_2_1_30_1","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Now Publishers Inc.."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Guy N. Rothblum and Salil Vadhan. 2010. Boosting and Differential Privacy. In FOCS. Pages 51\u201360.","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Alexander Edmonds Aleksandar Nikolov and Jonathan Ullman. 2020. The Power of Factorization Mechanisms in Local and Central Differential Privacy. In STOC. Pages 425\u2013438.","DOI":"10.1145\/3357713.3384297"},{"key":"e_1_3_2_1_33_1","unstructured":"Vitaly Feldman and David Xiao. 2014. Sample Complexity Bounds on Differentially Private Learning via Communication Complexity. In COLT. Pages 1\u201320."},{"key":"e_1_3_2_1_34_1","unstructured":"Badih Ghazi Noah Golowich Ravi Kumar and Pasin Manurangsi. 2021. Sample-efficient proper private PAC learning. In ALT."},{"key":"e_1_3_2_1_35_1","unstructured":"Badih Ghazi Ravi Kumar and Pasin Manurangsi. 2020. Differentially Private Clustering: Tight Approximation Ratios. In NeurIPS."},{"key":"e_1_3_2_1_36_1","unstructured":"Alon Gonen Elad Hazan and Shay Moran. 2019. Private Learning Implies Online Learning: An Efficient Reduction. In NeurIPS. Pages 8702\u20138712."},{"key":"e_1_3_2_1_37_1","unstructured":"Moritz Hardt Katrina Ligett and Frank McSherry. 2012. A Simple and Practical Algorithm for Differentially Private Data Release. In NIPS. Pages 2339\u20132347."},{"key":"e_1_3_2_1_38_1","volume-title":"Rothblum","author":"Hardt Moritz","year":"2010","unstructured":"Moritz Hardt and Guy N. Rothblum. 2010. A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. In FOCS. Pages 61\u201370."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Moritz Hardt and Kunal Talwar. 2010. On the Geometry of Differential Privacy. In STOC. Pages 705\u2013714.","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_3_2_1_40_1","unstructured":"Haim Kaplan Katrina Ligett Yishay Mansour Moni Naor and Uri Stemmer. 2020. Privately Learning Thresholds: Closing the Exponential Gap. In COLT. Pages 2263\u20132285."},{"key":"e_1_3_2_1_41_1","unstructured":"Haim Kaplan Yishay Mansour Uri Stemmer and Eliad Tsfadia. 2020. Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity. In NeurIPS."},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"How to Find a Point in the Convex Hull Privately","volume":"52","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Micha Sharir, and Uri Stemmer. 2020. How to Find a Point in the Convex Hull Privately. In SoCG. Pages 52:1\u201352:15.","journal-title":"SoCG. Pages"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Shiva Prasad Kasiviswanathan Homin K. Lee Kobbi Nissim Sofya Rashkodnikova and Adam Smith. 2008. What can we Learn Privately? In FOCS. Pages 531\u2013540.","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Nick Littlestone. 1987. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. In FOCS. Pages 68\u201377.","DOI":"10.1109\/SFCS.1987.37"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Seth Neel Aaron Roth and Zhiwei Steven Wu. 2019. How to use heuristics for differential privacy. In FOCS. Pages 72\u201393.","DOI":"10.1109\/FOCS.2019.00014"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"A. Nikolov. 2015. An Improved Private Mechanism for Small Databases. In ICALP. Pages 1010\u20131021.","DOI":"10.1007\/978-3-662-47672-7_82"},{"key":"e_1_3_2_1_47_1","first-page":"360","volume-title":"STOC","author":"Nikolov Aleksandar","year":"2012","unstructured":"Aleksandar Nikolov, Kunal Talwar, and Li Zhang. 2012. The Geometry of Differential Privacy: the Sparse and Approximate Cases. STOC, 2012. Pages 351\u2013360."},{"key":"e_1_3_2_1_48_1","first-page":"2016","article-title":"Bridging the Gap between Computer Science and Legal Approaches to Privacy","volume":"31","author":"Nissim Kobbi","year":"2018","unstructured":"Kobbi Nissim, Aaron Bembenek, Alexandra Wood, Mark Bun, Marco Gaboardi, Urs Gasser, David R. O\\textquoteright Brien, and Salil Vadhan. 2018. Bridging the Gap between Computer Science and Legal Approaches to Privacy. Harvard Journal of Law & Technology, 31, 2016, 2018. Pages 687\u2013780. https:\/\/jolt.law.harvard.edu\/assets\/articlePDFs\/v31\/02.-Article-Wood-7.21.pdf","journal-title":"Harvard Journal of Law & Technology"},{"key":"e_1_3_2_1_49_1","unstructured":"Article 29 Data Protection Working Party. 2014. Opinion 05\/2014 on Anonymisation Techniques."},{"volume-title":"The Ethical Algorithm: The Science of Socially Aware Algorithm Design","author":"Roth Aaron","key":"e_1_3_2_1_50_1","unstructured":"Aaron Roth and Michael Kearns. 2019. The Ethical Algorithm: The Science of Socially Aware Algorithm Design. Oxford University Press."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Aaron Roth and Tim Roughgarden. 2010. Interactive Privacy via the Median Mechanism. In STOC. Pages 765\u2013774.","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"S. Shalev-Shwartz. 2012. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning.","DOI":"10.1561\/9781601985477"},{"volume-title":"Understanding Machine Learning - From Theory to Algorithms","author":"Shalev-Shwartz Shai","key":"e_1_3_2_1_53_1","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press."},{"volume-title":"Tutorials on the Foundations of Cryptography","author":"Vadhan Salil","key":"e_1_3_2_1_54_1","unstructured":"Salil Vadhan. 2017. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography. Springer. Pages 347\u2013450."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3264-1"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451028","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451028","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":55,"alternative-id":["10.1145\/3406325.3451028","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451028","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}