An Algorithm for Iterative Selection of Blocks of
Features
Pierre Alquier
1

LPMA (University Paris 7)
175, rue du Chevaleret75013 Paris FRANCE
alquier@math.jussieu.fr
http://alquier.ensae.net/
2
CREST (ENSAE)

Abstract. We focus on the problem of linear regression estimation inhigh dimension, when the parameter β is "sparse" (most of its coordinates are 0) and "blocky" (βi and βi+1 are likely to be equal). Recently,
some authors defined estimators taking into account this information,such as the Fused-LASSO [19] or the S-LASSO [10] among others. However, there are no theoretical results about the obtained estimators in
the general design matrix case. Here, we propose an alternative point ofview, based on the Iterative Feature Selection method [1]. We propose an
iterative algorithm that takes into account the fact that β is sparse andblocky, with no prior knowledge on the position of the blocks. Moreover,
we give a theoretical result that ensures that every step of our algorithm
actually improves the statistical performance of the obtained estimator.
We provide some simulations, where our method outperforms LASSOtype methods in the cases where the parameter is sparse and blocky.
Moreover, we give an application to real data (CGH arrays), that showsthat our estimator can be used on large datasets.
Keywords: Feature Selection, Sparsity, Linear Regression, Grouped Variables, ArrayCGH.

1

Introduction

1.1

Setting of the Problem

We assume that we are in the gaussian linear regression setting
 

 2

Y1
σ ... 0 Y =  ...  ∼ N Xβ,  ... . . . ... Yn

0 ... σ(1)2where X is some (deterministic) real-valued matrix n × p and β = (β1 , ..., βp )′ ∈Rp , with possibly p > n (we use the convention that any u ∈ Rp is a column vector and we use the notation u′ for its transpose). Let X1 , ..., Xp be the columns

of X, and let P denote the probability distribution of Y given by Equation 1(for the sake of simplicity, we assume that the data are normalized in such a
way that Xj′ Xj = n). Our purpose is to estimate β, based on the observation ofboth X and Y . We use as a criterion the quadratic loss, for any b ∈ Rp , we put
2

L(b) = kX(b − β)k2 .
It is well known that, as soon as p > n, it is not possible to build an estimatorwith a small loss L(·) - unless some additional condition is satisfied. For example,
one may assume that β is sparse, which means that the number of non-zerocoefficients in β (usually refered as kβk0 ) is small. If kβk0 ≪ n, the LASSO
estimator [18], the Dantzig selector [6] or the nonnegative garrote [4], among
others, may achieve good performance: see for example the simulations in [18],and the theoretical results in [5] and [3]. Also note that [21] provides a nicesurvey of the theoretical results for the LASSO and the conditions needed toprove these theoretical results.
Here, we focus on the case where β is sparse and blocky. By this, we meanthat the non-zero coefficients of β are "grouped" in blocks where they have thesame value. For example, a typical parameter β could be
β = (0, 0, 0, 5, 5, 5, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 0, 0)′ .
An example of application is given in genomics, where models like the one in(1) may appear. The observation Yi represents a characteristic of a tumor anddepends on some lesions appearing on the chromosomes of cancer cells Xj,i , theindex j representing the localization on the chromosome. Since a lesion generally
affects a whole part of a chromosome (duplication or deletion of a region), one
may expect that two consecutive parameters βj and βj+1 have some strong
relationship. For example, [15] use such an assumption - the main difference isthat [15] considers the context of classification, and not of regression. They usea Support Vector Machine with a penalization of the type
λ

p
X
j=1

|βj | + µpX
j=2|βj − βj−1 |,called Fused-SVM in the paper. Using such a penalisation, we expect to finda sparse and blocky solution: the first term ensures sparsity when λ is large,
the second term ensures that for most j, βj = βj−1 and so there are blocks ofsimilar values in the solution. Such a penalization is also used in [12] for genomic
applications, with a logistic regression model.
Some estimators have been proposed for the regression case. Let us mention
F
the Fused-LASSO [19], say β̃s,t, given by


