Submitted to Bernoulli

arXiv:1406.3334v3 [] 6 Jul 2016

Sparse oracle inequalities for variable selection
via regularized quantization
CLÉMENT LEVRARD
Université Paris Diderot, 8 place Aurélie Nemours, 75013 Paris
E-mail: levrard@math.univ-paris-diderot.fr
We give oracle inequalities on procedures which combines quantization and variable selection
via a weighted Lasso k-means type algorithm. The results are derived for a general family of
weights, which can be tuned to size the influence of the variables in different ways. Moreover,
these theoretical guarantees are proved to adapt the corresponding sparsity of the optimal
codebooks, suggesting that these procedures might be of particular interest in high dimensional
settings. Even if there is no sparsity assumption on the optimal codebooks, our procedure is
proved to be close to a sparse approximation of the optimal codebooks, as has been done for the
Generalized Linear Models in regression. If the optimal codebooks have a sparse support, we also
show that this support can be asymptotically recovered, providing an asymptotic consistency
rate. These results are illustrated with Gaussian mixture models in arbitrary dimension with
sparsity assumptions on the means, which are standard distributions in model-based clustering.
Keywords: k-means, variable selection, sparsity, Lasso, oracle inequalities, clustering, high dimension.

1. Introduction
Let P be a distribution over Rd . Quantization is the problem of replacing P with a finite
set of points, without loosing too much information. To be more precise, if k denotes an
integer, a k points quantizer Q is defined as a map from Rd into a finite subset of Rd
with cardinality k. In other words, a k-quantizer divide Rd into k groups, and assigns
each group a representative, providing both a compression and a classification scheme
for the distribution P .
The quantization theory was originally developed as a way to answer signal compression issues in the late 40’s (see, e.g., [10]). However, unsupervised classification is also in
the scope of its application. Isolating meaningful groups from a cloud of data is a topic
of interest in many fields, from social science to biology.
Assume that P has a finite second moment, and let Q be a k points quantizer. The
performance of Q in representing P is measured by the distortion
R(Q) = P kx − Q(x)k2 ,
where P f means integration of f with respect to P . It is worth pointing out that many
other distortion functions can be defined, using kx − Q(x)kr or more general distance
1

2

C. Levrard

functions (see, e.g., [9] or [11]). However, the choice of the Euclidean squared norm is
convenient, since it allows to fully take advantage of the Euclidean structure of Rd , as
described in [15]. Moreover, from a practical point of view, the k-means algorithm (see
[16]) is designed to minimize this squared-norm distortion and can be easily implemented.
Since the distortion is based on the Euclidean distance between a point and its image,
it is well known that only nearest-neighbor quantizers are to be considered (see, e.g., [11]
or [21]). These quantizers are quantizers of the type x 7→ argminj=1,...,k kx − cj k, where
the ci ’s are elements of Rd and are called code points. A vector of code points (c1 , . . . , ck )
is called a codebook, so that the distortion takes the form
R(c) = P min kx − cj k2 .
j=1,...,k

It has been proved in [20] that, whenever P kxk2 < ∞, there exists optimal codebooks,
denoted by c∗ .
Let X1 , . . . , Xn denote an independent and identically distributed sample drawn from
P , and denote by Pn the associated empirical distribution, namely, for every measurable
subset A, Pn (A) = 1/n |{i|Xi ∈ A}|. The aim is to design a codebook from this n-sample,
whose distortion is as close as possible to the optimum R(c∗ ). The k-means algorithm
provides the empirical codebook ĉn , defined by
n

ĉn = argmin

1X
min kXi − cj k2 = argmin Pn min kx − cj k2 .
j=1,...,k
n i=1 j=1,...,k

Unfortunately, if P (p) 6= 0, where P (p) denotes the marginal distribution of P on the p-th
(p)
(p)
(p)
coordinate, then ĉn = (ĉ1 , . . . , ĉk ) may not be zero, even if the p-th coordinate has
no influence on the classification provided by the k-means. For instance, if c∗,(p) = 0, and
(p)
P (p) has a density, then ĉn 6= 0 almost surely. This suggests that the k-means algorithm
does not provide sparse codebooks, even in the case where some variables plays no role
in the classification, which can be detrimental to the computational tractability and to
the interpretation of the corresponding clustering scheme in high-dimensional settings.
Consequently, when d is large, a variable selection procedure is usually performed preliminary to the k-means algorithm. The variable selection can be achieved using penalized
BCCS strategies, as exposed in [7] or [31]. Though these procedures offer good performance in classifying the sample X1 , . . . , Xn , under the assumption that the marginal
distributions P (p) are independent, no theoretical result on the prediction performance
has been given. An other way to perform variable selection can be to select coordinates
whose empirical variances are larger than a determined ratio of the global variance, following the idea of [23]. This algorithm has shown good results on practical examples,
such as curve clustering (see, e.g., [1]). However, there is no theoretical result on the
prediction performance of the selected coordinates.
Algorithms combining variable selection through PCA and clustering via k-means, like
RKM (Reduced k-means, introduced in [8]) and FKM (Factorial k-means, introduced in
[30]), are also very popular in practice. Some results on the performance in classifying the

Sparse oracle inequalities for variable selection via regularized quantization

3

sample X1 , . . . , Xn have been derived in [27] under strong conditions on P . In addition,
some asymptotic prediction results on these procedures have been established in [25]
and [26], showing that both the resulting codebook and its distortion converge almost
surely to respectively a minimizer of the distortion constrained on a lower-dimensional
subspace of Rd and the distortion of the latter, following the approach of [20]. However,
these methods could be unsuitable for interpreting which variables are relevant for the
clustering. In addition, no bounds on the excess distortion are available to our knowledge,
and the choice of the dimension of the reduction space remains a hard issue, tackled in
our procedure by a L1 -type penalization.
In fact, excess risk bounds for procedures combining dimensionality reduction and
clustering are mostly to be found in the model-based clustering literature (see, e.g., [18]
for a L0 -type penalization method, and [19] for a L1 -type penalization method). This
approach, consisting in modeling P via a Gaussian mixture with sparse means through
density estimation via constrained Maximum Likelihood Estimators, is clearly connected
to ours. In fact, most of the derivation for the oracle inequalities stated in this paper
use the same tools, drawn from empirical process theory. Nevertheless, no results on the
convergence of the estimated means (i.e., model consistency) have been derived in this
framework, and this model-based approach theoretically fails when P is not continuous,
unlike k-means one (see, e.g., [15]).
This paper exposes a theoretical study of a weighted Lasso type procedure adapted to
k-means, as suggested in [24]. Results are given for a general family of weights, encompassing the weights proposed in [24] as well as those proposed in [28] in a Generalized
Linear Models for regression setting. To be more precise, we provide non-asymptotic
excess distortion bounds along with model consistency results, under weaker conditions
than ones required in [24] (for instance, the coordinates are not assumed to be independant), and adapting the sparsity of the optimal codebooks. From these non-asymptotic
bounds, some asymptotic rates of convergence are derived when both the dimension and
the sample size are large, showing that these Lasso type procedures may be suitable for
high dimensional quantization. Interestingly, the excess distortion bounds are valid in
the case where it may exist several optimal codebooks, contrary to results in [24] and
[28]. These results are illustrated with Gaussian mixture distributions, often encountered
in model-based clustering literature, showing at the same time that optimal codebooks
can be proved to be unique for this type of distributions, under some conditions on the
variances of the components of the mixture.
The paper is organized as follows. Some notation are introduced in Section 2, along
with the Lasso k-means procedure and the different assumptions. The consistency and
prediction results are gathered in Section 3, and the proof of these results are exposed in
Section 4. At last, the proofs of some auxiliary results are given in the Appendix section.

2. Notation
Let x be in Rd , then the p-th coordinate of x will be denoted by x(p) . Throughout
this paper, it is assumed that, for every p = 1, . . . , d, there exists a sequence Mp ,

4

C. Levrard

such that |x(p) | ≤ Mp P -almost surely. In other words P is assumed to have bounded
marginal
distributions P (p) . To shorten notation, the Euclidean coordinate-wise product
Qd
[−M
p , Mp ] will be denoted by C. To frame quantization as a contrast minimization
p=1
issue, let us introduce the following contrast function
γ:

