Sub-Gaussian mean estimators

Introduction

Estimating the mean of a probability distribution ${\rm P}$ on the real line based on a sample $X_{1}^{n}=(X_{1},\dots,X_{n})$ of $n$ independent and identically distributed random variables is arguably the most basic problem of statistics. While the standard empirical mean

is the most natural choice, its finite-sample performance is far from optimal when the distribution has a heavy tail.

The central limit theorem guarantees that if the $X_{i}$ have a finite second moment, this estimator has Gaussian tails, asymptotically, when $n\to\infty$. Indeed,

where $\mu_{{\rm P}}$ and $\sigma^{2}_{{\rm P}}>0$ are the mean and variance of ${\rm P}$ (respectively) and $\Phi$ is the cumulative distribution function of the standard normal distribution. This result is essentially optimal: no estimator can have better-than-Gaussian tails for all distributions in any “reasonable class” (cf. Remark 1 below).

This paper is concerned with a non-asymptotic version of the mean estimation problem. We are interested in large, non-parametric classes of distributions, such as

as well as some other classes introduced in Section 3. Given such a class $\mathcal{P}$, we would like to construct sub-Gaussian estimators. These should take an i.i.d. sample $X_{1}^{n}$ from some unknown ${\rm P}\in\mathcal{P}$ and produce an estimate $\widehat{E}_{n}(X_{1}^{n})$ of $\mu_{{\rm P}}$ that satisfies

for some constant $L>0$ that depends only on $\mathcal{P}$. One would like to keep $\delta_{\min}$ as small as possible (say exponentially small in $n$).

Of course, when $n\to\infty$ with $\delta$ fixed, (5) is a weaker form of (1) since $\Phi^{-1}(1-\delta/2)\leq\sqrt{2\ln(2/\delta)}$. The point is that (5) should hold non-asymptotically, for extremely small $\delta$, and uniformly over ${\rm P}\in\mathcal{P}$, even for classes $\mathcal{P}$ containing distributions with heavy tails. The empirical mean cannot satisfy this property unless either $\mathcal{P}$ contains only sub-Gaussian distributions or $\delta_{min}$ is quite large (cf. Section 2.3.1), so designing sub-Gaussian estimators with the kind of guarantee we look for is a non-trivial task.

In this paper we prove that, for most (but not all) classes $\mathcal{P}\subset\mathcal{P}_{2}$ we consider, there do exist estimators that achieve (5) for all large $n$, with $\delta_{\min}\approx e^{-c_{\mathcal{P}}\,n}$ and a value of $L$ that does not depend on $\delta$ or $n$. In each case, $c_{\mathcal{P}}>0$ is a constant that depends on the class $\mathcal{P}$ under consideration, and we also obtain nearly tight bounds on how $c_{\mathcal{P}}$ must depend on $\mathcal{P}$. (In particular, $\delta_{\min}$ cannot be superexponentially small in $n$.) In the specific case of bounded-kurtosis distributions (cf. (4) above), we achieve $L\leq\sqrt{2}+\epsilon$ for $\delta_{\min}\approx e^{-o\left((n/\kappa)^{2/3}\right)}$. This value of $L$ is nearly optimal by Remark 1 below.

Before this paper, it was known that (5) could be achieved for the whole class $\mathcal{P}_{2}$ of distributions with finite second moments, with a weaker notion of estimator that we call $\delta$-dependent estimator, that is, an estimator $\widehat{E}_{n}=\widehat{E}_{n,\delta}$ that may also depend on the confidence parameter $\delta$. By contrast, the estimators that we introduce here are called multiple-$\delta$ estimators: a single estimator works for the whole range of $\delta\in[\delta_{\min},1)$. This distinction is made formal in Definition 1 below. By way of comparison, we also prove some results on $\delta$-dependent estimators in the paper. In particular, we show that the distinction is substantial. For instance, there are no multiple-$\delta$ sub-Gaussian estimators for the full class $\mathcal{P}_{2}$ for any nontrivial range of $\delta_{\min}$. Interestingly, multiple-$\delta$ estimators do exist (with $\delta_{\min}\approx e^{-c\,n}$) for the class $\mathcal{P}_{2}^{\sigma^{2}}$ (corresponding to fixed variance). In fact, this is true when the variance is “known up to constants,” but not otherwise.

This result not only shows that one cannot expect sub-Gaussian confidence intervals for classes that contain distributions of infinite variance but also that in such cases it is impossible to have confidence intervals whose length scales as $n^{-1/2}$.

Weakly sub-Gaussian estimators

Consider the class $\mathcal{P}^{\text{Ber}}$ of all Bernoulli distributions, that is, the class that contains all distributions $P$ of the form

Perhaps surprisingly, no multiple-$\delta$ estimator exists for this class of distributions, even when $\delta_{\min}$ is a constant. (We do not explicitly prove this here but it is easy to deduce it using the techniques of Sections 4.3 and 4.5.) On the other hand, by standard tail bounds for the binomial distribution (e.g., by Hoeffding’s inequality), the standard empirical mean satisfies, for all $\delta>0$ and $P\in\mathcal{P}^{\text{Ber}}$,

Of course, this bound has a sub-Gaussian flavor as it resembles (5) except that the confidence bounds do not scale by $\sigma_{{\rm P}}(\log(1/\delta)/n)^{1/2}$ but rather by a distribution-free constant times $(\log(1/\delta)/n)^{1/2}$.

In general, we may call an estimate weakly sub-Gaussian with respect to the class $\mathcal{P}$ if there exists a constant $\overline{\sigma}_{\mathcal{P}}$ such that for all ${\rm P}\in\mathcal{P}$,

for some constant $L>0$. $\delta$-dependent and multiple-$\delta$ versions of this definition may be given in analogy to those of sub-Gaussian estimators.

Note that if a class $\mathcal{P}$ is such that $\sup_{{\rm P}\in\mathcal{P}}\sigma_{{\rm P}}<\infty$, then any sub-Gaussian estimator is weakly sub-Gaussian. However, for classes of distributions without uniformly bounded variance, this is not necessarily the case and the two notions are incomparable.