p
p


X
X
|βj − βj−1 |min kY − Xbk22 + 2ns|βj | + 2nt

b 
j=1

j=2

S
with s, t > 0, or the S-LASSO estimator, say β̃s,t
, by


p
p


X
X
min kY − Xbk22 + 2ns(βj − βj−1 )2|βj | + 2nt

b 
j=1

j=2

proposed in [9] and studied in [10] (the S-LASSO does not actually lead toblocky solutions, but to smooth solutions: most βj − βj−1 are small, but notnecessarily 0). See also the structured feature selection in [17]. These estimators
can be approximated in practice even for large p: for example the Pathwise
Coordinate Optimization algorithm [8] can be used for the S-LASSO, and is used
for the Fused-LASSO in [8] when X = In (from now Ik will denote the indentity
matrix of size k). The Fused-LASSO can be approximated in the general caseusing for example the algorithms in [11] and [20]. However, note that no general
theoretical results were provided in order to estimate a sparse blockwise β. Hebiri[9] provides good guarantees for the S-LASSO under the sparsity assumption but
does not take any advantage of the smooth aspect of β, if any. Rinaldo [16] gives
theoretical guarantees for the Fused-LASSO that can be applied only in the casewhere X = In , and so n = p.
Finally, the Group-LASSO introduced by [22] has very interesting practical performance, as well as good theoretical properties studied in [7]. See also[23]. However, this procedure requires the prior knowledge of the location of thegroups. The S-LASSO and Fused-LASSO do not require such a prior, and in thispaper, we are interested in the case where we do not have this knowledge. Our
setting is then:– we know that most of the βj = 0 but we do not know the j’s such thatβj 6= 0;– we know that most of the βj = βj+1 but we do not know the j’s such thatβj 6= βj+1 .
1.2

Overview of the Paper

In this paper, we propose an algorithm to estimate a sparse and blockwise β inthe model given by (1), without prior knowledge on the location of the groups.
This algorithm is an iterative algorithm. It starts from the initial value β̂ (0) =(0, . . . , 0). Then, at each step m, we compute β̂ (m+1) from β̂ (m) in the following
way: a particular coordinate or group of consecutive coordinates is selected,
and then updated. The way to update this coordinate, or group of coordinates,
is described in Section 2. The way to select the coordinate, or the group, ispostponed to Section 3.
Actually, in Section 3, we give the following result: with large probability,
at each step, whatever the choice of the coordinate (or group) to be updated,L(β̂ (m+1) ) ≤ L(β̂ (m) ). This is Theorem 1. A refinement of this result, Theorem
2, allows to choose the particular coordinate (or group) that ensures the largest
possible decrease from L(β̂ (m) ) to L(β̂ (m+1) ).

We then provide a simulation study in Section 4 with a comparison to the SLASSO and the Fused-LASSO estimators. Our method outperforms the LASSOtype estimators when the parameter is sparse and blocky. We also provide anapplication to real data (arrayCGH) in Section 5.
Finally, the proof of Theorems 1 and 2 are given in Section 6.

2

Construction of our Estimator

