arXiv:1607.05421v1 [] 19 Jul 2016

On the estimation of the mean of a random vector
Emilien Joly ∗
Universit Paris Ouest
Nanterre, France;
emilien.joly@u-paris10.fr

Gábor Lugosi †
ICREA and Department of Economics,
Pompeu Fabra University,
Barcelona, Spain;
gabor.lugosi@upf.edu

Roberto Imbuzeiro Oliveira ‡
IMPA, Rio de Janeiro, RJ,
Brazil;
rimfo@impa.br
April 2, 2018

Abstract
We study the problem of estimating the mean of a multivariate distribution based
on independent samples. The main result is the proof of existence of an estimator
with a non-asymptotic sub-Gaussian performance for all distributions satisfying some
mild moment assumptions.

1

Introduction

Let X be a random vector taking values in Rd . We assume throughout the paper that
the mean vector µ = EX and covariance matrix Σ = (X − µ)(X − µ)T exist. Given n
independent, identically distributed samples X1 , . . . , Xn drawn from the distribution of X,
one wishes to estimate the mean vector.
P
A natural and popular choice is the sample mean (1/n) ni=1 Xi that is known to have
a near-optimal behavior whenever the distribution is sufficiently light tailed. However,
∗

Supported by the French Agence Nationale de la Recherche (ANR), under grant ANR-13-BS01-0005
(project SPADRO).
†
Supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM2015-67304-P and
FEDER, EU.
‡
Support from CNPq, Brazil via Ciência sem Fronteiras grant # 401572/2014-5. Supported by a Bolsa
de Produtividade em Pesquisa from CNPq, Brazil. Supported by FAPESP Center for Neuromathematics
(grant# 2013/ 07699-0 , FAPESP - S. Paulo Research Foundation).

1

whenever heavy tails are a concern, the sample mean is to be avoided as it may have a suboptimal performance. While the one-dimensional case (i.e., d = 1) is quite well understood
(see [3], [5]), various aspects of the multidimensional problem are still to be revealed. This
paper aims at contributing to the understanding of the multi-dimensional case.
Before stating the main results, we briefly survey properties of some mean estimators
of real-valued random variables. Some of these techniques serve as basic building blocks
for the estimators we propose for the vector-valued case.

1.1

Estimating the mean of a real-valued random variable

WhenP
d = 1, the simplest and most popular mean estimator is the sample mean µn =
(1/n) ni=1 Xi . The sample mean is unbiased and the central limit theorem guarantees an
asymptotically Gaussian distribution. However, unless the distribution of X has a light
(e.g., sub-Gaussian) tail, there are no non-asymptotic sub-Gaussian performance guarantees for µn . We refer the reader to Catoni [3] for details. However, perhaps surprisingly,
there exist estimators of µ with much better concentration properties, see Catoni [3] and
Devroye, Lerasle, Lugosi, and Oliveira [5].
A conceptually simple and quite powerful estimator is the so-called median-of-means
estimator that has been proposed, in different forms, in various papers, see Nemirovsky
and Yudin [14], Hsu [8], Jerrum, Valiant, and Vazirani [10], Alon, Matias, and Szegedy
[1]. The median-of-means estimator is defined as follows. Given a positive integer b and
x1 , . . . , xb ∈ R, let q1/2 denote the median of these numbers, that is,
q1/2 (x1 , . . . , xb ) = xi , where #{k ∈ [b] : xk ≤ xi } ≥

b
b
and #{k ∈ [b] : xk ≥ xi } ≥ .
2
2

(If several i fit the above description, we take the smallest one.)
For any fixed δ ∈ [e1−n/2 , 1), first choose b = ⌈ln(1/δ)⌉ and note that b ≤ n/2 holds.
Next, partition [n] = {1, . . . , n} into b blocks B1 , . . . , Bb , each of size |Bi | ≥ ⌊n/b⌋ ≥ 2.
Given X1 , . . . , Xn , we compute the sample mean in each block
Yi =

1 X
Xj
|Bi | j∈B
i

(δ)

and define the median-of-means estimator by µ
bn = q1/2 (Y1 , . . . , YB ). One can show (see,
e.g., Hsu [8]) that for any n ≥ 4,
(
)
r
p
(1
+
ln(1/δ))
P |b
µ(δ)
≤δ ,
(1)
2Var(X)
n − µ| > 2e
n
where Var(X) denotes the variance of X.
(δ)
Note that the median-of-means estimator µ
bn does not require any knowledge of the
variance of X. However, it depends on the desired confidence level δ and the partition
B1 , . . . , Bb . Any partition satisfying ∀i, |Bi | ≥ ⌊n/b⌋ is valid in order to get (1). Hence,
2

(δ)

we do not keep the dependence on the partition B1 , . . . , Bb in the notation µ
bn . Devroye, Lerasle, Lugosi, and Oliveira [5] introduce estimators that work for a large range
of confidence levels under some mild assumptions. Catoni [3] introduces estimators of
quite different flavor and gets a non-asymptotic result of the same form as (1). Bubeck,
Cesa-Bianchi and Lugosi [2] apply these estimators in the context of bandit problems.

1.2

Estimating the mean of random vectors

P
Consider now the multi-dimensional case when d > 1. The sample mean µn = (1/n) ni=1 Xi
is still an obvious choice for estimating the mean vector µ.
If X has a multivariate normal distribution with mean vector µ and covariance matrix
Σ, then µn is also multivariate normal with mean µ and covariance matrix (1/n)Σ and
therefore, for δ ∈ (0, 1), with probability at least 1 − δ,
r
r
Tr(Σ)
2λmax log(1/δ)
+
,
(2)
kµn − µk ≤
n
n
where Tr(Σ) and λmax denote the trace and largest eigenvalue of the covariance matrix,
respectively (Hanson and Wright [7]). For non-Gaussian and possibly heavy-tailed distributions, one cannot expect such a sub-Gaussian behavior of the sample mean. The main
goal of this paper is to investigate under what conditions it is possible to define mean
estimators that reproduce a (non-asymptotic) sub-Gaussian performance similar to (2).
Lerasle and Oliveira [11], Hsu and Sabato [9], and Minsker [13] extend the median-ofmeans estimator to more general spaces. In particular, Minsker’s results imply that for
(δ)
each δ ∈ (0, 1) there exists a mean estimator µ
en and a universal constant C such that,
with probability at least 1 − δ,
r
Tr(Σ) log(1/δ)
ke
µ(δ)
.
(3)
n − µk ≤ C
n
While this bound is quite remarkable–note that no assumption other than the existence
of the covariance matrix is made–, it does not quite achieve a sub-Gaussian performance
bound that resembles (2). An instructive example is when all eigenvalues
are identical and
p
−1
equal to λmax . If the dimension
p d is large, (2) is of the order of (λmax /n)(d + log(δ ))
while (3) gives the order (λmax /n)(d log(δ −1 )). The main result of this paper is the
construction of a mean estimator that, under some mild moment assumptions, achieves
a sub-Gaussian performance bound in the sense of (2). More precisely, we prove the
following.
(δ)

Theorem 1 For all δ ∈ (0, 1) there exists a mean estimator µ
bn and a universal constant
d
C such that if X1 , . . . , Xn are i.i.d. random vectors in R with mean µ ∈ Rd and covariance
matrix Σ such that there exists a constant K > 0 such that, for all v ∈ Rd with kvk = 1,
h
4 i
E (X − µ)T v
≤ K(v T Σv)2 ,
3

then for all n ≥ CK log d (d + log(1/δ)),
!
r
r
Tr(Σ)
λ
log(log
d/δ)
max
kb
µ(δ)
.
+
n − µk ≤ C
n
n
The theorem guarantees the existence of a mean estimator whose performance
matches
p
the sub-Gaussian bound (2), up to the additional term of the order of (1/n)λmax log log d
for all distributions satisfying the fourth-moment assumption given above. The additional
term is clearly of minor importance. (For example, it is dominated by the first term
whenever Tr(Σ) > λmax log log d.) With the estimator we construct, this term is inevitable.
On the other hand, the inequality of the theorem only holds for sample sizes that are at
least a constant times d log d. This feature is not desirable for truly high-dimensional
problems, especially taking into account that Minsker’s bound is “dimension-free”.
The fourth-moment assumption can be interpreted as a boundedness assumption of the
kurtosis of (X − µ)T v. The same assumption has be used in Catoni [4] and Giulini [6]
for the robust estimation of the Gram matrix. The fourth-moment assumption may be
weakened to an analogous “(2 + ε)-th moment assumption” that we do not detail for the
clarity of the exposition.
We prove the theorem by constructing an estimator in several steps. First we construct
an estimator that performs well for “spherical” distributions (i.e., for distributions whose
covariance matrix has a trace comparable to dλmax ). This estimator is described in Section 2. In the second step, we decompose the space–in a data-dependent way–into the
orthogonal sum of O(log d) subspaces such that all but one subspaces are such that the
projection of X to the subspace has a spherical distribution. The last subspace is such
that the projection has a covariance matrix with a small trace. In each subspace we apply
(δ)
the first estimator and combine them to obtain the final estimator µ
bn . The proof below
provides an explicit value of the constant C, though no attempt has been made to optimize
its value.
The constructed estimator is computationally so demanding that even for moderate
values of d it is hopeless to compute it in reasonable time. In this sense, Theorem 1 should
be regarded as an existence result. It is an interesting an important challenge to construct
estimators with similar statistical performance that can be computed in polynomial time
(as a function of n and d). Note that the estimator of Minsker cited above may be computed
by solving a convex optimization problem, making it computationally feasible, see also Hsu
and Sabato [9] for further computational considerations.

2

An estimator for spherical distributions

In this section we construct an estimator that works well whenever the distribution of
X is sufficiently spherical in the sense that a positive fraction of the eigenvalues of the
covariance matrix is of the same order as λmax . More precisely, for c ≥ 1, we call a
distribution c-spherical if dλmax ≤ cTr(Σ).
4

For each δ ∈ (0, 1) and unit vector w ∈ S d−1 (where S d−1 = {x ∈ Rd : kxk = 1}),
(δ)
we may define mn (w) as the median-of-means estimate (as defined in Section 1.1) of
w T µ = Ew T X based on the i.i.d. sample w T X1 , . . . , w T Xn .
Let N1/2 ⊂ S d−1 be a minimal 1/2-cover, that is, a set of smallest cardinality that has
the property that for all u ∈ S d−1 there exists w ∈ N1/2 with ku − xk ≤ 1/2. It is well
known (see, e.g., [12, Lemma 13.1.1]) that |N1/2 | ≤ 8d .
Noting that Var(w T X) ≤ λmax , by (1) and the union bound, we have that, with probability at least 1 − δ,
r
ln(e8d /δ)
d
sup mn(δ/8 ) (w) − w T µ ≤ 2e 2λmax
.
n
w∈N1/2
In other words, if, for λ > 0, we define the empirical polytope
(
r
Pδ,λ =

x ∈ Rd : sup

w∈N1/2

(δ/8d )

mn

ln(e8d /δ)
(w) − w T x ≤ 2e 2λ
n

)

,

then with probability at least 1 − δ, µ ∈ Pδ,λmax . In particular, on this event, Pδ,λmax is
nonempty. Suppose that an upper bound of the largest eigenvalue of the covariance matrix
λ ≥ λmax is available. Then we may define the mean estimator

any element y ∈ Pδ,λ if Pδ,λ 6= ∅
(δ)
µ
bn,λ =
.
0
otherwise

Now suppose that µ ∈ Pδ,λ and let y ∈ Pδ,λ be arbitrary. Define u = (y −µ)/ky −µk ∈ S d−1 ,
and let w ∈ N1/2 be such that kw − uk ≤ 1/2. (Such a w exists by definition of N1/2 .)
Then
r
ln(e8d /δ)
ky − µk = uT (y − µ) = (u − w)T (y − µ) + w T (y − µ) ≤ (1/2)ky − µk + 4e 2λ
,
n
where we used Cauchy-Schwarz and the fact that y, µ ∈ Pδ,λ . Rearranging, we obtain that,
on the event that µ ∈ Pδ,λ,
r
d ln 8 + ln(e/δ)
(δ)
µ
bn,λ − µ ≤ 8e 2λ
,
n
provided that λ ≥ λmax . Summarizing, we have proved the following.
Proposition 1 Let λ > 0 and δ ∈ (0, 1). For any distribution with mean µ and covariance
(δ)
matrix Σ such that λmax = kΣk ≤ λ, the estimator µ
bn,λ defined above satisfies, with
probability at least 1 − δ,
r
d ln 8 + ln(e/δ)
(δ)
.
µ
bn,λ − µ ≤ 8e 2λ
n
In particular, if the distribution is c-spherical and λ ≤ 2λmax , then
r
cTr(Σ) ln 8 + λmax ln(e/δ)
(δ)
.
µ
bn,λ − µ ≤ 16e
n
5

The bound we obtained has the same sub-Gaussian form as (2), up to a multiplicative
constant, whenever the distribution is c-spherical. To make the estimator fully datab that falls in the interval [λmax , 2λmax ], with
dependent, we need to find an estimate λ
high probability. This may be achieved by splitting the sample in two parts of equal size
(assuming n is even), estimating λmax using samples from one part and computing the
mean estimate defined above using the other part. In the next section we describe such a
method as a part of a more general procedure.

3

Empirical eigendecomposition

In the previous section we presented a mean estimate that works well for “spherical” distributions. We will use this estimator as a building block in the construction of an estimator
that has the desirable performance guarantee for distributions with any covariance matrix.
In addition to finite covariances, we assume that there exists a constant K > 0 such that,
for all v ∈ Rd with kvk = 1,
h
4 i
T
E (X − µ) v
≤ K(v T Σv)2 .
(4)


In this section we assume that n ≥ 2(400e)2K log3/2 d d log 25 + log(2 log3/2 d) + log(1/δ) .
The basic idea is the following. We split the data into two equal halves. We use the
first half in order to decompose the space into the sum of orthogonal subspaces such that
the projection of X into each subspace is 4-spherical. Then we may estimate the projected
means by the estimator of the previous section.
Next we describe how we obtain an orthogonal decomposition of the space based on n
i.i.d. observations X1 , . . . , Xn .
Let s = ⌈log3/2 d2 ⌉ and m = ⌊n/s⌋. Divide the sample into s blocks, each of size at least
m. In what follows, we describe a way of sequentially decomposing Rd into the orthogonal
sum of s + 1 subspaces Rd = V1 ⊕ · · · ⊕ Vs+1 . First we construct V1 using the first block
X1 , . . . , Xm of observations. Then we use the second block to build V2 , and so on, for s
blocks. The key properties we need are that (a) the random vector X, projected to any of
these subspaces has a 4-spherical distribution; (b) the largest eigenvalue of the covariance
matrix of X, projected on Vi is at most λmax (2/3)i−1 .
To this end, just like in the previous section, let Nγ ⊂ S d−1 be a minimal γ-cover of
the unit sphere S d−1 for a sufficiently small constant γ ∈ (0, 1). The value γ = 1/100 is
sufficient for our purposes and in the sequel we assume this value. Note that |Nγ | ≤ (4/γ)d
(see [12, Lemma 13.1.1] for a proof of this fact).
Initially, we use the first block X1 , . . . , Xm . We may assume that m is even. Using these
(δ)
observations, for each u ∈ Nγ , we compute an estimate Vm (u) of uT Σu = E(uT (X −µ))2 =
(1/2)E(uT (X − X ′ ))2 , where X ′ is an i.i.d. copy of X. We may construct the estimate
by forming m/2 i.i.d. random variables (1/2)(uT (X1 − Xm/2+1 ))2 , . . . , (1/2)(uT (Xm/2 −
(δ)
Xm ))2 and estimate their mean by the median-of-means estimate Vm (u) with parameter

6

δ/(s(4/γ)d ). Then (1), together with assumption (4) implies that, with probability at least
1 − δ/s,
r
(δ)
uT Σu − Vm (u)
K log(s(4/γ)d /δ) def.
sup
= εm .
≤
4e
uT Σu
m
u∈Nγ
Our assumptions on the sample size guarantee that εm < 1/100. The event that the
inequality above holds is denoted by E1 so that P{E1 } ≥ 1 − δ/s.
Let Mδ,m be the set of all symmetric positive semidefinite d × d matrices M satisfying
(δ)

uT Mu − Vm (u)
sup
u∈Nγ

uT Σu

≤ εm .

By the argument above, Σ ∈ Mδ,m on the event E1 . In particular, on E1 , Mδ,m in nonempty. Define the estimated covariance matrix

(δ)
b = any element of Mδ,m if Mδ,m 6= ∅
Σ
m
0
otherwise
b (δ)
Since on E1 both Σ
m and Σ are in Mδ,m , on this event, we have
uT Σu


 1 − εm
b (δ) u ≤ uT Σu 1 + εm
≤ uT Σ
m
1 + εm
1 − εm

for all u ∈ Nγ .

(5)

Now compute the spectral decomposition
b (δ)
Σ
m =

d
X
i=1

bi vbi vbT ,
λ
i

bd ≥ 0 are the eigenvalues and b
where b
λ1 ≥ · · · ≥ λ
v1 , . . . , b
vd the corresponding orthogonal
eigenvectors.
Let u ∈ S d−1 be arbitrary and let v be a point in Nγ with smallest distance to u. Then
b (δ) u = v T Σ
b (δ) v + 2(u − v)T Σ
b (δ) v + (u − v)T Σ
b (δ) (u − v)
uT Σ
m
m
m
m
b1 (2γ + γ 2 )
b (δ) v + λ
≤ vT Σ
m

(by Cauchy-Schwarz and using the fact that ku − vk ≤ γ)
1 + εm
b1
+ 3γ λ
≤ (v T Σv)
1 − εm
(by (5))
1 + εm
b1 .
≤
λmax + 3γ λ
1 − εm

b1 ≤ βλmax where β =
In particular, on E1 we have λ
7

1+εm
/(1
1−εm

− 3γ) < 1.1.

(6)

By a similar argument, we have that for any u ∈ S d−1 , if v is the point in Nγ with
smallest distance to u, then on E1 ,
b (δ) v)
uT Σu ≤ (v T Σ
m

1 + εm b
1 + εm
λ1 + 3γλmax .
+ 3γλmax ≤
1 − εm
1 − εm

b1. Similarly,
In particular, λmax ≤ β b
λ1 ≤ (4/3)λ

b1
b (δ) v) 1 − εm − 3γ λ
uT Σu ≥ (v T Σ
m
1 + εm


b1 .
b1 1 − εm − 3γ λ
b (δ) u − 3γ λ
≥ uT Σ
m
1 + εm

1−ε
m
T b (δ)
b1 .
− 6γ λ
≥ u Σm u
1 + εm

(7)

bi that are at least λ
b1 /2 and let V1 be the subspace
Let db1 be number of eigenvalues λ
of Rd spanned by vb1 , . . . , b
vdb1 . Denote by Π1 (X) the orthogonal projection of the random
variable X (independent of the Xi used to build V1 ) onto V1 . Then for any u ∈ V1 ∩ S d−1 ,
on the event E1 , by (7),
b1 1
u Σu ≥ λ
2
T

and therefore



1 − εm
− 12γ
1 + εm



≥

b
λ1
3

EuT (Π1 (X) − EΠ1 (X))(Π1 (X) − EΠ1 (X))T u = uT Σu ∈

b 1 4λ
b1
λ
,
3 3

!

.

In particular, the ratio of the largest and smallest eigenvalues of the covariance matrix of
Π1 (X) is at most 4 and therefore the distribution of Π1 (X) is 4-spherical.
On the other hand, on the event E1 , for any unit vector u ∈ V1⊥ ∩S d−1 in the orthogonal
b
b (δ)
complement of V1 , we have uT Σu ≤ 2λmax /3. To see this, note that uT Σ
m u ≤ λ1 /2 and
therefore, denoting by v the point in Nγ closest to u,





T b (δ)
T b (δ)
(δ)
T
b
b (δ)
v
+
v
Σ
v
−
u
Σ
u
+ uT Σu − v T Σv
Σ
−
Σ
uT Σu = uT Σ
u
+
v
m
m
m
m
b1
λ
b1 + 3γλmax
+ 2εm λmax + 3γ λ
2
(by (5), (6), and a similar argument for the last term)
 


1
2λmax
≤ λmax β
+ 3γ + 2εm + 3γ ≤
.
2
3
≤

In other words, the largest eigenvalue of the covariance matrix of Π⊥
1 (X) (the projection
⊥
of X to the subspace V1 ) is at most (2/3)λmax.
8

In the next step we construct the subspace V2 ⊂ V1⊥ . To this end, we proceed exactly as
in the first step but now we replace Rd by V1⊥ and the sample X1 , . . . , Xm on the first block
⊥
⊥
⊥
by the variables Π⊥
1 (Xm+1 ), . . . , Π1 (X2m ) ∈ V1 . (Recall that Π1 (Xi ) is the projection of
⊥
Xi to the subspace V1 ). Just like in the first step, with probability at least 1 − δ/s we
obtain a (possibly empty) subspace V2 , orthogonal to V1 such that Π2 (X), the projection
of X on V2 , has a 4-spherical distribution and largest eigenvalue of the covariance matrix
⊥
2
of Π⊥
2 (X) (the projection of X to the subspace (V1 ⊕ V2 ) ) is at most (2/3) λmax .
We repeat the procedure s times and use a union bound the s events. We obtain, with
probability at least 1 − δ, a sequence of subspaces V1 , . . . , Vs , with the following properties:
(i) V1 , . . . , Vs are orthogonal subspaces.
(ii) For each i = 1, . . . , s, Πi (X), the projection of X on Vi , has a 4-spherical distribution.
(i)

(iii) The largest eigenvalue of the covariance matrix of Πi (X) is at most λ1 ≤ (2/3)i−1λmax .
b(i) of the estimated covariance matrix of Πi (X) satisfies
(iv) The largest eigenvalue λ
1
(i)

(i)

(i)

b ≤ 1.1λ .
(3/4)λ1 ≤ λ
1
1

Note that it may happen for some T < s, we have Rd = V1 ⊕ · · · ⊕ VT . In that case we
define VT +1 = · · · = Vs = ∅.

4

Putting it all together

In this section we construct our final multivariate mean estimator and prove Theorem 1.
To simplify notation, we assume that the sample size is 2n. This only effects the value of
the universal constant C in the statement of the theorem.
The data is split into two equal halves (X1 , . . . , Xn ) and (Xn+1 , . . . , X2n ). The second
half is used to construct the orthogonal spaces V1 , . . . , Vs as described in the previous section. Let db1 , . . . , dbs denote the dimension of these subspaces. Recall that, with probability
at least 1 − δ, the construction is successful in the sense that the subspaces satisfy properties (i)–(iv) described at the end of the previous section. Denote this event by E. In
the rest of the argument we condition on (Xn+1 , . . . , X2n ) and assume that E occurs. All
probabilities
Ps b below are conditional.
If i=1 di < d (i.e., V1 ⊕· · ·⊕Vs 6= Rd ), then we define Vs+1 = (V1 ⊕· · ·⊕Vs )⊥ and denote
P
by dbs+1 = d − si=1 dbi the dimension of Vs+1 . Let Π1 , . . . , Πs+1 denote the projection operators on the subspaces V1 , . . . , Vs+1 , respectively. For each i = 1, . . . , s + 1, we use the vectors Πi (X1 ), . . . , Πi (Xn ) to compute an estimator of the mean E [Πi (X)|(Xn+1 , . . . , X2n )] =
Πi (µ).
For i = 1, . . . , s, we use the estimator defined in Section 2. In particular, within
(δ/(s+1))
bi comes from
the dbi -dimensional space Vi , we compute µi = µ
bn,(4/3)λb . Note that since λ
i
an empirical estimation of Σ restricted to an empirical subspace Vi , µi is an estimator
9

constructed on the sample X1 , . . . , Xn . Then, by Proposition 1, with probability 1 − δ/(s +
1),


(i) b
b
(8/3)λ1 di ln 8 + ln(e(2 log3/2 d + 1)/δ)
kµi − Πi (µ)k2 ≤ (8e)2
.
n
In the last subspace Vs+1 , we may use Minsker’s estimator, based on Πs+1 (X1 ), . . . , Πs+1 (Xn )
(δ/(s+1))
en
of Πs+1 (µ). Since the largest eigenvalue of the coto compute an estimator µs+1 = µ
variance matrix of Πs+1 (X) is at most λmax /d2 , using (3), we obtain that, with probability
1 − δ/(s + 1),
λmax log((2 log3/2 d + 1)/δ)
kµs+1 − Πs+1 (µ)k2 ≤ C
.
n
P
(δ)
Our final estimator is µ
bn = s+1
i=1 µs+1 . By the union bound, we have that, with probability
at least 1 − δ,
µ
b(δ)
n

−µ

2

=

s+1
X

kµi − Πi (µ)k2

i=1

≤ (8e)

2 (8/3) ln 8

n
+C

s
X
i=1

(i)
b
λ1 dbi + (8e)2 (8/3)

λmax log((2 log3/2 d + 1)/δ)
n

s
ln(e(2 log3/2 d + 1)/δ) X
b(i)
λ
1
n
i=1

First notice that, by properties (iii) and (iv) at the end of the previous section,
s
X
i=1

b(i) ≤ 1.1
λ
1

s
X

(i)
λ1

≤ 1.1λmax

i=1

s
X

(2/3)i−1 ≤ 3.3λmax .

i=1

On the other hand, since

2

Tr(Σ) = EkX − µk =

s+1
X

EkΠi (X) − Πi (µ)k2

i=1

and for i ≤ s each Πi (X) has a 4-spherical distribution, we have that
s
X
i=1

b(i) dbi ≤ 1.1
λ
1

This concludes the proof of Theorem 1.

s
X
i=1

(i)
λ1 dbi ≤ 4.4Tr(Σ) .

References
[1] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the
frequency moments. Journal of Computer and System Sciences, 58:137–147, 2002.
10

[2] S. Bubeck, N. Cesa-Bianchi, and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59:7711–7717, 2013.
[3] O. Catoni. Challenging the empirical mean and empirical variance: a deviation study.
Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(4):1148–1185,
2012.
[4] O. Catoni. Pac-bayesian bounds for the gram matrix and least squares regression with
a random design. arXiv preprint arXiv:1603.05229, 2016.
[5] L. Devroye, M. Lerasle, G. Lugosi, and R.I. Oliveira. Sub-Gausssian mean estimators.
Annals of Statistics, 2016.
[6] I. Giulini.
Robust dimension-free gram operator estimates.
arXiv:1511.06259, 2015.

arXiv preprint

[7] D.L. Hanson and F.T. Wright. A bound on tail probabilities for quadratic forms in
independent random variables. Annals of Mathematical Statistics, 42:1079–1083, 1971.

[8] D. Hsu. Robust statistics. http://www.inherentuncertainty.org/2010/12/robust-statistics.ht
2010.
[9] D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails.
Journal of Machine Learning Research, 17:1–40, 2016.
[10] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:186–188, 1986.
[11] M. Lerasle and R. I. Oliveira. Robust empirical mean estimators. arXiv:1112.3914,
2012.
[12] J. Matoušek. Lectures on discrete geometry. Springer, 2002.
[13] S. Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli,
21:23082335, 2015.
[14] A.S. Nemirovsky and D.B. Yudin. Problem complexity and method efficiency in optimization. 1983.

11