In this paper we focus on the notion of sub-Gaussian estimators and we do not pursue further the characterization of the existence of weakly sub-Gaussian estimators.

1 Related work

To our knowledge, the explicit distinction between $\delta$-dependent and multiple-$\delta$ estimators, and our construction of multiple-$\delta$ sub-Gaussian estimators for exponentially small $\delta$, are all new. On the other hand, constructions of $\delta$-dependent estimators are implicit in older work on stochastic optimization of Nemirovsky and Yudin (see also Levin and Hsu ), sampling from large discrete structures by Jerrum, Valiant, and Vazirani , and sketching algorithms, see Alon, Matias, and Szegedy . Recently, there has been a surge of interest in sub-Gaussian estimators, their generalizations to multivariate settings, and their applications in a variety of statistical learning problems where heavy-tailed distributions may be present, see, for example, Catoni , Hsu and Sabato , Brownlees, Joly, and Lugosi , Lerasle and Oliveira , Minsker , Audibert and Catoni , Bubeck, Cesa-Bianchi, and Lugosi . Most of these papers use $\delta$-dependent sub-Gaussian estimators. Catoni’s paper is close in spirit to ours, as it focuses on sub-Gaussian mean estimation as a fundamental problem. That paper presents $\delta$-dependent sub-Gaussian estimators with nearly optimal $L=\sqrt{2}+o\left(1\right)$ for a wide range of $\delta$ and the classes $\mathcal{P}_{2}^{\sigma^{2}}$ and $\mathcal{P}_{{\rm krt}\leq\kappa}$ defined in (3). The $\delta$-dependent sub-Gaussian estimator introduced by may be converted into a multiple-$\delta$ estimators with subexponential (instead of sub-Gaussian) tails for $\mathcal{P}_{2}^{\sigma^{2}}$ by choosing the single parameter of the estimator appropriately. Loosely speaking, this corresponds to squaring the term $\ln(1/\delta)$ in (5). Catoni also obtains multiple-$\delta$ estimators for $\mathcal{P}_{2}$ with subexponential tails. These ideas are strongly related to Audibert and Catoni’s paper on robust least-squares linear regression .

2 Main proof ideas

The negative results we prove in this paper are minimax lower bounds for simple families of distributions such as scaled Bernoulli distributions (Theorem 3.1), Laplace distributions with fixed scale parameter for $\delta$-dependent (Theorem 4.3), and the Poisson family for multiple-$\delta$ estimators (Theorem 4.4). The main point about the latter choices is that it is easy to compare the probabilities of events when one changes the values of the parameter. Interestingly, Catoni’s lower bounds in also follow from a one dimensional family (in that case, Gaussians with fixed variance $\sigma^{2}>0$).

Our constructions of estimators use two main ideas. The first one is that, while one cannot turn $\delta$-dependent into multiple-$\delta$ estimators, one can build multiple-$\delta$ estimators from the slightly stronger concept of sub-Gaussian confidence intervals. That is, if for each $\delta>0$ one can find an empirical confidence interval for $\mu_{{\rm P}}$ with “sub-Gaussian length”, one may combine these intervals to produce a single multiple-$\delta$ estimator. This general construction is presented in Section 4.2 and is related at a high level to Lepskii’s adaptation method .

Although general, this method of confidence intervals loses constant factors. Our second idea for building estimators, which is specific to the bounded kurtosis case (see Theorem 3.6 below), is to use a data-driven truncation mechanism to make the empirical mean better behaved. By using preliminary estimators of the mean and variance, we truncate the random variables in the sample and obtain a Bennett-type concentration inequality with sharp constant $L=\sqrt{2}+o\left(1\right)$. A crucial point in this analysis is to show that our truncation mechanism is fairly insensitive to the preliminary estimators being used.

3 Organization.

The remainder of the paper is organized as follows. Section 2 fixes notation, formally defines our problem, and discusses previous work in light of our definition. Section 3 states our main results. Several general methods that we use throughout the paper are collected in Section 4. Proofs of the main results are given in Sections 5 to 7. Section 8 discusses several open problems.

Preliminaries

denote the integral of $f$ with respect to $X$. Assuming ${\rm P}\,X^{2}<\infty$, we use the symbols $\mu_{{\rm P}}={\rm P}\,X$ and $\sigma^{2}_{{\rm P}}={\rm P}\,X^{2}-\mu^{2}_{{\rm P}}$ for the mean and variance of ${\rm P}$.

We write $\widehat{\rm P}_{n}$ instead of $\widehat{\rm P}_{[n]}$ for simplicity.

2 The sub-Gaussian mean estimation problem

In this section, we begin a more formal discussion of the main problem in this paper. We start with the definition of a sub-Gaussian estimator of the mean.

We also write $\widehat{E}_{n,\delta}(\cdot)$ for $\widehat{E}_{n}(\cdot,\delta)$.

It transpires from these definitions that multiple-$\delta$ estimators are preferable whenever they are available, because they combine good typical behavior with nearly optimal bounds under extremely rare events. By contrast, the need to commit to a $\delta$ in advance means that $\delta$-dependent estimators may be too pessimistic when a small $\delta$ is desired. The main problem addressed in this paper is the following:

Given a family $\mathcal{P}$ (or more generally a sequence of families $\mathcal{P}_{n}$), find the smallest possible sequence $\delta_{\min}=\delta_{\min,n}$ such that multiple-$\delta$ $L$-sub-Gaussian estimators for $(\mathcal{P},n,\delta_{\min,n})$ (resp. $(\mathcal{P}_{n},n,\delta_{\min,n})$) exist for all large $n$, and with a constant $L$ that does not depend on $n$.

(optimality of sub-gaussian estimators.) Call a class $\mathcal{P}$ “reasonable” when it contains all Gaussian distributions with a given variance $\sigma^{2}>0$. Catoni [5, Proposition 6.1] shows that, if $\delta\in(0,1)$, $\mathcal{P}$ is reasonable and some estimator $\widehat{E}_{n,\delta}$ achieves