We now describe our algorithm. It is an iterative algorithm, that starts fromβ̂ (0) = (0, . . . , 0). At each step, we are going to compute β̂ (m+1) from β̂ (m) . Let
us define the soft thresholding function∀x ∈ R, ∀u ≥ 0,γ(x, u) = sign(x)(|x| − u)+where sign(x) is the sign of x. For any given j ∈ {1, ..., p} and k ∈ {1, ..., p−j +1}
let us define 1j,k ∈ Rp by (1j,k )i = 1 if i ∈ {j, ..., j + k − 1}, and (1j,k )i = 0
otherwise (in other words, 1j,k ∈ Rp is the pattern of the group of variables(j, j + 1, . . . , j + k − 1), of length k).
At each step, several possible moves are considered in our algorithm: a possible move is to update a coordinate or a group of coordinates of maximal size K,
for a given K ∈ {1, ..., p}. Let us now describe the move for a chosen coordinate
or group of coordinates. The way to choose what group of coordinates is to be
updated is discussed in the next section, in view of some theoretical results. Let
us choose s > 0 (the value of s is also discussed in the next section).
Parameter update Let us assume that we are going to update the group of
coordinates (j, j + 1, ..., j + k − 1) (a single coordinate is a particular case withk = 1). We define β̂ (m+1) byP(Y −X β̂ (m) )′ j+k−1
Xh
(m)
(m+1)

h=j
s

√
, 1′ X ′ X1
= β̂j + γ
1′j,k X ′ X1j,k
 β̂j
j,k

j,k

..
(2)
.




(m) ′ Pj+k−1s β̂ (m+1) = β̂ (m) + γ (Y −X β̂′ ) ′ h=j Xh , √

j+k−1
j+k−1
1 X X1j,k
1′ X ′ X1
j,k

(m+1)

(m)

(m+1)

(m)

j,k

j,k

and β̂ℓ= β̂ℓ for any ℓ ∈/ {j, ..., j + k − 1}.
Observe that in the case where k = 1, this expression is very natural:!
(Y − X β̂ (m) )′ Xj
(m)
(m+1)
,s
= β̂j + γβ̂jn

and β̂ℓ= β̂ℓ for any ℓ 6= j. If we take K = 1, so we never consider groupsof coordinates, we obtain the Iterative Feature Selection algorithm studied in
[1].

3

Main Result and Comments

We now give some properties satisfied by any algorithm using only the kindof moves described in the previous section. These results will also provide us arule to choose the group of coordinates that have to be updated at step m, tocalibrate the parameters s and K and, finally, to decide at which step m to stop
our iterations.
Note that the proof of the following result is given at the end of the paper,in Section 6, page 10.
Theorem 1 Let us assume that, as described previously, we start from β̂ (0) =(0, . . . , 0), that at each step m we update one group of coordinates following
Equation 2 (the choice of the group may be data-driven). We assume that westop after M steps. We have"#s2

P L(β̂ (M) ) ≤ L(β̂ (M−1) ) ≤ · · · ≤ L(β̂ (0) ) ≥ 1 − Kpe− 2σ2 .

In a way, this result states that every strategy using only the kind of moves
described in Section 2 cannot result in overfitting: we are "almost certain" to getcloser to our (unknown) objective β at each step. We can quantify this "almost
certain": it means "with probability at least 1 − ε", if we choose s such that
Kp exp(−ns2 /(2σ 2 )) ≤ ε. For example,
s


pK
2
s = 2σ log
εgives a confidence level 1 − ε. Note that it is very similar to the theoretical value
for the regularization parameter in the LASSO proposed in [3]. This link will bemade clearer in the conclusion of the paper.
Note that if we allow K = p (to test every group of size 1 to p), this will notmake a big difference because the threshold s will becomes 2 rpp2
s = 2σ log≤ 4σ 2 log.
εεHowever, when p is large, it could be more convenient to choose a smaller K
for algorithmic reasons. Let us stress this conclusion for K: K = p is probably
almost optimal in theory, but if p is large, we may want to choose a smaller K to
keep the computation time small (we will shortly discuss this point in Subsection
3.1).
Also, note that this choice for s is not necessarily the best choice in practice:
it requires the knowledge of σ 2 , and it is usually too large (see the experiments
in [2] for the case K = 1). Moreover it is not data-driven. Cross-validation will
provide better results in practice.
Finally, we still do not know "how much closer to β" we can move at every
step, and we still have no idea of how to choose if we are going to update 1, 2 ...
or K coordinates, and wich coordinates we are going to update - we just knowthat in some sense, every choice is allowed. We now make some propositions.

