arXiv:1705.10696v2 [math.ST] 26 Sep 2017

Localized Gaussian width of M -convex
hulls with applications to Lasso and
convex aggregation
Pierre C. Bellec
Rutgers University, Department of Statistics and Biostatistics
Abstract: Upper and lower bounds are derived for the Gaussian mean
width of the intersection of a convex hull of M points with an Euclidean
ball of a given radius. The upper bound holds for any collection of extreme point bounded in Euclidean norm. The upper bound and the
lower bound match up to a multiplicative constant whenever the extreme points satisfy a one sided Restricted Isometry Property.
This bound is then applied to study the Lasso estimator in fixeddesign regression, the Empirical Risk Minimizer in the anisotropic persistence problem, and the convex aggregation problem in density estimation.

1. Introduction
Let T be a subset of Rn . The Gaussian width of T is defined as
ℓ(T ) := E sup uT g,
u∈T

where g = (g1 , ..., gn )T and g1 , ..., gn are i.i.d. standard normal random variables. For any vector u ∈ Rn , denote by |u|2 its Euclidean norm and define
the Euclidean balls
B2 = {u ∈ Rn : |u|2 ≤ 1},

sB2 = {su ∈ Rn , u ∈ B2 } for all s ≥ 0.

We will also use the notation S n−1 = {u ∈ Rn : |u|2 = 1}. The localized
Gaussian width of T with radius s > 0 is the quantity ℓ(T ∩ sB2 ). For any
P
u ∈ Rp , define the ℓp norm by |u|p = ( ni=1 |ui |p )1/p for any p ≥ 1, and let
|u|0 be the number of nonzero coefficients of u.
This paper studies the localized Gaussian width
ℓ(sB2 ∩ T ),
where T is the convex hull of M points in Rn .
1
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

2

If T = B1 = {u ∈ Rn : |u|1 ≤ 1}, then matching upper and lower bounds
are available for the localized Gaussian width:
q
√ 
ℓ(sB2 ∩ B1 ) ≍ log (en(s2 ∧ 1)) ∧ s n ,
(1)

cf. [14] and [21, Section 4.1]. In the above display, a ≍ b means that a ≤ Cb
and b ≤ Ca for some large enough numerical constant C ≥ 1.
The first goal of this paper is to generalize this bound to any T that is
the convex hull of M ≥ 1 points in Rn .

Contributions. Section 2 is devoted to the generalization of (1) and provides sharp bounds on the localized Gaussian width of the convex hull of
M points in Rn , see Propositions 1 and 2 below. Sections 3 to 5 provide
statistical applications of the results of Section 2. Section 3 studies the Lasso
estimator and the convex aggregation problem in fixed-design regression. In
Section 4, we show that Empirical Risk Minimization achieves the minimax
rate for the persistence problem in the anisotropic setting. Finally, Section 5
provides results for bounded empirical processes and for the convex aggregation problem in density estimation.
2. Localized Gaussian width of a M -convex hull
The first contribution of the present paper is the following upper bound on
localized Gaussian width of the convex hull of M points in Rn .
Proposition 1. Let n ≥ 1 and M ≥ 2. Let T be the convex hull of M
points in Rn and assume that T ⊂ B2 . Let g be a centered Gaussian random
variable with covariance matrix In×n . Then for all s > 0,
 q

ℓ(T ∩ sB2 ) ≤ 4 log+

(4eM (s2

 √

∧ 1)) ∧ s n ∧ M


(2)

where log+ (a) = max(1, log a).
Proposition 1 is proved in the next two subsections. Inequality
√
ℓ(T ∩ sB2 ) ≤ s n ∧ M

(3)
√
is a direct consequence of the Cauchy-Schwarz inequality and E|P g|2 ≤ d
where P ∈ Rn×n is the orthogonal projection onto the linear span of T and
d ≤ (n ∧ M ) is the rank of P . The novelty of (2) is inequality
q

ℓ(T ∩ sB2 ) ≤ 4 log+ (4eM (s2 ∧ 1)).

(4)

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

3

Inequality (4) was known for the ℓ1 -ball T = {u ∈ Rn : |u|1 ≤ 1} [14], but
to our knowledge (4) is new for general M -convex hulls. If T is the ℓ1 -ball,
then the bound (2) is sharp up to numerical constants [14], [21, Section 4.1].
The above result does not assume any type of Restricted Isometry Property (RIP). The following proposition shows that (4) is essentially sharp
provided that the vertices of T satisfies a one-sided RIP of order 2/s2 .
Proposition 2. Let n ≥ 1 and M ≥ 2. Let g be a centered Gaussian
random variable with covariance matrix In×n . Let s ∈ (0, 1] and assume for
simplicity that m = 1/s2 is a positive integer such that m ≤ M/5. Let T be
the convex hull of the 2M points {±µ1 , ..., ±µM } where µ1 , ..., µM ∈ S n−1 .
Assume that for some real number κ ∈ (0, 1) we have
for all θ ∈ RM such that |θ|0 ≤ 2m,

κ|θ|2 ≤ |µθ |2
where µθ =

PM

j=1 θj µj .

Then
s



√
M s2
ℓ(T ∩ sB2 ) ≥ ( 2/4)κ log
.
5

(5)

The proof of Proposition 2 is given in Appendix A.
2.1. A refinement of Maurey’s argument
This subsection provides the main tool to derive the upper bound (4). Define
the simplex in RM by
n

ΛM = θ ∈ RM ,

M
X

j=1

θj = 1,

o

∀j = 1 . . . M, θj ≥ 0 .

(6)

Let m ≥ 1 be an integer, and let
Q(θ) = θ T Σθ,
where Σ = (Σjj ′ )j,j ′ =1,...,M is a positive semi-definite matrix of size M . Let
θ̄ ∈ ΛM be a deterministic vector such that Q(θ̄) is small. Maurey’s argument [27] has been used extensively to prove the existence of a sparse vector
θ̃ ∈ ΛM such that Q(θ̃) is of the same order as that of Q(θ̄). Maurey’s
argument uses the probabilistic method to prove the existence of such θ̃. A
sketch of this argument is as follows.

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

4

Define the discrete set ΛM
m as
ΛM
m

:=

(

m
1 X
uk , u1 , ..., um ∈ {e1 , ..., eM } ,
m k=1

)

(7)

where (e1 , ..., eM ) is the canonical basis in RM . The discrete set ΛM
m is a
subset of the simplex ΛM that contains only m-sparse vectors.
Let (e1 , ..., eM ) be the canonical basis in RM . Let Θ1 , ..., Θm be i.i.d.
random variables valued in {e1 , ..., eM } with distribution
P (Θk = ej ) = θ̄j

for all k = 1, ..., m.

(8)

Next, consider the random variable
θ̂ =

m
1 X
Θk .
m k=1

(9)

