{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T10:36:27Z","timestamp":1716892587868},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"Simons Foundation","doi-asserted-by":"publisher","award":[""]},{"name":"National Science Foundation","award":[""]},{"DOI":"10.13039\/100000893","name":"Google","doi-asserted-by":"publisher","award":[""]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","award":[""]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585194","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Privately Estimating a Gaussian: Efficient, Robust, and Optimal"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Alabi","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Pranay","family":"Tankala","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}]},{"given":"Prayaag","family":"Venkat","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}]},{"given":"Fred","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Ishaq Aden-Ali Hassan Ashtiani and Gautam Kamath. 2021. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Algorithmic Learning Theory (ALT). \t\t\t\t Ishaq Aden-Ali Hassan Ashtiani and Gautam Kamath. 2021. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Algorithmic Learning Theory (ALT)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1966.tb00626.x"},{"key":"e_1_3_2_1_3_1","volume-title":"Conference on Learning Theory (COLT).","author":"Ashtiani Hassan","year":"2022","unstructured":"Hassan Ashtiani and Christopher Liaw . 2022 . Private and polynomial time algorithms for learning Gaussians and beyond . In Conference on Learning Theory (COLT). Hassan Ashtiani and Christopher Liaw. 2022. Private and polynomial time algorithms for learning Gaussians and beyond. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_4_1","volume-title":"Bounds on the Sample Complexity for Private Learning and Private Data Release. In Conference on Theory of Cryptography (TCC) (Lecture Notes in Computer Science).","author":"Beimel Amos","year":"2010","unstructured":"Amos Beimel , Shiva Prasad Kasiviswanathan , and Kobbi Nissim . 2010 . Bounds on the Sample Complexity for Private Learning and Private Data Release. In Conference on Theory of Cryptography (TCC) (Lecture Notes in Computer Science). Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. 2010. Bounds on the Sample Complexity for Private Learning and Private Data Release. In Conference on Theory of Cryptography (TCC) (Lecture Notes in Computer Science)."},{"key":"e_1_3_2_1_5_1","volume-title":"Coinpress: Practical private mean and covariance estimation. In Advances in Neural Information Processing Systems (NeurIPS).","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 (NeurIPS). Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. 2020. Coinpress: Practical private mean and covariance estimation. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.705568"},{"key":"e_1_3_2_1_7_1","unstructured":"Gavin Brown Marco Gaboardi Adam Smith Jonathan Ullman and Lydia Zakynthinou. 2021. Covariance-aware private mean estimation without private covariance estimation. In Advances in Neural Information Processing Systems. \t\t\t\t Gavin Brown Marco Gaboardi Adam Smith Jonathan Ullman and Lydia Zakynthinou. 2021. Covariance-aware private mean estimation without private covariance estimation. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3049802"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591877"},{"key":"e_1_3_2_1_11_1","first-page":"229","article-title":"Information-type measures of difference of probability distributions and indirect observation","volume":"2","author":"I.","year":"1967","unstructured":"I. CSISZAR. 1967 . Information-type measures of difference of probability distributions and indirect observation . Studia Scientiarum Mathematicarum Hungarica , 2 (1967), 229 \u2013 318 . https:\/\/cir.nii.ac.jp\/crid\/1571417125811646464 I. CSISZAR. 1967. Information-type measures of difference of probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica, 2 (1967), 229\u2013318. https:\/\/cir.nii.ac.jp\/crid\/1571417125811646464","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.171"},{"key":"e_1_3_2_1_14_1","unstructured":"Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911. \t\t\t\t Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911."},{"key":"e_1_3_2_1_15_1","volume-title":"Ourselves: Privacy Via Distributed Noise Generation. In Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT).","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork , Krishnaram Kenthapadi , Frank McSherry , Ilya Mironov , and Moni Naor . 2006 . Our Data , Ourselves: Privacy Via Distributed Noise Generation. In Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT). Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In Annual International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT)."},{"key":"e_1_3_2_1_16_1","volume-title":"Third Theory of Cryptography Conference on Theory of Cryptography (TCC).","author":"Dwork Cynthia","unstructured":"Cynthia Dwork , Frank McSherry , Kobbi Nissim , and Adam D. Smith . 2006. Calibrating Noise to Sensitivity in Private Data Analysis . In Third Theory of Cryptography Conference on Theory of Cryptography (TCC). Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Third Theory of Cryptography Conference on Theory of Cryptography (TCC)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.12"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_20_1","unstructured":"Kristian Georgiev and Samuel B Hopkins. 2022. Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t Kristian Georgiev and Samuel B Hopkins. 2022. Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519947"},{"key":"#cr-split#-e_1_3_2_1_23_1.1","unstructured":"Samuel B. Hopkins Gautam Kamath Mahbod Majid and Shyam Narayanan. 2022. Robustness Implies Privacy in Statistical Estimation. https:\/\/doi.org\/10.48550\/ARXIV.2212.05015 10.48550\/ARXIV.2212.05015"},{"key":"#cr-split#-e_1_3_2_1_23_1.2","doi-asserted-by":"crossref","unstructured":"Samuel B. Hopkins Gautam Kamath Mahbod Majid and Shyam Narayanan. 2022. Robustness Implies Privacy in Statistical Estimation. https:\/\/doi.org\/10.48550\/ARXIV.2212.05015","DOI":"10.1145\/3564246.3585115"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_1_25_1","volume-title":"Conference on Learning Theory (COLT).","author":"Kamath Gautam","year":"2019","unstructured":"Gautam Kamath , Jerry Li , Vikrant Singhal , and Jonathan Ullman . 2019 . Privately learning high-dimensional distributions . In Conference on Learning Theory (COLT). Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. 2019. Privately learning high-dimensional distributions. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_26_1","unstructured":"Gautam Kamath Argyris Mouzakis and Vikrant Singhal. 2022. New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t Gautam Kamath Argyris Mouzakis and Vikrant Singhal. 2022. New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory (COLT).","author":"Kamath Gautam","year":"2022","unstructured":"Gautam Kamath , Argyris Mouzakis , Vikrant Singhal , Thomas Steinke , and Jonathan Ullman . 2022 . A private and computationally-efficient estimator for unbounded gaussians . In Conference on Learning Theory (COLT). Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. 2022. A private and computationally-efficient estimator for unbounded gaussians. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_28_1","volume-title":"Conference on Learning Theory (COLT).","author":"Kamath Gautam","year":"2020","unstructured":"Gautam Kamath , Vikrant Singhal , and Jonathan Ullman . 2020 . Private mean estimation of heavy-tailed distributions . In Conference on Learning Theory (COLT). Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. 2020. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_29_1","volume-title":"Finite Sample Differentially Private Confidence Intervals. In Innovations in Theoretical Computer Science Conference (ITCS).","author":"Karwa Vishesh","unstructured":"Vishesh Karwa and Salil P. Vadhan . 2018 . Finite Sample Differentially Private Confidence Intervals. In Innovations in Theoretical Computer Science Conference (ITCS). Vishesh Karwa and Salil P. Vadhan. 2018. Finite Sample Differentially Private Confidence Intervals. In Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.119"},{"key":"e_1_3_2_1_32_1","volume-title":"Conference on Learning Theory (COLT).","author":"Kothari Pravesh","year":"2022","unstructured":"Pravesh Kothari , Pasin Manurangsi , and Ameya Velingker . 2022 . Private robust estimation by stabilizing convex relaxations . In Conference on Learning Theory (COLT). Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. 2022. Private robust estimation by stabilizing convex relaxations. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_33_1","unstructured":"Pravesh K Kothari Peter Manohar and Brian Hu Zhang. 2022. Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. In Algorithmic Learning Theory (ALT). \t\t\t\t Pravesh K Kothari Peter Manohar and Brian Hu Zhang. 2022. Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. In Algorithmic Learning Theory (ALT)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_37_1","volume-title":"Advances in Convex Analysis and Global Optimization","author":"Lasserre Jean B","unstructured":"Jean B Lasserre . 2001. New positive semidefinite relaxations for nonconvex quadratic programs . In Advances in Convex Analysis and Global Optimization . Springer , 319\u2013331. Jean B Lasserre. 2001. New positive semidefinite relaxations for nonconvex quadratic programs. In Advances in Convex Analysis and Global Optimization. Springer, 319\u2013331."},{"key":"e_1_3_2_1_38_1","unstructured":"Xiyang Liu Weihao Kong Sham M. Kakade and Sewoong Oh. 2021. Robust and differentially private mean estimation. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t Xiyang Liu Weihao Kong Sham M. Kakade and Sewoong Oh. 2021. Robust and differentially private mean estimation. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_39_1","volume-title":"Conference on Learning Theory (COLT).","author":"Liu Xiyang","year":"2022","unstructured":"Xiyang Liu , Weihao Kong , and Sewoong Oh . 2022 . Differential privacy and robust statistics in high dimensions . In Conference on Learning Theory (COLT). Xiyang Liu, Weihao Kong, and Sewoong Oh. 2022. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810891.1810916"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_17"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"e_1_3_2_1_44_1","volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization","author":"Parrilo Pablo A","unstructured":"Pablo A Parrilo . 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization . California Institute of Technology . Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v18-2865"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2603151"},{"key":"e_1_3_2_1_47_1","first-page":"1","article-title":"Quadratic optimization problems","volume":"25","author":"Shor Naum Z","year":"1987","unstructured":"Naum Z Shor . 1987 . Quadratic optimization problems . Soviet Journal of Computer and Systems Sciences , 25 (1987), 1 \u2013 11 . Naum Z Shor. 1987. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25 (1987), 1\u201311.","journal-title":"Soviet Journal of Computer and Systems Sciences"},{"key":"e_1_3_2_1_48_1","unstructured":"Vikrant Singhal and Thomas Steinke. 2021. Privately learning subspaces. In Advances in Neural Information Processing Systems (NeurIPS). \t\t\t\t Vikrant Singhal and Thomas Steinke. 2021. Privately learning subspaces. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_49_1","volume-title":"Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In 9th Innovations in Theoretical Computer Science Conference (ITCS).","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 9th Innovations in Theoretical Computer Science Conference (ITCS). Jacob Steinhardt, Moses Charikar, and Gregory Valiant. 2018. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. In 9th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_50_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Tsfadia Eliad","year":"2022","unstructured":"Eliad Tsfadia , Edith Cohen , Haim Kaplan , Yishay Mansour , and Uri Stemmer . 2022 . Friendlycore: Practical differentially private aggregation . In International Conference on Machine Learning (ICML). Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. 2022. Friendlycore: Practical differentially private aggregation. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_51_1","volume-title":"A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2","author":"Tukey John W.","year":"1960","unstructured":"John W. Tukey . 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2 ( 1960 ), 448\u2013485. John W. Tukey. 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2 (1960), 448\u2013485."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_3_2_1_53_1","volume-title":"High-dimensional probability: An introduction with applications in data science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin . 2018. High-dimensional probability: An introduction with applications in data science. 47 , Cambridge University Press . Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. 47, Cambridge University Press."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585194","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T15:38:56Z","timestamp":1686584336000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":56,"alternative-id":["10.1145\/3564246.3585194","10.1145\/3564246"],"URL":"http:\/\/dx.doi.org\/10.1145\/3564246.3585194","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}