Sequential strategy Just sequentially update j = 1, j = 2, ..., j = p with 1
coordinates moves, then (j, j + 1) = (1, 2), ..., (j, j + 1) = (p − 1, p) with 2
coordinates moves, then (j, j + 1, j + 2) = (1, 2, 3) ... with 3 coordinates moves,... up to K coordinates moves, and start again. This strategy (with K = 2) isin some way similar to the one proposed for example in [8] for an algorithm
computing the Fused-LASSO estimate.
Now, a finer version of Theorem 1 will give us an opportunity to make adata-driven choice of the group of coordinates to update at each step.
Theorem 2 In the same setting as for Theorem 1,"

P ∀m ∈ {1, ..., M } : L(β̂(m)) ≤ L(β̂(m−1)) − kX(β̂

(m)

− β̂

(m−1)

)k22

#
s2

≥ 1 − Kpe− 2σ2 .
Note that the proof of Theorem 2 will be included in the proof of Theorem 1.
"Best single move" strategy We propose, at each step, to choose the move thatmaximises kX(β̂ (m) − β̂ (m−1) )k22 . Moreover, this allows to define a stopping criterion: we stop when all the possible moves give an improvement kX(β̂ (m) −β̂ (m−1) )k22 < 1/n2 for example.
Note that in any case we do not claim that this strategy is the best possible
one. It is possible that iterations gets stuck in some regions of Rp that are not themost interesting ones (in the same way that sequential optimization algorithms
may be trapped in some local minimum). A way to avoid this risk is not clear yet.
This is actually the object of an alternative estimator proposed in the conclusionof this paper: see Equation 5 page 14. This estimator will be the object of a future
work. However, there are two things that we know for sure about this strategy:s2

1. Theorem 2 ensures that, after m steps, with probability at least 1−Kpe− 2σ2 ,L(β̂ (m) ) ≤ L(β̂ (0) ) −

m
X

k=1

kX(β̂ (k) − β̂ (k−1) )k22 ;2. after m steps, only m coordinates, or groups of coordinates, have been updated so we know that the solution is sparse and blocky, at least when m issmall. In our experimental study, very often, only a few moves are necessary,
i.e. kX(β̂ (m) − β̂ (m−1) )k22 becomes very small after only a few steps.
3.1

A Note on the Computational Complexity of our Method

Let us remark that we can easily upper bound the computational complexityof the "best single move" strategy with a limited number of steps M (like in
Theorems 1 and 2).

First, we need to explore all the possible groups of variables, there are p +(p − 1)... + (p − K + 1) ≤ Kp such groups. Then for each group we have tocompute the quantities in (2), this costs roughly O(nk) = O(nK) operations.
This means that the computation time is roughly O(npK 2 M ). So, of course,
if we know that the blocks in β have a limited size, this is reasonable, but if we
do not have such an information and we take K = p, we can have trouble in thecase where p is large.

4

Simulations

4.1

Description of the Experiments

A toy example is proposed in the seminal paper of Tibshirani [18]. We slightly
modify this example to have∀i ∈ {1, . . . , 50},

