Fetching the paper…
Reading the bibliography…
We prove that $\tilde{\Theta}(k d^2 / \varepsilon^2)$ samples are necessary and sufficient for learning a mixture of $k$ Gaussians in $\mathbb{R}^d$, up to error $\varepsilon$ in total variation distance.
On information and sufficiency
S. Kullback and R. A. Leibler. 1951 · 1951
Earlier work this paper cites.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vladimir N. Vapnik and Alexey Ya. Chervonenkis. 1971 · 1971
Earlier work this paper cites.
Rates of convergence of minimum distance estimators and Kolmogorov’s entropy
Yannis G. Yatracos. 1985 · 1985
Earlier work this paper cites.
Relating data compression and learnability
Nick Littlestone and Manfred Warmuth. 1986 · 1986
Earlier work this paper cites.
Density estimation for statistics and data analysis
Bernard W. Silverman. 1986 · 1986
Earlier work this paper cites.
Estimates of the proximity of Gaussian measures
S. S. Barsov and V. V. Ul’yanov. 1987 · 1987
Earlier work this paper cites.
A course in density estimation . Progress in Probability and Statistics, Vol. 14
Luc Devroye. 1987 · 1987
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis Dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. 1989 · 1989
Earlier work this paper cites.
Approximate distributions of order statistics with applications to nonparametric statistics
Rolf-Dieter Reiss. 1989 · 1989
Earlier work this paper cites.
On the Learnability of Discrete Distributions. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (Montreal, Quebec, Canada) (STOC ’94) . ACM, New York, NY, USA, 273–282
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. 1994 · 1994
Earlier work this paper cites.
Graphical models . Oxford Statistical Science Series, Vol. 17
Steffen L. Lauritzen. 1996 · 1996
Earlier work this paper cites.
Bin Yu. 1997 · 1997
Earlier work this paper cites.
Neural network learning: theoretical foundations
Martin Anthony and Peter L. Bartlett. 1999 · 1999
Earlier work this paper cites.
Learning mixtures of Gaussians
Sanjoy Dasgupta. 1999 · 1999
Earlier work this paper cites.
Estimation of analytic functions
Ildar Ibragimov. 2001 · 1999
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
B. Laurent and P. Massart. 2000 · 2000
Earlier work this paper cites.
Local operator theory, random matrices and Banach spaces
Kenneth R. Davidson and Stanislaw J. Szarek. 2001 · 2001
Cited alongside, same era.
Combinatorial methods in density estimation
Luc Devroye and Gábor Lugosi. 2001 · 2001
Cited alongside, same era.
Convex optimization
Stephen Boyd and Lieven Vandenberghe. 2004 · 2004
Cited alongside, same era.
Coding theory: A first course
San Ling and Chaoping Xing. 2004 · 2004
Cited alongside, same era.
Smallest singular value of random matrices and geometry of random polytopes
Alexander E. Litvak, Alain Pajor, Mark Rudelson, and Nicole Tomczak-Jaegermann. 2005 · 2004
Cited alongside, same era.
Introduction to nonparametric estimation
Alexandre B. Tsybakov. 2009 · 2004
Cited alongside, same era.
Handbook of linear algebra (second ed.)
Leslie Hogben (Ed.). 2014 · 2014
Later among the works it cites.
Near-Optimal-Sample Estimators for Spherical Gaussian Mixtures
Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour. 2014 · 2014
Later among the works it cites.
Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms. In Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Melbourne, Victoria, Australia) (PODS ’15) . Association for Computing Machinery, New York, NY, USA, 249–263
Jayadev Acharya, Ilias Diakonikolas, Chinmay Hegde, Jerry Zheng Li, and Ludwig Schmidt. 2015 · 2015
Later among the works it cites.
Learning structured distributions
Ilias Diakonikolas. 2016 · 2016
Later among the works it cites.
Sample compression schemes for VC classes
Shay Moran and Amir Yehudayoff. 2016 · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sanjeev Arora and Ravi Kannan. 2005 · 2005
Cited alongside, same era.
Elements of information theory (second ed.)
Thomas M. Cover and Joy A. Thomas. 2006 · 2006
Cited alongside, same era.
PAC Learning Axis-aligned Mixtures of Gaussians with No Separation Assumption. In Proceedings of the 19th Annual Conference on Learning Theory (Pittsburgh, PA) (COLT’06) . Springer-Verlag, Berlin, Heidelberg, 20–34
Jon Feldman, Rocco A. Servedio, and Ryan O’Donnell. 2006 · 2006
Cited alongside, same era.
Gaussian processes for machine learning
Carl Edward Rasmussen and Christopher K. I. Williams. 2006 · 2006
Cited alongside, same era.
Polynomial Learning of Distribution Families. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS ’10) . IEEE Computer Society, Washington, DC, USA, 103–112
Mikhail Belkin and Kaushik Sinha. 2010 · 2010
Cited alongside, same era.
Settling the Polynomial Learnability of Mixtures of Gaussians. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS ’10) . IEEE Computer Society, Washington, DC, USA, 93–102
Ankur Moitra and Gregory Valiant. 2010 · 2010
Cited alongside, same era.
Learning Multivariate Log-concave Distributions. In Proceedings of the 2017 Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 65) , Satyen Kale and Ohad Shamir (Eds.). PMLR, Amsterdam, Netherlands, 711–727
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017b · 2017
Closest in time.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. 2017c · 2017
Closest in time.
Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis (second ed.)
Michael Mitzenmacher and Eli Upfal. 2017 · 2017
Closest in time.
The total variation distance between high-dimensional Gaussians
Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2018 · 2018
Closest in time.
Training Gaussian Mixture Models at Scale via Coresets
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. 2018 · 2018
Closest in time.
Strong coresets for k k -median and subspace approximation: goodbye dimension
Christian Sohler and David P. Woodruff. 2018 · 2018
Closest in time.
High-dimensional probability: An introduction with applications in data science . Cambridge Series in Statistical and Probabilistic Mathematics, Vol. 47
Roman Vershynin. 2018 · 2018
Closest in time.
The random matrix theory of the classical compact groups . Cambridge Tracts in Mathematics, Vol. 218
Elizabeth S. Meckes. 2019 · 2019
Closest in time.
Hassan Ashtiani, Shai Ben-David, Nicholas J.A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. 2020 · 2020
Closest in time.
The minimax learning rates of normal and Ising undirected graphical models
Luc Devroye, Abbas Mehrabian, and Tommy Reddad. 2020 · 2020
Closest in time.