arXiv:1802.04308v1 [] 12 Feb 2018

Dimension-free PAC-Bayesian bounds for the
estimation of the mean of a random vector
Olivier Catoni
CREST – CNRS UMR 9194
Université Paris Saclay
olivier.catoni@ensae.fr

Ilaria Giulini
Laboratoire de Probabilités
et Modèles Aléatoires
Université Paris Diderot
giulini@math.univ-paris-diderot.fr

Abstract
In this paper, we present a new estimator of the mean of a random vector,
computed by applying some threshold function to the norm. Non asymptotic
dimension-free almost sub-Gaussian bounds are proved under weak moment assumptions, using PAC-Bayesian inequalities.

1 Introduction
Estimating the mean of a random vector under weak tail assumptions has attracted a lot of attention recently. A number of properties have spurred the interest for these new results, where the
empirical mean is replaced by a more robust estimator. One aspect is that it is possible to obtain
an estimator with a sub-Gaussian tail while assuming much weaker assumptions on the data, up
to the fact of assuming only the existence of a finite covariance matrix. Another appealing feature
is that it is possible to obtain dimension-free non asymptotic bounds that remain valid in a separable Hilbert space. Some important references are Catoni [2012] in the one dimensional case and
Minsker [2015] and Lugosi and Mendelson [2017] in the multidimensional case. Building on the
breakthrough of Minsker [2015], that uses a multidimensional generalization of the median of means
estimator, Joly et al. [2017] and Lugosi and Mendelson [2017] propose successive improvements of
the median of means approach to get an estimator with a genuine sub-Gaussian dimension-free tail
bound, while still requiring only the existence of the covariance matrix. In the mean time, the Mestimator approach of Catoni [2012] has also been generalized to multidimensional settings through
the use of matrix inequalities in Minsker [2016] and Minsker and Wei [2017].
Here we follow a different route, based on a multidimensional extension of Catoni [2012] using
PAC-Bayesian bounds. Our new estimator is a simple modification of the empirical mean, where
some threshold is applied to the norm of the sample vectors. Therefore, it is straightforward to
compute, and this is a strong point of our approach, compared to others. Note also that we make
here some compromise on the sharpness of the estimation error bound, in order to simplify the
definition and computation of the estimator. This compromise consists in the presence of second
order terms, while the first order terms can be made as close as desired to a true sub-Gaussian bound
with exact constants, as stated in Lugosi and Mendelson [2017, eq. (1.1)]. With a more involved
estimator, a true sub-Gaussian bound without second order terms is possible and will be described
in a separate publication.

2 Thresholding the norm
Consider X ∈ Rd , a random vector, and (X1 , . . . , Xn ) a sample made of n independent copies
of

X. The question is to estimate E(X) from the sample, under the assumption that E kXkp < ∞,
for some p ≥ 2.
31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.

Consider the threshold function ψ(t) = min{t, 1}, t ∈ R+ , and for some positive real parameter λ
to be chosen later, introduce the thresholded sample

ψ λkXi k
Yi =
Xi .
λkXi k
n

Our estimator of m = E(X) will simply be the thresholded empirical mean m
b =
Proposition 2.1 Introduce the increasing functions


1
2
g1 (t) =
exp(t) − 1 and g2 (t) = 2 exp(t) − 1 − t ,
t
t

1X
Yi .
n i=1

t ∈ R,

that are defined by continuity at t = 0 and are such that g1 (0) = g2 (0) = 1. Assume that
E kXk2 < ∞ and that we know v such that

sup E hθ, X − mi2 ≤ v < ∞,
θ∈Sd



where Sd = θ ∈ Rd , kθk = 1 is the unit sphere of Rd . For some positive real parameter µ, put
r


2 log(δ −1 )
−1
λ=µ
,
T = max E kX − mk2 , v ,
avn
s
!
2av
2
≥ 1.
a = g2 (2µ) ≥ 1,
b = exp(2µ)g1 µ
T log(δ −1 )
With probability at least 1 − δ,
km
b − mk ≤

where

r

2av log(δ −1 )
+
n

r

Cp′
bT
Cp
+ inf p/2 + inf p/2 ,
p≥2 n
p≥1 n
n


p 
p/2

1
p
2 log(δ −1 )
sup E kXkp hθ, X − mi− , and
p + 1 (p + 1)µ
av
θ∈Sd
!
r

p 

p/2

1
p
2 log(δ −1 )
a log(δ −1 )
′
p
Cp =
E kXk kmk 1 +
kmk .
p + 1 (p + 1)µ
av
2vn
Cp =



