Near-optimal mean estimators with respect to general norms

Introduction

Formally, the problem studied in this note is as follows:

Given a norm $\|\cdot\|$, a confidence parameter $\delta\in(0,1)$ and an i.i.d. sample of cardinality $N$, find an estimator $\widehat{\mu}_{N}$ and the best possible accuracy $\varepsilon$ for which $\|\widehat{\mu}_{N}-\mu\|\leq\epsilon\ \ \ {\rm with\ probability\ at\ least\ }1-\delta~{}.$ Various versions of this question have been studied extensively in recent years, but it was far from resolved. In fact, even the correct order of the best accuracy $\epsilon$ was not clear, except in special situations. While there are some results for specific choices of norms, the only estimate that is known to be optimal was obtained in Lugosi and Mendelson for the Euclidean norm, see also Joly, Lugosi, and Oliveira and Catoni and Giulini . In addition, there are also several partial results (see Minsker , Catoni and Giulini ) for other special norms (mainly in the context of the matrix operator norm) and which are suboptimal, as we will see below.

We start by discussing what kind of accuracy $\epsilon$ one should be aiming for. To this end, first consider the case when $X$ is a real-valued random variable with finite mean $\mu$ and variance $\sigma^{2}$. Since the real-valued case is well-understood, it will eventually lead us to the possible identity of $\epsilon$ in the vector-valued scenario.

The first observation (see, e.g., Catoni ) is that if $X$ is a Gaussian random variable then the best mean estimate that one can hope for is such that, with probability $1-\delta$,

Here $c$ is an absolute constant. (In this article we focus on optimal orders of magnitude and ignore the–important–problem of optimizing constants.) If $X$ is indeed Gaussian, then the choice of $\widehat{\mu}_{N}$ is simple: the empirical mean

has the desired accuracy at all confidence levels $\delta$.

Unfortunately, this is as far as the empirical mean takes us. As soon as one leaves the sub-Gaussian realm, the empirical mean becomes a poor choice and its performance deteriorates for ‘heavy-tailed’ distributions of $X$. In fact, for all $\delta$ there are distributions in which the estimate that follows from Chebyshev’s inequality, that

is sharp. In other words, while the expected value

is of the right order of magnitude ($\sim\sigma/\sqrt{N}$), the empirical mean exhibits rather poor concentration around $\mu$.

Thus, the empirical mean has a performance comparable to the Gaussian case only in two situations:

Perhaps surprisingly, the error one incurs in these two special and restrictive situations can be attained in full generality (though obviously the estimator one uses is not the empirical mean). One estimator that attains a “sub-Gaussian” performance (i.e., an accuracy bounded by $cN^{-1/2}\sigma\sqrt{\log(2/\delta)}$ for an absolute constant $c$) for any $X$ with finite mean and variance is the median-of-means estimator. To compute this estimator, first the sample $X_{1},\ldots,X_{N}$ is split into $n$ blocks $I_{j}$, each one of the same cardinality $m$ (here we assume without loss of generality that $n$ divides $N$). For each block $I_{j}$, let

and put $\widehat{\mu}_{N}$ to be a median of $\{a_{1},\ldots,a_{n}\}$. Setting $n\sim\log(2/\delta)$, it is straightforward to verify that this choice of $\widehat{\mu}_{N}$ satisfies (1.1). This estimator was introduced independently by Nemirovsky and Yudin ; Jerrum, Valiant, and Vazirani ; and Alon, Matias, and Szegedy . Another, quite different, sub-Gaussian estimator was constructed by Catoni .

Note that unlike the empirical mean, here the procedure changes with the desired confidence. This is indeed necessary. As it is shown by Devroye, Lerasle, Lugosi, and Oliveira , there is no single procedure that attains (1.1) for all confidence levels and for all distributions with finite second moment.

While the one-dimensional picture was well understood, in higher dimensions the situation was far less clear. Unfortunately, establishing the ’right’ notion of error in higher dimensions and with respect to a general norm can be difficult, as parameters that are totally different in the multi-dimensional setup may ‘collapse’ to the same object in dimension one. However, one may still learn a lesson from the real-valued case and conclude the following:

