{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:55:53Z","timestamp":1773510953187,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519947","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1406-1417","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism"],"prefix":"10.1145","author":[{"given":"Samuel B.","family":"Hopkins","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA \/ Massachusetts Institute of Technology, USA"}]},{"given":"Gautam","family":"Kamath","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Mahbod","family":"Majid","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"185","volume-title":"Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT '21)","author":"Aden-Ali Ishaq","year":"2021","unstructured":"Ishaq Aden-Ali , Hassan Ashtiani , and Gautam Kamath . 2021 . On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians . In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT '21) . JMLR, Inc. , 185 - 216 . Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. 2021. On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT '21). JMLR, Inc., 185-216."},{"key":"e_1_3_2_1_2_1","volume-title":"Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates","author":"Aden-Ali Ishaq","unstructured":"Ishaq Aden-Ali , Hassan Ashtiani , and Christopher Liaw . 2021. Privately Learning Mixtures of Axis-Aligned Gaussians . In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates , Inc . Ishaq Aden-Ali, Hassan Ashtiani, and Christopher Liaw. 2021. Privately Learning Mixtures of Axis-Aligned Gaussians. In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates, Inc."},{"key":"e_1_3_2_1_3_1","first-page":"14190","article-title":"Diferentially Private Covariance Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates","author":"Amin Kareem","year":"2019","unstructured":"Kareem Amin , Travis Dick , Alex Kulesza , Andres Munoz , and Sergei Vassilvitskii . 2019 . Diferentially Private Covariance Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates , Inc. , 14190 - 14199 . Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskii. 2019. Diferentially Private Covariance Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates, Inc., 14190-14199.","journal-title":"Inc."},{"key":"e_1_3_2_1_4_1","unstructured":"Hassan Ashtiani and Christopher Liaw. 2021. Private and polynomial time algorithms for learning Gaussians and beyond. arXiv preprint arXiv:2111.11320 ( 2021 ).   Hassan Ashtiani and Christopher Liaw. 2021. Private and polynomial time algorithms for learning Gaussians and beyond. arXiv preprint arXiv:2111.11320 ( 2021 )."},{"key":"e_1_3_2_1_5_1","volume-title":"Diferentially Private Sub-Gaussian Location Estimators. arXiv preprint arXiv","author":"Avella-Medina Marco","year":"1906","unstructured":"Marco Avella-Medina and Victor-Emmanuel Brunel . 2019. Diferentially Private Sub-Gaussian Location Estimators. arXiv preprint arXiv : 1906 . 11923 ( 2019 ). Marco Avella-Medina and Victor-Emmanuel Brunel. 2019. Diferentially Private Sub-Gaussian Location Estimators. arXiv preprint arXiv: 1906. 11923 ( 2019 )."},{"key":"e_1_3_2_1_6_1","first-page":"48","volume-title":"Proceedings on Privacy Enhancing Technologies 2020","author":"Avent Brendan","year":"2019","unstructured":"Brendan Avent , Yatharth Dubey , and Aleksandra Korolova . 2019 . The Power of the Hybrid Model for Mean Estimation . Proceedings on Privacy Enhancing Technologies 2020 , 4 ( 2019 ), 48 - 68 . Brendan Avent, Yatharth Dubey, and Aleksandra Korolova. 2019. The Power of the Hybrid Model for Mean Estimation. Proceedings on Privacy Enhancing Technologies 2020, 4 ( 2019 ), 48-68."},{"key":"e_1_3_2_1_7_1","unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. Course notes: http:\/\/www. sumofsquares. org\/public\/index. html ( 2016 ).   Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. Course notes: http:\/\/www. sumofsquares. org\/public\/index. html ( 2016 )."},{"key":"e_1_3_2_1_8_1","unstructured":"Rina Foygel Barber and John C Duchi. 2014. Privacy and Statistical Risk: Formalisms and Minimax Bounds. arXiv preprint arXiv:1412.4451 ( 2014 ).   Rina Foygel Barber and John C Duchi. 2014. Privacy and Statistical Risk: Formalisms and Minimax Bounds. arXiv preprint arXiv:1412.4451 ( 2014 )."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.56"},{"key":"e_1_3_2_1_10_1","first-page":"14475","article-title":"CoinPress: Practical Private Mean and Covariance Estimation. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates","author":"Biswas Sourav","year":"2020","unstructured":"Sourav Biswas , Yihe Dong , Gautam Kamath , and Jonathan Ullman . 2020 . CoinPress: Practical Private Mean and Covariance Estimation. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates , Inc. , 14475 - 14485 . Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. 2020. CoinPress: Practical Private Mean and Covariance Estimation. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc., 14475-14485.","journal-title":"Inc."},{"key":"e_1_3_2_1_11_1","first-page":"410","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '12)","author":"Blocki Jeremiah","year":"2012","unstructured":"Jeremiah Blocki , Avrim Blum , Anupam Datta , and Or Shefet . 2012 . The JohnsonLindenstrauss Transform Itself Preserves Diferential Privacy . In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '12) . IEEE Computer Society, Washington, DC, USA , 410 - 419 . Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Shefet. 2012. The JohnsonLindenstrauss Transform Itself Preserves Diferential Privacy. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '12). IEEE Computer Society, Washington, DC, USA, 410-419."},{"key":"e_1_3_2_1_12_1","unstructured":"Gavin Brown Marco Gaboardi Adam Smith Jonathan Ullman and Lydia Zakynthinou. 2021. Covariance-Aware Private Mean Estimation Without Private Covariance Estimation. arXiv preprint arXiv:2106.13329 ( 2021 ).   Gavin Brown Marco Gaboardi Adam Smith Jonathan Ullman and Lydia Zakynthinou. 2021. Covariance-Aware Private Mean Estimation Without Private Covariance Estimation. arXiv preprint arXiv:2106.13329 ( 2021 )."},{"key":"e_1_3_2_1_13_1","first-page":"156","article-title":"Private Hypothesis Selection. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates","author":"Bun Mark","year":"2019","unstructured":"Mark Bun , Gautam Kamath , Thomas Steinke , and Zhiwei Steven Wu . 2019 . Private Hypothesis Selection. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates , Inc. , 156 - 167 . Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. 2019. Private Hypothesis Selection. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates, Inc., 156-167.","journal-title":"Inc."},{"key":"e_1_3_2_1_14_1","first-page":"181","article-title":"Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates","author":"Bun Mark","year":"2019","unstructured":"Mark Bun and Thomas Steinke . 2019 . Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates , Inc. , 181 - 191 . Mark Bun and Thomas Steinke. 2019. Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates, Inc., 181-191.","journal-title":"Inc."},{"key":"e_1_3_2_1_15_1","first-page":"1","volume-title":"Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC '14)","author":"Bun Mark","year":"2014","unstructured":"Mark Bun , Jonathan Ullman , and Salil Vadhan . 2014 . Fingerprinting Codes and the Price of Approximate Diferential Privacy . In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC '14) . ACM, New York, NY, USA , 1 - 10 . Mark Bun, Jonathan Ullman, and Salil Vadhan. 2014. Fingerprinting Codes and the Price of Approximate Diferential Privacy. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing (STOC '14). ACM, New York, NY, USA, 1-10."},{"key":"e_1_3_2_1_16_1","volume-title":"The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Diferential Privacy. arXiv preprint arXiv","author":"Cai T. Tony","year":"1902","unstructured":"T. Tony Cai , Yichen Wang , and Linjun Zhang . 2019. The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Diferential Privacy. arXiv preprint arXiv : 1902 . 04495 ( 2019 ). T. Tony Cai, Yichen Wang, and Linjun Zhang. 2019. The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Diferential Privacy. arXiv preprint arXiv: 1902. 04495 ( 2019 )."},{"key":"e_1_3_2_1_17_1","first-page":"786","volume-title":"Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19)","author":"Cherapanamjeri Yeshwanth","unstructured":"Yeshwanth Cherapanamjeri , Nicolas Flammarion , and Peter L. Bartlett . 2019. Fast Mean Estimation with Sub-Gaussian Rates . In Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19) . 786 - 806 . Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. 2019. Fast Mean Estimation with Sub-Gaussian Rates. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19). 786-806."},{"key":"e_1_3_2_1_18_1","volume-title":"Robust subgaussian estimation of a mean vector in nearly linear time. arXiv preprint arXiv","author":"Depersin Jules","year":"1906","unstructured":"Jules Depersin and Guillaume Lecu\u00e9 . 2019. Robust subgaussian estimation of a mean vector in nearly linear time. arXiv preprint arXiv : 1906 . 03058 ( 2019 ). Jules Depersin and Guillaume Lecu\u00e9. 2019. Robust subgaussian estimation of a mean vector in nearly linear time. arXiv preprint arXiv: 1906. 03058 ( 2019 )."},{"key":"e_1_3_2_1_19_1","first-page":"2566","article-title":"Diferentially Private Learning of Structured Discrete Distributions. In Advances in Neural Information Processing Systems 28 (NIPS '15). Curran Associates","author":"Diakonikolas Ilias","year":"2015","unstructured":"Ilias Diakonikolas , Moritz Hardt , and Ludwig Schmidt . 2015 . Diferentially Private Learning of Structured Discrete Distributions. In Advances in Neural Information Processing Systems 28 (NIPS '15). Curran Associates , Inc. , 2566 - 2574 . Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. 2015. Diferentially Private Learning of Structured Discrete Distributions. In Advances in Neural Information Processing Systems 28 (NIPS '15). Curran Associates, Inc., 2566-2574.","journal-title":"Inc."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"e_1_3_2_1_22_1","volume-title":"Kane","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas and Daniel M . Kane . 2019 . Recent Advances in Algorithmic High-Dimensional Robust Statistics . arXiv preprint arXiv: 1911. 05911 ( 2019 ). Ilias Diakonikolas and Daniel M. Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. arXiv preprint arXiv: 1911. 05911 ( 2019 )."},{"key":"e_1_3_2_1_23_1","first-page":"1830","article-title":"Outlier Robust Mean Estimation with Subgaussian Rates via Stability. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Daniel M Kane , and Ankit Pensia . 2020 . Outlier Robust Mean Estimation with Subgaussian Rates via Stability. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates , Inc. , 1830 - 1840 . Ilias Diakonikolas, Daniel M Kane, and Ankit Pensia. 2020. Outlier Robust Mean Estimation with Subgaussian Rates via Stability. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc., 1830-1840.","journal-title":"Inc."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_3_2_1_25_1","volume-title":"Diferentially Private Confidence Intervals. arXiv preprint arXiv","author":"Du Wenxin","year":"2001","unstructured":"Wenxin Du , Canyon Foot , Monica Moniot , Andrew Bray , and Adam Groce . 2020. Diferentially Private Confidence Intervals. arXiv preprint arXiv : 2001 . 02285 ( 2020 ). Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. 2020. Diferentially Private Confidence Intervals. arXiv preprint arXiv: 2001. 02285 ( 2020 )."},{"key":"e_1_3_2_1_26_1","first-page":"371","volume-title":"Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC '09)","author":"Dwork Cynthia","year":"2009","unstructured":"Cynthia Dwork and Jing Lei . 2009 . Diferential Privacy and Robust Statistics . In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC '09) . ACM, New York, NY, USA , 371 - 380 . Cynthia Dwork and Jing Lei. 2009. Diferential Privacy and Robust Statistics. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC '09). ACM, New York, NY, USA, 371-380."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-060116-054123"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.46"},{"key":"e_1_3_2_1_30_1","first-page":"560","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20)","author":"Eli\u00e1\u0161 Marek","year":"2020","unstructured":"Marek Eli\u00e1\u0161 , Michael Kapralov , Janardhan Kulkarni , and Yin Tat Lee . 2020 . Differentially Private Release of Synthetic Graphs . In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20) . SIAM, Philadelphia, PA, USA , 560 - 578 . Marek Eli\u00e1\u0161, Michael Kapralov, Janardhan Kulkarni, and Yin Tat Lee. 2020. Differentially Private Release of Synthetic Graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20). SIAM, Philadelphia, PA, USA, 560-578."},{"key":"e_1_3_2_1_31_1","first-page":"705","volume-title":"Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing (STOC '10)","author":"Hardt Moritz","year":"2010","unstructured":"Moritz Hardt and Kunal Talwar . 2010 . On the Geometry of Diferential Privacy . In Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing (STOC '10) . ACM, New York, NY, USA , 705 - 714 . Moritz Hardt and Kunal Talwar. 2010. On the Geometry of Diferential Privacy. In Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing (STOC '10). ACM, New York, NY, USA, 705-714."},{"key":"e_1_3_2_1_32_1","volume-title":"Craig","author":"Homer Nils","year":"2008","unstructured":"Nils Homer , Szabolcs Szelinger , Margot Redman , David Duggan , Waibhav Tembe , Jill Muehling , John V. Pearson , Dietrich A. Stephan , Stanley F. Nelson , and David W . Craig . 2008 . Resolving Individuals Contributing Trace Amounts of DNA to Highly Complex Mixtures using High-Density SNP Genotyping Microarrays. PLoS Genetics 4, 8 ( 2008 ), 1-9. Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V. Pearson, Dietrich A. Stephan, Stanley F. Nelson, and David W. Craig. 2008. Resolving Individuals Contributing Trace Amounts of DNA to Highly Complex Mixtures using High-Density SNP Genotyping Microarrays. PLoS Genetics 4, 8 ( 2008 ), 1-9."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1843"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_35_1","first-page":"1021","volume-title":"Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC '18)","author":"Samuel","unstructured":"Samuel B. Hopkins and Jerry Li. 2018. Mixture Models, Robustness, and Sum of Squares Proofs . In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC '18) . ACM, New York, NY, USA , 1021 - 1034 . Samuel B. Hopkins and Jerry Li. 2018. Mixture Models, Robustness, and Sum of Squares Proofs. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC '18). ACM, New York, NY, USA, 1021-1034."},{"key":"e_1_3_2_1_36_1","first-page":"11902","article-title":"Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates","author":"Hopkins Samuel B","year":"2020","unstructured":"Samuel B Hopkins , Jerry Li , and Fred Zhang . 2020 . Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates , Inc. , 11902 - 11912 . Samuel B Hopkins, Jerry Li, and Fred Zhang. 2020. Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc., 11902-11912.","journal-title":"Inc."},{"key":"e_1_3_2_1_37_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Hsu Justin","unstructured":"Justin Hsu , Aaron Roth , Tim Roughgarden , and Jonathan Ullman . 2014. Privately solving linear programs . In International Colloquium on Automata, Languages, and Programming . Springer , 612-624. Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman. 2014. Privately solving linear programs. In International Colloquium on Automata, Languages, and Programming. Springer, 612-624."},{"key":"e_1_3_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates","author":"Huang Ziyue","unstructured":"Ziyue Huang , Yuting Liang , and Ke Yi. 2021. Instance-optimal Mean Estimation Under Diferential Privacy . In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates , Inc . Ziyue Huang, Yuting Liang, and Ke Yi. 2021. Instance-optimal Mean Estimation Under Diferential Privacy. In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates, Inc."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19)","author":"Kamath Gautam","year":"2019","unstructured":"Gautam Kamath , Jerry Li , Vikrant Singhal , and Jonathan Ullman . 2019 . Privately Learning High-Dimensional Distributions . In Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19) . 1853-1902. Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. 2019. Privately Learning High-Dimensional Distributions. In Proceedings of the 32nd Annual Conference on Learning Theory (COLT '19). 1853-1902."},{"key":"e_1_3_2_1_40_1","unstructured":"Gautam Kamath Xingtu Liu and Huanyu Zhang. 2021. Improved Rates for Diferentially Private Stochastic Convex Optimization with Heavy-Tailed Data. arXiv preprint arXiv:2106.01336 ( 2021 ).   Gautam Kamath Xingtu Liu and Huanyu Zhang. 2021. Improved Rates for Diferentially Private Stochastic Convex Optimization with Heavy-Tailed Data. arXiv preprint arXiv:2106.01336 ( 2021 )."},{"key":"e_1_3_2_1_41_1","unstructured":"Gautam Kamath Argyris Mouzakis Vikrant Singhal Thomas Steinke and Jonathan Ullman. 2021. A Private and Computationally-Eficient Estimator for Unbounded Gaussians. arXiv preprint arXiv:2111.04609 ( 2021 ).   Gautam Kamath Argyris Mouzakis Vikrant Singhal Thomas Steinke and Jonathan Ullman. 2021. A Private and Computationally-Eficient Estimator for Unbounded Gaussians. arXiv preprint arXiv:2111.04609 ( 2021 )."},{"key":"e_1_3_2_1_42_1","first-page":"168","article-title":"Differentially Private Algorithms for Learning Mixtures of Separated Gaussians. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates","author":"Kamath Gautam","year":"2019","unstructured":"Gautam Kamath , Or Shefet , Vikrant Singhal , and Jonathan Ullman . 2019 . Differentially Private Algorithms for Learning Mixtures of Separated Gaussians. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates , Inc. , 168 - 180 . Gautam Kamath, Or Shefet, Vikrant Singhal, and Jonathan Ullman. 2019. Differentially Private Algorithms for Learning Mixtures of Separated Gaussians. In Advances in Neural Information Processing Systems 32 ( NeurIPS '19). Curran Associates, Inc., 168-180.","journal-title":"Inc."},{"key":"e_1_3_2_1_43_1","first-page":"2204","volume-title":"Proceedings of the 33rd Annual Conference on Learning Theory (COLT '20)","author":"Kamath Gautam","year":"2020","unstructured":"Gautam Kamath , Vikrant Singhal , and Jonathan Ullman . 2020 . Private Mean Estimation of Heavy-Tailed Distributions . In Proceedings of the 33rd Annual Conference on Learning Theory (COLT '20) . 2204 - 2235 . Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. 2020. Private Mean Estimation of Heavy-Tailed Distributions. In Proceedings of the 33rd Annual Conference on Learning Theory (COLT '20). 2204-2235."},{"key":"e_1_3_2_1_44_1","volume-title":"A Primer on Private Statistics. arXiv preprint arXiv","author":"Kamath Gautam","year":"2005","unstructured":"Gautam Kamath and Jonathan Ullman . 2020. A Primer on Private Statistics. arXiv preprint arXiv : 2005 . 00010 ( 2020 ). Gautam Kamath and Jonathan Ullman. 2020. A Primer on Private Statistics. arXiv preprint arXiv: 2005. 00010 ( 2020 )."},{"key":"e_1_3_2_1_45_1","first-page":"1395","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13)","author":"Kapralov Michael","year":"2013","unstructured":"Michael Kapralov and Kunal Talwar . 2013 . On Diferentially Private Low Rank Approximation . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13) . SIAM, Philadelphia, PA, USA , 1395 - 1414 . Michael Kapralov and Kunal Talwar. 2013. On Diferentially Private Low Rank Approximation. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '13). SIAM, Philadelphia, PA, USA, 1395-1414."},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18)","author":"Karwa Vishesh","year":"2018","unstructured":"Vishesh Karwa and Salil Vadhan . 2018 . Finite Sample Diferentially Private Confidence Intervals . In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 44 : 1-44 : 9. Vishesh Karwa and Salil Vadhan. 2018. Finite Sample Diferentially Private Confidence Intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 44 : 1-44 : 9."},{"key":"e_1_3_2_1_47_1","unstructured":"Pravesh K Kothari and Jacob Steinhardt. 2017. Better agnostic clustering via relaxed tensor norms. arXiv preprint arXiv:1711.07465 ( 2017 ).   Pravesh K Kothari and Jacob Steinhardt. 2017. Better agnostic clustering via relaxed tensor norms. arXiv preprint arXiv:1711.07465 ( 2017 )."},{"key":"e_1_3_2_1_48_1","unstructured":"Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581 ( 2017 ).   Pravesh K Kothari and David Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. arXiv preprint arXiv:1711.11581 ( 2017 )."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_50_1","first-page":"1384","volume-title":"Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing (STOC '21)","author":"Leake Jonathan","year":"2021","unstructured":"Jonathan Leake , Colin McSwiggen , and Nisheeth K Vishnoi . 2021 . Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and diferential privacy . In Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing (STOC '21) . ACM, New York, NY, USA , 1384 - 1397 . Jonathan Leake, Colin McSwiggen, and Nisheeth K Vishnoi. 2021. Sampling matrices from Harish-Chandra-Itzykson-Zuber densities with applications to Quantum inference and diferential privacy. In Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing (STOC '21). ACM, New York, NY, USA, 1384-1397."},{"key":"e_1_3_2_1_51_1","volume-title":"Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates","author":"Levy Daniel","unstructured":"Daniel Levy , Ziteng Sun , Kareem Amin , Satyen Kale , Alex Kulesza , Mehryar Mohri , and Ananda Theertha Suresh . 2021. Learning with User-Level Privacy . In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates , Inc . Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. 2021. Learning with User-Level Privacy. In Advances in Neural Information Processing Systems 34 ( NeurIPS '21). Curran Associates, Inc."},{"key":"e_1_3_2_1_52_1","unstructured":"Xiyang Liu Weihao Kong Sham Kakade and Sewoong Oh. 2021. Robust and Diferentially Private Mean Estimation. arXiv preprint arXiv:2102.09159 ( 2021 ).   Xiyang Liu Weihao Kong Sham Kakade and Sewoong Oh. 2021. Robust and Diferentially Private Mean Estimation. arXiv preprint arXiv:2102.09159 ( 2021 )."},{"key":"e_1_3_2_1_53_1","unstructured":"Xiyang Liu Weihao Kong and Sewoong Oh. 2021. Diferential privacy and robust statistics in high dimensions. arXiv preprint arXiv:2111.06578 ( 2021 ).   Xiyang Liu Weihao Kong and Sewoong Oh. 2021. Diferential privacy and robust statistics in high dimensions. arXiv preprint arXiv:2111.06578 ( 2021 )."},{"key":"e_1_3_2_1_54_1","volume-title":"Felix Yu, Sanjiv Kumar, and Michael Riley.","author":"Liu Yuhan","year":"2020","unstructured":"Yuhan Liu , Ananda Theertha Suresh , Felix Yu, Sanjiv Kumar, and Michael Riley. 2020 . Learning Discrete Distributions: User vs Item-level Privacy. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc . Yuhan Liu, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and Michael Riley. 2020. Learning Discrete Distributions: User vs Item-level Privacy. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"crossref","unstructured":"G\u00e1bor Lugosi and Shahar Mendelson. 2019. Mean Estimation and Regression under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics 19 5 ( 2019 ) 1145-1190.   G\u00e1bor Lugosi and Shahar Mendelson. 2019. Mean Estimation and Regression under Heavy-Tailed Distributions: A Survey. Foundations of Computational Mathematics 19 5 ( 2019 ) 1145-1190.","DOI":"10.1007\/s10208-019-09427-x"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1639"},{"key":"e_1_3_2_1_57_1","volume-title":"Vishnoi","author":"Mangoubi Oren","year":"2021","unstructured":"Oren Mangoubi and Nisheeth K . Vishnoi . 2021 . Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Diferentially Private Optimization . arXiv preprint arXiv:2111.04089 ( 2021 ). Oren Mangoubi and Nisheeth K. Vishnoi. 2021. Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Diferentially Private Optimization. arXiv preprint arXiv:2111.04089 ( 2021 )."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_2_1_59_1","volume-title":"Conference on Learning Theory. PMLR, 1619-1673","author":"Potechin Aaron","year":"2017","unstructured":"Aaron Potechin and David Steurer . 2017 . Exact tensor completion with sum-ofsquares . In Conference on Learning Theory. PMLR, 1619-1673 . Aaron Potechin and David Steurer. 2017. Exact tensor completion with sum-ofsquares. In Conference on Learning Theory. PMLR, 1619-1673."},{"key":"e_1_3_2_1_60_1","volume-title":"A Unified Approach to Robust Mean Estimation. arXiv preprint arXiv","author":"Prasad Adarsh","year":"1907","unstructured":"Adarsh Prasad , Sivaraman Balakrishnan , and Pradeep Ravikumar . 2019. A Unified Approach to Robust Mean Estimation. arXiv preprint arXiv : 1907 . 00927 ( 2019 ). Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. 2019. A Unified Approach to Robust Mean Estimation. arXiv preprint arXiv: 1907. 00927 ( 2019 )."},{"key":"e_1_3_2_1_61_1","first-page":"3389","volume-title":"Proceedings of the International Congress of Mathematicians: Rio de Janeiro","author":"Raghavendra Prasad","year":"2018","unstructured":"Prasad Raghavendra , Tselil Schramm , and David Steurer . 2018 . High dimensional estimation via sum-of-squares proofs . In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. World Scientific , 3389 - 3423 . Prasad Raghavendra, Tselil Schramm, and David Steurer. 2018. High dimensional estimation via sum-of-squares proofs. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018. World Scientific, 3389-3423."},{"key":"e_1_3_2_1_62_1","volume-title":"Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18)","author":"Steinhardt Jacob","year":"2018","unstructured":"Jacob Steinhardt , Moses Charikar , and Gregory Valiant . 2018 . Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers . In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 45 : 1-45 : 21. Jacob Steinhardt, Moses Charikar, and Gregory Valiant. 2018. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS '18). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 45 : 1-45 : 21."},{"key":"e_1_3_2_1_63_1","first-page":"1588","volume-title":"Proceedings of the 28th Annual Conference on Learning Theory (COLT '15)","author":"Steinke Thomas","year":"2015","unstructured":"Thomas Steinke and Jonathan Ullman . 2015 . Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery . In Proceedings of the 28th Annual Conference on Learning Theory (COLT '15) . 1588 - 1628 . Thomas Steinke and Jonathan Ullman. 2015. Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery. In Proceedings of the 28th Annual Conference on Learning Theory (COLT '15). 1588-1628."},{"key":"e_1_3_2_1_64_1","first-page":"3301","article-title":"Optimal Private Median Estimation under Minimal Distributional Assumptions. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates","author":"Tzamos Christos","year":"2020","unstructured":"Christos Tzamos , Emmanouil-Vasileios Vlatakis-Gkaragkounis , and Ilias Zadik . 2020 . Optimal Private Median Estimation under Minimal Distributional Assumptions. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates , Inc. , 3301 - 3311 . Christos Tzamos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, and Ilias Zadik. 2020. Optimal Private Median Estimation under Minimal Distributional Assumptions. In Advances in Neural Information Processing Systems 33 ( NeurIPS '20). Curran Associates, Inc., 3301-3311.","journal-title":"Inc."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525873"},{"key":"e_1_3_2_1_66_1","volume-title":"Polynomial proof systems, efective derivations, and their applications in the sum-of-squares hierarchy","author":"Weitz Benjamin","unstructured":"Benjamin Weitz . 2017. Polynomial proof systems, efective derivations, and their applications in the sum-of-squares hierarchy . University of California , Berkeley. Benjamin Weitz. 2017. Polynomial proof systems, efective derivations, and their applications in the sum-of-squares hierarchy. University of California, Berkeley."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525970"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519947","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519947","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519947"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":67,"alternative-id":["10.1145\/3519935.3519947","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519947","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}