then $r\geq\Phi^{-1}(1-\delta)$. The same result holds for the lower tail. Since $\Phi^{-1}(1-\delta)\sim\sqrt{2\ln(1/\delta)}$ for small $\delta$, this means that, for any reasonable class $\mathcal{P}$, no constant $L<\sqrt{2}$ is achievable for small $\delta_{\min}$, and no better dependence on $n$ or $\delta$ is possible. In particular, sub-Gaussian estimators are optimal up to constants, and estimators with $L\leq\sqrt{2}+o(1)$ are “nearly optimal.”

3 Known examples from previous work

In what follows we present some known estimators of the mean and discuss their sub-Gaussian properties (or lack thereof).

For large $n$, $\sigma^{2}>0$ fixed and $\delta_{\min}\to 0$, the empirical mean

is not a $L$-sub-Gaussian estimator for the class $\mathcal{P}^{\sigma^{2}}_{2}$ of all distibutions with variance $\sigma^{2}$. This is a consequence of [5, Proposition 6.2], which shows that the deviation bound obtained from Chebyshev’s inequality is essentially sharp.

Things change under slightly stronger assumptions. For example, a nonuniform version of the Berry-Esséen theorem ([15, Theorem 14, p. 125]) implies that, for large $n$, $\widehat{\sf emp}_{n}$ is a multiple-$\delta$ $\left(\sqrt{2}+\epsilon\right)$-sub-Gaussian estimator for $(\mathcal{P}_{3,\eta},n,\delta_{\min,n})$, where

for some $\eta>1)$ and $\delta_{\min,n}\gg n^{-1/2}(\log n)^{-3/2}$. Similar results (with worse constants) hold for the class $\mathcal{P}_{{\rm krt}\leq\kappa}$ (cf. (4)) when $\delta_{\min}\gg 1/n$ and $\kappa$ is bounded [5, Proposition 5.1]. Catoni [5, Proposition 6.3] shows that the sub-Gaussian property breaks down when $\delta_{\min}=o\left(1/n\right)$. Exponentially small $\delta_{\min}$ can be achieved under much stronger assumptions. For example, Bennett’s inequality implies that $\widehat{\sf emp}_{n}$ is $\left(\sqrt{2}+\epsilon\right)$-sub-Gaussian for the triple $(\mathcal{P}_{\infty,\eta},n,\delta_{\min})$, with $\delta_{\min}=e^{-\epsilon^{2}n/\eta^{2}}$ and

3.2 Median of means

Quite remarkably, as it has been known for some time, one can do much better than the empirical mean in the $\delta$-dependent setting. The so-called median of means construction gives $L$-sub-Gaussian estimators $\widehat{E}_{n,\delta}$ (with $L$ some constant) for any triple $(\mathcal{P}_{2},n,e^{1-n/2})$ where $n\geq 6$. The basic idea is to partition the data into disjoint blocks, calculate the empirical mean within each block, and finally take the median of them. This construction with a basic performance bound is reviewed in Section 4.1, as it provides a building block and an inspiration for the new constructions in this paper. We emphasize that, as pointed out in the introduction, variants of this result have been known for a long time, see Nemirovsky and Yudin , Levin , Jerrum, Valiant, and Vazirani , and Alon, Matias, and Szegedy . Note that this estimator has good performance even for distributions with infinite variance (see the remark following Theorem 3.1 below).

3.3 Catoni’s estimators

The constant $L$ obtained by the median-of-means estimator is larger than the optimal value $\sqrt{2}$ (see Remark 1). Catoni designs $\delta$-dependent sub-Gaussian estimators with nearly optimal $L=\sqrt{2}+o(1)$ for the classes $\mathcal{P}_{2}^{\sigma^{2}}$ (known variance) and $\mathcal{P}_{{\rm krt}\leq\kappa}$ (bounded kurtosis). A variant of Catoni’s estimator is a multiple-$\delta$ estimator, however with subexponential instead of sub-Gaussian tails (i.e., the $\sqrt{\ln(1/\delta)}$ term in (7) appears squared). Both estimators work for exponentially small $\delta$, although the constant in the exponent for $\mathcal{P}_{{\rm krt}\leq\kappa}$ depends on $\kappa$.

Main results

Here we present the main results of the paper. Proofs are deferred to Sections 4 to 7.

Let $n>5$ be a positive integer, $M>0$, $\alpha\in(0,1]$, and $\delta\in(2e^{-n/4},1/2)$. Then for any mean estimator $\widehat{E}_{n}$,

The proof is given in Section 4.3. The bound of the theorem is essentially tight. It is shown in Bubeck, Cesa-Bianchi, and Lugosi that for each $M>0$, $\alpha\in(0,1]$, and $\delta$, there exists an estimator $\widehat{E}_{n}(X_{1}^{n},\delta)$ such that

The estimator $\widehat{E}_{n}(X_{1}^{n},\delta)$ satisfying this bound is the median-of-means estimator with appropriately chosen parameters.

It is an interesting question whether multiple-$\delta$ estimators exist with similar performance. Since our primary goal in this paper is the study of sub-Gaussian estimators, we do not pursue the case of infinite variance further.

2 The value of knowing the variance

Given $0<\sigma_{1}\leq\sigma_{2}<\infty$, define the class of distributions with variance between $\sigma_{1}^{2}$ and $\sigma_{2}^{2}$:

This class interpolates between the classes of distributions with fixed variance $\mathcal{P}^{\sigma^{2}}_{2}$ and with completely unknown variance $\mathcal{P}_{2}$. The next theorem is proven in Section 5.

Let $0<\sigma_{1}<\sigma_{2}<\infty$ and define $R=\sigma_{2}/\sigma_{1}$.

Letting $L^{(1)}=(4e\sqrt{2+4\ln 2})R$ and $\delta^{(1)}_{\min}=4e^{1-n/2}$, for every $n\geq 6$ there exists a multiple-$\delta$ $L^{(1)}$-sub-Gaussian estimator for $(\mathcal{P}_{2}^{[\sigma^{2}_{1},\sigma^{2}_{2}]},n,\delta^{(1)}_{\min})$.