$\bullet$ An estimator with accuracy of optimal order should depend on the prescribed confidence level and on the norm in question.

We put (1.3) in a form more convenient for us. To this end, set

where $(\varepsilon_{i})_{i=1}^{N}$ are independent, symmetric, $\{-1,1\}$-valued random variables that are also independent of $(X_{i})_{i=1}^{N}$. A standard symmetrization argument shows that

(Also observe that by the central limit theorem, $Y_{N}$ tends, in distribution, to the centred Gaussian random vector $G$ that has the same covariance as $X$).

As for (1.4), if $X$ is $L$-sub-Gaussian, then by a standard chaining argument combined with the majorizing measures theorem, one has that, with probability at least $1-\delta$,

Hence, if Question 1 has an affirmative answer, the resulting mean estimation error for the Euclidean norm would satisfy

and with probability $1-\delta$. This coincides with the performance of the empirical mean if $X$ is Gaussian (see ).

As it happens, (1.7) was established in for an arbitrary random vector $X$ (that has a well-defined mean and covariance) using the notion of median-of-means tournaments.

In Section 4 we argue that (1.6) is not far from the best (uniform) estimate one can ever hope for. For now simply observe that the term $N^{-1/2}R\sqrt{\log(2/\delta)}$ is truly required. Indeed, let $X$ be a Gaussian random vector with mean $\mu$. Observe that for any estimator $\widehat{\psi}_{N}$ and any $x^{*}\in{\cal B}^{\circ}$,

Our main result is an affirmative answer to Question 1, and the mean estimator that achieves the desired accuracy is defined as follows. The estimator depends on the desired confidence $\delta\in(0,1)$ and also on an “accuracy parameter” $\epsilon>0$. We show below that the procedure achieves accuracy $\epsilon$ whenever it is at least as large as the expression on the right-hand side on (1.6). For simplicity of presentation we assume that $n=\log(2/\delta)$ is an integer and that $N$ is divisible by $n$. (Otherwise an obvious modification only effects the value of the unspecified constants so we do not lose any generality.)

Our main result is the following—formulated using the notation introduced previously.

There exist absolute constants $c,c^{\prime}$ such that the following holds. Given a norm $\|\ \|$, confidence parameter $\delta\in(0,1)$ and sample size $N$, if

There exist absolute constants $c,c^{\prime}$ such that the following holds. Given a norm, confidence parameter $\delta\in(0,1)$ and sample size $N$, if

then the estimator $\widetilde{\mu}_{N}$ satisfies that, with probability at least $1-c^{\prime}\delta$,

Theorem 1 is established using a general fact that is of independent interest: we construct an effective uniform median-of-means estimator in a class of real valued functions, as described in the next section.

The multivariate median-of-means estimators that behave well under heavy-tailed distributions have been the subject of intensive study. Minsker and Hsu and Sabato defined and analyzed multivariate extensions of the median-of-means estimator, see also Lerasle and Oliveira . The first truly sub-Gaussian estimator (under the Euclidean norm) was shown to exist by Lugosi and Mendelson . See Joly, Lugosi, and Oliveira for an earlier attempt and Catoni and Giulini for a different estimator.

Minsker and Catoni and Giulini consider estimating the mean of random matrices based on an i.i.d. sample under the spectral norm and the Hilbert-Schmidt norm. They both prove sub-Gaussian performance bounds but the bounds of these papers fall short, in various aspects, of the optimal order of magnitude achieved by the estimator of Theorem 1 above. As far as we know, estimators achieving the accuracy/tradeoff of Theorem 1 have only been known for the Euclidean norm.

Uniform median-of-means estimators

In this section we explore the next problem:

Recall that if one would like to ensure that the median-of-means estimator performs with an error of at most $r$ for a single function $f\in F$, then it suffices that