The random variable θ̂ is valued in ΛM
m and is such that EΘ [θ̂] = θ̄, where
EΘ denotes the expectation with respect to θ̂. Then a bias-variance decomposition yields
EΘ [θ̂] ≤ Q(θ̄) + R2 /m,

Q(θ) ≤
where R > 0 is a constant such that maxj=1,...,M Σjj ≤ R2 . As minθ∈ΛM
m
M
EΘ [θ̂], this yields the existence of θ̃ ∈ Λm such that
Q(θ̃) ≤ Q(θ̄) + R2 /m.
If m is chosen large enough, the two terms Q(θ̄) and R2 /m are of the same
order and we have established the existence of an m-sparse vector θ̃ so that
Q(θ̃) is not much substantially larger than Q(θ̄).
For our purpose, we need to refine this argument by controlling the deviation of the random variable Q(θ̂). This is done in Lemma 3 below.
M → [0, +∞) be a
Lemma 3. Let m ≥ 1 and define ΛM
m by (7). Let F : R
convex function. For all θ ∈ RM , let

Q(θ) = θ T Σθ,
where Σ = (Σjj ′ )j,j ′ =1,...,M is a positive semi-definite matrix of size M . Assume that the diagonal elements of Σ satisfy Σjj ≤ R2 for all j = 1, ..., M .
Then for all t > 0,
sup
θ∈ΛM :Q(θ)≤t2

F (θ) ≤

Z

1

+∞

"

max

2
2
θ∈ΛM
m : Q(θ)≤x(t +R /m)

#

F (θ)

dx
.
x2

(10)

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

5

In the next sections, it will be useful to bound from above the quantity
F (θ) maximized over ΛM subject to the constraint Q(θ) ≤ t2 . An interpretation of (10) is as follows. Consider the two optimization problems
maximize F (θ)
maximize F (θ)

for θ ∈ ΛM

for θ ∈ ΛM
m

subject to Q(θ) ≤ t2 ,

subject to Q(θ) ≤ Y (t2 + R2 /m),

for some Y ≥ 1. Equation (10) says that the optimal value of the first
optimization problem is smaller than the optimal value of the second optimization problem averaged over the distribution of Y given by the density
y 7→ 1/y 2 on [1, +∞). The second optimization problem above is over the
2
2
discrete set ΛM
m with the relaxed constraint Q(θ) ≤ Y (t + R /m), hence we
have relaxed the constraint in exchange for discreteness. The discreteness of
the set ΛM
m will be used in the next subsection for the proof of Proposition 1.
Proof of Lemma 3. The set {θ ∈ ΛM : Q(θ) ≤ t2 } is compact. The function
F is convex with domain RM and thus continuous. Hence the supremum in
the left hand side of (10) is achieved at some θ̄ ∈ ΛM such that Q(θ̄) ≤ t2 .
Let Θ1 , ..., Θm , θ̂ be the random variable defined in (8) and (9) above. Denote
by EΘ the expectation with respect to Θ1 , ..., Θm . By definition, θ̂ ∈ ΛM
m
and EΘ θ̂ = θ̄. Let E = EΘ [Q(θ̂)]. A bias-variance decomposition and the
independence of Θ1 , ..., Θm yield
E := EΘ [Q(θ̂)] = Q(θ̄) + EΘ (θ̂ − θ̄)T Σ(θ̂ − θ̄),
1
= Q(θ̄) + EΘ [(Θ1 − θ̄)T Σ(Θ1 − θ̄)].
m
Another bias-variance decomposition yields
EΘ (Θ1 − θ̄)T Σ(Θ1 − θ̄) = EΘ [Q(Θ1 )] − Q(θ̄) ≤ EΘ Q(Θ1 ) ≤ R2 ,
where we used that Q(·) ≥ 0 and that Θ1 ΣΘ1 ≤ R2 almost surely. Thus
E = EΘ [Q(θ̂)] ≤ Q(θ̄) + R2 /m ≤ t2 + R2 /m.

(11)

Define the random variable X = Q(θ̂)/E, which is nonnegative and satisfifes ER Θ [X] = 1. By Markov inequality, it holds that PΘ (X > t) ≤
1/t = 1+∞ (1/x2 )dx. Define the random variable Y by the density function x → 1/x2 on [1, +∞). Then we have PΘ (X > t) ≤ P(Y > t) for any
t > 0, so by stochastic dominance, there exists a rich enough probability
space Ω and random variables X̃ and Ỹ defined on Ω such that X̃ and X
have the same distribution, Ỹ and Y have the same distribution, and X̃ ≤ Ỹ
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

6

almost surely on Ω (see for instance Theorem 7.1 in [12]). Denote by EΩ the
expectation sign on the probability space Ω.
By definition of θ̄ and θ̂, using Jensen’s inequality, Fubini’s Theorem and
the fact that θ̂ ∈ ΛM
m we have
sup
θ∈ΛM :Q(θ)≤t2

F (θ) = F (θ̄) = F (EΘ [θ̂]) ≤ EΘ [F (θ̂)] ≤ EΘ [g(Q(θ̂)/E)]

where g(·) is the nondecreasing function g(x) = maxθ∈ΛM
F (θ). The
m :Q(θ)≤xE
right hand side of the previous display is equal to to EΘ [g(X)]. Next, we use
the random variables X̃ and Ỹ as follows:
EΘ [g(X)] = EΩ [g(X̃)] ≤ EΩ [g(Ỹ )] =

Z

1

+∞

g(x)
dx.
x2

Combining the previous display and (11) completes the proof.
2.2. Proof of (4)
We are now ready to prove Proposition 1. The main ingredients are Lemma 3
and the following upper bound on the cardinal of ΛM
m
log |ΛM
m|

!

M +m−1
2M
= log
≤ log
m
m

!

≤ m log



2eM
m



.

(12)

Proof of (4). If s2 < 1/M then by (3) we have ℓ(T ∩ sB2 ) ≤ 1, hence (4)
holds. Thus it is enough to focus on the case s2 ≥ 1/M .
Let r = min(s, 1) and set m = ⌊1/r 2 ⌋, which satisfies 1 ≤ m ≤ M . As T
is the convex hull of M points, let µ1 , ..., µM ∈ Rn be such that
T = convex hull of {µ1 , ..., µM } = {µθ , θ ∈ ΛM },
M
where µθ = M
j=1 θj µj for θ ∈ Λ .
Let Q(θ) = |µθ |22 for all θ ∈ RM . This is a polynomial of order 2, of
the form Q(θ) = θ T Σθ, where Σ is the Gram matrix with Σjk = µTk µj for
all j, k = 1, ..., M . As we assume that T ⊂ B2 , the diagonal elements of Σ
satisfy Σjj ≤ 1. For all θ ∈ RM , let F (θ) = g T µθ . Applying Lemma 3 with
the above notation, R = 1, m = ⌊1/r 2 ⌋ and t = r, we obtain