For any $L\geq\sqrt{2}$, there exist $\phi^{(2)}>0$ and $\delta^{(2)}_{\min}>0$ such that, when $R>\phi^{(2)}$, there is no multiple-$\delta$ $L$-sub-Gaussian estimator for $(\mathcal{P}_{2}^{[\sigma^{2}_{1},\sigma^{2}_{2}]},n,\delta^{(2)}_{\min})$ for any $n$.

For any value of $R\geq 1$ and $L\geq\sqrt{2}$, if we let $\delta_{\min}^{(3)}=e^{1-5L^{2}n}$, there is no $\delta$-dependent $L$-sub-Gaussian estimator for $(\mathcal{P}_{2}^{[\sigma^{2}_{1},\sigma^{2}_{2}]},n,\delta^{(3)}_{\min})$ for any $n$.

It is instructive to consider this result when $n$ grows and $R=R_{n}$ may change with $n$. The theorem says that, when $\sup_{n}R_{n}<\infty$, there are multiple-$\delta$ $L$-sub-Gaussian estimators for all large $n$, with exponentially small $\delta_{\min}$ and a constant $L$. On the other hand, if $R_{n}\to\infty$, for any constant $L$ and all large $n$, no multiple-$\delta$ $L$-sub-Gaussian estimators exist for any sequence $\delta=\delta_{\min,n}\to 0$. Finally, the third item says that even when $R_{n}\equiv 1$, $\delta$-dependent estimators are limited to $\delta_{\min}=e^{-O\left(n\right)}$, so the median-of-means estimator is optimal in this sense.

3 Regularity, symmetry and higher moments

Theorem 3.2 shows that finite, but completely unknown variance is too weak an assumption for multiple-$\delta$ sub-Gaussian estimation. The following shows that what we call regularity conditions can substitute for knowledge of the variance.

We say that a distribution ${\rm P}\in\mathcal{P}_{\rm 2}$ is symmetric around the mean if, given $X=_{d}{\rm P}$, $2\mu_{{\rm P}}-X=_{d}{\rm P}$ as well. Clearly, if ${\rm P}$ has this property, $p_{+}({\rm P},j)=p_{-}({\rm P},j)=1/2$ for all $j$ and thus ${\rm P}\in\mathcal{P}_{{\rm 2},1{\rm-reg}}$. In other words, $\mathcal{P}_{2,{\rm sym}}\subset\mathcal{P}_{2,1{\rm-reg}}$ where $\mathcal{P}_{2,{\rm sym}}$ is the class of all ${\rm P}\in\mathcal{P}_{2}$ that are symmetric around the mean.

Given $\eta\geq 1$ and $\alpha\in(2,3]$, set

We show in Lemma 6.2 that, for ${\rm P}$ in this family, $\min(p_{+}({\rm P},j),p_{-}({\rm P},j))\geq 1/3$ once $j\geq(C_{\alpha}\,\eta)^{\frac{2\alpha}{\alpha-2}}$ for a constant $C_{\alpha}$ depending only on $\alpha$. We deduce

Our main result about $k$-regular classes states that sub-Gaussian multiple-$\delta$ estimators exist for $\mathcal{P}_{2,k-{\rm reg}}$ in the sense of the following theorem, proven in Section 6.1.

Let $n,k$ be positive integers with $n\geq(3+\ln 4)\,124k$. Set $\delta_{\min,n,k}=4e^{3-n/(124k)}$ and $L_{*}=4\sqrt{2\,(1+2\ln 2)\,(1+62\ln(3))}\,e^{\frac{5}{2}}$. Then there exists a $L_{*}$-sub-Gaussian multiple-$\delta$ estimator for $(\mathcal{P}_{2,k-{\rm reg}},n,\delta_{\min,n,k})$.

We also show that the range of $\delta_{\min}=e^{-O\left(n/k\right)}$ in this result is optimal. This follows directly from stronger results that we prove for Examples 3.1 and 3.2. In other words, the general family of estimators designed for $k$-regular classes has nearly optimal range of $\delta$ for these two smaller classes. The next result, for symmetric distributions, is proven in Section 6.2.

Consider the class $\mathcal{P}_{2,{\rm sym}}$ defined in Example 3.1. Then

the estimator obtained in Theorem 3.3 for $k=1$ is a $L_{*}$-sub-Gaussian multiple-$\delta$ estimator for $(\mathcal{P}_{2,{\rm sym}},n,\delta_{\min,n,1})$ when $n\geq(3+\ln 2)\,124$;

on the other hand, for any $L\geq\sqrt{2}$, no $\delta$-dependent $L$-sub-Gaussian estimator can exist for $(\mathcal{P}_{2,{\rm sym}},n,e^{1-5L^{2}n})$.

We also have an analogue result for the class $\mathcal{P}_{\alpha,\eta}$. The proof may be found in Section 6.3.

Fix $\alpha\in(2,3]$ and assume $\eta\geq 3^{1/3}\,2^{1/6}$. Consider the class $\mathcal{P}_{\alpha,\eta}$ defined in Example 3.2. Then there exists some $C_{\alpha}>0$ depending only on $\alpha$ such that if $k_{\alpha}=\lceil C_{\alpha}\,\eta^{(2\alpha)/(\alpha-2)}\rceil$,

the estimator obtained in Theorem 3.3 for $k=k_{\alpha}$ is a $L_{*}$-sub-Gaussian multiple-$\delta$ estimator for $(\mathcal{P}_{\alpha,\eta},n,\delta_{\min,n,k_{\alpha}})$ when $n\geq(3+\ln 4)\,124k_{\alpha}$;

finally, for $L\geq\sqrt{2}$ there is no $\delta$-dependent $L$ sub-Gaussian estimator for $(\mathcal{P}_{\alpha,\eta},n,e^{1-5L^{2}n})$.

4 Bounded kurtosis and nearly optimal constants

