Sample-Efficient Learning of Mixtures

On the learnability of discrete distributions

Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie · 1994

Earlier work this paper cites.

Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks

Marek Karpinski and Angus Macintyre · 1997

Earlier work this paper cites.

Neural network learning: theoretical foundations

Martin Anthony and Peter Bartlett · 1999

Earlier work this paper cites.

Learning mixtures of Gaussians

Sanjoy Dasgupta · 1999

Earlier work this paper cites.

Combinatorial methods in density estimation

Luc Devroye and Gábor Lugosi · 2001

Earlier work this paper cites.

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Michael Mitzenmacher and Eli Upfal · 2005

Earlier work this paper cites.

PAC learning axis-aligned mixtures of Gaussians with no separation assumption

Jon Feldman, Rocco A. Servedio, and Ryan O’Donnell · 2006

Earlier work this paper cites.

Density estimation in linear time

Satyaki Mahalanabis and Daniel Stefankovic · 2008

Cited alongside, same era.

Polynomial learning of distribution families

Mikhail Belkin and Kaushik Sinha · 2010

Cited alongside, same era.

Settling the polynomial learnability of mixtures of Gaussians

Ankur Moitra and Gregory Valiant · 2010

Cited alongside, same era.

Efficient density estimation via piecewise polynomial approximation

Siu-On Chan, Ilias Diakonikolas, Rocco A. Servedio, and Xiaorui Sun · 2014

Cited alongside, same era.

Near-optimal-sample estimators for spherical Gaussian mixtures

Ananda Theertha Suresh, Alon Orlitsky, Jayadev Acharya, and Ashkan Jafarpour · 2014

Cited alongside, same era.

Robust estimators in high dimensions without the computational intractability

I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart · 2016

Cited alongside, same era.

Learning Structured Distributions

Ilias Diakonikolas · 2016

Later among the works it cites.

Sample-optimal density estimation in nearly-linear time

Jayadev Acharya, Ilias Diakonikolas, Jerry Li, and Ludwig Schmidt · 2017

Closest in time.

Learning multivariate log-concave distributions

Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart · 2017

Closest in time.

Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures

Original

Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart · 2017

Closest in time.

Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities

Jerry Li and Ludwig Schmidt · 2017

Closest in time.

Settling the sample complexity for learning mixtures of Gaussians