(

Rd

k

× Rd
(c, x)

−→ R
2 ,
7−→
min kx − cj k
j=1,...,k

where c = (c1 , . . . , ck ) denotes a codebook, that is a kd-dimensional vector. The risk
R(c) then takes the form R(c) = R(Q) = P γ(c, .), where we recall that P f denotes
the integration of the function f with respect to P . Similarly, the empirical risk R̂n (c)
can be defined as R̂n (c) = Pn γ(c, .), where Pn is the empirical distribution associated
with X1 , . . . , Xn , in other words Pn (A) = 1/n |{i|Xi ∈ A}|, for every measurable subset
A ⊂ Rd . The usual k-means codebook ĉn is then defined as a minimizer of R̂n (c).
It is worth pointing out that, since the support of P is bounded, then there exist such
minimizers ĉn and c∗ (see, e.g., Corollary 3.1 in [9]). In the sequel, the set of minimizers
of the risk R(.) will be denoted by M. Then, for any codebook c, the loss ℓ(c, c∗ ) may
be defined as the excess distortion, namely ℓ(c, c∗ ) = R(c) − R(c∗ ), for c∗ in M.
From now on we assume that k ≥ 2. Let c1 , . . . , ck be a sequence of code points. A
central role is played by the set of points which are closer to ci than to any other cj ’s.
To be more precise, the Voronoi cell, or quantization cell associated with ci is the closed
set defined by

Vi (c) = x ∈ Rd | ∀j 6= i kx − ci k ≤ kx − cj k .
It may be noted that (V1 (c), . . . , Vk (c)) does not form a partition of Rd , since Vi (c)∩Vj (c)
may be non empty. To address this issue, the Voronoi partition associated with c is defined
as the sequence of subsets Wi (c) = Vi (c) \ (∪i>j Vj (c)), for i = 1, . . . , k. It is immediate
that the Wi (c)’s form a partition of Rd , and that for every i = 1, . . . , k,
W̄i (c) = Vi (c),
where W̄i (c) denotes the closure of the subset Wi (c). The open Voronoi cell is defined
the same way by
o

V i (c) = x ∈ Rd | ∀j 6= i kx − ci k < kx − cj k ,

and the following inclusion holds, for i in {1, . . . , k},
o

V i (c) ⊂ Wi (c) ⊂ Vi (c).
The risk R(c) then takes the form
R(c) =

k
X
i=1


P kx − ci k2 1Wi (c) (x) ,

Sparse oracle inequalities for variable selection via regularized quantization

5

where 1A denotes the indicator function associated with A. In the case where P (Wi (c)) 6=
0, for every i = 1, . . . , k, it is clear that
P (kx − ci k2 1Wi (c) (x)) ≥ P (kx − ηi k2 1Wi (c) (x)),
with equality only if ci = ηi , where ηi denotes the conditional expectation of P over the
subset Wi (c), that is
P (x1Wi (c) (x))
ηi =
.
P (Wi (c))
Moreover, it is proved in Proposition 1 of [12] that, for every Voronoi partition W (c∗ )
associated with an optimal codebook c∗ , and every i = 1, . . . , k, P (Wi (c∗ )) 6= 0. Consequently, any optimal codebook satisfies the so-called centroid condition (see, e.g., Section
6.2 of [10]), that is
P (x1Wi (c∗ ) (x))
c∗i =
.
P (Wi (c∗ ))
As a remark, the centroid condition ensures that M ⊂ C k , and, for every c∗ in M, i 6= j,


P (Vi (c∗ ) ∩ Vj (c∗ )) = P x ∈ Rd | ∀i′ kx − c∗i k = kx − c∗j k ≤ kx − c∗i′ k
= 0.

A proof of this statement can be found in Proposition 1 of [12]. According to [15], for
every c∗ in M, the following set is of special interest:
[
Nc∗ =
Vi (c∗ ) ∩ Vj (c∗ ).
i6=j

To be more precise, the key quantity is the margin function, which is defined as
p(t) = sup P (Nc∗ (t)),
c∗ ∈M

where Nc∗ (t) denotes the t-neighborhood of Nc∗ . As shown in [15], bounds on this margin
function (see Assumption 2 below) can provide interesting results on the convergence rate
of the k-means codebook, along with basic properties of optimal codebooks.
In order to perform both variable selection and quantization, we introduce the Lasso
k-means codebook ĉn,λ as follows.
ĉn,λ ∈ argmin Pn γ(c, .) + λIŵ (c),

(1)

c∈C k

where ŵ is a possibly random sequence of weights of size d, and Iŵ () denotes the penalty
function
Iŵ (c) =

d
X
p=1

ŵp kc(p) k.

(2)

6

C. Levrard
(p)

(p)

Let us recall here that c(p) denote the vector (c1 , . . . , ck ) made of the p-th coordinates
of the different codepoints. The results exposed in the following section are illustrated
with three sequences of weights, corresponding to different codebooks: the plain Lasso
codebook, defined by the deterministic sequence ŵp = 1, the normalized Lasso codebook,
defined by ŵp = σ̂p , and the threshold Lasso codebook, which is a slight modification of
(p)
the original Lasso-type procedure mentioned in [24] and is defined by ŵp = 1/(δ ∨kĉn k),
where ĉn denotes the k-means codebook and δ a parameter to be tuned. It is likely that
other families of weights may be of special interest, for instance combining normalization
and threshold. Consequently the results are derived for an arbitrary family of weights
satisfying some convergence conditions.
These L1 -type penalties have been designed to drive the irrelevant (p)-th coordinates
(p)
(p)
c1 , . . . , ck together to zero (see, e.g., [2]), according to different criterions. Note that
this kind of penalties is well-adapted to centered distributions. In practice, centering the
data provides codebooks of the form (ĉn,λ,1 + X̄, . . . , ĉn,λ,k + X̄) for the non centered
distribution, where X̄ denotes the empirical mean and ĉn,λ is hopefully sparse. From a
theoretical point of view, deriving how close the codebook ĉn,λ computed on the centered
data is to a codebook c∗ − m would require a bound on kX̄ −
pmk, where m is the mean
of P . In our framework, such a bound is typically of order d/n (see, e.g., Figure 1),
hence might be unsuited for high dimensional settings. However, in some particular cases
(for instance when the mean is sparse), other estimators of the means that are adapted
to the high dimensional framework could be combined with our procedure.
To describe the influence of the different coordinates, the following notation are
adopted. Let S ⊂ {1, . . . , d} denote a subset of coordinates, then for any vector x in
(Rd )ℓ and set A ⊂ (Rd )ℓ , ℓ being a positive integer, xS will denote the vector in (R|S| )ℓ
corresponding to the coefficients of x on variables in S, and AS will denote the set of
such xS , for x in A. Moreover, let P S denote the marginal distribution of P over the set
R|S| . We may then define the restricted distortions and variances as follows:
 2
σ
=
P S kxk2 ,


 σ̂S2 =
P S kxk2 ,
S

R∗


 S
R̂S

n

= minc∈CS P S γ(c, .),
= minc∈CS PnS γ(c, .),

where the vector x is element of R|S| . Elementary properties of the distortion show that,
if S = S1 ∪ S2 , with empty intersection, then
 2
σ
= σ2 + σ2 ,


 σ̂S2 = σ̂S2 1 + σ̂S2 2 ,
S
S1
S2
(3)
RS∗ ≥ RS∗ 1 + RS∗ 2 ,



R̂S ≥ R̂S1 + R̂S2 .

These elementary properties will be of importance when choosing which coordinate to
select. A special attention will be paid to the subsets of variables formed by the support
of codebooks. To be more precise, for every codebook c in C k , we define the support

Sparse oracle inequalities for variable selection via regularized quantization

7

S(c) of c by S(c) = {j ∈ {1, . . . , d} |c(j) 6= 0}. The following Proposition gives a first
glance at which variables are in S(ĉn,λ ).
Proposition 2.1.

then

Let p be in {1, . . . , d}. If
q
ŵp λ
,
σ̂p2 − R̂p <
2
(p)

(p)

(p)

ĉn,λ = (ĉn,λ,1 , . . . , ĉn,λ,k ) = (0, . . . , 0).
According to Proposition 2.1, the Lasso k-means procedures may be thought of as a
multimodularity test on every coordinate, in the spirit of [13]. This result ensures that,
if the distortion of the codebook (0, . . . , 0) is close to the optimal empirical distortion,
on the p-th coordinate, then theqLasso k-means will drive the p-th variable to 0. For
the plain Lasso, the differences

σ̂p2 − R̂p are uniformly thresholded, whereas for the

normalized Lasso, the threshold in λ is applied on the ratios R̂p /σ̂p2 . This point suggests
that the normalized Lasso may succeed in recovering informative variables with small
ranges.
We introduce now the assumptions which will be required to derive theoretical results
on the performance of the Lasso codebooks. To deal with the case of possibly several
optimal codebooks, we introduce the following structural assumption on P .
Assumption 1.

For every c∗ in M and c in C k , if S(c) ( S(c∗ ), then R(c) > R(c∗ ).

Assumption 1 roughly requires that no optimal codebook has a support strictly contained in the support of another optimal codebook. This is obviously the case if P has a
unique optimal codebook, up to relabeling.
Assumption 2 (Margin Condition).
∀t ≤ r0

There exists r0 > 0 such that
p(t) ≤ c0 (P )t,

(4)

where c0 (P ) is a fixed constant, defined in [15].
As exposed in [15], Assumption 2 may be thought of as a margin condition for squared
distance based quantization. Some examples of distributions satisfying (4) are given in
[15], including Gaussian mixtures under some conditions. Roughly, if P is well concentrated around k poles, then (4) will hold. It is also worth mentioning that the condition
required in [24] seems stronger than the condition required in Assumption 2, since it
requires P to have a unique optimal codebook, to be a mixture of components centered
on the different optimal code points, and that the Hessian matrix of the risk function
located at the optimal codebook is positive definite.
Moreover, Assumption 2 is a sufficient condition to ensure that some elementary properties that are often assumed are satisfied, as described in the following Proposition.

8

C. Levrard

Proposition 2.2.

If P satisfies Assumption 2, then

i) M is finite,
ii) there exists κ′0 > 0 such that, for every c in C k , kc − c∗ (c)k2 ≤ κ′0 ℓ(c, c∗ ),

where c∗ (c) ∈ argminc∗ kc − c∗ k.
Moreover, if P satisfies Assumption 1, then there exists a constant κ′′0 such that, for
every c∗ in M and S(c) ( S(c∗ ), we have
kc − c∗ k2 ≤ κ′′0 ℓ(c, c∗ ).
The two first statements of Proposition 2.2 are to be found in Proposition 2.2 of [15],
the proof of the third statement is given in Section 4.2. Proposition 2.2 may be thought of
as a generalization of the positive Hessian matrix condition of [21] to the non-continuous
case. It also allows to deal with the case where P has several optimal codebooks. In the
following, we denote by κ0 the quantity κ′0 ∨κ′′0 , whenever Assumption 2 and Assumption
1 are satisfied.
In addition to Assumption 2, we assume that the weights ŵp satisfy a uniform concentration inequality around some deterministic weights, as stated below.
Assumption 3 (Weights concentration). There exist deterministic weights wp > 0,
p = 1, . . . , d, and a constant 0 ≤ κ1 < 1 such that
!
ŵp
P
sup
(5)
− 1 > κ1 := r1 (n) −→ 0.
n→∞
p=1,...,d wp
Assumption 3 is obviously satisfied for the plain Lasso (ŵp = 1). The following proposition ensures that this statement remains true for the two other examples of weights.
For any sequence wp , we denote by T (w) the quantity supp=1,...,d Mp /wp . With a slight
abuse of notation, T (σ) and T (δ) will refer to the sequences σp and 1/(kc∗,(p) k∨δ), where
the latter is well defined when P has a unique optimal codebook.
Proposition 2.3.

√
T 2 (σ) log(d)
√
For ŵp = σ̂p , if 1 > κ1 >
, then Assumption 3 holds with wp = σp and
2n
2
√
√
2nκ1
− log(d)
−
r1 (n) = e T 2 (σ)
.
p
(p)
For
ŵp = 1/(kĉn k ∨ δ), let M be defined as M = M12 + . . . + Md2 . If 1 > κ1 >
√
√ k , for a fixed constant C0 , Assumption 2 is satisfied, and c∗ is unique (up to
C0 M
nδ
relabeling), then Assumption 3 holds with wp = 1/(kc∗,(p) k∨δ) and r1 (n) = e

−



nδ2 κ2
1
C2 M 2
0

−k



.

The proof of Proposition 2.3 follows from standard concentration inequalities, and can
be found in the Section 5.1 of the Appendix. At first sight, the assumption that c∗ is
unique seems quite restrictive. However, as exposed in Section 3.4, it can be shown that

Sparse oracle inequalities for variable selection via regularized quantization

9

Gaussian mixtures satisfy this property, provided that the variances of the components
are small enough. In fact, if P has several optimal codebooks, there is no intuition about
toward which one ĉn will converge, hence the difficulty of defining deterministic limit
weights for ŵp .
At last, we define the following quantities λ0 and λ1 which will play the role of minimal
values for the regularization parameter λ, as exposed in [28].

√ q
 λ
= 8 2π k log(kd)
T (w),
0


qn
(6)
u+x
λ1 (x) = eλ0 1 +
,
k log(kd)

where x > 0 and u = log



2√

kwk2
√

n

log(kd)


. These two quantities come from empirical process

theory, their roles are explained in Section 4. Roughly, λ0 is the minimal value of the
regularization parameter which ensures that the empirical risk is close to the true risk
uniformly on C k , and λ1 (x) is the minimal value which ensures that the deviation between
empirical and true risk may be compared to the norm Iw uniformly on C k .

3. Results
We recall here that k ≥ 2. The case k = 1 may be treated as a special case of the standard
Lasso estimator for linear regression (see, e.g., Chapter 2 of [6]).

3.1. Sparsity adaptive slow rate of convergence for the distortion
Following the approach of [17], Lasso type procedures may be thought of as model selection procedures over L1 balls. Theorem 3.1 below is the adaptation of this idea for the
Lasso k-means procedures.
Theorem 3.1.
choose

Suppose that Assumption 3 is satisfied, for some constant κ1 < 1, and
λ≥

λ1 (x)
,
1 − κ1

for some x > 0, where λ1 is defined in (6). Then, with probability larger than 1 − r1 (n) −
e−x , for every c∗ in M, we have
ℓ(ĉn,λ , c∗ ) ≤ inf

inf

r>0 Iw (c)≤r

(ℓ(c, c∗ ) + (3 − κ1 )λ(r ∨ λ0 )) .

A direct implication of Theorem 3.1 is that ℓ(ĉn,λ , c∗ ) ≤ 4λ(Iw (c∗ ) ∨√
λ0 ). Hence,
choosing λ ∼ λ1 (x) gives a convergence rate for ℓ(ĉn,λ , c∗ ) of order T (w)/ n, up to a
log(n) factor. If T (w) is fixed, i.e. does not depend on n, this rate is roughly the same as
the rate of convergence of the k-means codebook without margin assumption, as shown
in [3].

10

C. Levrard

Besides, some asymptotic results for ℓ(ĉn,λ , c∗ ) when both d and n are large may also
be deduced from Theorem 3.1, as stated by the following corollary.
Corollary 3.1. Let c∗ be in M and denote by d∗ the quantity
|S(c∗ )|. Assume that
√
maxp=1,...,d Mp = O(1), n−1 log(d) → 0, and n−1 λ−2 log(d n) → 0.
For ŵp = 1, ℓ(ĉn,λ , c∗ ) = OP (λd∗ ).
For ŵp = σ̂p , if we further assume maxp=1,...,d σp = O(1) and 1 = O(minp=1,...,d σp ),
then ℓ(ĉn,λ , c∗ ) = OP (λd∗ ).
This result may be compared for instance with Theorem 4.1 of [22], in the framework
of high dimensional regression. In this case an asymptotic convergence rate of d∗ λ may be
similarly derived under the same assumptions (up to a log(n) factor) that log(d)n−1 → 0
and λ−2 n−1 → 0. This shows that the optimal distortion may be asymptotically attained
κ′ −1
κ
for dimension d of order en , with κ < 1, choosing λ of order n 2 , with κ < κ′ < 1.
Moreover, Corollary 3.1 can provide a convergence rate of order O(d∗ log(d)n−1/2 ) for
the excess distortion of these Lasso-type procedures, up to a log(n) factor, hence adapting
the sparsity of the optimal codebooks. In comparison to the O(dn−1/2 ) rate that can be
derived for the excess distortion of the k-means codebook (see, e.g., [3]), this suggests
that regularized k-means might outperform standard k-means whenever d∗ << d and d
is large. Some numerical illustration of this point is given below.
Numerical illustration: We consider the Gaussian mixture distributions with 4
components, each of them having covariance matrix Id (identity matrix on Rd ), and with
the following means:
5

µ1
µ2

5

d−10

}|
{ z }| {
z }| { z
= (0.8, . . . , 0.8, −0.8, . . . , −0.8, 0, . . . , 0),
10
d−10
z }| { z }| {
=
(0.8, . . . , 0.8, 0, . . . , 0),

µ3

=

−µ1 ,

µ4

=

−µ2 .

The weights of the mixture are chosen as (0.3, 0.2, 0.2, 0.3). For d growing from 10 to 500,
we compute √
the plain Lasso k-means codebooks with regularization parameter λ(d) =
1.5 × log(d)/ n, in the cases n = 50 and n = 200. Note that, since Gaussian mixture
distributions have not a bounded support, this example does not fall in the scope of
Theorem 3.1. This issue might be bypassed considering truncated Gaussian mixture
distributions, as exposed in Section 3.4.
Following the approach of Algorithm 1 of [24], the codebooks are computed using
a Lloyd’s-type algorithm: for any initial codebook, we update the assignments of data
points to the closest code point and then update the code points to minimize the penalized
squared distances to the previously assigned data points, using the Karush-Kuhn-Tucker
condition that is necessary and sufficient when assignments are fixed. This procedure
is repeated until convergence. Since every iteration decreases the penalized empirical
distortion, the outcome of such an algorithm is clearly a local minimum of the penalized
empirical distortion. This suggests that an effective global minimization of the penalized
empirical distortion could be achieved by the comparison of the outcomes of several

Sparse oracle inequalities for variable selection via regularized quantization

11

executions of the latter procedure with different initializations, as for the classical kmeans implementation.
We choose as initial code points the ones given by the standard k-means algorithm,
as suggested in [24], and the means of the mixture, leading to few iterations before
convergence, based on our limited experience. Then the best of these two codebooks
in terms of penalized empirical distortion is chosen. In full generality, the choice of a
good initialization for such an algorithm is likely to be a crucial issue, and is beyond the
scope of this paper. It may also be noted that the choice of the constant 1.5 is based on
experimental observations. The calibration of such a constant might be more generally
performed using cross-validation, as done in [24].
Figure 1 below depicts the average distortions of both plain Lasso k-means and kmeans codebook, over 100 replications. The both panels show that the excess distortion
of the k-means codebook grows linearly with respect to the dimension, whereas the excess
distortion of the plain Lasso k-means codebook exhibits a dependence on the dimension
that looks like sub logarithmic. In fact, in the case n = 50, the Lasso k-means codebook
turns out to be the zero codebook when d is larger than about 100, hence its constant
excess distortion.
n = 50

n=200

4

6

8

10

12

k−means
Lasso k−means

0

2

Average excess distortions

30
20
10
0

Average excess distortions

k−means
Lasso k−means

0

100

200

300
d

400

500

0

100

200

300

400

500

d

Figure 1. Average excess distortions of the plain Lasso k-means and k-means codebooks over 100
replications.

Under the sole assumptions of Corollary 3.1, no results on the threshold Lasso may
be stated, since Assumption 3 cannot be checked.

12

C. Levrard

3.2. Convergence towards a sparse codebook and fast rate of
convergence for the distortion
If P satisfies Assumption 2 and Assumption 1, further results may be derived, following
the approach of [28]. To this aim, we defined, for a fixed codebook c∗ and a weight family
w, the set of w-sparse approximations of c∗ at order λ by
)
(
Mλ (c∗ ) =

argmin 3R(c) + 8κ0 λ2 kwS(c) k2

,

S(c)⊂S(c∗ )

where κ0 = κ′0 ∨ κ′′0 , as defined below Proposition 2.2. Then, the closest w-sparse approximation of c∗ may be defined as c∗λ (c∗ ) ∈ argminc∈Mλ (c∗ ) kc − c∗ k. With a slight abuse
of notation, the w-sparse approximation of a codebook c is defined by c∗λ (c) = c∗λ (c∗ (c)).
It is immediate that, for the plain Lasso, kwS(c) k = |S(c)| = kck0 , whereas for the normalized Lasso, kwS(c) k = σS(c) . For the threshold Lasso, kwS(c) k has the slightly more
intricate expression
X
1
1
kwS(c) k2 = 2 S(c) ∩ {j|kc∗,(j) k ≤ δ} +
.
∗,(j) k2
δ
kc
∗,(j)
S(c)∩{j|kc

k>δ}

However, it is easy to see that kwS(c) k ≤ |S(c)|/δ. If we assume that the optimal codebooks c∗ are sparse, some guarantees on the support of the c∗λ (c∗ )’s may be given. To
be more precise, the following subset of variables is introduced
\
(S + )c =
S(c∗ )c .
c∗ ∈M

+

S may be thought of as the generalized support over optimal codebooks, extending the
definition of these sets from the unique optimal codebook case. If P has a unique optimal
codebook, it is immediate that S + = S(c∗ ). However, even if all the codebook are sparse,
S + may not be sparse. For instance, if d = k = 2 and P is a pointwise distribution with
support (−1, −1), (−1, 1), (1, −1), (1, 1) equally weighted, then every optimal codebook
has at least one zero coordinate, whereas S + = {1, 2}.
From its definition, it is straightforward that S(c∗λ (c∗ )) ⊂ S + , for c∗ in M. Nevertheless, in the case where S + = {1, . . . , d}, the c∗λ (c∗ )’s may still have zero coordinates. In
fact, c∗λ (c∗ ) may be thought of as tradeoff between distortion and size of the support, the
latter being measured by kwk2S . As in the empirical case of Proposition 2.1, this tradeoff
property may be illustrated in the following way.
Proposition 3.1.

Let p be in {1, . . . , d}. If
σp2 − Rp∗ <

then, for every c∗ in M,

∗,(p)

cλ

8λ2 κ0 wp2
,
3

(c∗ ) = (0, . . . , 0).

Sparse oracle inequalities for variable selection via regularized quantization

13

The proof of Proposition 3.1 is given in Section 4.4. Proposition 3.1, as well as Proposition 2.1, may be thought of as a comparison between the risk of optimal codebooks and
the risk of the codebook 0, on the p-th variable. It is worth noticing that, for the plain
Lasso and threshold Lasso, the comparison is based on the difference σp2 − Rp∗ , whereas
for the normalized Lasso only the ratio Rp∗ /σp2 is to be considered. Once more, this point
suggests that the sparse w-approximation may not be sensitive to coordinate-wise dilations in this case. We are now in position to state sharper oracle results, on both the
excess distortion and the convergence of the Lasso k-means codebooks.
Theorem 3.2.
isfied. If

Suppose that Assumption 1, Assumption 2 and Assumption 3 are satλ≥

2λ1 (x)
,
1 − κ1

where λ1 is defined in (6), then, with probability larger than 1 − r1 (n) − e−x , we have
ℓ(ĉn,λ , c∗ ) + λ(1 − κ1 )Iw (ĉn,λ − c∗λ (ĉn,λ )) ≤ 3ℓ(c∗λ , c∗ ) + 8κ0 λ2 kwS(c∗λ (ĉn,λ )) k2 ∨ 3λλ0 .
(7)
A consequence of Theorem 3.2 is ℓ(ĉn,λ , c∗ ) ≤ 8κ0 λ2 kwS(c∗ (ĉn,λ )) k2 ∨ 3λλ0 , which
provides an oracle inequality adapting the sparsity of the c∗ (ĉn,λ )’s. For instance, considering the plain Lasso, provided that c∗ 6= 0 for some c∗ , (7) leads to ℓ(ĉn,λ , c∗ ) ≤
8(κ0 ∨ 1)|S(c∗ (ĉn,λ ))|λ2 ≤ 8(κ0 ∨ 1)|S + |λ2 . However, Theorem 3.2 also deals with the
case where the c∗ ’s are not sparse, comparing the Lasso k-means codebook ĉn,λ to the
closest sparse w-approximations, for which Proposition 3.1 yields a reduced support
whenever λ is large enough.
Theorem 3.2 may be considered as an application of Theorem 2.1 in [29] to the k-means
case, with a slight improvement in the analysis of the complexity term (see Section 5.3
in the Appendix for more details). The numerical constants in Theorem 3.2 have been
arbitrarily fixed for clarity sakeness, note however that a more general version of Theorem
3.2 can be derived the same way as Theorem 2.1 in [29].
At last, it is worth pointing out that the inequality ℓ(ĉn,λ , c∗ ) ≤ 8κ0 λ2 kwS(c∗ (ĉn,λ )) k2 ∨
3λλ0 provides a convergence rate in 1/n, up to a log(n) factor, when λ ∼ λ1 and w does
not depend on n. Interestingly, this rate is the convergence rate of the k-means codebook
ĉn , when P satisfies a margin condition, as described in [15].
Similarly to Theorem 3.1, Theorem 3.2 may provide asymptotic convergence rates for
both distortion and distance to optimal codebooks.
Corollary 3.2.
For the plain and normalized Lasso, assume that P satisfies Assumption 1, Assumption
2 so that κ0 √= O(1), and the requirements of Corollary 3.1. If n−1 log(d) → 0 and
n−1 λ−2 log(d n) → 0, then
ℓ(ĉn,λ , c∗ ) + λ(1 − κ1 )Iw (ĉn,λ − c∗λ (ĉn,λ )) = OP (|S + |λ2 ).

14

C. Levrard

For the threshold Lasso, assume that c∗ is unique, P satisfies Assumption 2 so that
κ0 = O(1), and maxp=1,...,d Mp = O(1). If δ and λ are chosen so that δ → 0, dn−1 δ −2
→ 0, and λ−1 log(n)1/2 n−1/2 → 0, then
ℓ(ĉn,λ , c∗ ) + λ(1 − κ1 )Iw (ĉn,λ − c∗λ (c∗ )) = OP (d∗ λ2 ).
p
As a consequence, in every case, kĉn,λ − c∗ (ĉn,λ )k = OP ( |S + |λ).

According to Theorem 3.1 of [15], the excess distortion of the k-means codebook is
of order O(dn−1 ), under the assumptions of Corollary 3.2. In comparison, Corollary
3.2 yields convergence rates of order O(|S + | log(d)n−1 ), up to a log(n) factor, for the
plain and normalized Lasso. Again, this suggests that these procedures might outperform
standard k-means procedures in terms of distortion in high dimensional settings, when
|S + | << d.
The requirement κ0 = O(1) may be thought of as an assumption on the local strong
convexity of the excess distortion. This condition is similar to a uniform lower bound on
the Hessian matrix of the excess distortion, as required for the asymptotic results in [24].
This asymptotic framework also allows for further comparison between our results and
(p)
Theorem 1 of [24], which states that, when choosing ŵp = kĉn k−1 , provided that c∗ is
1/2
−2 −2
∗
1/2
unique, n λd → 0, and n λ d → 0, kĉn,λ − c k = OP (n λd−1 ).
√
If we choose λ close to the√given lower bounds, for instance λ = n−1/2 log(d n)−1/2 un
for our plain Lasso, and λ = dn−1 un in the setting of [24], with un → ∞, then Theorem
−1/2 −1/2
d
), whereas Corollary 3.2 gives a slightly
1 of [24] yields kĉn,λ − c∗ k = OP (up
nn
√
∗
worse bound, kĉ√n,λ − c k = OP (un |S + | log(d n)n−1/2 ). However, Theorem 1 of [24] is
valid for d = o( n), when Corollary 3.2 only requires log(d) = o(n) for the plain Lasso.
d = o(n) and
For the threshold Lasso, when c∗ is unique, Corollary 3.2 requires
√
λ = un log(n)1/2 n−1/2 to get bounds on kĉn,λ − c∗ k of order d∗ log(n)1/2 n−1/2 un ,
hence still worse than un n−1/2 d−1/2 . It is interesting to note that these two very similar
procedures give almost the same rate for kĉn,λ − c∗ k, but with possibly very different
choices of λ (of order n−1 in [24], and of order n−1/2 here). Some explanation can be given,
noting that our results are intended to provide bounds on the distance between ĉn,λ and
c∗λ (c∗ ), where c∗λ (c∗ ) is possibly different from c∗ . Thus, the empirical processes involved
in our derivations are not the same than those of [24]. Besides, Corollary 3.2 states
bounds in terms of the Iw distance, rather than the Euclidean one. This Iw distance is of
particular interest, especially for coordinates which are not in S(c∗ ). For instance, if j is
not in S(c∗ ), and if we choose δ = d1/2 n−1/2 un along with λ = un log(n)1/2 n−1/2 , then
√
(j)
Corollary 3.2 ensures that kĉn,λ k = OP (d∗ d log(n)1/2 n−1 u2n ). This convergence rate
turns out to be faster in terms of n than the one which can be derived from kĉn,λ − c∗ k.
In this particular case of a unique optimal codebook, further consistency results may be
given, as described in the following subsection.

Sparse oracle inequalities for variable selection via regularized quantization

15

3.3. Consistency of the threshold Lasso k-means
Throughout this subsection we assume that there exists a unique optimal codebook c∗ ,
(j)
up to relabeling. Let j be in S(c∗ )c . Then Theorem 2 in [24] established that ĉn,λ → 0
in probability under strong assumptions on P . To be more precise, it is assumed in [24]
that P|Vj∗ = c∗j + εj , where P|Vj∗ denotes the conditional law of P on the optimal Voronoi
cell centered at the j-th optimal code point c∗j , εj has independent coordinates, and the
εj ’s are independent. Theorem 3.3 below gives a generalization of this result, along with
(j)
a convergence rate for P(ĉn,λ 6= 0).
Theorem 3.3. Suppose that Assumption 2 is satisfied, and that d is fixed. For ŵp =
(p)
1/(δ ∨ kĉn k), if n−1 log(n)δ −2 → 0 and δ → 0, choose λ ∼ δ. Then, for every j in
∗ c
S(c ) , we have




2
(j)
(8)
P ĉn,λ 6= 0
= O e−nδ .
n→∞

Moreover, for every j in S(c∗ ), we have




2
(j)
= O e−nδ .
P ĉn,λ = 0
n→∞

(9)

Note that the two consistency rates given by (8) and (9) are in fact of order o(n−1 ).
The choice λ ∼ δ has been made to optimize the consistency rate. However, this choice
may lead to suboptimal convergence rate for ℓ(ĉn,λ , c∗ ) in Corollary 3.2. For instance, if
we choose δ = n−α , 0 < α < 1/2, then this choice of λ leads to ℓ(ĉn,λ , c∗ ) = OP (n−2α ).
In fact, we only need λ−1 log(n)1/2 n−1/2 → 0, as in Corollary 3.2, to ensure that this
model consistency result holds. Thus, the choice λ ∼ n−1/2 log(n)(1/2+ε) , for a positive
ε, provides both model consistency and almost optimal convergence of ℓ(ĉn,λ , c∗ ). Some
numerical illustration of this point is given below.
The way Theorem 3.3 is derived makes use of the Vapnik-Chervonenkis dimension of
the Voronoi cells associated with the codebooks. Provided that a sharp bound on this
dimension can be given, some asymptotic results when both d and n tend to infinity
could also be stated.
Numerical illustration: To illustrate this consistency result, we consider the same
Gaussian mixture distribution as in Section 3.1, but with fixed dimension d = 100 and
sample size n growing from 100 to 5000. The threshold δ is chosen as δ(n) = n−1/6 , and
the threshold Lasso k-means codebooks are computed
for two sequences of regularization
√
parameters, namely λpred (n) = 0.12 × log(n)/ n and λcons (n) = 0.12 × δ(n). The choice
of the constant 0.12 is based on experimental observations and is clearly suboptimal for
the small values of n, however it renders the comparison between the two regularization
parameters easier.
The right-hand side panel of Figure 2 shows that the threshold Lasso with parameter
λpred asymptotically outperforms the threshold Lasso with parameter λcons in terms of
distortion, as expected. However, for values of n below 1000, the λcons regularization gives

C. Levrard

0.120
0.115

Average excess distortion

λ = λpred
λ = λcons

0.110

0.0 0.2 0.4 0.6 0.8 1.0

λ = λpred
λ = λcons

−0.4

Average excess distortion

16

500

1000

1500

2000

2000

3000

n

4000

5000

n

Figure 2. Average excess distortion for λ ∼ λ1 (log(n)) and λ ∼ δ(n), over 100 replications.

10.0

10.5

λ = λpred
λ = λcons

9.5

30

40

50

Average codebook size

60

70

λ = λpred
λ = λcons

10

9.0

20

Average codebook size

11.0

the best excess distortion, as shown by the left-hand side panel. The intuition behind
Figure 2 is that for small values of n, λpred under-penalizes irrelevant coordinates p ≥ 11
compared to λcons , hence provides a too large support. On the other hand, for large values
of n, the optimal support {1, . . . , 10} is recovered by both regularization strategies, and
in this case the milder penalization λpred leads to better excess distortion. This intuition
is confirmed by Figure 3 below.

500

1000
n

1500

2000

2000

3000

4000

5000

n

Figure 3. Average support size for λ ∼ λ1 (log(n)) and λ ∼ δ(n), over 100 replications.

The left-hand side panel of Figure 3 illustrates the fact that the optimal support is
more efficiently recovered through the λcons regularization strategy. In the case n ≥ 2000
corresponding to the right-hand side panel, the support of the threshold Lass k-means
codebook with regularization parameter λcons is exactly the optimal support in each

Sparse oracle inequalities for variable selection via regularized quantization

17

of the replications, whereas the support corresponding to λpred may sometimes contain
some irrelevant coordinates. This illustrates that the probability of exact support recovery
given by Theorem 3.3 is in fact larger for the λcons strategy than for the λpred strategy.
To apply Theorem 3.3, checking that c∗ is unique remains a hard issue when d > 1.
The following section gives an example where this problem can be tackled using straightforward consequences of Assumption 2.

3.4. Quasi-Gaussian mixture example
The aim of this section is to provide some theoretical background for the application
of Theorem 3.3 to the Gaussian mixture distributions. In general, a Gaussian mixture
distribution P̃ may be defined by its density
f˜(x) =

k̃
X
i=1

t −1
θi
1
p
e− 2 (x−mi ) Σi (x−mi ) ,
|Σi |

(2π)d/2

where k̃ denotes the number ofP
components of the mixture, and the θi ’s denote the weights
k
of the mixture, which satisfy i=1 θi = 1. Moreover, the mi ’s denote the means of the
d
mixture, so that mi ∈ R , and the Σi ’s are the d×d variance matrices of the components.
In this case, we define the active set S̃ as S(m), where m denotes the codebook with
code points the mi ’s. For convenience it is assumed that S̃ = {1, . . . , d′ }, with d′ < d. We
restrict ourselves to the case where the number of components k̃ is known, and match
the size k of the codebooks.
Since the support of a Gaussian random variable is not bounded, we define the “quasiGaussian” mixture model as follows, truncating each Gaussian component. Let the density f of the distribution P be defined by
f (x) =

k
X
i=1

θi
(2π)d/2 N

1

p
e− 2 (x−mi )
i |Σi |

t

Σ−1
i (x−mi )

1B(0,M) ,

where Ni denotes a normalization constant for each Gaussian variable. To ensure that
this model is close to the Gaussian mixture model, M has to be chosen large enough,
2
say M ≥ 2 supj=1,...,k kmj k for instance. Let σ 2 and σ−
denote the largest and smallest
eigenvalues of the Σi ’s. Then the following proposition states that, provided that σ is
small enough, a model consistency result can be derived for the threshold Lasso.
Proposition 3.2. Assume that σ− ≥ c− σ, for some constant c− . Then there exists a
constant σ + such that, if σ ≤ σ + , then Assumption 2 holds, and c∗ is unique.
Moreover, if (Σi )pq = 0, for every (i, p, k) in {1, . . . , k} × {1, . . . , d′ } × {d′ + 1, . . . , d},
then, for every j ≥ d′ + 1, the threshold Lasso with n−1 log(n)δ −2 → 0 satisfies




2
(j)
P ĉn,λ 6= 0
= O e−nδ .
n→∞

18

C. Levrard

The assumption on the covariance matrices requires that the variable in S̃ are independent from the variables in S̃ c . As shown in Section 4.8, this strong requirement
ensures in fact that the support of the optimal codebook is contained in S̃. Proposition
3.2 then directly follows from Theorem 3.3.
The first part of Proposition 3.2 extends the results of Proposition 3.2 in [15] to
arbitrary dimension d. It also enhances the results of this Proposition, showing that
there exists a unique optimal codebook instead of finitely many ones.
It is worth noting that Proposition 3.2 is valid when k = k̃. When k differs from k̃,
Assumption 2 may not be satisfied. For instance, if P is rotationnaly symmetric and
k, d ≥ 2, then M cannot be finite, which contradicts Proposition 2.2.

4. Proofs
4.1. Proof of Proposition 2.1
Let W1 , . . . , Wk be the Voronoi partition associated with ĉn,λ , and let L(ĉn,λ ) be the
matrix of assignments, defined by
L(ĉn,λ )i,j = 1Xi ∈Wj .
(p)

(p)

(p)

(p)

Suppose that ĉn,λ 6= 0, where ĉn,λ denotes the vector (ĉn,λ,1 , . . . , ĉn,λ,k )t , and denote by
(p)

(p)

X (p) the vector (X1 , . . . , Xn )t . Then the Karush-Kuhn-Tucker condition, for this penalized empirical risk minimization strategy, ensures that (see, e.g., the proof of Theorem
2 in [24])
(p)


 √ ŵp ĉ
−2
n,λ
√ L(ĉn,λ )t X (p) − L(ĉn,λ )ĉ(p)
nλ (p) = 0.
n,λ +
n
kĉn,λ k


(p)
Since L(ĉn,λ )t X (p) − L(ĉn,λ )ĉn,λ is the following vector of size k
!
X
X
(p)
(p)
(p)
(p)
(Xi − ĉn,λ,k ) ,
(Xi − ĉn,λ,1 ), . . . ,
Xi ∈W1

(10)

Xi ∈Wk

it may be noted that


(p)
L(ĉn,λ )t X (p) − L(ĉn,λ )ĉn,λ

2

=

k
X
j=1

(p)

(p)

n2j (c̄j − ĉn,λ,j )2 ,

where nj denotes the number of sample vectors Xi ’s in WP
j , and c̄j denotes the empirical
mean of the sample over the set Wj , that is c̄j = n1j Xi ∈Wj Xi . Denote by p̂j the
empirical weight of Wj , i.e. p̂j = nj /n, then


1
(p)
(p)
t
)ĉ
X
−
L(ĉ
)
L(ĉ
n,λ
n,λ
n,λ
n2

2

≤

k
X
j=1

(p)

(p)

p̂j (c̄j − ĉn,λ,j )2 ,

Sparse oracle inequalities for variable selection via regularized quantization

19

where p̂j ≤ 1 has been used. Let Q1 be the quantizer which maps Wj to c̄j , then it is
easy to see that
k
X
(p)
(p)
p̂j (c̄j − ĉn,λ,j )2 = R̂p (ĉn,λ ) − R̂p (Q1 ),
j=1

(p)

where we recall that R̂p (Q) = Pn kx − Q(x)k2 , for any quantizer Q.
(−p)
Denote by ĉn,λ the codebook that has p-th coordinate 0 and the same coordinates
(−p)

as ĉn,λ otherwise, and let Q2 be the quantizer which maps Wj to ĉn,λ,j . Then, by defi(−p)

(−p)

(−p)

nition, R̂(ĉn,λ ) + Iŵ (ĉn,λ ) ≤ R̂(ĉn,λ ) + λIŵ (ĉn,λ ), and R̂(ĉn,λ ) ≤ R̂(Q2 ). Thus, direct
calculation leads to σ̂p2 ≥ R̂p (ĉn,λ ), according to (3). Since R̂p (ĉn,λ ) − R̂p (Q1 ) ≤ σ̂p2 − R̂p ,
(10) ensures that
q
λŵp
≤ σ̂p2 − R̂p .
2

4.2. Proof of Proposition 2.2
As mentioned below Proposition 2.2, a proof of the two first statements can be found
in the
 proof of Proposition 2.2 in [15]. The last statement follows from the compactness
of c ∈ C k |S(c) ( S(c∗ ) and the fact that M is finite, knowing that R() is continuous (see, e.g., Lemma 4.1 in [15]). This ensures that inf c∗ ∈M inf S(c)(S(c∗ ) ℓ(c, c∗ ) ≥
c > 0, for some constant c, whenever Assumption 1 is satisfied. Since C k is bounded,
supc∗ ∈M,S(c)(S(c∗ ) kc − c∗ k2 /ℓ(c, c∗ ) is finite.

4.3. Proof of Theorem 3.1
We recall here that√T (w) denotes the quantity T (w) = maxp=1,...,d Mp /wp . Let also
M̄ (w) be defined as kkwk2 T (w). It is immediate that, for every c in C k , Iw (c) ≤ M̄ (w).
Moreover, we define γ̄ by
γ̄(c, x) = min −2 hx, cj i + kcj k2 ,
j=1,...,k

for every c in C k and x in Rd . The prediction results of this paper are based on the
following concentration inequality, which connects the deviation of the empirical processes (P − Pn )γ̄(c, .) to the Iw norm. Note that, since γ̄ is continuous and (Rd )k+1 is
a separable metric space, the empirical processes introduced throughout the derivation
are measurable.
Proposition 4.1.
 that w is a deterministic sequence of weights. Denote by u
 Suppose
2√
kwk n
. If we denote by
the quantity log √
log(kd)

√
λ0 = 8 2π

r

k log(kd)
T (w),
n

20

C. Levrard

then, for every x > 0, denoting by
r


u+x
,
λ1 = eλ0 1 +
k log kd
we have, for any fixed c′ in C k , with probability larger than 1 − e−x ,
|(P − Pn )(γ̄(c, .) − γ̄(c′ , .))|
≤ λ1 .
Iw (c − c′ ) ∨ λ0
Iw (c−c′ )≤2M̄ (w)
sup

(11)

Proposition 4.1 may be thought of as a slight generalization of inequality (7) in [29].
Its proof, given in Section 5.2 of the Appendix, differs from the original one by the use
of Gaussian complexities rather than Talagrand’s generic chaining principle to derive a
multivariate contraction principle. We are now in position to prove Theorem 3.1.
λ1
. From Assumption 3, it easily follows that (1−κ1 )Iw (c) ≤
We recall here that λ ≥ 1−κ
1
Iŵ (c) ≤ (1 + κ1 )Iw (c), with probability larger than 1 − r1 (n). On this event, we have,
for every c in C k ,
Pn γ̄(ĉn,λ , .) + λ(1 − κ1 )Iw (ĉn,λ ) ≤ Pn γ̄(c, .) + λ(1 + κ1 )Iw (c).
Using (11), with c′ = 0, it follows that
P γ̄(ĉn,λ , .) ≤ P γ̄(c, .) + λ(1 + κ1 )Iw (c) + λ1 (Iw (c) ∨ λ0 )

+ λ1 (Iw (ĉn,λ ) ∨ λ0 ) − λ(1 − κ1 )Iw (ĉn,λ ). (12)

If Iw (ĉn,λ ) > λ0 , adding −P γ̄(c∗ , .) on the both sides leads to
ℓ(ĉn,λ , c∗ ) ≤ ℓ(c, c∗ ) + λ(1 + κ1 )Iw (c) + λ1 (Iw (c) ∨ λ0 ).
Hence
ℓ(ĉn,λ , c∗ ) ≤ inf

inf

r>0 Iw (c)≤r

ℓ(c, c∗ ) + 2λ(r ∨ λ0 ).

If Iw (ĉn,λ ) ≤ λ0 , (12) may be written
ℓ(ĉn,λ , c∗ ) ≤ ℓ(c, c∗ ) + 2λ(Iw (c) ∨ λ0 ) + λ(1 − κ1 )λ0 ,
hence
ℓ(ĉn,λ , c∗ ) ≤ inf

inf

r>0 Iw (c)≤r

ℓ(c, c∗ ) + (3 − κ1 )λ(r ∨ λ0 ).

4.4. Proof of Proposition 3.1
Let S be a subset of {1, . . . , d}, and let p be in S such that
σp2 − Rp∗ <

8κ0 λ2 wp2
.
3

Sparse oracle inequalities for variable selection via regularized quantization

21

Denote by c∗S an optimal codebook with support S, that is
c∗S = argmin R(c).
S(c)=S

Then, according to (3), we may write
∗
2
∗
2
∗
+ σ(S\{p})
R(c∗S\{p} ) − R(c∗S ) ≤ RS\{p}
c − (RS\{p} + Rp ) − σS c

≤ σp2 − Rp∗ .

Therefore
3R(c∗S\{p} ) + 8λ2 κ0 kwS\{p} k2 < 3R(c∗S ) + 8λ2 κ0 kwS k2 .

4.5. Proof of Theorem 3.2
Let c be a fixed codebook in C k , and c′ be another codebook in C k . Following the notation
of [29], with a slight abuse of notation, we denote by Iw,1 (c′ − c) and Iw,2 (c′ − c) the
quantities

Iw,1 (c′ − c) = Iw ((c′ − c)S(c) ),
Iw,2 (c′ − c) = Iw ((c′ − c)S c (c) ).
The following result is derived from Lemma A.4 in [28].
Lemma 4.1. Let c and c′ be in C k , and denote by c∗ = c∗ (c′ ). If S(c) ( S(c∗ ) or
c∗ (c) = c∗ , for any δ > 0, we have
2λIw,1 (c′ − c) ≤

1
1
ℓ(c, c∗ ) + ℓ(c′ , c∗ ) + 2δκ0 λ2 kwS(c) k2 .
δ
δ

(13)

The proof of Lemma 4.1 can be found in [28]. For the sake of completeness it is briefly
recalled here.
Proof of Lemma 4.1. Using Cauchy-Schwarz inequality, it is easy to see that
s X
wp2 kc′ − ck
2λIw,1 (c′ − c) ≤ 2λ
p∈S(c)

s X
≤ 2λ
wp2 (kc′ − c∗ k + kc − c∗ k).
p∈S(c)

Using the inequality 2ab ≤ κ0 δa2 +
2λIw,1 (c′ − c) ≤

1 2
δκ0 b

and Proposition 2.2 leads to

1
(ℓ(c, c∗ ) + ℓ(c′ , c∗ )) + 2δκ0 λ2 kwS(c) k2 .
δ

22

C. Levrard

Equipped with this Lemma, we are in position to prove Theorem 3.2. By definition,
ĉn,λ satisfies
Pn γ̄(ĉn,λ , .) + λIŵ (ĉn,λ ) ≤ Pn γ̄(c, .) + λIŵ (c).
Using Proposition 4.1, we get
P γ̄(ĉn,λ , .) + λIŵ,2 (ĉn,λ − c) ≤ P γ̄(c, .) + λIŵ,1 (ĉn,λ − c) + λ1 (λ0 ∨ Iw (ĉn,λ − c)).
(14)
If Iw (ĉn,λ − c) > λ0 , then adding −P γ̄(c∗ , .) on the both sides an using Assumption 3
leads to
ℓ(ĉn,λ , c∗ ) + (1 − κ1 )λIw,2 (ĉn,λ − c) ≤ ℓ(c, c∗ ) + (1 + κ1 )λIw,1 (ĉn,λ − c) + λ1 Iw (ĉn,λ − c).
Hence, if c∗ (c) = c∗ (ĉn,λ ) = c∗ or S(c) ( S(c∗ ),
ℓ(ĉn,λ , c∗ ) + [(1 − κ1 )λ − λ1 ] Iw (ĉn,λ − c) ≤ ℓ(c, c∗ ) + 2λIw,1 (ĉn,λ − c)
3
1
≤ ℓ(c, c∗ ) + ℓ(ĉn,λ , c∗ ) + 4κ0 λ2 kwS(c) k2 ,
2
2
according to Lemma 4.1, with δ = 2. Noting that λ1 ≤ (1 − κ1 )λ/2 yields
ℓ(ĉn,λ , c∗ ) + (1 − κ1 )λIw (ĉn,λ − c) ≤ 3ℓ(c, c∗ ) + 8κ0 λ2 kwS(c) k2 .
If Iw (ĉn,λ − c) ≤ λ0 , then combining Assumption 3 with (14) entails
ℓ(ĉn,λ , c∗ ) + (1 − κ1 )λIw (ĉn,λ − c) ≤ ℓ(c, c∗ ) + 2λIw,1 (ĉn,λ − c) + λ1 λ0
≤ ℓ(c, c∗ ) + 3λλ0 .
Since c∗λ (ĉn,λ ) satisfies S(c∗λ (ĉn,λ )) ( S(c∗ (ĉn,λ )) or c∗ (ĉn,λ ) = c∗ (c∗λ (ĉn,λ )), choosing
c = c∗λ gives the result.

4.6. Proofs of Corollary 3.1 and Corollary 3.2
For the plain√Lasso, log(d)n−1 →
√ 0 and supp=1,...,d Mp = O(1) ensures that λ0 → 0.
n−1 λ−2 log(d n) yields λ1 (log(d n)) = O(λ). Applying Theorem 3.1 or 3.2 gives the
results for ℓ(ĉn,λ , c∗ ) and ℓ(ĉn,λ , c∗ ) + λ(1 − κ1 )Iw (ĉn,λ − c∗λ (ĉn,λ )), since κ0 = O(1). The
result on kĉn,λ − c∗ (ĉn,λ )k follows from Proposition 2.2.
Similarly, for the normalized Lasso, the additional requirement 1 = O(minp=1,...,d σp )
according to Proposition 2.3. In turn,
entails λ0 → 0, and Assumption 3 is satisfied,
√
maxp=1,...,d σp = O(1) leads to λ1 (log(d n)) = O(λ), hence the results.
At last, for the threshold Lasso, supp=1,...,d Mp = O(1), δ → 0 and dn−1 δ −2 imply that
Assumption 3 is satisfied, λ0 → 0, and d = O(n). Since T (δ) = O(1), combining d = o(n)
with λ−1 log(n)1/2 n−1/2 = o(1) leads to λ1 (log(n)) = o(λ). Noting that κ0 = O(1) and
applying Theorem 3.2 gives the result.

Sparse oracle inequalities for variable selection via regularized quantization

23

4.7. Proof of Theorem 3.3
Let j be in S(c∗ )c , and denote by f (n) the quantity nδ 2 ∼ nλ2 . Since n−1 δ −2 log(n)
→ 0, then log(n) = o(f (n)). Hence Assumption 3 holds, for some 0 < κ1 < 1, with
2
r1 (n) = O(e−nδ ). Theorem 3.3 follows from the Karush-Kuhn-Tucker condition, as in
[24], combined with some standard deviation bounds, which are listed below. Throughout
this derivation, K will denote a generic positive constant not depending on n.
Proposition 4.2.

Then, we have

For every x in Rd , let G(j) (x, c∗ ) denote the k dimensional vector


x(j) 1W1 (c∗ ) (x), . . . , x(j) 1Wk (c∗ ) (x) .



P (P − Pn )G(j) (., c∗ ) ≥ Kn−1/2 f (n)1/2
h
i
P
P supc∈C k |(Pn − P ) i6=p 1Wi (c)∩Wp (c∗ ) | ≥ Kn−1/2 f (n)1/2

= O(e−f (n) ),
= O(e−f (n) ).
(j)

The proof of Proposition 4.2 is deferred to Section 5.4. Assume that ĉn,λ 6= 0, then
the K.K.T condition yields
(j)

ĉn,λ
√
√
2
2
(j)
√ kL̂X̂ (j) k =
nλŵj (j) + √ L̂t L̂ĉn,λ ≥ nλŵj ,
n
n
kĉ k
n,λ

√
since L̂t L̂ is positive. According to Proposition 2.3, it follows that nλŵj ≥ (1 − κ1 )n1/2 ,
with probability larger than 1 − O(e−f (n) ), when n is large enough. On the other hand,
we have
kL(ĉn,λ )X (j) k ≤ kL(c∗ )X (j) k + k(L(ĉn,λ ) − L(c∗ ))X (j) k
X
1Wi (ĉn,λ )∩Wp (c∗ ) .
≤ nkPn G(j) (., c∗ )k + M (j) nPn
i6=p

According to the centroid condition, P G(j) (., c∗ ) = 0. Thus, it follows from Proposition
4.2 that kPn G(j) (., c∗ )k ≤ Kn−1/2 f (n)1/2 with probability 1 − O(e−f (n) ). Lemma 4.2 in
[15] ensures that
X
P
1Wi (ĉn,λ )∩Wp (c∗ ) ≤ p(Kkĉn,λ − c∗ k) ≤ Kkĉn,λ − c∗ k,
i6=p

according to Assumption 2. Besides, since log(n)P= o(f (n)), we may write λ ∼ λ1 (f (n)).
∗,(i)
k, Theorem 3.2 yields
Taking into account that kwS(c∗ ) k tends to
i∈S(c∗ ) 1/kc
∗
2
−f (n)
ℓ(ĉn,λ , c ) ≤ Kλ , with probability larger than 1 − O(e
), for n large enough. On
the same event, Proposition 2.2 gives kĉn,λ − c∗ k ≤ Kλ, which leads to
X
Pn
1Wi (ĉn,λ )∩Wp (c∗ ) ≤ Kλ,
i6=p

24

C. Levrard

with probability larger than 1 − O(e−f (n) ), according to Proposition 4.2. Then the K.K.T
condition entails
(1 − κ1 )n1/2 ≤ Kn1/2 λ,

with probability larger than 1 − O(e−f (n) ), which is impossible when n is large enough.
(j)
Conversely, if j is in S(c∗ ) and ĉn,λ = 0, then the K.K.T condition yields
2
kL(ĉn,λ )X̂ (j) k ≤ λŵj .
n

Since wj tends to 1/kc∗,(j) k and kP G(j) (., c∗ )k > 0, according to the centroid condition,
using the same concentration bounds as above leads to a contradiction.

4.8. Proof of Proposition 3.2
The first part of Proposition 3.2 is derived from the following Lemma, which extends
Proposition 3.2 of [15]. We denote by B̃ the quantity inf i6=j kmi − mj k.
Lemma 4.2.
as follows.

Denote by η = supj=1,...,k 1 − Ni . Then the risk R(m) may be bounded
R(m) ≤

σ 2 kθmax d
,
(1 − η)

(15)

where θmax = maxj=1,...,k θj . For any 0 < τ < 1/2, let c be a codebook with a code point
ci such that kci − mj k > τ B̃, for every j in {1, . . . , k}. Then we have
τ 2 B̃ 2 θmin
R(c) >
4

!d
√
2σ d − τ 2 B̃22
1− √
,
e 4dσ
2πτ B̃

(16)

where θmin = minj=1,...,k θj . At last, if σ − ≥ c− σ, for any τ ′ such that 2τ + τ ′ < 1/2,
we have
′

∀t ≤ τ B̃

′
1
2k 2 θmax M d−1 Sd−1 − [ 2 −(2τ +τ2 )]
2σ
p(t) ≤ t
e
(2π)d/2 (1 − η)cd− σ d

2

B̃ 2

,

(17)

where Sd−1 denotes the Lebesgue measure of the unit ball in Rd−1 .
The proof of Lemma 4.2 follows from direct calculation, as in the proof of Proposition
3.2 of [15]. For the sake of completeness it is given in Section 5.5 of the√Appendix.
Let τ and τ ′ be positive quantities satisfying 2τ +τ ′ < 1/2, and τ ′ > 8 2M τ /(1−2τ )B̃.
According to (15) and (16), if σ is small enough, then every optimal codebook c∗ satisfies
supj=1,...,k kmj − c∗j k ≤ τ B̃, up to relabeling code points.
On the other hand, (17) ensures that, for σ small enough, P satisfies Assumption 2
with radius r0 ≥ τ ′ B̃. Let c∗ be an optimal codebook. According to i) of Proposition 2.2

Sparse oracle inequalities for variable selection via regularized quantization

25

√
be found in a ball of radius (1 − 2τ )B̃τ ′ /4 2M
in [15], no other optimal codebook can
√
centered at c∗ . Since (1 − 2τ )B̃τ ′ /4 2M > 2τ , this proves that c∗ must be unique.
To apply Theorem 3.3, we need to show that S(c∗ ) ⊂ S̃. Suppose that there exists
j ≥ d′ + 1 such that c∗,(j) 6= 0. Let s denote the orthogonal transformation defined by
s(x1 , . . . , xd′ , xd′ +1 , . . . , xd ) = (x1 , . . . , xd′ , −xd′ +1 , . . . , −xd ). Since (Σi )p,q = 0, for every
(i, p, k) in {1, . . . , k} × {1, . . . , d′ } × {d′ + 1, . . . , d}, P is invariant through composition
by s. Hence s(c∗ ) is an optimal codebook, and c∗ 6= s(c∗ ), which contradicts the fact
that c∗ is unique.

Acknowledgement
The author is supported by the ANR project TopData ANR-13-BS01-0008.

5. Appendix
5.1. Proof of Proposition 2.3
A bounded difference inequality such as Theorem 6.2 of [5] yields, for x > 0,
#
!
"
2
σ̂p2
σ̂p2
− T2nx
4 (σ)
.
P
max
−
1
−
1
+
x
≤
e
≥
E
max
2
2
p=1,...,d σp
p=1,...,d σp
Besides, Theorem 2.8 of [5] ensures that, for every p = 1, . . . , d, σ̂p2 /σp2 −1 is a subgaussian
random variable with variance bounded by T (σ)4 /4n. For a comprehensive introduction
to subgaussian random variables and its application to empirical process theory, the
interested reader is referred to Section 2.3 of [5] or Chapter 14 of [6]. A direct application
of Theorem 2.5 of [5] leads to
"
#
p
σ̂p2
T (σ)2 log(d)
√
,
−
1
E max
≤
2
p=1,...,d σp
2n
hence

p

!
r
σ̂p2
T (σ)2 log(d)
x
√
P
max
1+
≤ e−x .
−1 ≥
2
p=1,...,d σp
log(d)
2n
 √
2
p
√
2nκ
1
√
Since 2nκ1 > T (σ)2 log(d), choosing x = log(d)
−
1
leads to the
2
T (σ)

log(d)

result.
For the threshold Lasso with unique optimal codebook, Theorem 3.1 in [15], combined
with Assumption 2, provides a constant C0 such that
r 
x
k
∗
1+
,
kĉn − c k ≤ C0 M
n
k

26

C. Levrard

with probability larger than 1 − e−x . Since, for every p in {1, . . . , d},
kc∗,(p) k ∨ δ
(p)

kĉn k ∨ δ

(p)

−1 ≤

kc∗,(p) k ∨ δ − kĉn k ∨ δ
δ

≤

kĉn − c∗ k
,
δ

the results easily follows.

5.2. Proof of Proposition 4.1
For a fixed c in ck , denote by Zr (c) the following random variable
Zr (c) =

sup
Iw (c′ −c)≤r

|(P − Pn )(γ̄(c′ , .) − γ̄(c, .))| .

The following proposition gives a non-asymptotic bound on Zr (c).
Proposition 5.1. Suppose that kd > 1 and w is deterministic. Let x > 0, and c be a
fixed codebook. Then, with probability larger than 1 − e−x ,
r


r
√
k log(kd)
x
1
Zr (c) ≤ 8 2π
.
rT (w) 1 + √
n
4 π k log(kd)
The proof of Proposition 5.1 is postponed to the next subsection. Proposition 4.1
derives from a peeling argument, as in Section 3.4 of [29], combined with Proposition
5.1. Let a be the smallest integer
that e−(a−1) 2M̄ (w) ≤ λ0 , and take u0 = log(a)
√ such
2
(we recall here that M̄ (w) = kkwk T (w) is an upper bound on Iw (c), for c in C k ).
Then it is easy to see that u0 ≤ u, where u is defined in Proposition 4.1. We may write
!
|(P − Pn )(γ̄(c′ , .) − γ̄(c, .))|
P
sup
≥ λ1
Iw (c′ − c) ∨ λ0
Iw (c′ −c)≤2M̄ (w)


≤

a−1
X

P

j=1


|(P − Pn )(γ̄(c′ , .) − γ̄(c, .))|
≥ λ1 

−j
2e M̄ (w)
Iw (c′ −c)≤2e−(j−1) M̄ (w)
sup

Iw (c′ −c)≥2e−j M̄ (w)

|(P − Pn )(γ̄(c′ , .) − γ̄(c, .))|
+P
sup
≥ λ1
2e−a M̄ (w)
Iw (c′ −c)≤2e−(a−1) M̄ (w)
r



a
X
u+x
P Z2e−(j−1) M̄(w) ≥ 2e−(j−1) M̄ (w)λ0 1 +
≤
k log kd
j=1

!

≤ ae−u e−x ,

where the last inequality follows from Proposition 5.1. Noticing that ae−u ≤ 1 proves
the result.

Sparse oracle inequalities for variable selection via regularized quantization

27

5.3. Proof of Proposition 5.1
This proof is a slight modification of the proof of Theorem 3.1 in [15], and mainly relies
on the use of Gaussian complexities combined with Slepian’s Lemma (see, e.g., Theorem
13.3 in [5]). For every j = 1, . . . , k, if Iw (c′ − c) ≤ r, then, for all x in C, using |a2 − b2 | ≤
2 max(|a|, |b|)|a − b| for a,b in R and the Cauchy-Schwarz inequality, we get
−2

x, c′j

+

kc′j k2

+ 2 hx, cj i − kcj k

2

≤2
≤4

d
X
p=1

′(p)
|x|p cj

d
X
Mp
p=1

wp

wp

−

k
X
l=1

(p)
cj

+

d
X

′(p) 2

cj

p=1

(p) 2

− cj

(p)
1(l = j) c′(p)
− cl
l

≤ 4T (w)Iw (c′ − c) ≤ 4rT (w).
which leads to
kγ̄(c′ , .) − γ̄(c, .)k∞ := sup kγ̄(c′ , x) − γ̄(c, x)k ≤ 4rT (w).
x∈C

As a consequence, a bounded difference concentration inequality (see, e.g., Theorem 6.2
in [5]) yields, with probability larger than 1 − e−x ,
r
2x
.
Zr (c) ≤ EZr (c) + 4rT (w)
n
It remains to bound from above EZr (c). According to the symmetrization principle (see,
e.g., Section 2.2 of [14]), introducing some independent Rademacher variables εi and
standard Gaussian variables gi (also independent of the εi ’s), we have
n

1X
εi (γ̄(c′ , Xi ) − γ̄(c, Xi ))
Iw (c′ −c)≤r n i=1
" n
#
r
1X
π
′
=2
εi |gi |(γ̄(c , Xi ) − γ̄(c, Xi ))
EX Eε
sup
Eg
2
n i=1
Iw (c′ −c)≤r
r
n
π
1X
≤2
gi (γ̄(c′ , Xi ) − γ̄(c, Xi )).
EX Eg
sup
2
Iw (c′ −c)≤r n i=1

EZr (c) ≤ 2EX Eε

sup

Let c and X1 , . . . , Xn be fixed, and define, for c′ such that Iw (c′ − c) ≤ r the Gaussian
process
n
X
gi (γ̄(c′ , Xi ) − γ̄(c, Xi )).
Yc′ =
i=1

Since, for every codebooks c′1 and c′2 ,

(γ̄(c′1 , Xi ) − γ̄(c′2 , Xi ))2 ≤ max 8 c′1,j − c′2,j , Xi
j=1,...,k

2

+ 2(kc′1,j k2 − kc′2,j |2 )2 ,

28

C. Levrard

it is easy to see that
Var(Yc′1 − Yc′2 ) ≤

n X
k
X
i=1 j=1

2

8 c′1,j − c′2,j , Xi

+ 2n

k
X
j=1

(kc′1,j k2 − kc′2,j k2 )2 .

To derive bounds on the Gaussian complexity defined above, the following comparison
result between Gaussian processes is needed.
Theorem 5.1 (Slepian’s Lemma). Let V be a separable metric space, and Yt , Nt , t in
V, be some continuous centered real Gaussian processes. Assume that
∀t1 , t2 ∈ V

Var(Yt1 − Yt2 ) ≤ Var(Nt1 − Nt2 ),

then
E sup Yt ≤ E sup Nt .
t∈V

t∈V

Theorem 5.1 is a straightforward extension of Theorem 13.3 in [5] to separable index
sets. Denote by V the separable set of codebooks c′ in C k such that Iw (c′ − c) ≤ r. Now
introduce, for c′ such that Iw (c′ − c) ≤ r, the following Gaussian process
n X
k
k
√ X
√ X
(kc′j k2 − kcj k2 )ξj′ ,
c′j − cj , Xi ξi,j + 2n
Nc′ = 2 2
i=1 j=1

j=1

where the ξ’s and ξ ′ ’s are independent standard Gaussian random variables. Note that
c′ 7→ Nc′ is continuous, and for all c′1 and c′2 in V, Var(Yc′1 − Yc′2 ) ≤ Var(Nc′1 − Nc′2 ).
Consequently, applying Theorem 5.1 yields
Eg

sup
Iw (c′ −c)≤r

Yc′ ≤ Eξ,ξ′

sup
Iw (c′ −c)≤r

Nc′ .

It follows that
Eξ,ξ′

sup
Iw (c′ −c)≤r

Nc′ ≤ Eξ

sup
Iw (c′ −c)≤r

n X
k
√ X
2 2
c′j − cj , Xi ξi,j
i=1 j=1

+ Eξ′

sup
Iw (c′ −c)≤r

k
√ X
(kc′j k2 − kcj k2 )ξj′ .
2n
j=1

Sparse oracle inequalities for variable selection via regularized quantization

29

The first term of the right side can be bounded as follows.
Eξ

sup
Iw (c′ −c)≤r

√
≤ 2 2Eξ
√
≤ 2 2Eξ

n X
k
√ X
c′j − cj , Xi ξi,j
2 2
i=1 j=1
k
X

sup

Iw (c′ −c)≤r j=1

sup
Iw (c′ −c)≤r

√
≤ 2 2krEξ




*

c′j

− cj ,

k X
d
X
j=1 p=1

max

j=1,...,k,p=1,...,d

+

n
X

ξi,j Xi

(p)

(p)

i=1



wp |c′ j − cj | max

n
X

(p)
ξi,j Xi

wp

i=1

j,p

n
(p)
X
ξi,j X
i

i=1

wp

.

Pn ξ X (p)
Note that, for every (j, p), the random variable i=1 i,jwpi is Gaussian, with variance
bounded by nT 2 (w). Consequently, applying Theorem 2.5 in [5] gives
Eξ

n
(p)
X
ξi,j X
i

max

j=1,...,k,p=1,...,d

wp

i=1

p
≤ T (w) 2n log(kd).

In turn, the second term of the right side may be bounded by
Eξ′

sup
Iw (c′ −c)≤r

k
√ X
(kc′j k2 − kcj k2 )ξj′
2n
j=1

≤

√

2nEξ′

sup

d
k
X
X

Iw (c′ −c)≤r j=1

√
≤ 2 2nT (w)Eξ′
√

p=1

sup
Iw (c′ −c)≤r

≤ 2T (w)r 2nk.

(p)
wp |c′ j

−

(p) 2Mp
cj |
wp

!

ξj′

v
u k
uX 2
′
I(c − c)t
ξ′ j
j=1

Combining these two bounds leads to
√
EZr (c) ≤ 8 2π

r

k log(kd)
rT (w).
n

5.4. Proof of Proposition 4.2
For every u in Rk , let us denote by Yu the function u, G(j) (., c∗ ) , so that k(P −
Pn )G(j) (., c∗ )k = supkuk≤1 (P − Pn )Yu := Y . Since, for every u such that kuk ≤ 1 and

30

C. Levrard

for every x in C, |Yu (x)| ≤ Mj , a bounded difference inequality yields (see, e.g., Theorem
6.2 in [5]), with probability larger than 1 − e−x ,
r
2x
.
Y ≤ EY + Mj
n
An upper bound on EY may be derived the same way as in the proof of Proposition
5.1: introducing some Rademacher random variables εi , i = 1, . . . , n, and using the
symmetrization principle, we get
+
*
n
1X
(j)
∗
εi G (Xi , c )
EY ≤ 2EX,ε sup u,
n i=1
kuk≤1
v
u
2
n
X
2u
t
(j)
∗
εi G (Xi , c )
≤
EX,ε
n
i=1
2Mj
≤ √ ,
n

according to Cauchy-Schwarz and Jensen’s inequalities. Choosing x = f (n) gives the first
concentration inequality of Proposition 4.2.
k
Now consider the {0, 1}-valued random variables
by Yc =
S Yc , indexed by∗ C , defined
S
1 i6=p Wi (c)∩Wp (c∗ ) . According to [21], the sets { i6=p Wi (c) ∩ Wp (c )|c ∈ C k } have finite
VC-dimension, say D. Using the well-known Vapnik-Chervonenkis bound (see, e.g., [4]),
combined with a bounded difference concentration inequality yields
r 
r 
D
x
Pn Yc ≤ P Yc + K
1+
,
n
D
with probability larger than 1 − e−x , for every c in C k , and for some absolute constant
K. Choosing x = f (n) provides the second inequality of Proposition 4.2.

5.5. Proof of Lemma 4.2
The proof of Proposition 4.2 follows from the Proof of Proposition 3.2 in [15]. To give an
upper bound on R(m), we may write
R(m) =

k
X
i=1

k
X

k

X
θi
p
d/2
(2π) Ni |Σi | j=1

Z

1

Wj (m)

kx − mj k2 e− 2 (x−mi )

t

Σ−1
i (x−mi )

Z
t −1
1
p
kx − mi k2 e− 2 (x−mi ) Σi (x−mi ) dx
d/2
|Σi | Rd
i=1 (1 − η)(2π)
Z
k
X
p
2
1
θi
Σi uk2 e− 2 kuk du,
≤
k
d/2
(1 − η)(2π)
Rd
i=1

≤

θi

1B(0,M) (x)dx

Sparse oracle inequalities for variable selection via regularized quantization

31

√
where Σi denotes the square root
√ of the matrix Σi . Since Σi has its largest eigenvalue
bounded by σ 2 , it follows that k Σi uk2 ≤ σ 2 kuk2 , for every u in Rd . We deduce that
Z
2
1
σ 2 kθmax
R(m) ≤
kuk2 e− 2 kuk du
d/2
(2π) (1 − η) Rd
σ 2 kθmax d
≤
,
(1 − η)
which proves (15). Now let c be a codebook, and let i be such that kci − mj k > τ B̃, for
every j in {1, . . . , k}, with τ < 1/2. Since B(mi , τ B̃/2) ⊂ B(0, M ), we may write
!2
Z
t −1
τ B̃
θi
1
p
R(c) >
e− 2 (x−mi ) Σi (x−mi ) dx
2
(2π)d/2 |Σi |
B(mi ,τ B̃/2)
Z
2
1
θmin τ 2 B̃ 2
e− 2 kuk du
>
4(2π)d/2 √Σi −1 B(0,τ B̃/2)
Z
2
θmin τ 2 B̃ 2
1
>
e− 2 kuk du.
d/2
B̃
4(2π)
B(0, τ2σ
)
h
√
√ id
R∞
2
2
Since, for every positive r, −r/ d, r/ d ⊂ B(0, r), and r e−r /2 dr ≤ e−r /2 /r, it
follows that
!d
Z τ B̃
√
2σ d
r2
θmin τ 2 B̃ 2
2
e− 2 dr
R(c) >
4(2π)d/2
0
!d
√
2σ d − τ 2 B̃22
τ 2 B̃ 2 θmin
1− √
e 4dσ
>
,
4
2πτ B̃
which proves (16). At last, let τ ′ be such that 2τ + τ ′ < 12 , and let y be in Nc∗ (τ ′ B̃).


Then, for every i in {1, . . . , k}, we have kmi − yk ≥ 12 − (2τ + τ ′ ) B̃. Hence
[ 1 −(2τ +τ ′ )]2 B̃2
kθmax
− 2
2σ2
e
.
f (y) ≤
d
(2π)d/2 (1 − η)σ−

Since σ− ≥ c− σ and λ(Nc∗ (t)) ≤ 2tkM d−1Sd−1 , straightforward calculation leads to
(17).

References
[1] Antoniadis, A., Brossat, X., Cugliari, J. and Poggi, J.-M. (2013). Clustering functional data using wavelets. Int. J. Wavelets Multiresolut. Inf. Process. 11
1350003, 30. MR3038615

32

C. Levrard

[2] Bach, F. R. (2008). Consistency of the group lasso and multiple kernel learning.
J. Mach. Learn. Res. 9 1179–1225. MR2417268 (2010a:68132)
[3] Biau, G., Devroye, L. and Lugosi, G. (2008). On the performance
of clustering in Hilbert spaces. IEEE Trans. Inform. Theory 54 781–790.
MR2444554 (2009m:68221)
[4] Boucheron, S., Bousquet, O. and Lugosi, G. (2005). Theory of classification: a survey of some recent advances. ESAIM Probab. Stat. 9 323–375.
MR2182250 (2006g:68234)
[5] Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration inequalities.
Oxford University Press, Oxford. MR3185193
[6] Bühlmann, P. and van de Geer, S. (2011). Statistics for high-dimensional data.
Springer Series in Statistics. Springer, Heidelberg. MR2807761
[7] Chang, X., Wang, Y., Li, R. and Xu, Z. (2014). Sparse K-Means with ℓ∞ /ℓ0
Penalty for High-Dimensional Data Clustering. ArXiv e-prints.
[8] De Soete, G. and Carroll, J. D. (1994). K-means clustering in a low-dimensional
Euclidean space. In New Approaches in Classification and Data Analysis, (E. Diday, Y. Lechevallier, M. Schader, P. Bertrand and B. Burtschy, eds.). Studies in
Classification, Data Analysis, and Knowledge Organization 212-219. Springer Berlin
Heidelberg.
[9] Fischer, A. (2010). Quantization and clustering with Bregman divergences. J.
Multivariate Anal. 101 2207–2221. MR2671211 (2012c:62188)
[10] Gersho, A. and Gray, R. M. (1991). Vector quantization and signal compression.
Kluwer Academic Publishers, Norwell, MA, USA.
[11] Graf, S. and Luschgy, H. (2000). Foundations of quantization for probability distributions. Lecture Notes in Mathematics 1730. Springer-Verlag, Berlin.
MR1764176 (2001m:60043)
[12] Graf, S., Luschgy, H. and Pagès, G. (2007). Optimal quantizers for
Radon random vectors in a Banach space. J. Approx. Theory 144 27–53.
MR2287375 (2007k:41084)
[13] Jin, J. and Wang, W. (2014). Important Feature PCA for high dimensional clustering. ArXiv e-prints.
[14] Koltchinskii, V. (2006). Local Rademacher complexities and oracle inequalities
in risk minimization. Ann. Statist. 34 2593–2656. MR2329442 (2009h:62060)
[15] Levrard, C. (2015). Nonasymptotic bounds for vector quantization in Hilbert
spaces. Ann. Statist. 43 592–619. MR3316191
[16] Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Trans. Inform.
Theory 28 129–137. MR651807 (84a:94012)
[17] Massart, P. and Meynet, C. (2011). The Lasso as an ℓ1 -ball model selection
procedure. Electron. J. Stat. 5 669–687. MR2820635 (2012m:62210)
[18] Maugis-Rabusseau, C. and Michel, B. (2013). Adaptive density estimation for
clustering with Gaussian mixtures. ESAIM Probab. Stat. 17 698–724. MR3126158
[19] Meynet, C. (2013). An ℓ1 -oracle inequality for the Lasso in finite mixture Gaussian
regression models. ESAIM Probab. Stat. 17 650–671. MR3126156
[20] Pollard, D. (1981). Strong consistency of k-means clustering. Ann. Statist. 9 135–

Sparse oracle inequalities for variable selection via regularized quantization

33

140. MR600539 (83c:62098)
[21] Pollard, D. (1982). A central limit theorem for k-means clustering. Ann. Probab.
10 919–926. MR672292 (84c:60047)
[22] Rigollet, P. and Tsybakov, A. (2011). Exponential screening and optimal rates
of sparse estimation. Ann. Statist. 39 731–771. MR2816337
[23] Steinley, D. and Brusco, M. J. (2008). Selection of variables in cluster analysis: an empirical comparison of eight procedures. Psychometrika 73 125–144.
MR2395296
[24] Sun, W., Wang, J. and Fang, Y. (2012). Regularized k-means clustering of
high-dimensional data and its asymptotic consistency. Electron. J. Stat. 6 148–167.
MR2879675
[25] Terada, Y. (2014). Strong consistency of reduced K-means clustering. Scand. J.
Stat. 41 913–931. MR3277030
[26] Terada, Y. (2015). Strong consistency of factorial K-means clustering. Ann. Inst.
Statist. Math. 67 335–357. MR3315263
[27] Timmerman, M. E., Ceulemans, E., Kiers, H. A. L. and Vichi, M. (2010).
Factorial and reduced K-means reconsidered. Comput. Statist. Data Anal. 54 1858–
1871. MR2608979
[28] van de Geer, S. A. (2008). High-dimensional generalized linear models and the
lasso. Ann. Statist. 36 614–645. MR2396809 (2009h:62048)
[29] van de Geer, S. A. (2013). Generic chaining and the ℓ1 -penalty. J. Statist. Plann.
Inference 143 1001–1012. MR3029225
[30] Vichi, M. and Kiers, H. A. L. (2001). Factorial k-means analysis for two-way
data. Comput. Statist. Data Anal. 37 49–64. MR1862479
[31] Witten, D. M. and Tibshirani, R. (2010). A framework for feature selection in
clustering. J. Amer. Statist. Assoc. 105 713–726. MR2724855 (2011m:62219)

