Fetching the paper…
Reading the bibliography…
We give the first outlier-robust efficient algorithm for clustering a mixture of $k$ statistically separated d-dimensional Gaussians (k-GMMs).
M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization , Combinatorica 1
1981
Earlier work this paper cites.
N. Z. Shor, Quadratic optimization problems , Izv. Akad. Nauk SSSR Tekhn. Kibernet. (1987), no. 1, 128–139, 222. MR 939596
1987
Earlier work this paper cites.
Richard D. De Veaux, Mixtures of linear regressions , Comput. Statist. Data Anal. 8
1989
Earlier work this paper cites.
Michael I. Jordan and Robert A. Jacobs, Hierarchical mixtures of experts and the em algorithm , Neural Computation 6
1994
Earlier work this paper cites.
Sanjoy Dasgupta, Learning mixtures of gaussians , 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), IEEE, 1999, pp. 634–644
1999
Earlier work this paper cites.
Yurii Nesterov, Squared functional systems and optimization problems , High performance optimization, Appl. Optim., vol. 33, Kluwer Acad. Publ., Dordrecht, 2000, pp. 405–440. MR 1748764
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000
2000
Earlier work this paper cites.
Sanjeev Arora and Ravi Kannan, Learning mixtures of arbitrary gaussians , Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, pp. 247–257
2001
Earlier work this paper cites.
Jean B. Lasserre, New positive semidefinite relaxations for nonconvex quadratic programs , Advances in convex analysis and global optimization (Pythagorion, 2000), Nonconvex Optim. Appl., vol. 54, Kluwer Acad. Publ., Dordrecht, 2001, pp. 319–331. MR 1846160
2001
Earlier work this paper cites.
Eli Ben-Sasson, Size space tradeoffs for resolution , Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, 2002, pp. 457–464
2002
Earlier work this paper cites.
Lance Parsons, Ehtesham Haque, and Huan Liu, Subspace clustering for high dimensional data: a review , SIGKDD Explor. Newsl. 6
2004
Earlier work this paper cites.
Santosh Vempala and Grant Wang, A spectral algorithm for learning mixture models , Journal of Computer and System Sciences 68
2004
Earlier work this paper cites.
S Charles Brubaker and Santosh S Vempala, Isotropic pca and affine-invariant clustering , Building Bridges, Springer, 2008, pp. 241–281
2008
Earlier work this paper cites.
S Charles Brubaker, Robust pca and clustering in noisy mixtures , Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2009, pp. 1078–1087
2009
Earlier work this paper cites.
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola, Bounded independence fools halfspaces , Electronic Colloquium on Computational Complexity (ECCC) 16
2009
Earlier work this paper cites.
Monique Laurent, Sums of squares, moment matrices and optimization over polynomials , Emerging applications of algebraic geometry, Springer, 2009, pp. 157–270
2009
Earlier work this paper cites.
Susana Faria and Gilda Soromenho, Fitting mixtures of linear regressions , J. Stat. Comput. Simul. 80
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
Earlier work this paper cites.
R Vidal, Subspace clustering , IEEE Signal Process. Mag. 28
2011
Cited alongside, same era.
Roman Vershynin, How close is the sample covariance matrix to the actual covariance matrix? , J. Theoret. Probab. 25
2012
Cited alongside, same era.
2013
Cited alongside, same era.
2014
Cited alongside, same era.
Yudong Chen, Xinyang Yi, and Constantine Caramanis, A convex formulation for mixed regression with two components: Minimax optimal rates , Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, 2014, pp. 560–604
Pravesh K. Kothari and Jacob Steinhardt, Better agnostic clustering via relaxed tensor norms , 2017
2017
Later among the works it cites.
2017
Later among the works it cites.
2017
Later among the works it cites.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, List-decodable robust mean estimation and learning mixtures of spherical gaussians , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1047–1060
2018
Later among the works it cites.
Luc Devroye, Abbas Mehrabian, and Tommy Reddad, The total variation distance between high-dimensional gaussians , 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2014
Cited alongside, same era.
Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou, Hypercontractive inequalities via sos, and the frankl-rödl graph , SODA, SIAM, 2014, pp. 1644–1658
2014
Cited alongside, same era.
Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou, Hypercontractive inequalities via SOS, and the Frankl-Rödl graph , Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2014, pp. 1644–1658. MR 3376479
2014
Cited alongside, same era.
Ryan O’Donnell, Analysis of Boolean functions , Cambridge University Press, New York, 2014. MR 3443800
2014
Cited alongside, same era.
Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method [extended abstract] , STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 143–151. MR 3388192
2015
Cited alongside, same era.
Mikhail Belkin and Kaushik Sinha, Polynomial learning of distribution families , SIAM J. Comput. 44
2015
Cited alongside, same era.
Boaz Barak and David Steurer, Proofs, beliefs, and algorithms through the lens of sum-of-squares , 2016, Lecture notes in preparation, available on http://sumofsquares.org
2016
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
Cited alongside, same era.
2018
Later among the works it cites.
Adam R. Klivans, Pravesh K. Kothari, and Raghu Meka, Efficient algorithms for outlier-robust regression , Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, 2018, pp. 1420–1430
2018
Later among the works it cites.
Yuanzhi Li and Yingyu Liang, Learning mixtures of linear regressions with nearly optimal complexity , Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., 2018, pp. 1125–1144
2018
Later among the works it cites.
2018
Later among the works it cites.
Yu Cheng, Ilias Diakonikolas, and Rong Ge, High-dimensional robust mean estimation in nearly-linear time , Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (Timothy M. Chan, ed.), SIAM, 2019, pp. 2755–2771
2019
Later among the works it cites.
Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P. Woodruff, Faster algorithms for high-dimensional robust covariance estimation , Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA (Alina Beygelzimer and Daniel Hsu, eds.), Proceedings of Machine Learning Research, vol. 99, PMLR, 2019, pp. 727–757
2019
Later among the works it cites.
2019
Later among the works it cites.
2019
Later among the works it cites.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart, Sever: A robust meta-algorithm for stochastic optimization , Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA (Kamalika Chaudhuri and Ruslan Salakhutdinov, eds.), Proceedings of Machine Learning Research, vol. 97, PMLR, 2019, pp. 1596–1606
2019
Later among the works it cites.
Noah Fleming, Pravesh Kothari, and Toniann Pitassi, Semialgebraic proofs and efficient algorithm design , Foundations and Trends® in Theoretical Computer Science 14
2019
Later among the works it cites.
2019
Later among the works it cites.
Prasad Raghavendra and Morris Yau, List decodable learning via sum of squares , CoRR abs/1905.04660
2019
Later among the works it cites.
2020
Closest in time.
Ilias Diakonikolas, Samuel Hopkins, Daniel Kane, and Sushrut Karmalkar, Robustly learning any clusterable mixture of gaussians , Personal Communication (2020)
2020
Closest in time.