Yi = β ′ Xi + εiwith Xi ∈ Rp , β ∈ Rp and the εi are i. i. d. from a gaussian N (0, σ 2 ). The
Xi ’s are i.i.d., and each Xi is drawn from a Gaussian distribution with mean
(0, . . . , 0)′ and with variance matrix:Σ(ρ) = ρ|i−j| i ∈ {1, . . . , p}j ∈ {1, . . . , p}for ρ ∈ [0, 1[. Note that Tibshirani’s toy example is set with p = 8. Here we willconsider p > 8.
We will use two values for β:β ∗ = (5, 5, 5, 5, 5, 0, 0, 0, 0, 0, 2, 2, 2, 2, 0, ..., 0) ∈ Rp ,β ∗∗ = (5, 4.5, 4, 3.5, 3, 2.5, 2, 1.5, 1, 0.5, 0, ..., 0) ∈ Rp ,β ∗ is sparse and blocky while β ∗∗ is sparse and, in some way, smooth (a context
that should be in favor of the S-LASSO estimator). We use two values for σ:
1 ("low noise") and 3 ("noisy case"); one value for ρ: ρ = 0.5, and finally twovalues for p: p = 15 < n and p = 100 > n.
The S-LASSO and Fused-LASSO estimators are computed via the Pathwise
Coordinate Optimization procedure described in [8]. Our procedure will be calledin the experiments ISBF (Iterative Selection of Blocks of Features). It is usedwith the "best single move" strategy, and with K = 10.
We will finally use the parameters s and t in a grid:s, t ∈ G =

(

10

−i/8

r

σ 2 log(p);n)

i = 0, ..., 20 .

(3)

4.2

Results

In a first time, we present in detail the results for one particular experiment. We
then give an overview of the results in the whole set of experiments.
First, we focus on an experiment realized in the case β = β ∗ , σ = 1, ρ = 0.5
and p = 15. We define, for a given s ∈ G, LISBF,s as the loss obtained using the
ISBF method with threshold value s, andF
LF,s = arg min L(β̃s,t)t∈G

the oracle for the Fused-LASSO with s fixed. We define in the same way LS,sfor the S-LASSO. Figure 1 gives a plot of LISBF,s , LF,s and LS,s as a functionof s.

Fig. 1. The quantities LISBF,s (thick line), LF,s (thin line) and LS,s (dotted line) as afunction of s. The horizontal axis gives i ∈ {0, ..., 20}, the vertical axis is the value ofthe risk LISBF,s , LF,s and LS,s with s = s(i) as defined in Equation 3.

Note that LISBF,s is almost always under LF,s and LS,s . So, for any reasonables, the ISBF procedure reaches a better performance than the oracle of the FusedLASSO and the S-LASSO - note that the oracles are not even available to thepractitioners. In practice, we use some data-driven method to choose s for ISBFand (s, t) for the LASSO-type procedures, as cross-validation. Note that ISBF
is more easy to deal with as it involves only one parameter to tune.
Now, let us have a look at the whole set of experiments (for each pair (σ, p)
we run 20 experiments). For the Fused-LASSO and the S-LASSO, we report theperformance of the oracle: namely, for each simulation, we defineF
LF = arg min 2 L(β̃s,t)(s,t)∈G

the oracle loss for the Fused-LASSO, and we do the same to define the oracle
loss of the S-LASSO, LS , and for the ISBF, LISBF . The results for the estimationof β ∗ are reported in Table 1.

Table 1. Results for the estimation of β ∗ (sparse and blocky).
σ
1

p
15

3

15

1

100

3

100

medianmeans.d.
medianmeans.d.
medianmeans.d.
median
mean
s.d.

LF
0.41
0.52
0.28
0.49
0.75
0.58
0.51
0.64
0.32
0.92
0.95
0.46

LS
0.18
0.24
0.15
0.70
0.71
0.39
0.55
0.55
0.13
1.32
1.25
0.29

LISBF
0.10
0.14
0.11
0.41
0.46
0.28
0.35
0.38
0.16
0.75
0.77
0.32

We can see that ISBF clearly outperforms the other methods on this particular set of experiments. The results for the estimation of β ∗∗ are reported inTable 2. Here, the S-LASSO is better.

Table 2. Results for the estimation of β ∗∗ (sparse and smooth).
σ
1
1

p
15
15

3

15

1

100

3

100

medianmeans.d.
medianmeans.d.
medianmeans.d.
median
mean
s.d.

LF
0.51
0.61
0.52
0.85
0.91
0.37
0.44
0.47
0.12
0.81
1.08
0.80

LS
0.12
0.13
0.05
0.36
0.39
0.28
0.31
0.35
0.12
0.70
0.71
0.22

LISBF
0.21
0.24
0.08
0.63
0.76
0.44
0.66
0.64
0.08
1.21
1.22
0.22

A conclusion to the very short experimental study is that the IFSF seems
better in the case of a sparse and blocky parameter, while the S-LASSO is betterin the case of a sparse and smooth parameter.

5

Application on CGH Data

We now present an application to the detection of amplification or deletion of
DNA using CGH arrays. The data we have are partial CGH arrays (only forchromosome 17) of cancer cells. The model (for one patient) is the following:
Yi = βi + εifor 1 ≤ i ≤ n with n = 7728, here i represents ordered positions of measurementson the chromosome. Remark that this is a particular case of Model (1) with p = n
and X = In (this context is the one studied by Rinaldo [16]), here i represents
ordered positions of measurements on the chromosome of the patient.
The data we use are on a logarithmic scale, so, βi = 0 means no amplification
or deletion of DNA at position i, βi < 0 means deletion and βi > 0 means
amplification. We use ISBF to estimate β, the results are given in Figures 2 and
3 (for two different patients, with K = 100 and s ≃ 0.01). Note that there is work
left to compare this method to the already available ones in this context. As an
illustration we also give here the results of the estimation using the S-LASSO
procedure with s = t = 0.4, see Figures 4 and 5. However, it is a good point
to see that our method works in a reasonable time on a large dataset and gives
reasonable results, probably more suited for interpretation by a practitioner.
Remark 1 All simulations and experiments were performed with the R software[14]. The code is available from the author.

6

Proof of Theorem 1

We now give the proof of our main result. First, we give some preliminary definitions and result.
Definition 1 For the sake of simplicity let us put Kj = min(K, p − j + 1).
Actually Kj is the maximal length for a group {j, j + 1, ..., j + k − 1} constrainedby j + k − 1 ≤ p and k ≤ K.
Definition 2 Let us put, for any s > 0, j ∈ {1, ..., p} and k ∈ {1, ..., Kj }:
Pj+k−1 ′


(Y
−
Xb)
X
h
h=j
q
≤s
Rs (j, k) = b ∈ Rp :
1′ X ′ X1j,kj,kand, for any s > 0 and b ∈ Rp let us define the event
As (b) =Kjp \\j=1 k=1{b ∈ Rs (j, k)} .

Fig. 2. The data Y (in black) and the es- Fig. 3. The data Y (in black) and the estimated β (in red) using Iterative Selection timated β (in red) using Iterative Selectionof Blocks of Features, for Patient 2.
of Blocks of Features, for Patient 1.

Fig. 4. The data Y (in black) and the esti- Fig. 5. The data Y (in black) and the estimated β (in red) using the S-LASSO esti- mated β (in red) using the S-LASSO estimator, for Patient 1.
mator, for Patient 2.

Lemma 1 For any s > 0 we haveK − 1 − s22
P [As (β)] ≥ 1 − K p −e 2σ .
2
Proof. First, let us note that (1) implies that
X ′ (Y − Xβ) ∼ N (0, σ 2 X ′ X)

and so for any j ∈ {1, ..., p} and k ∈ {1, ..., Kj },
j+k−1
X
h=j

or

Xh′ (Y − Xβ) ∼ N (0, σ 2 1′j,k X ′ X1j,k )Pj+k−1Xh′ (Y − Xβ)q∼ N (0, σ 2 ).
′′1j,k X X1j,kh=jThis implies that, for any j ∈ {1, ..., p}, for any k ∈ {1, ..., Kj } and for any s > 0,′s2
|X (Y − Xβ)|P q h> s ≤ e− 2σ2
1′j,k X ′ X1j,kand, by a union bound argument over all j ∈ {1, ..., p} and k ∈ {1, ..., Kj },P ∃j ∈ {1, ..., p}, ∃k ∈ {1, ..., Kj } :s2≤ e− 2σ2

K−1
X
ℓ=0

Pj+k−1h=j

Xh′ (Y − Xβ)q1′j,k X ′ X1j,k



> s



K(K − 1) − s22e 2σ .
(p − ℓ) = Kp −2

This ends the proof.

Definition 3 For any closed and convex set C ⊂ Rp we define ΠC (.) the orthogonal projection on C with respect to the norm induced by X:
ΠC (b) = arg min kX(b − p)k22 .
p∈C

We are now ready to give the proof of Theorem 1. The proof heavily uses thegeometrical considerations given in [2].
Proof of Theorem 1. From now, let us fix s > 0 and assume that we are in
the event As (β) (according to Lemma 1, this is true with probability at least
1 − pK exp(−s2 /(2σ 2 ))).
So, for any j ∈ {1, ..., p}, k ∈ {1, ..., Kj }, we have β ∈ Rs (j, k). Moreover,note that Rs (j, k) is convex and closed. Using classical convex analysis result(see [2] for example), we have, for any b ∈ Rp ,kX(ΠRs (j,k) (b) − β)k22 ≤ kX(b − β)k22 − kX(ΠRs (j,k) (b) − b)k22 ,(4)

see Figure 6 for an illustration.
The last point of the proof will be to remark that, once that j and k are
fixed, the β̂ (m+1) defined in the "1 coordinate move" satisfiesβ̂ (m+1) = ΠRs (j,k) (β̂ (m) ).

Fig. 6. Illustration of Equation 4.

To see this, remark that the projection ΠRs (j,k) (β̂ (m) ) is defined by the program
minu∈Rp kX(β̂ (m) − u)k22





 s.t.

Pj+k−1

√ ′

h=j

′
Xh
(Y −Xu)1j,k X ′ X1j,k≤ s,of which the solution is given by (2).

7Conclusion and Perspectives

In this paper, we tried to give an estimator that takes advantage of the sparsity ofβ as well as of its blockwise aspect in the setting of regression in large dimension.
We proposed a very simple algorithm that performs well in practice, and give
directions for the study of its theoretical performances.
In future works, we would like to give more precise theoretical results - inthe spirit of [3] on the LASSO.
Eventually, we would like to point out some similarities between our estimator and other well-known estimators. In the proof of our main result, we presented our sequence of estimators (β̂ (m) )m as successive projections on various
confidence regions of the formRs (j, k) =b ∈ Rp :Pj+k−1h=j

Xh′ (Y − Xb)q
1′j,k X ′ X1j,k

≤s





.

We may wonder what happens if we project directly the first value β̂ (0) = 0
into the intersections of these confidence regions. We obtain an estimator β̂(s, t)defined by the following program:arg minb∈Rp kXbk22
β̂(s, t) =Pj+k−1 ′X (Y −Xb)h=j
√ ′ h′≤ s.
 s.t. supj,k1 X X1

(5)

j,k

j,k

If we fix K = 1 (so we only work with constraints defined by single variables
and not by groups of variables), we obtain minb∈Rp kXbk22
s.t. k n1 X ′ (Y − Xb)k∞ ≤ sthat was proved to have as a solution the LASSO estimator given by


p


X
|bj | ,
minp kY − Xbk22 + 2ns

b∈R 
j=1

see for example [13] for the proof, and [2] for a discussion of the geometric role ofthe constraint k(1/n)X ′ (Y − Xb)k∞ ≤ s . So, in some way, the estimator β̂(s, t)
is really a variant of the LASSO, that tries to take into account the fact that β
has blocks. The study of β̂(s, t) will be the object of future works.
Acknowledgments We would like to thank Dr. Jean-Paul Feugeas (INSERM
U944, Institut Universitaire d’Hématologie) who provided the CGH data withdetailed explanations. We would also like to thank Dr. Mohamed Hebiri (ETH
- Zürich) and Joseph Salmon (Université Paris 7) as well as the anonymousreferees for useful comments. The project was funded by: ANR PARCIMONIE.

References
1. Alquier, P. Iterative feature selection in regression estimation. Annales del’Institut Henri Poincaré, Probability and Statistics 44, 1 (2008), 47–88.
2. Alquier, P. LASSO, iterative feature selection and the correlation selector: Oracle
inequalities and numerical performances. Electron. J. Stat. (2008), 1129–1152.
3. Bickel, P., Ritov, Y., and Tsybakov, A. Simultaneous analysis of LASSO
and dantzig selector. The Annals of Statistics 37, 4 (2009), 1705–1732.
4. Breiman, L. Better subset regression using the nonnegative garrote. Technometrics 37 (1995), 373–384.
5. Bunea, F., Tsybakov, A., and Wegkamp, M. Sparsity oracle inequalities forthe lasso. Electron. J. Stat. 1 (2007), 169–194.
6. Candès, E., and Tao, T. The dantzig selector: statistical estimation when p ismuch larger than n. Ann. Statist. 35 (2007).
7. Chesnau, C., and Hebiri, M. Some theoretical results on the grouped variables
lasso. Mathematical Methods of Statistics 17, 4 (2008), 317–326.

8. Friedman, J., Hastie, T., Höfling, H., and Tibshirani, R. Pathwise coordinate optimization. Ann. Appl. Statist. 1, 2 (2007), 302–332.
9. Hebiri, M. Regularization with the smooth-LASSO procedure. Preprint LPMA,
arXiv:0803.0668, 2008.
10. Hebiri, M., and Van de Geer, S. The smooth-lasso and other ℓ1 + ℓ2 -penalized
methods. arXiv:1003.4885, 2010.
11. Hoefling, H. A path algorithm for the fused LASSO signal approwimator.
Preprint arXiv:0910.0526, 2009.
12. Huang, J., Salim, A., Lei, K., O’Sullivan, K., and Pawitan, Y. Classification of array cgh data using smoothed logistic regression model. Statistics in
Medicine 8, 30 (2009), 3798–3810.
13. Osborne, M., Presnell, B., and Turlach, B. On the LASSO and its dual.
J. Comput. Graph. Statist. 9, 2 (2000), 319–337.
14. R Development Core Team. R: A Language and Environment for StatisticalComputing. R Foundation for Statistical Computing, Vienna, Austria, 2008. ISBN
3-900051-07-0.
15. Rapaport, F., Barillot, E., and Vert, J.-P. Classification of array-CGH
data using fused SVM. Bioinformatics 24, 13 (2008), 1375,1382.
16. Rinaldo, A. Properties and refinements of the fused LASSO. The Annals of
Statistics 37, 5B (2009), 2922–2952.
17. Slawski, M., zu Castell, W., and Tutz, G. Feature selection guided bystructural information. To appear in the Annals of Applied Statistics.
18. Tibshirani, R. Regression shrinkage and selection via the LASSO. J. Roy. Statist.
Soc. Ser. B 58, 1 (1996), 267–288.
19. Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., and Knight, K. Sparsity
and smoothness via the fused lasso. JRSS-B 67, 1 (2005), 91–108.
20. Tibshirani, R. J., and Taylor, J. Regularization path for least squares problems with generalized ℓ1 penalties. Preprint, 2009.
21. Van de Geer, S., and Bühlmann, P. On the conditions used to prove oracle
results for the lasso. Electronic Journal of Statistics 3 (2009), 1360–1392.
22. Yuan, M., and Lin, Y. Model selection and estimation in regression with groupedvariables. JRSS-B 68, 1 (2006), 49–67.
23. Zhao, P., Rocha, G., and Yu, B. The composite absolute penalties for groupedand hierarchical variable selection. The Annals of Statistics 37, 6A (2009), 3468–
3497.