Remarks Note that in case E kXk2 < ∞ but E kXkp = ∞ for p > 2, we can use the bound
C2′

1
C
√1 +
≤
n
n
2µ

s


log(δ −1 )(T + kmk2 ) 8 log(δ −1 )
+
E kXk2 kmk
2
2an
27µ avn
!
!
r
r
1
a log(δ −1 )
log(δ −1 )(T + kmk2 )
.
× 1+
kmk = O
2vn
2µ
2an

Note also that if we take
 µ = 1/4 and assume that δ ≤ exp(−1), then a ≤ 1.2 and b ≤ 4. If
moreover E kXkp+1 < ∞, for some p > 1, we obtain with probability at least 1 − δ that
r
r
′
Cp+1
Cp
2.4 v log(δ −1 )
4T
km
b − mk ≤
+
+ p/2 + (p+1)/2 ,
n
n
n
n

meaning that the tail distribution of km
b − mk has a sub-Gaussian behavior, up to second order terms.
Remark that by taking µ small, we can make a and b as close as desired to 1, at the expense of the
values of Cp and Cp′ .
2

Proof The rest of the paper is devoted to the proof of Proposition 2.1.
An elementary computation shows that the threshold function ψ satisfies

p
ψ(t)
p
tp
0≤1−
≤ inf
,
t ∈ R+ ,
(1)
p≥1 p + 1 p + 1
t

ψ λkXk
where non integer values of the exponent p are allowed. Let Y =
X and m
e = E(Y ). We
λkXk
can decompose the estimation error in direction θ into
n

1X
hθ, m
b − mi = hθ, m
e − mi +
hθ, Yi − mi,
e
θ ∈ Rd .
(2)
n i=1

ψ λkXk
Introduce α =
and let us deal with the first term first. As 0 ≤ 1 − α ≤
λkXk


p
p
λp kXkp
p+1
p+1




hθ, m
e − mi = E (α − 1)hθ, Xi = E (α − 1)hθ, X − mi + E(α − 1)hθ, mi

p 

p


λp
λp
p
p
≤ inf
E kXkphθ, X − mi− + inf
E kXkp hθ, mi− ,
p≥2 (p + 1) p + 1
p≥1 (p + 1) p + 1

where r− = max{0, −r} is the negative part of integer r.

Let us now look at the second term of the decomposition (2). To gain uniformity inθ, we will use a
PAC-Bayesian inequality and the family of normal distributions ρθ = N θ, β −1 Id , bearing on the
parameter θ ∈ Rd , where Id ∈ Rd×d is the identity matrix of size d × d, and where β is a positive
parameter to be chosen later on.

We will use the following PAC-Bayesian inequality without recalling its proof, that is a simple
consequence of Catoni [2004, eq. (5.2.1) page 159]:
d
d
Lemma 2.2 For
 any bounded measurable function f : R × R → R, for any probability measure