for some $\theta>0$. Indeed, if (2.1) holds then with probability at least $1-2\exp(-c\theta^{2}n)$,

for more than $n/2$ of the blocks $I_{j}$, where $c$ is an absolute constant. However, a uniform result calls for a little more flexibility. Firstly, there is a need to have a larger number of ‘good’ blocks $I_{j}$. It suffices that for any fixed function one controls $0.9n$ of them. Clearly, that may be achieved if (2.1) holds for $1/2-\theta\leq 0.05$. With that in mind, let

From here on we write at times $p_{m}$ instead of $p_{m}(\eta)$. We set $D$ to be the unit ball in $L_{2}(\nu)$ and let ${\cal M}(F,rD)$ be the maximal cardinality of a subset of $F$ that is $r$-separated with respect to the $L_{2}(\nu)$ norm. We also denote $F-F=\{f_{1}-f_{2}:f_{1},f_{2}\in F\}$.

Let us describe the performance of the uniform median-of-means estimator:

There exist absolute constants $c_{0},\ldots,c_{4}$ for which the following holds. Set $\eta_{0},\eta_{1}$ and $\eta_{2}\geq c_{0}\eta_{1}/\sqrt{m}$ that satisfy the following:

$(2)$ $\log{\cal M}(F,\eta_{1}D)\leq c_{2}n\log(e/p_{m}(\eta_{0}))$ ;

Let $r=\eta_{0}+\eta_{2}$. Then with probability at least $1-2\exp(-c_{4}n)$, for any $f\in F$ one has that

To put Theorem 2 in some perspective, note that $\eta_{0}$ captures the worst individual error caused by a function in $F$. Moreover, as noted previously, the standard median-of-means estimator would perform with accuracy $\eta_{0}$ and confidence $1-\delta$ if

and by Chebyshev’s inequality, one may set

as one would expect from a sub-Gaussian estimate.

In contrast, the role of $\eta_{2}$ is to calibrate the impact of the ‘size’ of $F$.

In particular, $|\{j:\delta_{j}=1\}|\leq 0.1n$ with probability at least $1-2\exp(-c_{1}n\log(e/p_{m}))$.

The importance of the high-probability estimate is seen in the next step of the proof: one may control all the elements of an $\eta_{1}$-net of $F$ (with respect to the $L_{2}(\nu)$ norm) as long as its cardinality is at most $\exp(c_{2}n\log(e/p_{m}))$. Indeed, by the union bound, with probability at least $1-2\exp(-c_{3}n\log(e/p_{m}))$, for every $h$ in the net there are at least $0.9n$ blocks $I_{j}$ such that

The final and crucial step in the proof is passing from the net to the entire class: for every $f\in F$ set $\pi f$ to be the best approximation to $f$ in the net. Thus, $\|f-\pi f\|_{L_{2}}\leq\eta_{1}$. We show that for every $f\in F$ there are at most $0.2n$ blocks $I_{j}$ such that

If that is indeed the case then for every $f\in F$ there are at least $0.7n$ blocks for which

To control $S$, note that by the bounded differences inequality (see, e.g., ) there is an absolute constant $c_{1}$ such that

Hence, by standard methods of empirical processes, via an analogous argument to that in , one has

Note that if $F$ is a finite class and $\log|F|\leq c_{2}n\log(e/p_{m}(\eta_{0}))$ then $\widehat{\Phi}_{N}$ performs with accuracy $\eta_{0}$. The proof follows from the standard bound on the performance of the median-of-means estimator for each real random variable $f(X)$ and a straightforward application of the union bound.

Estimation with respect to a general norm

In this section we establish Theorem 1 by invoking Theorem 2.

where ${\rm ext}({\cal B}^{\circ})$ denotes the set of extreme points in ${\cal B}^{\circ}$, and that the empirical average within block $I_{j}$, for $1\leq j\leq n$, is denoted by

Let $r>0$ be as in Theorem 2 for the class of functions $F=\left\{x^{*}(\cdot):x^{*}\in{\rm ext}({\cal B}^{\circ})\right\}$ and with the respect to the measure $\nu$ endowed by $X-\mu$. Finally, let ${\cal A}$ be the event for which the assertion of Theorem 2 holds.