This section shows that multiple-$\delta$ sub-Gaussian estimation with nearly optimal constants can be proved when the kurtosis

(when $X=_{d}{\rm P}$) is uniformly bounded in the class. (For completeness, we set $\kappa_{{\rm P}}=1$ when $\sigma^{2}_{{\rm P}}=0$.) More specifically, we will consider the class $\mathcal{P}_{{\rm krt}\leq\kappa}$ of all distributions ${\rm P}\in\mathcal{P}_{2}$ with $\kappa_{{\rm P}}\leq\kappa$.

To state the result, let $b_{\max}$ be a positive integer to be specified below. Also define

Note that when $b_{\max}\ll(n/\kappa)^{2/3}$, $\xi=o(1)$. The main result for classes of distributions with bounded kurtosis is the following. For the proof see Section 7.

Let $n\geq 4$, $L=\sqrt{2}(1+\xi)$, $\delta_{\min}^{(4)}=\frac{4e}{e-2}e^{-b_{\max}}$. There exists an absolute constant $C$ such that, if $\kappa b_{\max}/n\leq C$, then there exists a multiple-$\delta$ $L$-sub-Gaussian estimator for $(\mathcal{P}_{4}^{\kappa},n,\delta_{\min}^{(4)})$.

This result is most interesting in the regime where $n\to\infty$, $\kappa=\kappa_{n}$ possibly depends on $n$ and $n/\kappa_{n}\to\infty$. In this case, we may take $b_{\max}\ll(n/\kappa_{n})^{2/3}$ and obtain multiple-$\delta$ $\left(\sqrt{2}+o\left(1\right)\right)$-sub-Gaussian estimators $(\mathcal{P}_{{\rm krt}\leq\kappa},n,\delta^{(4)}_{\min})$ for $\delta^{(4)}_{\min}\approx e^{-b_{\max}}$. Catoni obtained $\delta$-dependent $\sqrt{2}+o\left(1\right)$-estimators for a smaller value $\delta^{(5)}_{\min}\approx e^{-n/\kappa}$. In Remark 2 we show how one can obtain a similar range of $\delta$ with a multiple-$\delta$ estimator, albeit with worse constant $L$.

General methods

We collect here some ideas that recur in the remainder of the paper.

Section 4.1 presents an analysis of the median-of-means estimator mentioned in Section 2.3.2 above. We present a proof based on Hsu’s argument .

Section 4.2 presents a “black-box method” of deriving multiple-$\delta$ estimators from confidence intervals. The point is that confidence intervals are “$\delta$-dependent objects”, and thus easier to design and analyze.

In Section 4.3 we use scaled Bernoulli distributions to prove the impossibility of designing (weakly) sub-Gaussian estimators for classes with distributions with unbounded variance.

Section 4.4 uses the family of Laplace distributions to lower bound $\delta_{\min}$ for $\delta$-dependent estimators.

Section 4.5 uses the Poisson family to derive lower bounds on $\delta_{\min}$ for multiple-$\delta$ estimators.

A combination of the above results will allow us to derive the sharp range for $\ln(1/\delta_{\min})$ for all families of distributions we consider.

The next result is a well known performance bound for the median-of-means estimator. We include the proof for completeness.

For any $n\geq 4$ and $L=2\sqrt{2}\,e$ there exists a $\delta$-dependent $L$-sub-Gaussian estimators for $(\mathcal{P}_{\rm 2},n,e^{1-n/2}).$

(If several $i$ fit the above description, we take the smallest one.) We need the following Lemma (proven subsequently):

In our case we set $L_{0}=e=L/2\sqrt{2}$. To build our estimator for a given $\delta\in[e^{1-n/2},1)$, we first choose

and define the median-of-means estimator by $\widehat{E}_{n,\delta}(x_{1}^{n})=q_{1/2}(y_{n,\delta}(x_{1}^{n})).$

We now show that $\widehat{E}_{n,\delta}$ is a sub-Gaussian estimator for the class $\mathcal{P}_{2}$. Let $X_{1}^{n}=_{d}{\rm P}^{\otimes n}$ for a distribution ${\rm P}\in\mathcal{P}_{2}$. $\widehat{E}_{n,\delta}(X_{1}^{n})$ is the median of random variables

Each $Y_{i}$ has mean $\mu_{{\rm P}}$ and variance $\sigma^{2}_{{\rm P}}/\#B_{i}\leq\sigma^{2}_{{\rm P}}/k$. Then, using our choice of $b$, Lemma 4.1 implies

Now, because $b=\lceil\ln(1/\delta)\rceil\leq n/2$

and since this works for any ${\rm P}\in\mathcal{P}_{\rm 2}$, the proof is complete. $\Box$

Proof of Lemma 4.1: Let $I=[\mu-2\,L_{0}\,\sigma,\mu+2\,L_{0}\sigma]$. Clearly,

The indicators variables on the right-hand side are all independent, and by Chebyshev’s inequality, for all $j\in[b]$,

since $\sum_{k=\lceil b/2\rceil}^{b}\binom{b}{k}\leq\sum_{k=0}^{b}\binom{b}{k}=2^{b}$.

2 The method of confidence intervals for multiple-δ𝛿\delta estimators

In this section we detail how sub-Gaussian confidence intervals may be combined to produce multiple-$\delta$ estimators. This will be our main tool in defining all multiple-$\delta$ estimators whose existence is claimed in Theorems 3.2 and 3.3. First we need a definition.

The next theorem shows how one can combine sub-Gaussian confidence intervals to obtain a multiple-$\delta$ sub-Gaussian mean estimator.

so it makes sense to define the estimator $\widehat{E}_{n}(x_{1}^{n})$ as its midpoint.

We claim that $\widehat{E}_{n}$ is the sub-Gaussian estimator we are looking for. To prove this, we let $2^{-m}\leq\delta\leq 1$ and choose the smallest $k\in\{1,2,\dots,m+1\}$ with $2^{1-k}\leq\delta$. Assume $X_{1}^{n}=_{d}{\rm P}^{\otimes n}$ with ${\rm P}\in\mathcal{P}$. Then

