Fetching the paper…
Reading the bibliography…
We construct an algorithm, running in time $\tilde{\mathcal O}(N d + uK d)$, which is robust to outliers and heavy-tailed data and which achieves the subgaussian rate from [Lugosi, Mendelson] \begin{equation}\label{eq:intro_subgaus_rate} \sqrt{\frac{{\rm Tr}(\Sigma)}{N}}+\sqrt{\frac{||\Sigma||_{op}K}{N}} \end{equation}with probability at least $1-\exp(-c_0K)-\exp(-c_1 u)$ where $\Sigma$ is the covariance matrix of the informative data, $K\in\{1, \ldots, K\}$ is some parameter (number of block means) and $u>0$ is another parameter of the algorithm.
A survey of sampling from contaminated distributions
John W. Tukey · 1960
Earlier work this paper cites.
John W. Tukey · 1962
Earlier work this paper cites.
Robust estimation of a location parameter
Peter J. Huber · 1964
Earlier work this paper cites.
A general qualitative definition of robustness
Frank R. Hampel · 1971
Earlier work this paper cites.
Robust estimation: a condensed partial survey
Frank R. Hampel · 1973
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
A. S. Nemirovsky and D. B. and Yudin · 1983
Earlier work this paper cites.
Random generation of combinatorial structures from a uniform distribution
Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani · 1986
Earlier work this paper cites.
A survey of multidimensional medians
Christopher G Small · 1990
Earlier work this paper cites.
Probability in Banach spaces
Michel Ledoux and Michel Talagrand · 1991
Earlier work this paper cites.
Breakdown properties of location estimates based on halfspace depth and projected outlyingness
David L. Donoho and Miriam Gasko · 1992
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1996
Earlier work this paper cites.
Decoupling
Víctor H. de la Peña and Evarist Giné · 1999
Earlier work this paper cites.
The concentration of measure phenomenon
Michel Ledoux · 2001
Cited alongside, same era.
Robust statistics
Peter J. Huber and Elvezio M. Ronchetti · 2009
Cited alongside, same era.
Robust empirical mean estimators
M. Lerasle and R. Oliveira · 2011
Cited alongside, same era.
Challenging the empirical mean and empirical variance: A deviation study
Olivier Catoni · 2012
Cited alongside, same era.
Faster and simpler width-independent parallel algorithms for positive semidefinite programming, 2012
Richard Peng, Kanat Tangwongsan, and Peng Zhang · 2012
Cited alongside, same era.
Concentration inequalities
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart · 2013
Cited alongside, same era.
Bandits with heavy tail
Monk – outliers-robust mean embedding estimation by median-of-means
Z. Szabo M. Lerasle, T. Matthieu and G. Lecué · 2017
Later among the works it cites.
Distributed statistical estimation and rates of convergence in normal approximation
S Minsker and N. Strawn · 2017
Later among the works it cites.
Robust covariance and scatter matrix estimation under Huber’s contamination model
Mengjie Chen, Chao Gao, and Zhao Ren · 2018
Later among the works it cites.
Robustly learning a gaussian: Getting optimal error, efficiently
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2018
Later among the works it cites.
List-decodable robust mean estimation and learning mixtures of spherical Gaussians
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart · 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…
Sébastien Bubeck, Nicolò Cesa-Bianchi, and Gábor Lugosi · 2013
Cited alongside, same era.
Geometric median and robust estimation in banach spaces
Stanislav Minsker · 2015
Cited alongside, same era.
Sub-Gaussian mean estimators
Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira · 2016
Cited alongside, same era.
Robust estimators in high dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2016
Cited alongside, same era.
Robust estimators in high dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2016
Cited alongside, same era.
Dimension-free pac-bayesian bounds for matrices, vectors, and linear least squares regression
Olivier Catoni and Ilaria Giulini · 2017
Cited alongside, same era.
Samuel B Hopkins · 2018
Later among the works it cites.
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries
Stanislav Minsker · 2018
Later among the works it cites.
High-dimensional robust mean estimation in nearly-linear time
Yu Cheng, Ilias Diakonikolas, and Rong Ge · 2019
Closest in time.
Fast mean estimation with sub-gaussian rates, 2019
Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett · 2019
Closest in time.
Robust Estimators in High-Dimensions Without the Computational Intractability
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2019
Closest in time.
Efficient algorithms and lower bounds for robust linear regression
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart · 2019
Closest in time.
Sub-gaussian estimators of the mean of a random vector
Gábor Lugosi, Shahar Mendelson, et al · 2019
Closest in time.