Fetching the paper…
Reading the bibliography…
We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that substantially improve upon the statistical guarantees achieved by previous efficient algorithms.
Andrew C Berry, The accuracy of the gaussian approximation to the sum of independent variates , Transactions of the american mathematical society 49
1941
Earlier work this paper cites.
Peter J Huber, Robust estimation of a location parameter , The Annals of Mathematical Statistics 35
1964
Earlier work this paper cites.
John W Tukey, Mathematics and the picturing of data , Proceedings of the international congress of mathematicians, vol. 2, 1975, pp. 523–531
1975
Earlier work this paper cites.
J.W. Tukey, Mathematics and picturing of data , Proceedings of ICM, vol. 6, 1975, pp. 523–531
1975
Earlier work this paper cites.
D. S. Johnson and F. P. Preparata, The densest hemisphere problem , Theoretical Computer Science 6
1978
Earlier work this paper cites.
CF Jeff Wu, On the convergence properties of the em algorithm , The Annals of statistics (1983), 95–103
1983
Earlier work this paper cites.
D Michael Titterington, Adrian FM Smith, and Udi E Makov, Statistical analysis of finite mixture distributions , Wiley,, 1985
1985
Earlier work this paper cites.
Leslie G. Valiant, Learning disjunction of conjunctions , IJCAI, Morgan Kaufmann, 1985, pp. 560–566
1985
Earlier work this paper cites.
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel, Robust statistics. the approach based on influence functions , Wiley New York, 1986
1986
Earlier work this paper cites.
Sanjoy Dasgupta, Learning mixtures of gaussians , Foundations of computer science, 1999. 40th annual symposium on, IEEE, 1999, pp. 634–644
1999
Earlier work this paper cites.
Santosh Vempala and Grant Wang, A spectral algorithm for learning mixtures of distributions , FOCS, IEEE Computer Society, 2002, p. 113
2002
Earlier work this paper cites.
R. Servedio, Smooth boosting and learning with malicious noise , JMLR 4
2003
Earlier work this paper cites.
Geoffrey McLachlan and David Peel, Finite mixture models , John Wiley & Sons, 2004
2004
Earlier work this paper cites.
Sanjeev Arora and Ravi Kannan, Learning mixtures of separated nonspherical Gaussians , Ann. Appl. Probab. 15
2005
Earlier work this paper cites.
Dimitris Achlioptas and Frank McSherry, On spectral learning of mixtures of distributions , International Conference on Computational Learning Theory, Springer, 2005, pp. 458–469
2005
Earlier work this paper cites.
T. Bernholt, Robust estimators are hard to compute , Tech. report, University of Dortmund, Germany, 2006
2006
Earlier work this paper cites.
Jon Feldman, Rocco A. Servedio, and Ryan O’Donnell, PAC learning axis-aligned mixtures of gaussians with no separation assumption , COLT, Lecture Notes in Computer Science, vol. 4005, Springer, 2006, pp. 20–34
2006
Earlier work this paper cites.
Sanjoy Dasgupta and Leonard Schulman, A probabilistic analysis of em for mixtures of separated, spherical gaussians , Journal of Machine Learning Research 8
2007
Earlier work this paper cites.
S. C. Brubaker, Robust PCA and clustering in noisy mixtures , SODA 2009, 2009, pp. 1078–1087
2009
Earlier work this paper cites.
Mikhail Belkin and Kaushik Sinha, Polynomial learning of distribution families , FOCS, IEEE Computer Society, 2010, pp. 103–112
2010
Earlier work this paper cites.
Amit Kumar and Ravindran Kannan, Clustering with spectral norm and the k-means algorithm , FOCS, IEEE Computer Society, 2010, pp. 299–308
2010
Earlier work this paper cites.
Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant, Efficiently learning mixtures of two gaussians , STOC, ACM, 2010, pp. 553–562
2010
Earlier work this paper cites.
Ankur Moitra and Gregory Valiant, Settling the polynomial learnability of mixtures of gaussians , FOCS, IEEE Computer Society, 2010, pp. 93–102
2010
Cited alongside, same era.
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices , CoRR abs/1011.3027
2010
Cited alongside, same era.
E. J. Candès, X. Li, Y. Ma, and J. Wright, Robust principal component analysis? , J. ACM 58
2011
Cited alongside, same era.
2012
Cited alongside, same era.
Joel A. Tropp, User-friendly tail bounds for sums of random matrices , Foundations of Computational Mathematics 12
2012
Cited alongside, same era.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robust estimators in high dimensions without the computational intractability , FOCS, IEEE Computer Society, 2016, pp. 655–664
2016
Later among the works it cites.
2016
Later among the works it cites.
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer, Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors , STOC, ACM, 2016, pp. 178–191
2016
Later among the works it cites.
Kevin A. Lai, Anup B. Rao, and Santosh Vempala, Agnostic estimation of mean and covariance , FOCS, IEEE Computer Society, 2016, pp. 665–674
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…
Daniel Hsu and Sham M. Kakade, Learning mixtures of spherical Gaussians: moment methods and spectral decompositions , ITCS’13—Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, ACM, New York, 2013, pp. 11–19. MR 3385380
2013
Cited alongside, same era.
Ryan O’Donnell and Yuan Zhou, Approximability and proof complexity , SODA, SIAM, 2013, pp. 1537–1556
2013
Cited alongside, same era.
Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James R. Voss, The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures , COLT, JMLR Workshop and Conference Proceedings, vol. 35, JMLR.org, 2014, pp. 1135–1164
2014
Cited alongside, same era.
P. Awasthi, M. F. Balcan, and P. M. Long, The power of localization for efficiently learning linear separators with noise , STOC, 2014, pp. 449–458
2014
Cited alongside, same era.
Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan, Smoothed analysis of tensor decompositions , STOC, ACM, 2014, pp. 594–603
2014
Cited alongside, same era.
Boaz Barak, Jonathan A. Kelner, and David Steurer, Rounding sum-of-squares relaxations , STOC, ACM, 2014, pp. 31–40
2014
Cited alongside, same era.
2014
Cited alongside, same era.
Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial-time tensor decompositions with sum-of-squares , FOCS, IEEE Computer Society, 2016, pp. 438–446
2016
Later among the works it cites.
Ji Xu, Daniel J Hsu, and Arian Maleki, Global analysis of expectation maximization for mixtures of two gaussians , Advances in Neural Information Processing Systems, 2016, pp. 2676–2684
2016
Later among the works it cites.
Yeshwanth Cherapanamjeri, Prateek Jain, and Praneeth Netrapalli, Thresholding based efficient outlier robust pca , COLT, 2017
2017
Closest in time.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Being robust (in high dimensions) can be practical , ICML, 2017
2017
Closest in time.
Ilias Diakonikolas, Daniel Kane, and Alastair Stewart, personal communication, 2017
2017
Closest in time.
2017
Closest in time.
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampetakis, Ten steps of em suffice for mixtures of two gaussians , Conference on Learning Theory (2017)
2017
Closest in time.
Samuel B Hopkins, Pravesh Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures , Symposium on Foundations of Computer Science (2017)
2017
Closest in time.
Pravesh Kothari and Jacob Steinhardt, Better clustering via relaxed tensor norms , personal communication, 2017
2017
Closest in time.
Pravesh Kothari and David Steurer, Outlier-robust moment estimation via sum-of-squares , personal communication, 2017
2017
Closest in time.
Jerry Li and Ludwig Schmidt, Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities , Conference on Learning Theory, 2017
2017
Closest in time.
Dustin G Mixon, Soledad Villar, and Rachel Ward, Clustering subgaussian mixtures by semidefinite programming , Information and Inference: A Journal of the IMA (2017), iax001
2017
Closest in time.
Aaron Potechin and David Steurer, Exact tensor completion with sum-of-squares , CoRR abs/1702.06237
2017
Closest in time.
Oded Regev and Aravindan Vijayraghavan, On learning mixtures of well-separated gaussians , Symposium on Foundations of Computer Science, 2017
2017
Closest in time.
2017
Closest in time.
Jacob Steinhardt, Moses Charikar, and Gregory Valiant, Resilience: A criterion for learning in the presence of arbitrary outliers , 2017
2017
Closest in time.
Tselil Schramm and David Steurer, Fast and robust tensor decomposition with applications to dictionary learning , Conference on Learning Theory (2017)
2017
Closest in time.