When $\bigcap_{j=k}^{m}\mathcal{G}_{j}$ holds, $\mu_{{\rm P}}\in\widehat{I}_{j}(X_{1}^{n})$ for all $k\leq j\leq m+1$, so $\mu_{{\rm P}}\in\bigcap_{j=k}^{m+1}\widehat{I}_{j}(X_{1}^{n})$. In particular, $\bigcap_{j=k}^{m}\widehat{I}_{j}(X_{1}^{n})\neq\emptyset$ and $\hat{k}_{n}(X_{1}^{n})\leq k$.

Finally, our choice of $k$ implies $2^{1-k}\leq\delta\leq 2^{2-k}$, so, under $\bigcap_{j=k}^{m}\mathcal{G}_{j}$ we have

with $L^{\prime}=L\sqrt{1+2\ln 2}$ as in the statement of the theorem.

and since this holds for all ${\rm P}\in\mathcal{P}$ and all $2^{-m}\leq\delta\leq 1/2$, the proof is complete. $\Box$

3 Scaled Bernoulli distributions and single-δ𝛿\delta estimators

In this subsection we prove Theorem 3.1. In order to do so, we derive a simple minimax lower bound for single-$\delta$ estimators for the class $\mathcal{P}_{c,p}=\{P_{+},P_{-}\}$ of distributions that contains two discrete distributions defined by

where $p\in$ and $c>0$. Note that $\mu_{P_{+}}=pc$, $\mu_{P_{-}}=-pc$ and that for any $\alpha>0$, the $(1+\alpha)$-th central moment of both distributions equals

For $i=1,\ldots,n$, let $(X_{i},Y_{i})$ be independent pairs of real-valued random variables such that

Note that $X_{i}\stackrel{{\scriptstyle\cal L}}{{\sim}}P_{+}$ and $Y_{i}\stackrel{{\scriptstyle\cal L}}{{\sim}}P_{-}$. Let $\delta\in(0,1/2)$. If $\delta\geq 2e^{-n/4}$ and $p=(2/n)\log(2/\delta)$, then (using $1-p\geq\exp(-p/(1-p))$),

Let $\widehat{E}_{n,\delta}$ be any mean estimator, possibly depending on $\delta$. Then

From (10) we have that $cp\geq M^{1/(1+\alpha)}(p/2)^{\alpha/(1+\alpha)}$ and therefore

Theorem 3.1 simply follows by noting that $\mathcal{P}_{c,p}\subset\mathcal{P}^{M}_{1+\alpha}$.

4 Laplace distributions and single-δ𝛿\delta estimators

The next result proves that $\delta$-dependent $L$-sub-Gaussian estimators are limited to exponentially small $\delta$ even over the one-dimensional family $\mathcal{P}_{{\sf La}}$.

If $n\geq 3$ then, for any constant $L\geq\sqrt{2}$, there are no $\delta$-dependent $L$-sub-Gaussian estimators for $(\mathcal{P}_{{\sf La}},n,e^{1-5L^{2}n})$.

Proof: We proceed by contradiction, assuming that there exist $L$-sub-Gaussian $\delta$-dependent estimators $\widehat{E}_{n,\delta}$ for $(\mathcal{P}_{{\sf La}},n,\delta)$ where $\delta=e^{1-5L^{2}n}$ and arbitrarily large $n$. We set

Using the definition of $\lambda$ and the fact that $\mu_{{\sf La}_{\lambda}}=\lambda$ and $\sigma^{2}_{{\sf La}_{\lambda}}=2$, we see that the right-hand side above is simply

On the other hand, the left-hand side in (11) is

If we use again the definition of $\lambda$, we see that

For $L\geq\sqrt{2}$, some simple estimates show that this leads to a contradiction when $n\geq 3$. $\Box$

5 Poisson distributions and multiple-δ𝛿\delta estimators

We use the family of Poisson distributions for bounding the range of confidence values of multiple-$\delta$ estimators. Denote by ${\sf Po}_{\lambda}$ the Poisson distribution with parameter $\lambda>0$. Given $0<\lambda_{1}\leq\lambda_{2}<\infty$, define

Proof: We prove the following stronger result: there exist constants $c_{0},s>0$ such that, when $c\geq c_{0}$, $L\geq\sqrt{2}$ and $C=\lceil s\,(L^{2}\ln L)\rceil$, there is no multiple-$\delta$ sub-Gaussian estimator for

The theorem then follows by taking $2C=\phi(L)-1=s\,L^{2}\ln L$ and $s_{0}=s^{2}$.

$\mu_{{\sf Po}_{c/n}}=\sigma^{2}_{{\sf Po}_{c/n}}=c/n$ and $\mu_{{\sf Po}_{(1+2C)c/n}}=\sigma^{2}_{{\sf Po}_{(1+2C)c/n}}=(1+2C)c/n$.

$S_{X}=X_{1}+X_{2}+\dots+X_{n}=_{d}{\sf Po}_{c}$ and $S_{Y}=Y_{1}+Y_{2}+\dots+Y_{n}=_{d}{\sf Po}_{(1+2C)\,c}$.

We apply the sub-Gaussian property for the triple ($\star$) to $\delta=1/4\sqrt{(1+2C)\,c}$. This is possible because, for $C=\lceil s\,(L^{2}\ln L)\rceil$ with a large enough $s$, this value is $\approx 1/L\sqrt{s\ln L\,c}$, which is much larger than the minimum confidence parameter $e^{1-C^{2}\,c/L^{2}}$ allowed by ($\star$) (at least if $c\geq c_{0}$ with a large enough $c_{0}$). Recalling F0, we obtain

Now F1 implies that the left-hand side is the same if we switch from $Y$ to $X$. In particular, by looking at the complementary event we obtain

Since we are taking $c\geq c_{0}$ and $C\geq s\,L^{2}\,\ln L$, a calculation reveals

Therefore, by taking a large enough $c_{0}$ we can ensure that

We now use F0 to rewrite the previous probability as

