{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T02:26:38Z","timestamp":1773714398646,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"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"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CF-1763786, CCF-1947889"],"award-info":[{"award-number":["CF-1763786, CCF-1947889"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451131","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"123-132","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["When is memorization of irrelevant training data necessary for high-accuracy learning?"],"prefix":"10.1145","author":[{"given":"Gavin","family":"Brown","sequence":"first","affiliation":[{"name":"Boston University, USA"}]},{"given":"Mark","family":"Bun","sequence":"additional","affiliation":[{"name":"Boston University, USA"}]},{"given":"Vitaly","family":"Feldman","sequence":"additional","affiliation":[{"name":"Apple, USA"}]},{"given":"Adam","family":"Smith","sequence":"additional","affiliation":[{"name":"Boston University, USA"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Apple, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Symposium on Advances in Approximate Bayesian Inference. Pages 1\u20136.","author":"Alemi Alexander A","year":"2020","unstructured":"Alexander A Alemi. 2020. Variational predictive information bottleneck. In Symposium on Advances in Approximate Bayesian Inference. Pages 1\u20136."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"e_1_3_2_1_3_1","first-page":"242","volume-title":"Proceedings of the 34th International Conference on Machine Learning-Volume 70","author":"Arpit Devansh","year":"2017","unstructured":"Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, and Yoshua Bengio. 2017. A closer look at memorization in deep networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. Pages 233\u2013242."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_5_1","unstructured":"Raef Bassily Shay Moran Ido Nachum Jonathan Shafer and Amir Yehudayoff. 2018. Learners that use little information. In Algorithmic Learning Theory. Pages 25\u201355."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.56"},{"key":"e_1_3_2_1_7_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.. Journal of Machine Learning Research, 20, 146, 2019. Pages 1\u201333.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_3_2_1_9_1","volume-title":"When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? arXiv preprint arXiv:2012.06421","author":"Brown Gavin","year":"2020","unstructured":"Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. 2020. When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? arXiv preprint arXiv:2012.06421, 2020."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1033587"},{"key":"e_1_3_2_1_12_1","volume-title":"28th \\USENIX\\ Security Symposium (\\USENIX\\ Security 19). Pages 267\u2013284.","author":"Carlini Nicholas","unstructured":"Nicholas Carlini, Chang Liu, \\'Ulfar Erlingsson, Jernej Kos, and Dawn Song. 2019. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th \\USENIX\\ Security Symposium (\\USENIX\\ Security 19). Pages 267\u2013284."},{"key":"e_1_3_2_1_13_1","volume-title":"Extracting Training Data from Large Language Models","author":"Carlini Nicholas","year":"2020","unstructured":"Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. 2020. Extracting Training Data from Large Language Models. 2020."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_3_2_1_15_1","unstructured":"Cynthia Dwork Vitaly Feldman Moritz Hardt Toni Pitassi Omer Reingold and Aaron Roth. 2015. Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems. Pages 2350\u20132358."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-060116-054123"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384290"},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. Pages 1000\u20131019","author":"Feldman Vitaly","year":"2014","unstructured":"Vitaly Feldman and David Xiao. 2014. Sample complexity bounds on differentially private learning via communication complexity. In Conference on Learning Theory. Pages 1000\u20131019."},{"key":"e_1_3_2_1_20_1","first-page":"2020","article-title":"What neural networks memorize and why: Discovering the long tail via influence estimation","volume":"33","author":"Feldman Vitaly","year":"2020","unstructured":"Vitaly Feldman and Chiyuan Zhang. 2020. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316332"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_24_1","first-page":"2020","article-title":"A limitation of the pac-bayes framework","volume":"33","author":"Livni Roi","year":"2020","unstructured":"Roi Livni and Shay Moran. 2020. A limitation of the pac-bayes framework. Advances in Neural Information Processing Systems, 33, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_25_1","volume-title":"International Conference on Machine Learning. Pages 3325\u20133334","author":"Ma Siyuan","year":"2018","unstructured":"Siyuan Ma, Raef Bassily, and Mikhail Belkin. 2018. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In International Conference on Machine Learning. Pages 3325\u20133334."},{"key":"e_1_3_2_1_26_1","volume-title":"Vadhan","author":"McGregor Andrew","year":"2010","unstructured":"Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. 2010. The Limits of Two-Party Differential Privacy. In FOCS. Pages 81\u201390."},{"key":"e_1_3_2_1_27_1","volume-title":"A direct sum result for the information complexity of learning. arXiv preprint arXiv:1804.05474","author":"Nachum Ido","year":"2018","unstructured":"Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. 2018. A direct sum result for the information complexity of learning. arXiv preprint arXiv:1804.05474, 2018."},{"key":"e_1_3_2_1_28_1","unstructured":"Ido Nachum and Amir Yehudayoff. 2019. Average-case information complexity of learning. In Algorithmic Learning Theory. Pages 633\u2013646."},{"key":"e_1_3_2_1_29_1","volume-title":"Overparameterized neural networks can implement associative memory. arXiv preprint arXiv:1909.12362","author":"Radhakrishnan Adityanarayanan","year":"2019","unstructured":"Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. 2019. Overparameterized neural networks can implement associative memory. arXiv preprint arXiv:1909.12362, 2019."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186563"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.59"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.41"},{"key":"e_1_3_2_1_33_1","volume-title":"The information bottleneck method. arXiv preprint physics\/0004057","author":"Tishby Naftali","year":"2000","unstructured":"Naftali Tishby, Fernando C Pereira, and William Bialek. 2000. The information bottleneck method. arXiv preprint physics\/0004057, 2000."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2015.7133169"},{"key":"e_1_3_2_1_35_1","unstructured":"Chulhee Yun Suvrit Sra and Ali Jadbabaie. 2019. Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity. In Advances in Neural Information Processing Systems. Pages 15558\u201315569."},{"key":"e_1_3_2_1_36_1","volume-title":"Identity crisis: Memorization and generalization under extreme overparameterization. arXiv preprint arXiv:1902.04698","author":"Zhang Chiyuan","year":"2019","unstructured":"Chiyuan Zhang, Samy Bengio, Moritz Hardt, Michael C Mozer, and Yoram Singer. 2019. Identity crisis: Memorization and generalization under extreme overparameterization. arXiv preprint arXiv:1902.04698, 2019."},{"key":"e_1_3_2_1_37_1","volume-title":"Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530","author":"Zhang Chiyuan","year":"2016","unstructured":"Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. 2016. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.122"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3451131","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451131","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3451131","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451131","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"}}]}}