Challenging the empirical mean and empirical variance: a deviation study

By Olivier Catoni. 2010

522 citations recorded by the source corpus.

We present new M-estimators of the mean and variance of real valued random variables, based on PAC-Bayes bounds. We analyze the non-asymptotic minimax properties of the deviations of those estimators for sample distributions having either a bounded variance or a bounded variance and a bounded kurtosis. Under those weak hypotheses, allowing for heavy-tailed distributions, we show that the worst case deviations of the empirical mean are suboptimal. We prove indeed that for any confidence level, there is some M-estimator whose deviations are of the same order as the deviations of the empirical mean of a Gaussian statistical sample, even when the statistical sample is instead heavy-tailed. Experiments reveal that these new estimators perform even better than predicted by our bounds, showing deviation quantile functions uniformly lower at all probability levels than the empirical mean for non Gaussian sample distributions as simple as the mixture of two Gaussian measures.

Subfields: Management Science and Operations Research, Marketing, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f27768c792607e6187f1667f44551a0e98b79594

How researchers see this paper

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

In Management Science and Operations Research

In Marketing

In Statistics and Probability

Citations in the corpus

Robust estimation via robust gradient estimation (2018, methodology): “For the problem of one-dimensional mean estimation, Lerasle and Oliveira (2011) and Catoni (2012) proposed robust mean estimators that achieve exponential concentration around the true mean for any distribution with bounded second moment.”
Bernstein's inequalities for general Markov chains (2018, unknown): “With a slight overload of notation, we assume π has only bounded second moment such that To estimate the mean µ ∗ , the sample mean estimator ni = 1 y i / n is known to achieve at best a polynomial-type non-asymptotic conﬁdence width even in the independent case (Catoni, 2012).”
Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence (2018, background): “To give an example of such a result, a (sharp) lower bound from [1] on the mean estimation problem whenW is a gaussian random vector is the following: if |||μ̂− μ||| ≤ ε with probability at least 1− δ then ε ≥ c √ N ( E|||W − μ|||+R √ log(1/δ) )”
Simple regret for infinitely many armed bandits (2015, background): “Let log 2 be the logarithm in base 2.”
Bandit Algorithms (2020, background): “For more on the online learning approach to learning under the logarithmic loss see Chapter 9 of the book by Cesa-Bianchi and Lugosi [2006]. The Bayesian approach is covered in the book by Hutter [2004].”
An Overview on the Estimation of Large Covariance and Precision Matrices (2015, unknown): “Catoni (2012) shows that the solutions to (22) and (23) must exist and can be efficiently solved using the Newton-Raphson algorithm (Stoer et al., 1993).”
PAC-Bayesian bounds for the Gram matrix and least squares regression with a random design (2016, methodology): “the sample size, whereas A= O B means that Bbounds the order of magnitude of Ain all circumstances. 1. A robust Gram matrix estimate 1.1. Definition of a new estimator. Following the same route as in [10] in a more elaborate setting, we dene some M-estimator of N(), the energy in direction , and der”
On the properties of variational approximations of Gibbs posteriors (2015, methodology): “However, using the robust loss function of Audibert and Catoni, it is possible to relax this assumption (Audibert and Catoni, 2011; Catoni, 2012).”
Sub-Gaussian mean estimators (2015, unknown): “Catoni [5, Proposition 6.1] shows that, if δ ∈ (0 , 1) , P is reasonable and some estimator (cid:98) E n,δ achieves The same result holds for the lower tail.”
ROBUST EMPIRICAL MEAN ESTIMATORS (2011, methodology): “The main idea behind the constructions [14] is to do “soft-truncation” of the data, so as to mitigate heavy tails.”
Robust machine learning by median-of-means: Theory and practice (2017, methodology): “This program was initiated by Catoni [20] for the estimation of the mean on the real line and Audibert and Catoni [5] in the least-squares regression framework.”
Risk minimization by median-of-means tournaments (2016, unknown): “We mention here that Brownlees, Joly, and Lugosi [8] propose empirical minimization based on a diﬀerent robust mean estimator, a carefully designed M-estimator proposed by Catoni [11].”
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries (2016, background): “Assuming that n > 2t, it is shown in [Cat12] that |μ̂θ∗−μ| ≤ η with probability ≥ 1− 2e−t.”
Geometric median and robust estimation in Banach spaces (2013, background): “4) can be further improved in a situation when tight upper bounds on the true variances or kurtoses of coordinates of X are known by using a univariate estimator of [14] to construct μ̂∗.”
Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations (2015, background): “Indeed, under a heavy-tailed distribution the sample average of the loss corresponding to any ﬁxed decision x ∈ X may not even converge to the expected loss; see e.g. [13, 15].”