Since we assumed $\widehat{E}_{n}$ is $L$-sub-Gaussian for the triple ($\star$), we obtain

Comparing the left and right hand sides, and recalling $c\geq c_{0}$, we obtain $h(C)\geq C^{2}/4L^{2}-1-(\ln 2/c_{0})$. This is a contradiction if $C\gg L^{2}\ln L$ because $h(C)$ grows like $C\ln C$ (cf. F4). This contradiction shows that there does not exist a $L$-sub-Gaussian estimator for $(\star)$, as desired. $\Box$

Degrees of knowledge about the variance

In this section we present the proof of Theorem 3.2. This is mostly a matter of combining the main results in the previous section. Recall that we consider the class

and that $R=\sigma_{2}/\sigma_{1}$. The three parts of the theorem are proven separately.

whenever $X_{1}^{n}={\rm P}^{\otimes n}$ for some ${\rm P}\in\mathcal{P}_{{\rm 2}}$. We define a confidence interval for each $\delta$ via

Clearly, (14) and the fact that $\sigma_{2}\leq R\,\sigma_{{\rm P}}$ for all $\mathcal{P}_{2}^{[\sigma_{1}^{2},\sigma_{2}^{2}]}$ imply that $\{\widehat{I}_{n,\delta}\}_{\delta\in[e^{1-n/2},1)}$ is a $4\sqrt{2}\,{e}\,R$-sub-Gaussian confidence interval for $(\mathcal{P}^{[\sigma_{1}^{2},\sigma_{2}^{2}]}_{2},n,e^{1-n/2})$. Applying Theorem 4.2 gives the desired result.

(Non-existence of multiple-$\delta$ estimators when $R>\phi^{(2)}(L)$.) We use Theorem 4.4. By rescaling, we may assume $\sigma_{1}^{2}=c_{0}/n$, where $c_{0}$ is the constant appearing in Theorem 4.4. We also set $\phi^{(2)}(L):=\sqrt{\phi(L)}$ for $\phi(L)$ as in Theorem 4.4. The assumption on $R$ ensures that $\mathcal{P}^{[c_{0}/n,\phi(L)\,c_{0}/n]}_{{\sf Po}}\subset\mathcal{P}_{2}^{[\sigma_{1}^{2},\sigma_{2}^{2}]}$, so there cannot be a $L$-sub-Gaussian estimator when $\delta^{(2)}_{\min}(L)=e^{1-s\,(L\ln L)^{2}\,c_{0}}$.

(Non-existence of $\delta$-dependent estimators when $\delta_{\min}=e^{1-5L^{2}n}$.) By rescaling, we may assume $\sigma_{1}^{2}=2$. Then the class $\mathcal{P}_{{\sf La}}$ in Theorem 4.3 is contained in $\mathcal{P}_{2}^{[\sigma_{1}^{2},\sigma_{2}^{2}]}$, and the theorem implies the desired result directly.

The regularity condition, symmetry and higher moments

In this section we prove the results described in Section 3.3.

We start with Theorem 3.3, the general positive result on $k$-regular classes.

Proof of Theorem 3.3: By Theorem 4.2, it suffices to build a $4\sqrt{2\,(1+62\ln(3))}\,e^{\frac{5}{2}}$-sub-Gaussian confidence interval for $(\mathcal{P}_{2,k{\rm-reg}},n,e^{3-n/(124)k})$.

To build these intervals, we use an idea related to the proof of Theorem 4.1. Just like in the case of the median-of-means estimator, we divide the data into blocks, but instead of taking the median of the means, we look at the $1/4$ and $3/4$-quantiles to build an interval.

The next result (proven subsequently) is an analogue of Lemma 4.1.

and $L_{0}=2\,e^{2d+\frac{1}{2}}\leq 2\,e^{\frac{5}{2}}.$

Now fix $\delta\in[e^{3-n/(124k)},1)$. We define a confidence interval $\widehat{I}_{n,\delta}(\cdot)$ as follows. First set $b=\lceil 62\ln(3/\delta)\rceil$ and note that

$\{\widehat{I}_{n,\delta}(\cdot)\}_{\delta\in[e^{3-n/(124k)},1)}$ is a $4\sqrt{2\,(1+62\ln(3))}\,e^{\frac{5}{2}}$-sub-Gaussian collection of confidence intervals for $(\mathcal{P}_{2,k{\rm-reg}},n,e^{3-n/(124k)})$.

To see this, we take a distribution ${\rm P}$ in this family and assume $X_{1}^{n}=_{d}{\rm P}^{\otimes n}$. Set $s=\lfloor n/b\rfloor$. Because the blocks $B_{i}$ are disjoint and have at least $s$ elements each, the random variables

all have mean $\mu_{{\rm P}}$ and variance $\leq\sigma_{{\rm P}}^{2}/s$. Moreover, using (15),

so the $k$-regularity property implies that for all $i\in[b]$,

by the choice of $b$ and the fact that $d\geq 1/62$. To finish, we use (15) and the definition of $b$ to obtain

Plugging this back into (16) and recalling $L_{0}\leq 2e^{5/2}$ implies the desired result.

Proof of Lemma 6.1: Define $J=[\mu-L_{0}\sigma,\mu+L_{0}\sigma]$. Assume the following three properties hold.

The number of indices $i\in[b]$ with $Y_{i}\in J$ is at least $3b/4$.

Then clearly $\mu\in[q_{1/4}(Y_{1}^{b}),q_{3/4}(Y_{1}^{b})]$. Moreover, item 3 implies that $q_{1/4}(Y_{1}^{b}),q_{3/4}(Y_{1}^{b})\in J$, so that

and these events are independent. It follows that

2 Symmetric distributions

To prove Theorem 3.4, notice that the existence of the multiple-$\delta$ sub-Gaussian estimator follows from Theorem 3.3. The second part is a simple consequence of Theorem 4.3 and the fact that Laplace distributions are symmetric around their means.

3 Higher moments

