Fetching the paper…
Reading the bibliography…
We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions instead about only finitely-many moments.
Karl Pearson, Liii. on lines and planes of closest fit to systems of points in space , The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 2
1901
Earlier work this paper cites.
A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization , Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, 1983
1983
Earlier work this paper cites.
Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani, Random generation of combinatorial structures from a uniform distribution , Theoretical Computer Science 43
1986
Earlier work this paper cites.
David E Tyler et al., A distribution-free m m -estimator of multivariate scatter , The annals of Statistics 15
1987
Earlier work this paper cites.
M. Ledoux and M. Talagrand, Probability in banach spaces: Isoperimetry and processes , vol. 23, Springer Science & Business Media, 1991
1991
Earlier work this paper cites.
Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization , second ed., Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. MR 1261419
1993
Earlier work this paper cites.
Jun S Liu, Siegel’s formula via stein’s identities , Statistics & Probability Letters 21
1994
Earlier work this paper cites.
Noga Alon, Yossi Matias, and Mario Szegedy, The space complexity of approximating the frequency moments , Journal of Computer and system sciences 58
1999
Earlier work this paper cites.
Noga Alon, Yossi Matias, and Mario Szegedy, The space complexity of approximating the frequency moments , J. Comput. Syst. Sci. 58
1999
Earlier work this paper cites.
Uriel Feige and Eran Ofek, Easily refutable subformulas of large random 3cnf formulas , Theory of Computing 3
2007
Earlier work this paper cites.
2011
Earlier work this paper cites.
Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , STOC, 2012, pp. 307–326
2012
Earlier work this paper cites.
Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , STOC, ACM, 2012, pp. 307–326
2012
Earlier work this paper cites.
Olivier Catoni et al., Challenging the empirical mean and empirical variance: a deviation study , Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, vol. 48, Institut Henri Poincaré, 2012, pp. 1148–1185
2012
Earlier work this paper cites.
Joel A. Tropp, User-friendly tail bounds for sums of random matrices , Foundations of Computational Mathematics 12
2012
Earlier work this paper cites.
Ryan O’Donnell, Analysis of boolean functions , Cambridge University Press, 2014
2014
Earlier work this paper cites.
Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method , STOC, ACM, 2015, pp. 143–151
2015
Earlier work this paper cites.
2015
Earlier work this paper cites.
Samuel B. Hopkins, Jonathan Shi, and David Steurer, Tensor principal component analysis via sum-of-square proofs , COLT, JMLR Workshop and Conference Proceedings, vol. 40, JMLR.org, 2015, pp. 956–1006
2015
Cited alongside, same era.
S. Minsker, Geometric median and robust estimation in Banach spaces , Bernoulli 21
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.
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.
Jianqing Fan, Yuan Liao, and Han Liu, An overview of the estimation of large covariance and precision matrices , 2016
Pravesh K Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum of squares , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 1035–1046
2018
Later among the works it cites.
Jerry Zheng Li, Principled approaches to robust machine learning and beyond , Ph.D. thesis, Massachusetts Institute of Technology, 2018
2018
Later among the works it cites.
2018
Later among the works it cites.
2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2016
Cited alongside, same era.
D. Hsu and S. Sabato, Loss minimization and parameter estimation with heavy tails , J. Mach. Learn. Res. 17
2016
Cited alongside, same era.
Daniel Hsu and Sivan Sabato, Loss minimization and parameter estimation with heavy tails , The Journal of Machine Learning Research 17
2016
Cited alongside, same era.
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
Cited alongside, same era.
Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer, Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors , Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, ACM, 2016, pp. 178–191
2016
Cited alongside, same era.
2016
Cited alongside, same era.
Kevin A. Lai, Anup B. Rao, and Santosh Vempala, Agnostic estimation of mean and covariance , FOCS, IEEE Computer Society, 2016, pp. 665–674
2016
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
Cited alongside, same era.
2018
Later among the works it cites.
Jacob Steinhardt, Robust learning: Information theory and algorithms , Ph.D. thesis, Stanford University, 2018
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, SIAM, 2019, pp. 2755–2771
2019
Closest in time.
2019
Closest in time.
2019
Closest in time.
Samuel B Hopkins, Tselil Schramm, and Jonathan Shi, A robust spectral algorithm for overcomplete tensor decomposition , Conference on Learning Theory, 2019, pp. 1683–1722
2019
Closest in time.
2019
Closest in time.
2019
Closest in time.
2019
Closest in time.
G. Lugosi and S. Mendelson, Sub-Gaussian estimators of the mean of a random vector , Ann. Statist. 47
2019
Closest in time.
2019
Closest in time.
2019
Closest in time.
Hermite polynomials , Aug 2019
2019
Closest in time.
Wikipedia contributors, Least squares— Wikipedia, the free encyclopedia , 2019, [Online; accessed 24-July-2019]
2019
Closest in time.