Sub-Gaussian estimators of the mean of a random vector

By Gábor Lugosi, Shahar Mendelson. 2017

192 citations recorded by the source corpus.

We study the problem of estimating the mean of a random vector $X$ given a sample of $N$ independent, identically distributed points. We introduce a new estimator that achieves a purely sub-Gaussian performance under the only condition that the second moment of $X$ exists. The estimator is based on a novel concept of a multivariate median.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, background): “Second, even when there are no Byzantine machines, it is known that no aggregator can achieve � = o ( � / p b ) [21], and because we achieve � = ˜ O ( / p b ) , we cannot expect to get an order of better robustness by any other aggregator.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as problems involving heavy-tailed distributions (Hsu and Sabato, 2016, Lugosi and Mendelson, 2017).”
A Theoretical Explanation for Perplexing Behaviors of Backpropagation-based Visualizations (2018, background): “From (Lugosi & Mendelson, 2017), we can set N = ˜ O ( p(cid:15) 2 ) such that with high probability ˜ w ( i,j ) − E [ ˜ w ( i,j ) ] (cid:107) (cid:15) , where p denotes the ﬁl-ter size and ˜ O ( · ) hides some other factors.”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, methodology): “We refer the readers to, for example, [18, 38, 40] and references therein for this line of research.”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, background): “Recently, Lugosi and Mendelson (2017, 2018) proposed new estimators that attains optimal bounds and requires existence of only 2 moments.”
Robust estimation via robust gradient estimation (2018, background): “From a conceptual standpoint, the classical analysis of risk-minimization which relies on uniform concentration of the empirical risk around the true risk, fails in the heavy-tailed setting necessitating new estimators and analyses [33, 34, 35, 38].”
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries (2016, unknown): “[LM17] Gábor Lugosi and Shahar Mendelson.”
Private Mean Estimation of Heavy-Tailed Distributions (2020, unknown): “A recent series of papers has focused on identifying effective methods and making them computationally efﬁcient [LM19b, Hop18, CFB19, DL19, LM19a].”
Robust multivariate mean estimation: The optimality of trimmed mean (2019, background): “The existence of such a “sub-Gaussian” estimator was established by Lugosi and Mendelson [21].”
Robust machine learning by median-of-means: Theory and practice (2017, background): “MOM estimators have been recently considered see [60, 50, 59, 61] and Section 2.2 for details.”
Regularization, sparse recovery, and median-of-means tournaments (2017, methodology): “This paper mostly builds upon the methodology of median-of-means tournaments, developed in [10], (see also Lugosi and Mendelson [11]).”