P

E

sup
θ∈ΛM :Q(θ)≤r 2

T

g µθ ≤ E

Z

1

+∞

"

max

2
θ∈ΛM
m : Q(θ)≤x(r +1/m)

#

F (θ)

dx
.
x2

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

7

By definition of m, r 2 ≤ 1/m so that x(r 2 + 1/m) ≤ 2x/m. Using Fubini
Theorem and a bound on the expectation of the maximum of |ΛM
m | centered
Gaussian random variables with variances bounded from above by 2x/m,
we obtain that the right hand side of the previous display is bounded from
above by
Z

1

+∞

1
x2

s

q
4x log |ΛM
m|
dx ≤ log(2eM/m)
m

Z

+∞
1

2
x3/2

dx.

where we used the bound
(12). To complete the proof of (4), notice that we
R
2
dx = 4.
have 1/m ≤ 2r 2 and 1+∞ x3/2
3. Statistical applications in fixed-design regression
Numerous works have established a close relationship between localized
Gaussian widths and the performance of statistical and compressed sensing procedures. Some of these works are reviewed below.
• In a regression problem with random design where the design and the
target are subgaussian, Lecué and Mendelson [21] established that two
quantities govern the performance of empirical risk minimizer over a
convex class F. These two quantities are defined using the Gaussian
width of the class F intersected with an L2 ball [21, Definition 1.3],
• If p, p′ > 1 are such that p′ ≤ p ≤ +∞ and log(2n)/(log(2en) ≤ p′ .
Gordon et al. [14] provide precise estimates of ℓ(Bp ∩ sBp′ ) where
Bp ⊂ Rn is the unit Lp ball and sBp′ is the Lp′ ball of radius s > 0.
These estimates are then used to solve the approximate reconstruction
problem where one wants to recover an unknown high dimensional
vector from a few random measurements [14, Section 7].
• Plan et al. [28] shows that in the semiparametric single index model,
if the signal is known to belong to some star-shaped set T ⊂ Rn , then
the Gaussian width of T and its localized version characterize the gain
obtained by using the additional information that the signal belongs
to T , cf. Theorem 1.3 in [28].
• Finally, Chatterjee [9] exhibits connection between localized Gaussian
widths and shape-constrained estimation.
These results are reminiscent of the isomorphic method [17, 3, 2], where localized expected supremum of empirical processes are used to obtain upper
bounds on the performance of Empirical Risk Minimization (ERM) procedures. These results show that Gaussian width estimates are important to
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

8

understand the statistical properties of estimators in many statistical contexts.
In Proposition 1, we established an upper bound on the Gaussian width of
M -convex hulls. We now provide some statistical applications of this result
in regression with fixed-design. We will use the following Theorem from [7].
Theorem 4 ([7]). Let K be a closed convex subset of Rn and ξ ∼ N (0, σ 2 In×n ).
Let f 0 ∈ Rn be an unknown vector and let y = f 0 + ξ. Denote by f ∗0 the
projection of f 0 onto K. Assume that for some t∗ > 0,




t2
1 
ξ T (u − f ∗0 ) ≤ ∗ .
E
sup
n
2
u∈K: 1 |f ∗ −u|2 ≤t2∗
n

0

(13)

2

Then for any x > 0, with probability greater than 1 − e−x , the Least Squares
estimator fˆ = argminf ∈K |y − f |22 satisfies
1
4σ 2 x
1 ˆ
|f − f 0 |22 ≤ |f ∗0 − f 0 |22 + 2t2∗ +
.
n
n
n
Hence, to prove an oracle inequality of the form (14), it is enough to prove
the existence of a quantity t∗ such that (13) holds. If the convex set K in
the above theorem is the convex hull of M points, then a quantity t∗ is given
by the following proposition.
Proposition 5. Let σ 2 > 0, R > 0, n ≥ 1 and M ≥ 2. Let µ1 , ..., µM ∈ Rn
such that n1 |µj |22 ≤ R2 for all j = 1, ..., M . For all θ ∈ ΛM , let µθ =
P
a centered Gaussian random variable with covarij=1,...,M θj µj . Let g be √
ance matrix σ 2 In×n . If R n ≤ M σ then the quantity
t2∗ = 31σR

v


u
σ
u log eM
√
t
R n

n

satisfies

1
E
sup
n θ∈ΛM : 1 |µ
n

2
2
θ |2 ≤t∗

g T µθ ≤

t2∗
,
2

(14)

provided that t∗ ≤ R.
Proof. Inequality
q
1
√ E
(σg)T µθ ≤ 4σR log (4eM min(1, r 2 /R2 )).
sup
n θ∈ΛM : 1 |µθ |2 ≤r2
n

2

is a reformulation of Proposition 1 using the notation of Proposition 5. Thus,
in order to prove (14), it is enough to establish that for γ = 31 we have
q

√ 


4eM σγ log(eM σ/(R n))
eM σ
γ2


√
√
log
≤
(∗) := 64 log
.
(15)
R n
4
R n
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

9

√
As 1 ≤ log(eM σ/(R n)) and log t ≤ t for all t > 0, the left hand side of the
previous display satisfies
√ 
eM σ
1
√
(∗) ≤ 64 log
+ log(4γ) + log log(eM σ/(R n)) ,
R n
2


eM σ
√
.
≤ 64(3/2 + log(4γ)) log
R n








Thus (15) holds if 64(3/2 + log(4γ)) ≤ γ 2 /4, which is the case if the absolute
constant is γ = 31.
Inequality (14) establishes the existence of a quantity t∗ such that
t2
1
E
sup
g T µθ ≤ ∗ ,
n µ∈T : 1 |µ|2 ≤t2∗
2
n

(16)

2

where T is the convex hull of µ1 , ..., µM . Consequences of (16) and Theorem 4 are given in the next subsections.
We now introduce two statistical frameworks where the localized Gaussian
width of an M -convex hull has applications: the Lasso estimator in highdimensional statistics and the convex aggregation problem.
3.1. Convex aggregation
Let f 0 ∈ Rn be an unknown regression vector and let y = f 0 + ξ be
an observed random vector, where ξ satisfies E[ξ] = 0. Let M ≥ 2 and
let f 1 , ..., f M be deterministic vectors in Rn . The set {f 1 , ..., f M } will be
referred to as the dictionary. For any θ = (θ1 , ..., θM )T ∈ RM , let f θ =
PM
M is given, the goal of the aggregation problem
j=1 θj f j . If a set Θ ⊂ R
induced by Θ is to find an estimator fˆ constructed with y and the dictionary
such that


1
1 ˆ
2
2
|f − f 0 |2 ≤ inf
|f θ − f 0 |2 + δn,M,Θ ,
(17)
θ∈Θ n
n
either in expectation or with high probability, where δn,M,Θ is a small quantity. Inequality (17) is called a sharp oracle inequality, where "sharp" means
that in the right hand side of (17), the multiplicative constant of the term
inf θ∈Θ n1 |f θ − f 0 |22 is 1. Similar notations will be defined for regression with
random design and density estimation. Define the simplex in RM by (6).
The following aggregation problems were introduced in [26, 34].

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

10

• Model Selection type aggregation with Θ = {e1 , ..., eM }, i.e., Θ is the
canonical basis of RM . The goal is to construct an estimator whose
risk is as close as possible to the best function in the dictionary. Such
results can be found in [34, 22, 1] for random design regression, in
[23, 10, 5, 11] for fixed design regression, and in [16, 6] for density
estimation.
• Convex aggregation with Θ = ΛM , i.e., Θ is the simplex in RM . The
goal is to construct an estimator whose risk is as close as possible to the
best convex combination of the dictionary functions. See [34, 20, 19, 33]
for results of this type in the regression framework and [29] for such
results in density estimation.
• Linear aggregation with Θ = RM . The goal is to construct an estimator whose risk is as close as possible to the best linear combination of
the dictionary functions, cf. [34, 33] for such results in regression and
[29] for such results in density estimation.
One may also define the Sparse or Sparse Convex aggregation problems:
construct an estimator whose risk is as close as possible to the best sparse
combination of the dictionary functions. Such results can be found in [31, 30,
33] for fixed design regression and in [24] for regression with random design.
These problems are out of the scope of the present paper.
A goal of the present paper is to provide a unified argument that shows
that empirical risk minimization is optimal for the convex aggregation problem in density estimation, regression with fixed design and regression with
random design.
Theorem 6. Let f 0 ∈ Rn , let ξ ∼ N (0, σ 2 In×n ) and define y = f 0 + ξ. Let
P
T
M
f 1 , ..., f M ∈ Rn and let f θ = M
j=1 θj f j for all θ = (θ1 , ..., θM ) ∈ R .
Let
θ̂ ∈ argmin |f θ − y|22 .
θ∈ΛM

Then for all x > 0, with probability greater than 1 − exp(−x),
1
4σ 2 x
1
|f θ̂ − f 0 |22 ≤ min |f θ − f 0 |22 + 2t2∗ +
,
n
n
θ∈ΛM n


√
√
σ/(R n))
4σ2 M 31σR log(eM
2
√
where t∗ = min
and R2 = 14 maxj=1,...,M n1 |f j |22 .
n ,
n
Proof of Theorem 6. Let V be the linear span of f 1 , ..., f M and let P ∈

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

11

Rn×n be the orthogonal projector onto V . If t2∗ = 4σ 2 M/n, then
1
ξT v =
E
sup
n v∈V : 1 |v|2 ≤t2∗
n

2

s

t2∗
E|P ξ|2 ≤
n

s

t2∗ q
E|P ξ|22 =
n

s

t2∗ σ 2 M
= t2∗ /2.
n

Let K be the convex hull of f 1 , ..., f M . Let f ∗0 be the convex projection of
f 0 onto K. We apply Proposition 5 to K − f ∗0 which is a convex hull of M
points, and for all v ∈ K, n1 |v|22 ≤ R2 . By (21) and (14), the quantity t∗
satisfies (13). Applying Theorem 4 completes the proof.
3.2. Lasso
We consider the following regression model. Let x1 , ..., xM ∈ Rn and assume
that n1 |xj |22 ≤ 1 for all j = 1, ..., M . We will refer to x1 , ..., xM as the
covariates. Let X be the matrix of dimension n×M with columns x1 , ..., xM .
We observe
y = f 0 + ξ,
ξ ∼ N (0, σ 2 In×n ).
(18)
where f 0 ∈ Rn is an unknown mean. The goal is to estimate f 0 using the
design matrix X.
Let R > 0 be a tuning parameter and define the constrained Lasso estimator [32] by
β̂ ∈ argmin |y − Xβ|22 .
(19)
β∈R M :|β|1 ≤R

Our goal will be to study the performance of the estimator (19) with respect
to the prediction loss
1
|f − Xβ̂|22 .
n 0
Let x1 , ..., xM ∈ Rn and assume that n1 |xj |22 ≤ 1 for all j = 1, ..., M . Let
X be the matrix of dimension n × M with columns x1 , ..., xM .
Theorem 7. Let R > 0 be a tuning parameter and consider the regression
model (18). Define the Lasso estimator β̂ by (19). Then for all x > 0, with
probability greater than 1 − exp(−x),
1
4σ 2 x
1
|Xβ̂ − f 0 |22 ≤
min
|Xβ − f 0 |22 + 2t2∗ +
,
n
n
β∈R M :|β|1 ≤R n
where t2∗ = min



√

4σ2 rank(X) 62σR
,
n

(20)


√
log(2eM σ/(R n))
√
.
n

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

12

Proof of Theorem 7. Let V be the linear span of x1 , ..., xM and let P ∈
Rn×n be the orthogonal projector onto V . If t2∗ = 4σ 2 rank(X)/n, then
1
ξT v =
E
sup
n v∈V : 1 |v|2 ≤t2∗
n

2

s

t2∗
E|P ξ|2 ≤
n

s

t2∗ q
E|P ξ|22 =
n

s

t2∗ σ 2 rank(X)
= t2∗ /2.
n

(21)
Let K be the convex hull of {±Rx1 , ..., ±RxM }, so that K = {Xβ : β ∈
RM : |β|1 ≤ R}. Let f ∗0 be the convex projection of f 0 onto K. We apply
Proposition 5 to K − f ∗0 which is a convex hull of 2M points of empirical
norm less or equal to R2 . By (21) and (14), the quantity t∗ satisfies (13).
Applying Theorem 4 completes the proof.
The lower bound [30, Theorem 5.4 and (5.25)] states that there exists an
√
absolute constant C0 > 0 such that the following holds. If log(1+eM/ n) ≤
√
C0 n, then there exists a design matrix X such that for all estimator fˆ,


 σ 2 rank(X)

1
1
EXβ |Xβ−fˆ|22 ≥
min 

n
C
M
0
β∈R :|β|1 ≤R
sup

n

, σR

v

u
u log 1 +
t

n

eM
√σ
R n



,


where for all f 0 ∈ Rn , Ef 0 denotes the expectation with respect to the
distribution of y ∼ N (f 0 , σ 2 In×n ). Thus, Theorem 7 shows that the Least
Squares estimator over the set {Xβ, β ∈ RM : |β|1 ≤ R} is minimax optimal. In particular, the right hand side of inequality (20) cannot be improved.
4. The anisotropic persistence problem in regression with
random design
Consider n iid observations (Yi , Xi )i=1,...,n where (Yi )i=1,...,n are real valued
and the (Xi )i=1,..,n are design random variables in RM with E[Xi XiT ] = Σ
for some covariance matrix Σ ∈ RM ×M . We consider the learning problem
over the function class
n

fβ :

fβ (x) = xT β for some β ∈ RM with |β|1 ≤ R

o

for a given constant R > 0. We consider the Emprical Risk Minimizer defined
by
β̂ =

argmin
β∈R M :|β|

1 ≤R

n
X
i=1

(Yi − β T Xi )2

(22)

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

13

This problem is sometimes referred to as the persistence problem or the
persistence framework [15, 4]. The prediction risk of fβ̂ is given by
R(fβ̂ ) = E[(fβ̂ (X) − Y ) | (Xi , Yi )i=1,...,n],
where (X, Y ) is a new observation distributed as (X1 , Y1 ) and independent
from the data (Xi , Yi )i=1,...,n . Define also the oracle β ∗ by
β∗ =

argmin

R(β)

(23)

β∈R M :|β|1 ≤R

and define σ > 0 by
σ = kY − X T β ∗ kψ2 ,

(24)
√
where the subgaussian norm k·kψ2 is defined by kZkψ2 = supp≥1 E[|Z|p ]1/p / p
for any random variable Z (see Section 5.2.3 in [35] for equivalent definitions
of the ψ2 norm).
To analyse the above learning problem, we use the machinery developed
by Lecué and Mendelson [21] to study learning problems over subgaussian
classes. Consider the two quantities
(

rn (γ) = inf r > 0 : E
(

sn (γ) = inf s > 0 : E

sup
β:|β|1 ≤2R, E[(GT β)2 ]≤s2

T

√

)

β G ≤ γr n ,

sup
β: |β|1 ≤2R, E[(GT β)2 ]≤s2

β T G ≤ γs

2√

(25)
)

n/σ ,

(26)

where G ∼ N (0, Σ). In the present setting, Theorem A from Lecué and
Mendelson [21] reads as follows.
Theorem 8 (Theorem A in Lecué and Mendelson [21]). There exist absolute
constants c1 , c2 , c4 > 0 such that the following holds. Let R > 0. Consider
iid observations (Xi , Yi ) with E[Xi XiT ] = Σ. Assume that the design random
vectors Xi are subgaussian with respect to the covariance matrix Σ in the
sense that kXiT τ kψ2 ≤ 10|Σ1/2 τ |2 for any τ ∈ Rp . Define β ∗ by (23) and σ
by (24). Assume that the diagonal elements of Σ are no larger than 1. Then,
there exists absolute constants c0 , c1 , c2 , c3 > 0 such that the estimator β̂
defined in (22) satisfies
R(fβ̂ ) ≤ R(fβ∗ ) + max(s2n (c1 ), rn2 (c2 )),
with probability at least 1 − 6 exp(−c4 n min(c2 , sn (c1 ))).
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

14

In the isotropic case (Σ = IM ), [25] proves that
rn2 (γ)

≤

(

c3 R2
n

0

log( c3nM ) if n ≤ c4 M
if n > c4 M,

(27)

for some constants c3 , c4 > 0 that only depends on γ, while
s2n (γ) ≤


q
5 Rσ
 c√
log( c√5 M σ )
n
 c5 σ 2 M
n

nR

if n ≤ c6 σ 2 M 2 /R2

if n > c6 σ 2 M 2 /R2 ,

(28)

for some constants c5 , c6 > 0 that only depend on γ.
Using Proposition 1 and Equation (9) above lets us extend these bounds
to the anisotropic case where Σ is not proportional to the identity matrix.
Proposition 9. Let R > 0, let G ∼ N (0, Σ) and assume that the diagonal
elements of Σ are no larger than 1. For any γ > 0, define rn (γ) and sn (γ)
by (26) and (25). Then for any γ > 0, there exists constants c3 , c4 , c5 , c6 > 0
that depend only on γ such that (28) and (27) hold.
The proof of Proposition 9 will be given at the end of this subsection.
The primary improvement of Proposition 1 over previous results is that this
result is agnostic to the underlying covariance structure. This lets us handle
the anisotropic case with Σ 6= IM in the above proposition.
Proposition 9 combined with Theorem 8 lets us obtained the minimax rate
of estimation for the persistence problem in the anisotropic case. Although
the minimax rate was previously obtained in the isotropic case, we are not
aware of a previous result that yields this rate for general covariance matrices
Σ 6= IM .
Proof of Proposition 9. In this proof, c > 0 is an absolute constant whose
value may change from line to line. Let γ > 0. We first bound rn (γ) from
above. Let r > 0 and define
Tr (R) = {β ∈ Rp : |β|1 ≤ 2R, β T Σβ ≤ r 2 }.
The random variable X ∼ N (0, Σ) has the same distribution as Σ1/2 g where
g ∼ N (0, IM ). Thus, the expectation inside the infimum in (25) is equal to
E sup β T Σ1/2 g.

(29)

β∈Tr (R)

To bound rn (γ) from above, it is enough to find some r > 0 such that (29)
√
is bounded from above by γr n.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

15

By the Cauchy-Schwarz
inequality, the right hand side is bounded from
√
√
above by r M , which is smaller than γr n for all small enough s > 0
provided that n > c4 M for some constant c4 that only depends on γ.
We now bound rn (γ) from above in the regime n ≤ c4 M . Let u1 , ..., uM be
the columns of Σ and let T̃ be the convex hull of the 2M points {±u1 , ..., ±uM }.
Using the fact that Tr (R) = 2RTr/(2R) (1) ⊂ 2R(T̃ ∩ (r/(2R))B2 ), the right
hand side of the previous display is bounded from above by
q

r 2
2R ℓ(T̃ ∩ (r/R))B2 ) ≤ 8R log+ (4eM ( 2R
) ),

(30)

where we used Proposition 1 for
p the last inequality. By simple algebra, one
can show that if r = c3 (γ) √Rn log(c3 (γ)M/n) for some large enough constant c3 (γ) that only depends on γ, then the right hand side of (30) is
√
bounded from above by γr n.
We now bound sn (γ) from above. Let s > 0. By definition of sn (γ), to
prove that sn (γ) ≤ s, it is enough to show that
σEξ

sup β T Σ1/2 g
β∈Ts (R)

√
is smaller than γs2 n. We use Proposition 1 to show that the right hand
side of the previous display is bounded from above by
q

 √
s 2
) ) .
cσ min s M , R log+ (4eM ( 2R

By simple algebra very similar to that of the proof of Proposition 5, we obtain
that if s2 equals the right hand side of (28) for large enough c5 = c5 (γ) and
c6 = c6 (γ), then the right hand side of the previous display is bounded from
√
above by γs2 n. This completes the proof of (28).
5. Bounded empirical processes and density estimation
We now prove a result similar to Proposition 1 for bounded empirical processes indexed by the convex hull of M points. This will be useful to study
the convex aggregation problem for density estimation. Throughout the paper, ε1 , ..., εn are i.i.d. Rademacher random variables that are independent
of all other random variables.
Proposition 10. There exists an absolute constant c > 0 such that the following holds. Let M ≥ 2, n ≥ 1 be integers and let b, R, L > 0 be real numbers.
Let Q(θ) = θ T Σθ for some semi-positive matrix Σ. Let Z1 , ..., Zn be i.i.d.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

16

random variables valued in some measurable set Z. Let h1 , ..., hM : Z → R
P
T
M
be measurable functions. Let hθ = M
j=1 θj hj for all θ = (θ1 , ..., θM ) ∈ R .
Assume that almost surely
Q(ej ) = Σjj ≤ R2 ,

|hj (Z1 )| ≤ b,

E[h2θ (Z1 )] ≤ LQ(θ),

(31)

√
for all j = 1, ..., M and all θ ∈ ΛM . Then for all r > 0 such that R/ M ≤
r ≤ R we have
E

"

sup

θ∈ΛM : Q(θ)≤r 2

where F (θ) =



√

#

F (θ) ≤ c max  LR

1 Pn
i=1 εi hθ (Zi )|
n|

s

log(eM r 2 /R2 )
n

,

bR2 log(eM r 2 /R2 )
r2n
(32)

for all θ ∈



,

RM .

Proof of Proposition 10. Let m = ⌊R2 /r 2 ⌋ ≥ 1. The function F is convex
since it can be written as the maximum of two linear functions. Applying
Lemma 3 with the above notation and t = r yields
E

sup
θ∈ΛM :Q(θ)≤r 2

F (θ) ≤ E

Z

+∞

M (x)

1

dx
=
x2

Z

+∞

1

E [M (x)]

dx
.
x2

(33)

where the second inequality is a consequence of Fubini’s Theorem and for
all x ≥ 1,
M (x) =
max
F (θ).
2
2
θ∈ΛM
m : Q(θ)≤x(r +R /m)

Using (31) and the Rademacher complexity bound for finite classes given in
[18, Theorem 3.5], we obtain that for all x ≥ 1,
s

E[M (x)] ≤ c′ max 



M
Lx(r 2 + R2 /m) log |ΛM
m | b log |Λm | 
,
,
n
n

(34)

M
where c′ > 0 is a numerical constant and |ΛM
m | is the cardinal of the set Λm .
M
By definition of m we have r 2 ≤ R2 /m. The cardinal |ΛM
m | of the set Λm is
bounded from above by the right hand side of (12).
Combining
inequality
R +∞ dx
R +∞ dx
(33), inequality (34), the fact that the integrals 1
are
x2 and 1
x3/2
finite, we obtain

E

sup
θ∈ΛM :Q(θ)≤r 2



√

F (θ) ≤ c′′ max  LR

s



log(eM/m) bm log(eM/m) 
,
n
n

for some absolute constant c′′ > 0. By definition of m, we have R2 /(2r 2 ) ≤
m ≤ R2 /r 2 . A monotonicity argument completes the proof.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

17

Next, we show that Proposition 10 can be used to derive a condition
similar to (14) for bounded empirical processes. To bound from above the
performance of ERM procedures in density estimation, Theorem 13 in the
appendix requires the existence of a quantity r∗ > 0 such that
E

"

sup

θ∈ΛM : Q(θ)≤r∗2

#

F (θ) ≤

r∗2
,
16

(35)

where F is the function defined in Proposition 10 above.
To obtain such quantity r∗ > 0 under√the assumptions of Proposition 10,
we proceed as follows. Let K = max(b, L) and assume that
√
M K > R n.
q
√
Define r 2 = CKR log(eM K/(R n)) where C ≥ 1 is a numerical constant
that will be chosen later. We now bound from above the right hand side of
(32). We have
√
√
log(eM r 2 /R2 ) ≤ log(C) + log(eM K/(R n)) + (1/2) log log(eM K/(R n))
√
≤ (log(C) + 3/2) log(eM K/(R n)),
where for the last inequality we used that log log(u) ≤ log u for all u > 1 and
√
√
that log(C) ≤ log(C) log(eM K/(R n)), since C ≥ 1 and M K/(R n) ≥ 1.
Thus, the right hand side of (32) is bounded from above by
c max

p

log(C) + 3/2 log(C) + 3/2
,
C
C2

!

r2.

It is clear that the above quantity is bounded from above by r 2 /16 if the
numerical constant C is large enough. Thus we have proved that as long as
√
M K > R n, inequality (35) holds for
s
√
log(eM K/(R n))
r∗2 = CRK
,
n
where C ≥ 1 is a numerical constant.
ERM and convex aggregation in density estimation
The minimax optimal rate for the convex aggregation problem is known to
be of order

v


u
u log eM
√
M t
n 
 ,

φC
M (n) := min 

n
n
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

18

for regression with fixed design [30] and regression with random design [34]
√
√
√
if the integers M and n satisfy eM σ ≤ R n exp( n) or equivalently
φC
M (n) ≤ 1. The arguments for the convex aggregation lower bound from
[34] can be readily applied to density estimation, showing that the rate
φC
M (n) is a lower bound on the optimal rate of convex aggregation for density
estimation.
We now use the results of the previous sections to show that ERM is
optimal for the convex aggregation problem in regression with fixed design,
regression with random design and density estimation.
Theorem 11. There exists an absolute constant c > 0 such that the following holds. Let (Z, µ) be a measurable space with measure µ. Let p0 be
an unknown density with respect to the measure µ. Let Z1 , ..., Zn be i.i.d.
random variables valued in Z with density p0 . Let p1 , ..., pM ∈ L2 (µ) and let
P
T
M
pθ = M
j=1 θj pj for all θ = (θ1 , ..., θM ) ∈ R . Let
θ̂ ∈ argmin
θ∈ΛM

Z

p2θ dµ

n
2X
pθ (Zi ) .
−
n i=1

!

Then for all x > 0, with probability greater than 1 − exp(−x),
Z

(pθ̂ −p0 )2 dµ ≤ min

where R2 =

θ∈ΛM

1
4

Z


v
√
u
eM √b∞
u
p t log( R n )  88b∞ x
 b∞ M
+
b∞
(pθ −p0 )2 dµ+c max 
,
R
,
 n

n
3n

maxj=1,...,M



R

p2j dµ and b∞ = maxj=0,1,...,M kpj kL∞ (µ) .

√
If M b∞ ≤
Proof. It is a direct application of Theorem 13 in the appendix.
√
√
√
R n, a fixed point t∗ is given
by Lemma 14. If M b∞ > R n, we use
R ∗
Proposition 10 with Q(θ) = (p0 − pθ )2 , L = b∞ and b = b∞ . The bound
(35) yields the existence of a fixed point t∗ in this regime.
References
[1] Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates
for plug-in classifiers. Ann. Statist., 35(2):608–633, 04 2007. . URL
http://dx.doi.org/10.1214/009053606000001217.
[2] Peter L Bartlett and Shahar Mendelson. Empirical minimization. Probability Theory and Related Fields, 135(3):311–334, 2006.
[3] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local
rademacher complexities. Ann. Statist., 33(4):1497–1537, 08 2005. .
URL http://dx.doi.org/10.1214/009053605000000282.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

19

[4] Peter L Bartlett, Shahar Mendelson, and Joseph Neeman.
L1regularized linear regression: persistence and oracle inequalities. Probability theory and related fields, 154(1-2):193–224, 2012.
[5] Pierre C. Bellec.
Optimal bounds for aggregation of affine
estimators.
Annals of Statistics, to appear, 2017.
URL
https://arxiv.org/pdf/1410.0346v4.pdf.
[6] Pierre C. Bellec.
Optimal exponential bounds for aggregation
of density estimators. Bernoulli, 23(1):219–248, 2017. . URL
http://dx.doi.org/10.3150/15-BEJ742.
[7] Pierre C. Bellec. Sharp oracle inequalities for least squares estimators in
shape restricted regression. Annals of Statistics, to appear, 2017. URL
https://arxiv.org/pdf/1510.08029.pdf.
[8] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration
inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
[9] Sourav Chatterjee. A new perspective on least squares under convex constraint. Ann. Statist., 42(6):2340–2381, 12 2014. . URL
http://dx.doi.org/10.1214/14-AOS1254.
[10] D. Dai, P. Rigollet, and T. Zhang. Deviation optimal learning using
greedy Q-aggregation. The Annals of Statistics, 40(3):1878–1905, 2012.
[11] Arnak S. Dalalyan and Alexandre B. Tsybakov. Aggregation by
exponential weighting and sharp oracle inequalities. In Learning
theory, volume 4539 of Lecture Notes in Comput. Sci., pages 97–
111. Springer, Berlin, 2007. ISBN 978-3-540-72925-9.
. URL
http://dx.doi.org/10.1007/978-3-540-72927-3_9.
[12] Frank den Hollander. Probability theory: The coupling method.
[13] Christophe Giraud. Introduction to high-dimensional statistics, volume
138. CRC Press, 2014.
[14] Yehoram Gordon, Alexander E Litvak, Shahar Mendelson, and Alain
Pajor. Gaussian averages of interpolated bodies and applications to
approximate reconstruction. Journal of Approximation Theory, 149(1):
59–73, 2007.
[15] Eitan Greenshtein, Ya’Acov Ritov, et al.
Persistence in highdimensional linear predictor selection and the virtue of overparametrization. Bernoulli, 10(6):971–988, 2004.
[16] Anatoli Juditsky, Philippe Rigollet, and Alexandre B. Tsybakov. Learning by mirror averaging. The Annals of Statistics, 36(5):2183–2206,
2008.
[17] Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. Ann. Statist., 34(6):2593–2656, 12 2006.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

20

. URL http://dx.doi.org/10.1214/009053606000001019.
[18] Vladimir Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de SaintFlour XXXVIII-2008, volume 2033. Springer, 2011.
[19] Guillaume Lecué. Empirical risk minimization is optimal for the convex
aggregation problem. Bernoulli, 19(5B):2153–2166, 11 2013. . URL
http://dx.doi.org/10.3150/12-BEJ447.
[20] Guillaume Lecué and Shahar Mendelson. Aggregation via empirical
risk minimization. Probability theory and related fields, 145(3-4):591–
613, 2009.
[21] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes:
Upper and minimax bounds. arXiv preprint arXiv:1305.4825, 2013.
[22] Guillaume Lecué and Philippe Rigollet. Optimal learning with Qaggregation. Ann. Statist., 42(1):211–224, 2014.
[23] Gilbert Leung and Andrew R. Barron. Information theory and mixing
least-squares regressions. Information Theory, IEEE Transactions on,
52(8):3396–3410, 2006.
[24] K Lounici. Generalized mirror averaging and D-convex aggregation.
Mathematical methods of statistics, 16(3):246–259, 2007.
[25] Shahar Mendelson. Learning without concentration. arXiv preprint
arXiv:1401.0304, 2014.
[26] Arkadi Nemirovski. Topics in non-parametric statistics. In Lectures
on probability theory and statistics (Saint-Flour, 1998), volume 1738 of
Lecture Notes in Mathematics. Springer, Berlin, 2000.
[27] Gilles Pisier. Remarques sur un résultat non publié de b. maurey. Séminaire Analyse fonctionnelle, pages 1–12, 1980.
[28] Yaniv Plan, Roman Vershynin, and Elena Yudovina. High-dimensional
estimation with geometric constraints. arXiv preprint arXiv:1404.3749,
2014.
[29] Ph. Rigollet and A. B. Tsybakov. Linear and convex aggregation of
density estimators. Math. Methods Statist., 16(3):260–280, 2007. . URL
http://dx.doi.org/10.3103/S1066530707030052.
[30] Philippe Rigollet and Alexandre Tsybakov. Exponential screening and
optimal rates of sparse estimation. The Annals of Statistics, 39(2):731–
771, 2011.
[31] Philippe Rigollet and Alexandre B. Tsybakov. Sparse estimation by
exponential weighting. Statist. Sci., 27(4):558–575, 11 2012. URL
http://dx.doi.org/10.1214/12-STS393.
[32] Robert Tibshirani. Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society. Series B (Methodological),
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

21

pages 267–288, 1996.
[33] A.B. Tsybakov.
Aggregation and minimax optimality in highdimensional estimation. In Proceedings of the International Congress
of Mathematicians, Seoul, 2014. To appear.
[34] Alexandre B. Tsybakov. Optimal rates of aggregation. In Learning
Theory and Kernel Machines, pages 303–313. Springer, 2003.
[35] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Appendix A: Proof of the lower bound (5)
Proof of Proposition 2. By the Varshamov-Gilbert extraction lemma [13,
Lemma 2.5], there exist a subset Ω of {0, 1}M such that
|ω|0 = m,

|ω − ω ′ |0 > m,

log |Ω| ≥ (m/2) log(M/(5m))

for any distinct ω, ω ′ ∈ Ω.
For each ω ∈ Ω, we define s(ω) ∈ {−1, 0, 1}M , a signed version of ω,
as follows. Let ε1 , ..., εM be M iid Rademacher random variables. Then we
have
E[|

M
X

j=1

ωj εj µj |22 ] =

M
X

j=1

ωj |µj |22 = m.

Hence, there exists some s(ω) ∈ {−1, 0, 1}M with |s(ω)j | = ωj for all j =
1, ..., M such that |µs(ω) |22 ≤ m.
Define TΩ = {s2 µs(ω) , ω ∈ Ω}. Since s2 = 1/m, each element of TΩ is of
the form (1/m)(±µj1 ± ... ± µjm ) where µj1 , ..., µjm are m distinct elements
of {µ1 , ..., µM }, hence by convexity of T we have TΩ ⊂ T . By definition of
s(ω), it holds that TΩ ⊂ sB2 , and thus TΩ ⊂ T ∩ sB2 . For any two distinct
u, v ∈ TΩ ,
|u − v|22 ≥ κ2 s4 sup |s(ω) − s(ω ′ )|22 > κ2 s4 m = κ2 s2 ,
ω,ω ′

where the supremum is taken over any two distinct elements of Ω. By Sudakov’s inequality (see for instance [8, Theorem 13.4]) we have
√
p
√ q
ℓ(T ∩ sB2 ) ≥ ℓ(TΩ ) ≥ (1/2)κs log Ω ≥ 1/(2 2)κs m log(M/5m).

Since 1/m = s2 , the right hand side of the previous display is equal to the
right hand side of (5) and the proof is complete.
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

22

Appendix B: Local Rademacher complexities and density
estimation
In the last decade emerged a vast literature on local Rademacher complexities to study the performance of empirical risk minimizers (ERM) for general
learning problems, cf. [3, 2, 17] and the references therein. The following result is given in [3, Theorem 2.1]. Let ε1 , ..., εn be independent Rademacher
random variables, that are independent from all other random variables considered in the paper.
Theorem 12 (Bartlett et al. [3]). Let Z1 , ..., Zn be i.i.d. random variables
valued in some measurable space Z. Let H : Z → [−b∞ , b∞ ] be a class of
measurable functions. Assume that there is some v > 0 such that E[h(Z1 )2 ] ≤
v for all h ∈ H. Then for all x > 0, with probability greater than 1−exp(−x),
n
1X
εi h(Zi ) +
sup (P − Pn )h ≤ 4E sup
h∈H
h∈H n i=1

#

"

r

2vx 8b∞ x
+
.
n
3n

Theorem 12 is a straightforward consequence of Talagrand inequality. We
now explain how Theorem 12 can be used to derive sharp oracle inequalities
in density estimation.
Theorem 13. Let (Z, µ) be a measurable space with measure µ. Let p0 be an
unknown density with respect to the measure µ. Let Z1 , ..., Zn be i.i.d. random
variables valued in Z with density p0 . Let P
be a convex subset of RL2 (µ).
R
∗
Assume that there exists p0 ∈ P such that (p0 − p∗0 )2 dµ = inf p∈P (p0 −
p)2 dµ. Assume that for some t∗ > 0,


E

p∈P:

R sup∗

(p−p0 )2 dµ≤t2∗

n
1X

n

i=1



εi (p − p∗0 )(Zi ) ≤

t2∗
.
16

(36)

Assume that there exists an estimator p̂ such that almost surely,
p̂ ∈ argmin
p∈P

Z

n
1X
2p(Zi ) .
p dµ −
n i=1

!

2

Then for all x > 0, with probability greater than 1 − exp(−x),
Z

2

(p̂ − p0 ) dµ ≤ min
p∈P

Z

2

(p − p0 ) dµ + 2 max

t2∗ ,

4(kp0 kL∞ (µ) + 8b∞ /3)x
n

!

,

where b∞ = supp∈P kpkL∞ (µ) .
imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

23

Proof of Theorem 13. By optimality of p̂ we have
Z

2

(p̂ − p0 ) dµ ≤

Z

(p∗0 − p0 )2 dµ + 2Ξp̂ .

where for all p ∈ P, Ξp is the random variable
Ξp = (P − Pn )(p − p∗0 ) −

1
2

Z

(p∗0 − p)2 dµ.





Let ρ = max t2∗ , 4(kp0 kL∞ (µ) + 8b∞ /3)x/n and define


H = h = p∗0 − p for some p ∈ P such that



Z

h2 dµ ≤ ρ .

The class H is convex, 0 ∈ H and t2∗ ≤ ρ so that h ∈ H implies
any linear form L,
1
1
sup
L(h), ≤ 2
R
ρ h∈H: h2 dµ≤ρ
t∗

!

t2∗
sup
L
h
R
ρ
h∈H: h2 dµ≤ρ

≤

1
t2∗

h∈H:

t2∗
ρh

Rsup

∈ H. For
L(h)

h2 dµ≤t2∗

so that by taking expectations, (36) holds if t2∗ is replaced by ρ.
For any h ∈ H, E[h(Z1 )2 ] ≤ kp0 kL∞ (µ) ρ and h is valued in [−2b∞ , 2b∞ ]
µ-almost surely. We apply Theorem 12 to the class H. This yields that with
probability greater than 1 − e−x , if p ∈ P is such that p80 − p ∈ H, then
s

2ρkp0 kL∞ (µ) x 16b∞ x
ρ
(P − Pn )(p∗0 − p) ≤ +
+
,
4
n
n

x
ρ
≤ + 2 kp0 kL∞ (µ) + 8b∞ /3
≤ ρ.
2
n
−x
On the same event of probability greater than
qR 1 − e , if p ∈ P is such that
R ∗
√
(p∗0 − p)2 dµ which belongs to
(p0 − p)2 dµ > ρ, consider h = ρ(p∗0 − p)/
H. We have (P − Pn )h ≤ ρ, which can be rewritten

(P

− Pn )(p∗0

− p) ≤

√

ρ

sZ

(p∗0

−

p)2 dµ

≤ ρ/2 +

Z

(p∗0 − p)dµ/2,

so that Ξp ≤ ρ/2 ≤ ρ. In summary, we have proved that on an event of
probability greater than 1 − e−x , supp∈P Ξp ≤ ρ. In particular, this holds for
p = p̂ which completes the proof.

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

/

24

Appendix C: A fixed point t∗ for finite dimensional classes
Lemma 14. Consider the notations of Theorem 13 and assume that the
linear span of P is finite dimensional of dimension d. Then (36) is satisfied
for t2∗ = 256kp0 kL∞ (µ) d/n.
Proof. Let e1 , ..., ed be anRorthonormal basis of the linear span of P, for the
scalar product hp1 , p2 i = p1 p2 dµ. Then


E

p∈P:

R sup∗

(p−p0 )2 dµ≤t2∗



d
n
n
X
1X
1X
ej (Xi )
εi (p − p∗0 )(Zi ) ≤ E
sup
εi
n i=1
θ∈R d : |θ|2 ≤t2∗ n i=1
j=1
2

v
u
d
uX
u
≤ t∗ t

j=1

≤

!2

n
1X
εi ej (Xi )
n i=1

q

t∗ kp0 kL∞ (µ) d
t2
√
= ∗,
n
16

where we have used the Cauchy-Schwarz inequality, Jensen’ inequality, and
that Eej (X)2 ≤ kp0 kL∞ (µ) for all j = 1, ..., d.

imsart-generic ver. 2014/07/30 file: deviations.tex date: September 28, 2017

