{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:03Z","timestamp":1750220583315,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,10,6]],"date-time":"2020-10-06T00:00:00Z","timestamp":1601942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["22R23068"],"award-info":[{"award-number":["22R23068"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"CRM-ISM postdoctoral fellowship and an IVADO-Apog\u00e9e-CFREF postdoctoral fellowship"},{"name":"NSERC Discovery"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"<jats:p>\n            We introduce a novel technique for distribution learning based on a notion of\n            <jats:italic>sample compression<\/jats:italic>\n            . Any class of distributions that allows such a compression scheme can be learned with few samples. Moreover, if a class of distributions has such a compression scheme, then so do the classes of\n            <jats:italic>products<\/jats:italic>\n            and\n            <jats:italic>mixtures<\/jats:italic>\n            of those distributions.\n          <\/jats:p>\n          <jats:p>\n            As an application of this technique, we prove that \u02dc\u0398(\n            <jats:italic>kd<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\u03b5\n            <jats:sup>2<\/jats:sup>\n            ) samples are necessary and sufficient for learning a mixture of\n            <jats:italic>k<\/jats:italic>\n            Gaussians in R\n            <jats:italic>\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            , up to error \u03b5 in total variation distance. This improves both the known upper bounds and lower bounds for this problem. For mixtures of axis-aligned Gaussians, we show that \u00d5(\n            <jats:italic>kd<\/jats:italic>\n            \/\u03b5\n            <jats:sup>2<\/jats:sup>\n            ) samples suffice, matching a known lower bound. Moreover, these results hold in an agnostic learning (or robust estimation) setting, in which the target distribution is only approximately a mixture of Gaussians. Our main upper bound is proven by showing that the class of Gaussians in R\n            <jats:italic>\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            admits a small compression scheme.\n          <\/jats:p>","DOI":"10.1145\/3417994","type":"journal-article","created":{"date-parts":[[2020,10,6]],"date-time":"2020-10-06T22:04:39Z","timestamp":1602021879000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes"],"prefix":"10.1145","volume":"67","author":[{"given":"Hassan","family":"Ashtiani","sequence":"first","affiliation":[{"name":"McMaster University, Canada and Vector Institute, Toronto, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shai","family":"Ben-David","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicholas J. A.","family":"Harvey","sequence":"additional","affiliation":[{"name":"University of British Columbia, British Columbia, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Liaw","sequence":"additional","affiliation":[{"name":"University of British Columbia, British Columbia, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0658-7709","authenticated-orcid":false,"given":"Abbas","family":"Mehrabian","sequence":"additional","affiliation":[{"name":"McGill University, Montr\u00e9al, Qu\u00e9bec Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaniv","family":"Plan","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, British Columbia, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,10,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745772"},{"key":"e_1_2_1_2_1","volume-title":"Bartlett","author":"Anthony Martin","year":"1999","unstructured":"Martin Anthony and Peter L . Bartlett . 1999 . Neural Network Learning: Theoretical Foundations . Cambridge University Press , Cambridge, UK. DOI:https:\/\/doi.org\/10.1017\/CBO9780511624216 10.1017\/CBO9780511624216 Martin Anthony and Peter L. Bartlett. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, UK. DOI:https:\/\/doi.org\/10.1017\/CBO9780511624216"},{"key":"e_1_2_1_3_1","volume-title":"Learning mixtures of separated nonspherical Gaussians. Ann. Appl. Probab. 15, 1A (02","author":"Arora Sanjeev","year":"2005","unstructured":"Sanjeev Arora and Ravi Kannan . 2005. Learning mixtures of separated nonspherical Gaussians. Ann. Appl. Probab. 15, 1A (02 2005 ), 69--92. DOI:https:\/\/doi.org\/10.1214\/105051604000000512 10.1214\/105051604000000512 Sanjeev Arora and Ravi Kannan. 2005. Learning mixtures of separated nonspherical Gaussians. Ann. Appl. Probab. 15, 1A (02 2005), 69--92. DOI:https:\/\/doi.org\/10.1214\/105051604000000512"},{"volume-title":"Advances in Neural Information Processing Systems 31","author":"Ashtiani Hassan","key":"e_1_2_1_4_1","unstructured":"Hassan Ashtiani , Shai Ben-David , Nicholas J. A. Harvey , Christopher Liaw , Abbas Mehrabian , and Yaniv Plan . 2018. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes . In Advances in Neural Information Processing Systems 31 , S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc. , 3412--3421. Retrieved from https:\/\/papers.nips.cc\/paper\/7601-nearly-tight-sample-complexity-bounds-for-learning-mixtures-of-gaussians-via-sample-compression-schemes. Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. 2018. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. In Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc., 3412--3421. Retrieved from https:\/\/papers.nips.cc\/paper\/7601-nearly-tight-sample-complexity-bounds-for-learning-mixtures-of-gaussians-via-sample-compression-schemes."},{"key":"e_1_2_1_5_1","volume-title":"Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. arxiv:cs.LG\/1710.05209","author":"Ashtiani Hassan","year":"2020","unstructured":"Hassan Ashtiani , Shai Ben-David , Nicholas J. A. Harvey , Christopher Liaw , Abbas Mehrabian , and Yaniv Plan . 2020. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. arxiv:cs.LG\/1710.05209 ( 2020 ). Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. 2020. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. arxiv:cs.LG\/1710.05209 (2020)."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918)","author":"Ashtiani Hassan","year":"2018","unstructured":"Hassan Ashtiani , Shai Ben-David , and Abbas Mehrabian . 2018 . Sample-efficient learning of mixtures . In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918) . AAAI Publications, 2679--2686. Retrieved from https:\/\/arxiv.org\/abs\/1706.01596. Hassan Ashtiani, Shai Ben-David, and Abbas Mehrabian. 2018. Sample-efficient learning of mixtures. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI\u201918). AAAI Publications, 2679--2686. Retrieved from https:\/\/arxiv.org\/abs\/1706.01596."},{"key":"e_1_2_1_7_1","first-page":"462","article-title":"Estimates of the proximity of Gaussian measures","volume":"34","author":"Barsov S. S.","year":"1987","unstructured":"S. S. Barsov and V. V. Ul\u2019yanov . 1987 . Estimates of the proximity of Gaussian measures . Sov. Math., Dokl. 34 (1987), 462 -- 466 . S. S. Barsov and V. V. Ul\u2019yanov. 1987. Estimates of the proximity of Gaussian measures. Sov. Math., Dokl. 34 (1987), 462--466.","journal-title":"Sov. Math., Dokl."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"volume-title":"Convex Optimization","author":"Boyd Stephen","key":"e_1_2_1_10_1","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press , Cambridge, UK . DOI:https:\/\/doi.org\/10.1017\/CBO9780511804441 10.1017\/CBO9780511804441 Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, Cambridge, UK. DOI:https:\/\/doi.org\/10.1017\/CBO9780511804441"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591848"},{"key":"e_1_2_1_12_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A . Thomas . 2006 . Elements of Information Theory (2nd ed.). Wiley-Interscience (John Wiley 8 Sons), Hoboken, NJ. Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (2nd ed.). Wiley-Interscience (John Wiley 8 Sons), Hoboken, NJ."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 27th Conference on Learning Theory (Proceedings of Machine Learning Research), Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.)","volume":"35","author":"Daskalakis Constantinos","year":"2014","unstructured":"Constantinos Daskalakis and Gautam Kamath . 2014 . Faster and sample near-optimal algorithms for proper learning mixtures of Gaussians . In Proceedings of the 27th Conference on Learning Theory (Proceedings of Machine Learning Research), Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.) , Vol. 35 . PMLR, Barcelona, Spain, 1183--1213. Retrieved from http:\/\/proceedings.mlr.press\/v35\/daskalakis14.html. Constantinos Daskalakis and Gautam Kamath. 2014. Faster and sample near-optimal algorithms for proper learning mixtures of Gaussians. In Proceedings of the 27th Conference on Learning Theory (Proceedings of Machine Learning Research), Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesv\u00e1ri (Eds.), Vol. 35. PMLR, Barcelona, Spain, 1183--1213. Retrieved from http:\/\/proceedings.mlr.press\/v35\/daskalakis14.html."},{"key":"e_1_2_1_15_1","first-page":"80010","volume-title":"Handbook of the Geometry of Banach Spaces","author":"Kenneth","year":"1874","unstructured":"Kenneth R. Davidson and Stanislaw J. Szarek. 2001. Local operator theory, random matrices and Banach spaces . In Handbook of the Geometry of Banach Spaces , Vol. I . North-Holland, Amsterdam, 317--366. DOI:https:\/\/doi.org\/10.1016\/S 1874 -5849(01) 80010 - 80013 10.1016\/S1874-5849(01)80010-3 Kenneth R. Davidson and Stanislaw J. Szarek. 2001. Local operator theory, random matrices and Banach spaces. In Handbook of the Geometry of Banach Spaces, Vol. I. North-Holland, Amsterdam, 317--366. DOI:https:\/\/doi.org\/10.1016\/S1874-5849(01)80010-3"},{"volume-title":"A Course in Density Estimation (Progress in Probability and Statistics)","author":"Devroye Luc","key":"e_1_2_1_16_1","unstructured":"Luc Devroye . 1987. A Course in Density Estimation (Progress in Probability and Statistics) , Vol. 14 . Birkh\u00e4user Boston, Inc. , Boston, MA . Luc Devroye. 1987. A Course in Density Estimation (Progress in Probability and Statistics), Vol. 14. Birkh\u00e4user Boston, Inc., Boston, MA."},{"volume-title":"Combinatorial Methods in Density Estimation","author":"Devroye Luc","key":"e_1_2_1_17_1","unstructured":"Luc Devroye and G\u00e1bor Lugosi . 2001. Combinatorial Methods in Density Estimation . Springer-Verlag , New York . DOI:https:\/\/doi.org\/10.1007\/978-1-4613-0125-7 10.1007\/978-1-4613-0125-7 Luc Devroye and G\u00e1bor Lugosi. 2001. Combinatorial Methods in Density Estimation. Springer-Verlag, New York. DOI:https:\/\/doi.org\/10.1007\/978-1-4613-0125-7"},{"key":"e_1_2_1_18_1","volume-title":"The total variation distance between high-dimensional Gaussians. arxiv:math.ST\/1810.08693","author":"Devroye Luc","year":"2018","unstructured":"Luc Devroye , Abbas Mehrabian , and Tommy Reddad . 2018. The total variation distance between high-dimensional Gaussians. arxiv:math.ST\/1810.08693 ( 2018 ). Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2018. The total variation distance between high-dimensional Gaussians. arxiv:math.ST\/1810.08693 (2018)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1721"},{"volume-title":"Handbook of Big Data","author":"Diakonikolas Ilias","key":"e_1_2_1_20_1","unstructured":"Ilias Diakonikolas . 2016. Learning structured distributions . In Handbook of Big Data . CRC Press , Boca Raton, FL , 267--283. Retrieved from http:\/\/www.iliasdiakonikolas.org\/distribution-learning-survey.pdf. Ilias Diakonikolas. 2016. Learning structured distributions. In Handbook of Big Data. CRC Press, Boca Raton, FL, 267--283. Retrieved from http:\/\/www.iliasdiakonikolas.org\/distribution-learning-survey.pdf."},{"key":"e_1_2_1_21_1","first-page":"I","article-title":"Communication-efficient distributed learning of discrete distributions","volume":"30","author":"Diakonikolas Ilias","year":"2017","unstructured":"Ilias Diakonikolas , Elena Grigorescu , Jerry Li , Abhiram Natarajan , Krzysztof Onak , and Ludwig Schmidt . 2017 . Communication-efficient distributed learning of discrete distributions . In Advances in Neural Information Processing Systems 30 , I . Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 6391--6401. Retrieved from http:\/\/papers.nips.cc\/paper\/7218-communication-efficient-distributed-learning-of-discrete-distributions. Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, and Ludwig Schmidt. 2017. Communication-efficient distributed learning of discrete distributions. In Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 6391--6401. Retrieved from http:\/\/papers.nips.cc\/paper\/7218-communication-efficient-distributed-learning-of-discrete-distributions.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Conference on Learning Theory (Proceedings of Machine Learning Research), Satyen Kale and Ohad Shamir (Eds.)","volume":"65","author":"Diakonikolas Ilias","year":"2017","unstructured":"Ilias Diakonikolas , Daniel M. Kane , and Alistair Stewart . 2017 . Learning multivariate log-concave distributions . In Proceedings of the Conference on Learning Theory (Proceedings of Machine Learning Research), Satyen Kale and Ohad Shamir (Eds.) , Vol. 65 . PMLR, Amsterdam, Netherlands, 711--727. Retrieved from http:\/\/proceedings.mlr.press\/v65\/diakonikolas17a.html. Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Learning multivariate log-concave distributions. In Proceedings of the Conference on Learning Theory (Proceedings of Machine Learning Research), Satyen Kale and Ohad Shamir (Eds.), Vol. 65. PMLR, Amsterdam, Netherlands, 711--727. Retrieved from http:\/\/proceedings.mlr.press\/v65\/diakonikolas17a.html."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907)","author":"Diakonikolas Ilias","year":"2017","unstructured":"Ilias Diakonikolas , Daniel M. Kane , and Alistair Stewart . 2017 . Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures (extended abstract) . In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907) . IEEE Computer Society, Los Alamitos, CA, 73--84. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2017.16 10.1109\/FOCS.2017.16 Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures (extended abstract). In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907). IEEE Computer Society, Los Alamitos, CA, 73--84. DOI:https:\/\/doi.org\/10.1109\/FOCS.2017.16"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_5"},{"key":"e_1_2_1_25_1","unstructured":"Leslie Hogben (Ed.). 2014. Handbook of Linear Algebra (2nd ed.). CRC Press Boca Raton FL.  Leslie Hogben (Ed.). 2014. Handbook of Linear Algebra (2nd ed.). CRC Press Boca Raton FL."},{"key":"e_1_2_1_26_1","volume-title":"State of the Art in Probability and Statistics (Leiden","author":"Ibragimov Ildar","year":"1999","unstructured":"Ildar Ibragimov . 2001. Estimation of analytic functions . In State of the Art in Probability and Statistics (Leiden , 1999 ) (IMS Lecture Notes--Monograph Series), Vol . 36. Institute of Mathematical Statistics , Beachwood, OH, 359--383. DOI:https:\/\/doi.org\/10.1214\/lnms\/1215090078 10.1214\/lnms Ildar Ibragimov. 2001. Estimation of analytic functions. In State of the Art in Probability and Statistics (Leiden, 1999) (IMS Lecture Notes--Monograph Series), Vol. 36. Institute of Mathematical Statistics, Beachwood, OH, 359--383. DOI:https:\/\/doi.org\/10.1214\/lnms\/1215090078"},{"key":"e_1_2_1_27_1","first-page":"2","article-title":"Disentangling","volume":"55","author":"Kalai Adam Tauman","year":"2012","unstructured":"Adam Tauman Kalai , Ankur Moitra , and Gregory Valiant . 2012 . Disentangling Gaussians. Commun. ACM 55 , 2 (Feb. 2012), 113--120. DOI:https:\/\/doi.org\/10.1145\/2076450.2076474 10.1145\/2076450.2076474 Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. 2012. Disentangling Gaussians. Commun. ACM 55, 2 (Feb. 2012), 113--120. DOI:https:\/\/doi.org\/10.1145\/2076450.2076474","journal-title":"Gaussians. Commun. ACM"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015957395"},{"volume-title":"The Clarendon Press","author":"Lauritzen Steffen L.","key":"e_1_2_1_31_1","unstructured":"Steffen L. Lauritzen . 1996. Graphical Models ( Oxford Statistical Science Series), Vol. 17. The Clarendon Press , Oxford University Press , New York . Oxford Science Publications. Steffen L. Lauritzen. 1996. Graphical Models (Oxford Statistical Science Series), Vol. 17. The Clarendon Press, Oxford University Press, New York. Oxford Science Publications."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755279"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.08.004"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"Training Gaussian mixture models at scale via coresets","volume":"18","author":"Lucic Mario","year":"2018","unstructured":"Mario Lucic , Matthew Faulkner , Andreas Krause , and Dan Feldman . 2018 . Training Gaussian mixture models at scale via coresets . J. Mach. Learn. Res. 18 , 160 (2018), 1 -- 25 . Retrieved from http:\/\/jmlr.org\/papers\/v18\/15-506.html. Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. 2018. Training Gaussian mixture models at scale via coresets. J. Mach. Learn. Res. 18, 160 (2018), 1--25. Retrieved from http:\/\/jmlr.org\/papers\/v18\/15-506.html.","journal-title":"J. Mach. Learn. Res."},{"volume-title":"The Random Matrix Theory of the Classical Compact Groups","author":"Meckes Elizabeth S.","key":"e_1_2_1_36_1","unstructured":"Elizabeth S. Meckes . 2019. The Random Matrix Theory of the Classical Compact Groups (Cambridge Tracts in Mathematics), Vol. 218 . Cambridge University Press , Cambridge, UK. DOI:https:\/\/doi.org\/10.1017\/9781108303453.009 10.1017\/9781108303453.009 Elizabeth S. Meckes. 2019. The Random Matrix Theory of the Classical Compact Groups (Cambridge Tracts in Mathematics), Vol. 218. Cambridge University Press, Cambridge, UK. DOI:https:\/\/doi.org\/10.1017\/9781108303453.009"},{"key":"e_1_2_1_37_1","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis ( 2 nd ed.). Cambridge University Press , Cambridge, UK . Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press, Cambridge, UK.","edition":"2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2890490"},{"key":"e_1_2_1_40_1","volume-title":"Williams","author":"Rasmussen Carl Edward","year":"2006","unstructured":"Carl Edward Rasmussen and Christopher K. I . Williams . 2006 . Gaussian Processes for Machine Learning. The MIT Press , Cambridge, MA. Retrieved from http:\/\/www.gaussianprocess.org\/gpml\/chapters\/. Carl Edward Rasmussen and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning. The MIT Press, Cambridge, MA. Retrieved from http:\/\/www.gaussianprocess.org\/gpml\/chapters\/."},{"volume-title":"Approximate Distributions of Order Statistics with Applications to Nonparametric Statistics","author":"Reiss Rolf-Dieter","key":"e_1_2_1_41_1","unstructured":"Rolf-Dieter Reiss . 1989. Approximate Distributions of Order Statistics with Applications to Nonparametric Statistics . Springer-Verlag , New York . https:\/\/doi.org\/10.1007\/978-1-4613-9620-8 10.1007\/978-1-4613-9620-8 Rolf-Dieter Reiss. 1989. Approximate Distributions of Order Statistics with Applications to Nonparametric Statistics. Springer-Verlag, New York. https:\/\/doi.org\/10.1007\/978-1-4613-9620-8"},{"volume-title":"Density Estimation for Statistics and Data Analysis","author":"Silverman Bernard W.","key":"e_1_2_1_42_1","unstructured":"Bernard W. Silverman . 1986. Density Estimation for Statistics and Data Analysis . Chapman 8 Hall, London. Bernard W. Silverman. 1986. Density Estimation for Statistics and Data Analysis. Chapman 8 Hall, London."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Sohler Christian","year":"2018","unstructured":"Christian Sohler and David P. Woodruff . 2018. Strong coresets for k-median and subspace approximation: Goodbye dimension . In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918) . IEEE Computer Society, Los Alamitos, CA, 802--813. DOI:https:\/\/doi.org\/10.1109\/FOCS. 2018 .00081 10.1109\/FOCS.2018.00081 Christian Sohler and David P. Woodruff. 2018. Strong coresets for k-median and subspace approximation: Goodbye dimension. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918). IEEE Computer Society, Los Alamitos, CA, 802--813. DOI:https:\/\/doi.org\/10.1109\/FOCS.2018.00081"},{"volume-title":"Advances in Neural Information Processing Systems 27","author":"Suresh Ananda Theertha","key":"e_1_2_1_44_1","unstructured":"Ananda Theertha Suresh , Alon Orlitsky , Jayadev Acharya , and Ashkan Jafarpour . 2014. Near-optimal-sample estimators for spherical Gaussian mixtures . In Advances in Neural Information Processing Systems 27 , Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (Eds.). Curran Associates, Inc. , 1395--1403. Retrieved from http:\/\/papers.nips.cc\/paper\/5251-near-optimal-sample-estimators-for-spherical-gaussian-mixtures. Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. 2014. Near-optimal-sample estimators for spherical Gaussian mixtures. In Advances in Neural Information Processing Systems 27, Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (Eds.). Curran Associates, Inc., 1395--1403. Retrieved from http:\/\/papers.nips.cc\/paper\/5251-near-optimal-sample-estimators-for-spherical-gaussian-mixtures."},{"volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov Alexandre B.","key":"e_1_2_1_45_1","unstructured":"Alexandre B. Tsybakov . 2009. Introduction to Nonparametric Estimation . Springer , New York . DOI:https:\/\/doi.org\/10.1007\/b13794 10.1007\/b13794 Alexandre B. Tsybakov. 2009. Introduction to Nonparametric Estimation. Springer, New York. DOI:https:\/\/doi.org\/10.1007\/b13794"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349553"},{"volume-title":"Festschrift for Lucien Le Cam","author":"Assouad Bin Yu.","key":"e_1_2_1_49_1","unstructured":"Bin Yu. 1997. Assouad , Fano, and Le Cam . In Festschrift for Lucien Le Cam . Springer , New York , 423--435. Retrieved from https:\/\/www.stat.berkeley.edu\/&sim;binyu\/ps\/LeCam.pdf. Bin Yu. 1997. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam. Springer, New York, 423--435. Retrieved from https:\/\/www.stat.berkeley.edu\/&sim;binyu\/ps\/LeCam.pdf."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417994","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3417994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:35Z","timestamp":1750195895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3417994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,6]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3417994"],"URL":"https:\/\/doi.org\/10.1145\/3417994","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2020,10,6]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}