Privately estimating a Gaussian: efficient, robust, and optimal. (English) Zbl 07844606
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 483-496 (2023).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | 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). |
| [2] | S. M. Ali and S. D. Silvey. 1966. A General Class of Coefficients of Divergence of One Distribution from Another. Journal of the Royal Statistical Society: Series B (Methodological), 28, 1 (1966), 131-142. https://doi.org/10.1111/j.2517-6161.1966.tb00626.x 10.1111/j.2517-6161.1966.tb00626.x · Zbl 0203.19902 |
| [3] | Hassan Ashtiani and Christopher Liaw. 2022. Private and polynomial time algorithms for learning Gaussians and beyond. In Conference on Learning Theory (COLT). |
| [4] | 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). · Zbl 1274.94038 |
| [5] | 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). |
| [6] | Dan Boneh and James Shaw. 1998. Collusion-Secure Fingerprinting for Digital Data. IEEE Trans. Inf. Theory, 44, 5 (1998), 1897-1905. · Zbl 0931.94051 |
| [7] | 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. |
| [8] | Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. 2021. Private Hypothesis Selection. IEEE Transactions on Information Theory, 67, 3 (2021), 1981-2000. https://doi.org/10.1109/TIT.2021.3049802 10.1109/TIT.2021.3049802 · Zbl 1473.62156 |
| [9] | Mark Bun and Thomas Steinke. 2016. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Conference on Theory of Cryptography (TCC), Martin Hirt and Adam D. Smith (Eds.). · Zbl 1406.94030 |
| [10] | Mark Bun, Jonathan Ullman, and Salil Vadhan. 2014. Fingerprinting Codes and the Price of Approximate Differential Privacy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC). · Zbl 1315.94113 |
| [11] | I. CSISZAR. 1967. Information-type measures of difference of probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica, 2 (1967), 229-318. https://cir.nii.ac.jp/crid/1571417125811646464 · Zbl 0157.25802 |
| [12] | Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2019. Robust estimators in high-dimensions without the computational intractability. SIAM J. Comput., 48, 2 (2019), 742-864. · Zbl 1421.68149 |
| [13] | Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2018. Robustly learning a gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). · Zbl 1403.68185 |
| [14] | Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911. · Zbl 07705538 |
| [15] | 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). · Zbl 1140.94336 |
| [16] | 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). · Zbl 1112.94027 |
| [17] | Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. 2010. Boosting and differential privacy. In IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). |
| [18] | Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. 2003. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS). |
| [19] | Noah Fleming, Pravesh Kothari, and Toniann Pitassi. 2019. Semialgebraic proofs and efficient algorithm design. Foundations and Trends® in Theoretical Computer Science, 14, 1-2 (2019), 1-221. · Zbl 1430.68428 |
| [20] | 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). |
| [21] | Moritz Hardt and Kunal Talwar. 2010. On the geometry of differential privacy. In Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC). · Zbl 1293.68098 |
| [22] | Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. 2022. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC). · Zbl 07774426 |
| [23] | 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 |
| [24] | Peter J Huber. 1964. Robust Estimation of a Location Parameter. The Annals of Mathematical Statistics, 35, 1 (1964), 73-101. · Zbl 0136.39805 |
| [25] | Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. 2019. Privately learning high-dimensional distributions. In Conference on Learning Theory (COLT). |
| [26] | 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). |
| [27] | 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). |
| [28] | Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. 2020. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory (COLT). |
| [29] | Vishesh Karwa and Salil P. Vadhan. 2018. Finite Sample Differentially Private Confidence Intervals. In Innovations in Theoretical Computer Science Conference (ITCS). · Zbl 1462.68084 |
| [30] | Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. 2011. What Can We Learn Privately? SIAM J. Comput., 40, 3 (2011), 793-826. https://doi.org/10.1137/090756090 10.1137/090756090 · Zbl 1235.68093 |
| [31] | Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou. 2014. Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 1644-1658. · Zbl 1423.68348 |
| [32] | Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. 2022. Private robust estimation by stabilizing convex relaxations. In Conference on Learning Theory (COLT). |
| [33] | 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). |
| [34] | Pravesh K Kothari, Jacob Steinhardt, and David Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). · Zbl 1434.62125 |
| [35] | Pravesh K Kothari, Jacob Steinhardt, and David Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 1035-1046. · Zbl 1434.62125 |
| [36] | Kevin A Lai, Anup B Rao, and Santosh Vempala. 2016. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). |
| [37] | Jean B Lasserre. 2001. New positive semidefinite relaxations for nonconvex quadratic programs. In Advances in Convex Analysis and Global Optimization. Springer, 319-331. · Zbl 1015.90063 |
| [38] | 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). |
| [39] | Xiyang Liu, Weihao Kong, and Sewoong Oh. 2022. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory (COLT). |
| [40] | Frank McSherry. 2010. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. Commun. ACM, 53, 9 (2010), 89-97. https://doi.org/10.1145/1810891.1810916 10.1145/1810891.1810916 |
| [41] | Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS). · Zbl 1232.68047 |
| [42] | Yurii Nesterov. 2000. Squared functional systems and optimization problems. In High performance optimization. Springer, 405-440. · Zbl 0958.90090 |
| [43] | Aleksandar Nikolov, Kunal Talwar, and Li Zhang. 2013. The geometry of differential privacy: the sparse and approximate cases. In Annual ACM Symposium on Theory of Computing (STOC). · Zbl 1294.68087 |
| [44] | Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology. |
| [45] | Mark Rudelson and Roman Vershynin. 2013. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18 (2013), 1-9. · Zbl 1329.60056 |
| [46] | Igal Sason and Sergio Verdú. 2016. f-Divergence Inequalities. IEEE Transactions on Information Theory, 62, 11 (2016), 5973-6006. https://doi.org/10.1109/TIT.2016.2603151 10.1109/TIT.2016.2603151 · Zbl 1359.94363 |
| [47] | Naum Z Shor. 1987. Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences, 25 (1987), 1-11. · Zbl 0655.90055 |
| [48] | Vikrant Singhal and Thomas Steinke. 2021. Privately learning subspaces. In Advances in Neural Information Processing Systems (NeurIPS). |
| [49] | 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). · Zbl 1462.68163 |
| [50] | Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. 2022. Friendlycore: Practical differentially private aggregation. In International Conference on Machine Learning (ICML). |
| [51] | John W. Tukey. 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics, 2 (1960), 448-485. · Zbl 0201.52803 |
| [52] | Salil P. Vadhan. 2017. The Complexity of Differential Privacy. In Tutorials on the Foundations of Cryptography — Dedicated to Oded Goldreich. Springer, 347-450. isbn:978-3-319-57047-1 https://doi.org/10.1007/978-3-319-57048-8_7 10.1007/978-3-319-57048-8_7 · Zbl 1481.94070 |
| [53] | Roman Vershynin. 2018. High-dimensional probability: An introduction with applications in data science. 47, Cambridge University Press. · Zbl 1430.60005 |
| [54] | Martin J. Wainwright. 2019. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. https://doi.org/10.1017/9781108627771 10.1017/9781108627771 · Zbl 1457.62011 |
| [55] | Stanley L. Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias. J. Amer. Statist. Assoc., 60, 309 (1965), 63-69. · Zbl 1298.62024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