In this section we first prove that $\mathcal{P}_{\alpha,\eta}\subset\mathcal{P}_{2,k{\rm-reg}}$ for large enough $k$, and then prove Theorem 3.5. We recall the definition of $\min(p_{+}({\rm P},j)$ and $p_{-}({\rm P},j)$ from Definition 2.

For all $\alpha\in(2,3]$, there exists $C=C_{\alpha}$ such that, if $j\geq(C_{\alpha}\eta)^{\frac{2\alpha}{\alpha-2}}$, then $\min(p_{+}({\rm P},j),p_{-}({\rm P},j))\geq 1/3$.

Proof: We only prove that $p_{+}({\rm P},j)\geq 1/3$, as the other proof is analogous.

Lindberg’s proof of the central limit theorem (see ), specialized to the case where $X_{1}^{j}$ are i.i.d., gives

The right-hand side is $\geq 1/3$ when $j\geq(C\eta)^{\frac{2\alpha}{\alpha-2}}$ for some universal $C=C_{\alpha}$. $\Box$

Proof of Theorem 3.5: The positive result follows directly from Theorem 3.3 plus Lemma 6.2, which guarantees $p_{\pm}({\rm P},j)\geq 1/3$ for $j\geq k_{\alpha}$. For the second part, we first assume $\eta>\eta_{0}$ for a sufficiently large constant $\eta_{0}$. We use the Poisson family of distributions from Section 4.5. For $\lambda=o\left(1\right)$ and $\alpha\in(2,3]$, we have that

If we compare this to Example 3.2, we see that ${\sf Po}_{\lambda}\in\mathcal{P}_{\alpha,\eta}$ if $\lambda\geq h\,/\eta^{2\alpha/(\alpha-2)}$ for some constant $h=h_{\alpha}>0$ (recall we are assuming that $\eta\geq\eta_{0}$ is at least a large constant). Now take $c>0$ such that $c/n=h\,/\eta^{2\alpha/(\alpha-2)}$. If $c>c_{0}$ for the constant $c_{0}$ in the statement of Theorem 4.4, we can apply the theorem to deduce that there is no multiple-$\delta$ estimator for $(\mathcal{P}^{[c/n,\phi(L)\,c/n]}_{{\sf Po}},n,e^{-\,c})$. Noting that $c$ is of the order $n/k_{\alpha}$ finishes the proof in this case.

Now assume $\eta\leq\eta_{0}$. In this case we use the Laplace distributions in Section 4.4. Since $2<\alpha\leq 3$, we may apply the fact that the central third moment of a Laplace distribution satisfies ${\sf La}_{\lambda}|X-\lambda|^{3}=6\leq(3^{1/3}\,2^{1/6}\sigma_{{\sf La}_{\lambda}})^{3}$ to obtain

Our assumption on $\eta$ implies that $\mathcal{P}_{{\sf La}}\subset\mathcal{P}_{\alpha,\eta}$. Thus Theorem 4.3 implies that there is no $\delta$-dependent or multiple-$\delta$ sub-Gaussian estimator for $(\mathcal{P}_{\alpha,\eta},n.e^{1-5L^{2}n})$. This is the desired result since $k_{\alpha}$ is bounded when $\eta\leq\eta_{0}$.

Finally, the third part of the theorem follows from the same reasoning as in the previous paragraph.

Bounded kurtosis and nearly optimal constants

In this section we prove Theorem 3.6. Throughout the proof we assume $X=_{d}{\rm P}$ and $X_{1}^{n}=_{d}{\rm P}^{\otimes n}$ for some ${\rm P}\in\mathcal{P}_{{\rm krt}\leq\kappa}$, and let $b_{\max}$, $C$, $\xi$ be as in Section 3.4. Our proof is divided into four steps.

Preliminary estimates for mean and variance. We use the median-of-means technology to obtain preliminary estimates for the mean and variance of ${\rm P}$. These estimates are not good enough to satisfy the claimed properties, but with extremely high probability they are reasonably close to the true values.

Truncation at the ideal point. We introduce a two-parameter family of truncation-based estimators for $\mu_{{\rm P}}$, and analyze the behavior of one such estimator, chosen under knowledge of $\mu_{{\rm P}}$ and $\sigma_{{\rm P}}$.

Truncated estimators are insensitive. Finally, we use a chaining argument to show that this two-parameter family is insensitive to the choice of parameters.

Wrap up. The insensitivity property means that the preliminary estimates from Step 1 are good enough to “make everything work.”

We conclude the section by a remark on how to obtain a broader range of $\delta_{\min}$ with a worse constant $L$.

(Preliminary estimates via median of means.) Denote by $\widehat{\mu}_{b_{\max}}=\widehat{\mu}_{b_{\max}}(X_{1}^{n})$ the estimator given by Theorem 4.1 with $\delta=e^{-b_{\max}}$, which is possible if $C\geq 6/(1-\log 2)$. The next lemma provides an estimator of the variance.

Let $B_{1},\ldots,B_{b_{\max}}$ denote a partition of $[n]$ into blocks of size $|B_{i}|\geq k=\lfloor n/b_{\max}\rfloor\geq 2$. For each block $B_{i}$ with $i\in[b_{\max}]$, define

The theorem follows by the definition of $\widehat{\mu}_{b_{\max}}$ and an application of Theorem 4.1. $\Box$

Assume $b_{\max}\geq t$, $R=\sigma_{{\rm P}}\sqrt{n/b_{\max}}$ and $\mu=\mu_{{\rm P}}$. Then, with probability at least $1-2e^{-t}$,

Proof: The proof is a consequence of Benett’s inequality. It suffices to estimate the moments of $\Psi_{\mu,R}(X)-\mu_{{\rm P}}$. For the first moment,

where we used Hölder’s inequality. On the other hand,

By the Cauchy-Schwarz inequality, and using the bounded kurtosis assumption,

Finally, for any $p\geq 4$, since $\left|\Psi_{\mu,R}(X)-\mu_{{\rm P}}\right|^{p}\leq R$,

For $s=\sqrt{2nt}/\sigma_{{\rm P}}$, we have $\left|sR\right|/n\leq 1$ and therefore