π ∈ M1+ Rd , for any δ ∈]0, 1[, with probability at least 1 − δ, for any probability measure
ρ ∈ M1+ (Rd ),
Z
n Z
h 

i
1X
K(ρ, π) + log(δ −1 )
dρ(θ) +
,
f θ, Xi dρ(θ) ≤ log E exp f (θ, X)
n i=1
n

R
log ρ/π dρ, when ρ ≪ π,
where K is the Kullback-Liebler divergence K(ρ, π) =
+∞,
otherwise.
n

Remarking that

n

1X
1X
hθ, Yi − mi
e =
n i=1
n i=1

Z

hθ′ , Yi − mi
e dρθ (θ′ ), using π = ρ0 , and taking into

account the fact that K(ρθ , ρ0 ) = βkθk2 /2, we obtain as a consequence of the previous lemma that
with probability at least 1 − δ, for any θ ∈ Sd ,

Z
n


1
log(δ −1 )
β
1X
hθ, Yi − mi
e ≤
+
.
log E exp µλhθ′ , Y − mi
e
dρθ (θ′ ) +
n i=1
µλ
2nµλ
nµλ

In our setting f is not bounded in θ, but the required extension is valid as explained in Catoni [2004].
Since the logarithm is concave,
" Z

#
Z




′
′
′
′
log E exp µλhθ , Y − mi
e
dρθ (θ ) ≤ log E
exp µλhθ , Y − mi
e dρθ (θ )
#
" 


µ2 λ2
2
,
kY − mk
e
= log E exp µλhθ, Y − mi
e +
2β
3

where we have used the explicit expression of the Laplace transform of a Gaussian distribution.
To go further, reminding as a source of inspiration the proof of Bennett’s inequality, let us introduce
the increasing functions g1 and g2 defined in Proposition 2.1. These functions will be used to bound
the exponential function by polynomials. More precisely, we will exploit the fact that when t ≤ b,
exp(t) ≤ 1 + t + g2 (b)t2 /2 and exp(t) ≤ 1 + g1 (b)t. From this, it results that if t ≤ b and u ≤ c,

exp(t + u) ≤ exp(t) 1 + g1 (c)u ≤ exp(t) + g1 (c) exp(b)u
≤ 1 + t + g2 (b)t2 /2 + g1 (c) exp(b)u.

Legitimate values for b and c will be deduced from the remark that λkY k ≤ 1, implying λkmk
e ≤ 1.
Namely, in our context, we will use b = 2µ and c = 2µ2 /β.

These arguments put together lead to the inequality

!
µ2 λ2
2
E exp µλhθ, Y − mi
e +
Y −m
e
2β

 2 2 2 

2µ µ λ
µ2 λ2
2
+ exp(2µ)g1
E hθ, Y − mi
e
E Y −m
≤ 1 + g2 (2µ)
e
2
β
2β

2



.

Replacing in the previous inequalities, we obtain

Lemma 2.3 With probability at least 1 − δ, for any θ ∈ Sd ,
hθ, m
b − mi
e =
Remark that

n

µλ
1X
hθ, Yi − mi
e ≤ g2 (2µ) E hθ, Y − mi
e 2
n i=1
2
 2
 β + 2 log(δ −1 )
2µ µλ
E kY − mk
e 2 +
.
+ exp(2µ)g1
β
2β
2µλn


2
hθ, Y − mi2 = hθ, αX − mi2 = αhθ, X − mi − (1 − α)hθ, mi

≤ αhθ, X − mi2 + (1 − α)hθ, mi2 ≤ hθ, X − mi2 + (1 − α)hθ, mi2 .
Therefore, using inequality (1) and the definition of α,

p




p
λp
2
2
2
2
E kXkp .
≤ E hθ, Y − mi ≤ E hθ, X − mi + hθ, mi inf
E hθ, Y − mi
e
p≥2 p + 1 p + 1
Remark also that Y = g(X), where g is a contraction (being the projection on a ball). Consequently
 1
 1


E kY − mk
e 2 = E kY1 − Y2 k2 ≤ E kX1 − X2 k2 = E kX − mk2 .
2
2
In view of these remarks, the previous lemma translates to
 2

2µ
.
Lemma 2.4 Let a = g2 2µ and b ≥ exp(2µ)g1
β
With probability at least 1 − δ, for any θ ∈ Sd ,
hθ, m
b − mi ≤

 bµλ
 β + 2 log(δ −1 )
aµλ
E hθ, X − mi2 +
E kX − mk2 +
2
2β
2µλn

p

λp
p
+ inf
E kXkp hθ, X − mi−
p≥1 p + 1 p + 1
!

p

λp
aµλ
p
+ inf
E kXkp hθ, mi− +
hθ, mi2 .
p≥2 p + 1 p + 1
2

r
1 2 log(δ −1 )
, and β =
Proposition 2.1 follows by taking b as mentioned there, λ =
µ
nav
r
r
2bT log(δ −1 )
2T log(δ −1 )
≥
, so that the condition on b is satisfied.
av
av
4

References
O. Catoni. Statistical Learning Theory and Stochastic Optimization, Lectures on Probability Theory and Statistics, École d’Été de Probabilités de Saint-Flour XXXI – 2001, volume 1851 of Lecture Notes in Mathematics.
Springer, 2004. pages 1–269.
O. Catoni. Challenging the empirical mean and empirical variance: a deviation study. Ann. Inst. Henri Poincaré,
48(4):1148–1185, 2012.
E. Joly, G. Lugosi, and R. I. Oliveira. On the estimation of the mean of a random vector. Electronic Journal of
Statistics, 11:440–451, 2017.
G. Lugosi and S. Mendelson. Sub-gaussian estimators of the mean of a random vector. Annals of Statistics, to
appear, 2017.
S. Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli, 4:2308–2335, 2015.
S. Minsker. Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries. Annals of
Statistics, to appear, 2016.
S. Minsker and X. Wei. Estimation of the covariance structure of heavy-tailed distributions. In NIPS–2017, to
appear, 2017.

5