and put $\widehat{\mu}_{N}(\epsilon,\delta)$ to be any point that belongs to the set

for a majority of the indices $j$, which means that $\mu\in S_{x^{*}}$ for every $x^{*}\in{\rm ext}({\cal B}^{\circ})$.

because both conditions hold for more than half of the indices $j$. Thus,

Finally, recalling that $\|v\|=\sup_{x^{*}\in{\rm ext}({\cal B}^{\circ})}x^{*}(v)$, one has that

To complete the proof of Theorem 1 let us bound $\eta_{0}$ and $\eta_{2}$. To that end, recall that

$G$ is the centred Gaussian vector that has the same covariance as $X$, and

We show that the three conditions of Theorem 2 can be controlled when $F=\{x^{*}(\cdot):x^{*}\in{\rm ext}({\cal B}^{\circ})\}$ and with respect to the measure $\nu$ endowed by $\overline{X}=X-\mu$.

To verify $(1)$, fix $x^{*}\in{\cal B}^{\circ}$ and note that

where we have used the fact that $n=\log(2/\delta)$. (Recall that we assume, without loss of generality, that $\log(2/\delta)$ is an integer that divides $N$.) Thus, to ensure that $p_{m}\leq 0.05$ it suffices that

In particular, this forces the constraint

where $Y_{N}=N^{-1/2}\sum_{i=1}^{N}\varepsilon_{i}(X_{i}-\mu)$. Clearly, it suffices that

Note that the choices of $\eta_{0},\eta_{1}$ and $\eta_{2}$ need not be optimal for each $F$ and $\overline{X}$ as above. Indeed, $\eta_{1}$ was chosen via Sudakov’s inequality which is not always sharp, and $\eta_{2}$ was determined after the ‘localization’ $2{\cal B}^{\circ}\cap\eta_{1}D$ was replaced by $2{\cal B}^{\circ}$. Therefore, it stands to reason that there are cases in which the resulting estimate may be improved with more care. However, as we explain in the next section, Theorem 1 is likely to be the best uniform result that one can hope for.

Lower bounds

Here we show that the order of magnitude of the bound of Theorem 1 is essentially un-improvable even if one only considers isotropic Gaussian distributions, with one minor caveat. Recall that the proof of Theorem 1 uses Sudakov’s inequality to ensure that

and then the contribution to the error is $\sim\eta_{1}/\sqrt{m}=\eta_{1}\sqrt{n/N}$. As noted previously, while it is convenient to use Sudakov’s inequality, its application may be loose. A more accurate upper estimate on the error is $\sim\eta_{1}/\sqrt{m}$ where $\eta_{1}$ is the smallest value for which (4.1) holds.

We show now that if $X$ is a Gaussian measure whose covariance is the identity matrix, then this more accurate upper estimate is actually a lower bound as well.

Proof. To define the set $T$, observe that if $\log{\cal M}({\cal B}^{\circ},\eta D)\geq c_{1}n$ then by the duality theorem of metric entropy , and since $D^{\circ}=B_{2}^{d}$, it follows that $\log{\cal M}(D,c_{2}\eta{\cal B})\geq c_{3}n$. In other words, the set $D$ contains a subset that is $c_{2}\eta$-separated with respect to the norm $\|\ \|$ and whose cardinality is $c_{3}n$. Set $R=\sqrt{n/N}=1/\sqrt{m}$ and $r=c_{2}\eta/\sqrt{m}$. Clearly,

and let $T\subset RD$ be the $r$-separated set with respect to the norm $\|\ \|$.

Now, assume that there is a mean estimator that performs with confidence $1/2$ and accuracy $r/3$ for every one of the Gaussian random vector $G+t$, $t\in T$, and let as reach a contradiction.

On the other hand, the sets $U_{t}$ are disjoint and thus

which is a contradiction to our choice of $T$.

References