Fetching the paper…
Reading the bibliography…
We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than $1/2$ fraction of examples.
1903
Earlier work this paper cites.
P. Erdös, On a lemma of littlewood and offord , Bull. Amer. Math. Soc. 51
1945
Earlier work this paper cites.
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.
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.
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.
Thorsten Bernholt, Robust estimators are hard to compute , Tech. report, Technical Report/Universität Dortmund, SFB 475 Komplexitätsreduktion in Multivariaten Datenstrukturen, 2006
2006
Earlier work this paper cites.
RARD Maronna, R Douglas Martin, and Victor Yohai, Robust statistics , John Wiley & Sons, Chichester. ISBN, 2006
2006
Earlier work this paper cites.
Alexandre Eremenko and Peter Yuditskii, Uniform approximation of sgn x {\rm sgn}\,x by polynomials and entire functions , J. Anal. Math. 101
2007
Earlier work this paper cites.
Doron S Lubinsky, A Survey of Weighted Approximation for Exponential Weights , arXiv Mathematics e-prints (2007), math/0701099
2007
Earlier work this paper cites.
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala, A discriminative framework for clustering via similarity functions , STOC, ACM, 2008, pp. 671–680
2008
Earlier work this paper cites.
Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices , Adv. Math. 218
2008
Earlier work this paper cites.
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola, Bounded independence fools halfspaces , 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, 2009, pp. 171–180
2009
Earlier work this paper cites.
Adam R. Klivans, Philip M. Long, and Rocco A. Servedio, Learning halfspaces with malicious noise , Journal of Machine Learning Research 10
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
Cited alongside, same era.
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.
Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel, Robust statistics: the approach based on influence functions , vol. 114, John Wiley & Sons, 2011
2011
Cited alongside, same era.
Peter J Huber, Robust statistics , International Encyclopedia of Statistical Science, Springer, 2011, pp. 1248–1251
2011
Cited alongside, same era.
Terence Tao and Van Vu, The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi , Combinatorica 32
2012
Cited alongside, same era.
2016
Later among the works it cites.
Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar, Consistent robust regression , Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, 2017, pp. 2107–2116
2017
Later among the works it cites.
Moses Charikar, Jacob Steinhardt, and Gregory Valiant, Learning from untrusted data , STOC, ACM, 2017, pp. 47–60
2017
Later among the works it cites.
2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2013
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
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.
Boaz Barak and Ankur Moitra, Noisy tensor completion via the sum-of-squares hierarchy , COLT, JMLR Workshop and Conference Proceedings, vol. 49, JMLR.org, 2016, pp. 417–445
2016
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.
2017
Later among the works it cites.
Sam B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs , 2017
2017
Later among the works it cites.
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.
2018
Later among the works it cites.
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart, Robustly learning a gaussian: Getting optimal error, efficiently , Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, 2018, pp. 2683–2702
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, 2019, pp. 2755–2771
2019
Closest in time.
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart, Efficient algorithms and lower bounds for robust linear regression , 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. 2745–2754
2019
Closest in time.
Sushrut Karmalkar and Eric Price, Compressed sensing with adversarial sparse noise via l1 regression , SOSA@SODA (Jeremy T. Fineman and Michael Mitzenmacher, eds.), OASICS, vol. 69, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, pp. 19:1–19:19
2019
Closest in time.
Prasad Raghavendra and Morris Yau, List decodable learning via sum of squares , Manuscript, 2019
2019
Closest in time.