# Lasso Screening Rules via Dual Polytope Projection

Jie Wang  Computer Science and Engineering, Arizona State University, USA
Peter Wonka  Computer Science and Engineering, Arizona State University, USA
Jieping Ye  Computer Science and Engineering, Arizona State University, USA

###### Abstract

Lasso is a widely used regression technique to find sparse representations.
When the dimension of the feature space and the number of samples are
extremely large, solving the Lasso problem remains challenging. To improve the
efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues
have proposed the SAFE rules which are able to quickly identify the inactive
predictors, i.e., predictors that have $0$ components in the solution vector.
Then, the inactive predictors or features can be removed from the optimization
problem to reduce its scale. By transforming the standard Lasso to its dual
form, it can be shown that the inactive predictors include the set of inactive
constraints on the optimal dual solution. In this paper, we propose an
efficient and effective screening rule via Dual Polytope Projections (DPP),
which is mainly based on the uniqueness and nonexpansiveness of the optimal
dual solution due to the fact that the feasible set in the dual space is a
convex and closed polytope. Moreover, we show that our screening rule can be
extended to identify inactive groups in group Lasso. To the best of our
knowledge, there is currently no exact screening rule for group Lasso. We have
evaluated our screening rule using synthetic and real data sets. Results show
that our rule is more effective in identifying inactive predictors than
existing state-of-the-art screening rules for Lasso.

##  1 Introduction

Data with various structures and scales comes from almost every aspect of
daily life. To effectively extract patterns in the data and build
interpretable models with high prediction accuracy is always desirable. One
popular technique to identify important explanatory features is by sparse
regularization. For instance, consider the widely used $\ell_{1}$-regularized
least squares regression problem known as Lasso [31]. The most appealing
property of Lasso is the sparsity of the solutions, which is equivalent to
feature selection. Suppose we have $N$ observations and $p$ features. Let
${\bf y}$ denote the $N$ dimensional response vector and ${\bf X}=[{\bf
x}_{1},{\bf x}_{2},\ldots,{\bf x}_{p}]$ be the $N\times p$ feature matrix. Let
$\lambda\geq 0$ be the regularization parameter. The Lasso problem is
formulated as the following optimization problem:

$\inf_{\beta\in\mathbb{R}^{p}}\frac{1}{2}\left\|{\bf
y-X\beta}\right\|_{2}^{2}+\lambda\|{\beta}\|_{1}.$ (1)

Lasso has achieved great success in a wide range of applications [13, 12, 38,
9, 34] and in recent years many algorithms have been developed to efficiently
solve the Lasso problem [15, 20, 26, 14, 18, 4, 19]. However, when the
dimension of feature space and the number of samples are very large, solving
the Lasso problem remains challenging because we may not even be able to load
the data matrix into main memory. The idea of screening has been shown very
promising in solving Lasso for large-scale problems. Essentially, screening
aims to quickly identify the inactive features that have $0$ components in the
solution and then remove them from the optimization. Therefore, we can work on
a reduced feature matrix to solve the Lasso problem, which may lead to
substantial savings in computational cost and memory usage.

Existing screening methods for Lasso can be roughly divided into two
categories: the Heuristic Screening Methods and the Safe Screening Methods. As
the name indicated, the heuristic screening methods can not guarantee that the
discarded features have zero coefficients in the solution vector. In other
words, they may mistakenly discard the active features which have nonzero
coefficients in the sparse representations. Well-known heuristic screening
methods for Lasso include SIS [17] and strong rules [32]. SIS is based on the
associations between features and the prediction task, but not from an
optimization point of view. Strong rules rely on the assumption that the
absolute values of the inner products between features and the residue are
nonexpansive [3] with respect to the parameter values. Notice that, in real
applications, this assumption is not always true. In order to ensure the
correctness of the solutions, strong rules check the KKT conditions for
violations. In case of violations, they weaken the screened set and repeat
this process. In contrast to the heuristic screening methods, the safe
screening methods for Lasso can guarantee that the discarded features are
absent from the resulting sparse models. Existing safe screening methods for
Lasso includes SAFE [16] and DOME [36, 35], which are based on an estimation
of the dual optimal solution. The key challenge of searching for effective
safe screening rules is how to accurately estimate the dual optimal solution.
The more accurate the estimation is, the more effective the resulting
screening rule is in discarding the inactive features. Moreover, Xiang et al.
[36] have shown that the SAFE rule for Lasso can be read as a special case of
their testing rules.

In this paper, we develop novel efficient and effective screening rules for
the Lasso problem; our screening rules are safe in the sense that no active
features will be discarded. As the name indicated (DPP), the proposed
approaches heavily rely on the geometric properties of the Lasso problem.
Indeed, the dual problem of problem (1) can be formulated as a projection
problem. More specifically, the dual optimal solution of the Lasso problem is
the projection of the scaled response vector onto a nonempty closed and convex
polytope (the feasible set of the dual problem). This nice property provides
us many elegant approaches to accurately estimate the dual optimal solutions,
e.g., nonexpansiveness, firmly nonexpansiveness [3]. In fact, the estimation
of the dual optimal solution in DPP is a direct application of the
nonexpansiveness of the projection operators. Moreover, by further exploiting
the properties of the projection operators, we can significantly improve the
estimation of the dual optimal solution. Based on this estimation, we develop
the so called enhanced DPP (EDPP) rules which are able to detect far more
inactive features than DPP. Therefore, the speedup gained by EDPP is much
higher than the one by DPP.

In real applications, the optimal parameter value of $\lambda$ is generally
unknown and needs to be estimated. To determine an appropriate value of
$\lambda$, commonly used approaches such as cross validation and stability
selection involve solving the Lasso problems over a grid of tuning parameters
$\lambda_{1}>\lambda_{2}>\ldots>\lambda_{\mathcal{K}}$. Thus, the process can
be very time consuming. To address this challenge, we develop the sequential
version of the DPP families. Briefly speaking, for the Lasso problem, suppose
we are given the solution $\beta^{*}(\lambda_{k-1})$ at $\lambda_{k-1}$. We
then apply the screening rules to identify the inactive features of problem
(1) at $\lambda_{k}$ by making use of $\beta^{*}(\lambda_{k-1})$. The idea of
the sequential screening rules is proposed by [16] and [32] and has been shown
to be very effective for the aforementioned scenario. In [32], the authors
demonstrate that the sequential strong rules are very effective in discarding
inactive features especially for very small parameter values and achieve the
state-of-the-art performance. However, in contrast to the recursive SAFE (the
sequential version of SAFE rules) and the sequential version of DPP rules, it
is worthwhile to mention that the sequential strong rules may mistakenly
discard active features because they are heuristic methods. Moreover, it is
worthwhile to mention that, for the existing screening rules including SAFE
and strong rules, the basic versions are usually special cases of their
sequential versions, and the same applies to our DPP and EDPP rules. For the
DOME rule [36, 35], it is unclear whether its sequential version exists.

The rest of this paper is organized as follows. We present the family of DPP
screening rules, i.e., DPP and EDPP, in detail for the Lasso problem in
Section 2. Section 3 extends the idea of DPP screening rules to identify
inactive groups in group Lasso [37]. We evaluate our screening rules on
synthetic and real data sets from many different applications. In Section 4,
the experimental results demonstrate that our rules are more effective in
discarding inactive features than existing state-of-the-art screening rules.
We show that the efficiency of the solver can be improved by several orders of
magnitude with the enhanced DPP rules, especially for the high-dimensional
data sets (notice that, the screening methods can be integrated with any
existing solvers for the Lasso problem). Some concluding remarks are given in
Section 5.

##  2 Screening Rules for Lasso via Dual Polytope Projections

In this section, we present the details of the proposed DPP and EDPP screening
rules for the Lasso problem. We first review some basics of the dual problem
of Lasso including its geometric properties in Section 2.1; we also briefly
discuss some basic guidelines for developing safe screening rules for Lasso.
Based on the geometric properties discussed in Section 2.1, we then develop
the basic DPP screening rule in Section 2.2. As a straightforward extension in
dealing with the model selection problems, we also develop the sequential
version of DPP rules. In Section 2.3, by exploiting more geometric properties
of the dual problem of Lasso, we further improve the DPP rules by developing
the so called enhanced DPP (EDPP) rules. The EDPP screening rules
significantly outperform DPP rules in identifying the inactive features for
the Lasso problem.

###  2.1 Basics

Different from [36, 35], we do not assume ${\bf y}$ and all ${\bf x}_{i}$ have
unit length.The dual problem of problem (1) takes the form of (to make the
paper self-contained, we provide the detailed derivation of the dual form in
the appendix):

$\displaystyle\sup_{\theta}\quad\left\\{\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{\lambda^{2}}{2}\left\|\theta-\frac{{\bf
y}}{\lambda}\right\|_{2}^{2}:\,\,|{\bf x}_{i}^{T}\theta|\leq
1,\,i=1,2,\ldots,p\right\\},$ (2)

where $\theta$ is the dual variable. For notational convenience, let the
optimal solution of problem (2) be $\theta^{\ast}(\lambda)$ [recall that the
optimal solution of problem (1) with parameter $\lambda$ is denoted by
$\beta^{*}(\lambda)$]. Then, the KKT conditions are given by:

$\displaystyle{\bf y}$ $\displaystyle={\bf
X}{\beta}^{\ast}(\lambda)+\lambda\theta^{\ast}(\lambda),$ (3)
$\displaystyle{\bf x}_{i}^{T}\theta^{*}(\lambda)$
$\displaystyle\in\begin{cases}{\operatorname*{sign}([\beta^{\ast}(\lambda)]_{i})},\hskip
5.69054pt\rm{if}\hskip 2.84526pt[\beta^{\ast}(\lambda)]_{i}\neq 0,\\\
[-1,1],\hskip 39.83385pt\rm{if}\hskip
2.84526pt[\beta^{\ast}(\lambda)]_{i}=0,\\\ \end{cases}i=1,\ldots,p,$ (4)

where $[\cdot]_{k}$ denotes the $k^{th}$ component. In view of the KKT
condition in (4), we have

$\displaystyle|{\bf
x}_{i}^{T}(\theta^{*}(\lambda))^{T}|<1\Rightarrow[\beta^{*}(\lambda)]_{i}=0\Rightarrow{\bf
x}_{i}\,\,\mbox{\rm is an inactive feature.}$ (R1)

In other words, we can potentially make use of (R1) to identify the inactive
features for the Lasso problem. However, since $\theta^{*}(\lambda)$ is
generally unknown, we can not directly apply (R1) to identify the inactive
features. Inspired by the SAFE rules [16], we can first estimate a region
${\bf\Theta}$ which contains $\theta^{*}(\lambda^{\prime\prime})$. Then, (R1)
can be relaxed as follows:

$\displaystyle\sup_{\theta\in{\bf\Theta}}|{\bf
x}_{i}^{T}\theta|<1\Rightarrow[\beta^{*}(\lambda)]_{i}=0\Rightarrow{\bf
x}_{i}\,\,\mbox{\rm is an inactive feature.}$ (R1’)

Clearly, as long as we can find a region ${\bf\Theta}$ which contains
$\theta^{*}(\lambda)$, (R1’) will lead to a screening rule to detect the
inactive features for the Lasso problem. Moreover, in view of (R1) and (R1’),
we can see that the smaller the region ${\bf\Theta}$ is, the more accurate the
estimation of $\theta^{*}(\lambda)$ is. As a result, more inactive features
can be identified by the resulting screening rules.

Geometric Interpretations of the Dual Problem By a closer look at the dual
problem (2), we can observe that the dual optimal solution is the feasible
point which is closest to ${\bf y}/{\lambda}$. For notational convenience, let
the feasible set of problem (2) be $F$. Clearly, $F$ is the intersection of
$2p$ closed half-spaces, and thus a closed and convex polytope. (Notice that,
$F$ is also nonempty since $0\in F$.) In other words, $\theta^{\ast}(\lambda)$
is the projection of ${\bf y}/{\lambda}$ onto the polytope $F$.
Mathematically, for an arbitrary vector ${\bf w}$ and a convex set $C$ in a
Hilbert space $\mathcal{H}$, let us define the projection operator as

$P_{C}({\bf w})=\operatorname*{argmin}_{{\bf u}\in C}\|{\bf u}-{\bf w}\|_{2}.$
(5)

Then, the dual optimal solution $\theta^{*}(\lambda)$ can be expressed by

$\theta^{\ast}(\lambda)=P_{F}({\bf
y}/{\lambda})=\operatorname*{argmin}_{\theta\in F}\left\|\theta-\frac{\bf
y}{\lambda}\right\|_{2}.$ (6)

Indeed, the nice property of problem (2) illustrated by Eq. (6) leads to many
interesting results. For example, it is easy to see that ${\bf y}/\lambda$
would be an interior point of $F$ when $\lambda$ is large enough. If this is
the case, we immediately have the following assertions: 1) ${\bf y}/\lambda$
is an interior point of $F$ implies that none of the constraints of problem
(2) would be active on ${\bf y}/\lambda$, i.e., $|{\bf x}_{i}^{T}({\bf
y}/(\lambda)|)<1$ for all $i=1,\ldots,p$; 2) $\theta^{*}(\lambda)$ is an
interior point of $F$ as well since $\theta^{*}(\lambda)=P_{F}({\bf
y}/\lambda)={\bf y}/\lambda$ by Eq. (6) and the fact ${\bf y}/\lambda\in F$.
Combining the results in 1) and 2), it is easy to see that $|{\bf
x}_{i}^{T}\theta^{*}(\lambda)|<1$ for all $i=1,\ldots,p$. By (R1), we can
conclude that $\beta^{*}(\lambda)=0$, under the assumption that $\lambda$ is
large enough.

The above analysis may naturally lead to a question: does there exist a
specific parameter value $\lambda_{\rm max}$ such that the optimal solution of
problem (1) is $0$ whenever $\lambda>\lambda_{\rm max}$? The answer is
affirmative. Indeed, let us define

$\displaystyle\lambda_{\rm max}=\max_{i}|{\bf x}_{i}^{T}{\bf y}|.$ (7)

It is well known [32] that $\lambda_{\rm max}$ defined by Eq. (7) is the
smallest parameter such that problem (1) has a trivial solution, i.e.,

$\displaystyle\beta^{*}(\lambda)=0,\hskip 5.69054pt\forall\hskip
2.84526pt\lambda\in[\lambda_{\rm max},\infty).$ (8)

Combining the results in (8) and Eq. (3), we immediately have

$\displaystyle\theta^{*}(\lambda)=\frac{\bf y}{\lambda},\hskip
5.69054pt\forall\hskip 2.84526pt\lambda\in[\lambda_{\rm max},\infty).$ (9)

Therefore, through out the rest of this paper, we will focus on the cases with
$\lambda\in(0,\lambda_{\rm max})$.

In the subsequent sections, we will follow (R1’) to develop our screening
rules. More specifically, the derivation of the proposed screening rules can
be divided into the following three steps:

  1. Step 1.

We first estimate a region ${\bf\Theta}$ which contains the dual optimal
solution $\theta^{*}(\lambda)$.

  2. Step 2.

We solve the maximization problem in (R1’), i.e.,
$\sup_{\theta\in{\bf\Theta}}|{\bf x}_{i}^{T}\theta|$.

  3. Step 3.

By plugging in the upper bound we find in Step ${\bf 2}$, it is
straightforward to develop the screening rule based on (R1’).

The geometric property of the dual problem illustrated by Eq. (6) serves as a
fundamentally important role in developing our DPP and EDPP screening rules.

###  2.2 Fundamental Screening Rules via Dual Polytope Projections (DPP)

In this Section, we propose the so called DPP screening rules for discarding
the inactive features for Lasso. As the name indicates, the idea of DPP
heavily relies on the properties of projection operators, e.g., the
nonexpansiveness [5]. We will follow the three steps stated in Section 2.1 to
develop the DPP screening rules.

First, we need to find a region ${\bf\Theta}$ which contains the dual optimal
solution $\theta^{*}(\lambda)$. Indeed, the result in (9) provides us an
important clue. That is, we may be able to estimate a possible region for
$\theta^{*}(\lambda)$ in terms of a known $\theta^{*}(\lambda_{0})$ with
$\lambda<\lambda_{0}$. Notice that, we can always set
$\lambda_{0}=\lambda_{\rm max}$ and make use of the fact that
$\theta^{*}(\lambda_{\rm max})={\bf y}/\lambda_{\rm max}$ implied by (9).
Another key ingredient comes from Eq. (6), i.e., the dual optimal solution
$\theta^{*}(\lambda)$ is the projection of ${\bf y}/\lambda$ onto the feasible
set $F$, which is nonempty closed and convex. A nice property of the
projection operators defined in a Hilbert space with respect to a nonempty
closed and convex set is the so called nonexpansiveness. For convenience, we
restate the definition of nonexpansiveness in the following theorem.

######  Theorem 1.

Let $C$ be a nonempty closed convex subset of a Hilbert space $\mathcal{H}$.
Then the projection operator defined in Eq. (5) is continuous and
nonexpansive, i.e.,

$\|P_{C}({\bf w}_{2})-P_{C}({\bf w}_{1})\|_{2}\leq\|{\bf w}_{2}-{\bf
w}_{1}\|_{2},\,\,\forall{\bf w}_{2},{\bf w}_{1}\in\mathcal{H}.$ (10)

In view of Eq. (6), a direct application of Theorem 1 leads to the following
result:

######  Theorem 2.

For the Lasso problem, let $\lambda,\lambda_{0}>0$ be two regularization
parameters. Then,

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}\leq\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2}.$ (11)

For notational convenience, let a ball centered at ${\bf c}$ with radius
$\rho$ be denoted by $B({\bf c},\rho)$. Theorem 2 actually implies that the
dual optimal solution must be inside a ball centered at
$\theta^{*}(\lambda_{0})$ with radius
$\left|1/\lambda-1/\lambda_{0}\right|\|{\bf y}\|_{2}$, i.e.,

$\displaystyle\theta^{*}(\lambda)\in
B\left(\theta^{*}(\lambda_{0}),\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2}\right).$ (12)

We thus complete the first step for developing DPP. Because it is easy to find
the upper bound of a linear functional over a ball, we combine the remaining
two steps as follows.

######  Theorem 3.

For the Lasso problem, assume we are given the solution of its dual problem
$\theta^{\ast}(\lambda_{0})$ for a specific $\lambda_{0}$. Let $\lambda$ be a
positive value different from $\lambda_{0}$. Then
$[\beta^{\ast}(\lambda)]_{i}=0$ if

$\displaystyle\left|{\bf x}_{i}^{T}\theta^{\ast}(\lambda)\right|<1-\|{\bf
x}_{i}\|_{2}\|{\bf
y}\|_{2}\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|.$ (13)

###### Proof.

The dual optimal solution $\theta^{*}(\lambda)$ is estimated to be inside the
ball given by Eq. (12). To simplify notations, let ${\bf
c}=\theta^{\ast}(\lambda_{0})$ and
$\rho=\left|1/\lambda-1/\lambda_{0}\right|\|{\bf y}\|_{2}$. To develop a
screening rule based on (R1’), we need to solve the optimization problem:
$\sup_{\theta\in B({\bf c},\rho)}|{\bf x}_{i}^{T}\theta|$.

Indeed, for any $\theta\in B({\bf c},\rho)$, it can be expressed by:

$\displaystyle\theta=\theta^{*}(\lambda_{0})+{\bf v},\hskip 5.69054pt\|{\bf
v}\|_{2}\leq\rho.$

Therefore, the optimization problem can be easily solved as follows:

$\displaystyle\sup_{\theta\in B({\bf c},\rho)}\left|{\bf
x}_{i}^{T}\theta\right|=\sup_{\|{\bf v}\|_{2}\leq\rho}\left|{\bf
x}_{i}^{T}\left(\theta^{*}(\lambda_{0})+{\bf v}\right)\right|=\left|{\bf
x}_{i}^{T}\theta^{*}(\lambda_{0})\right|+\rho\|{\bf x}_{i}\|_{2}.$ (14)

By plugging the upper bound in Eq. (14) to (R1’), we obtain the statement in
Theorem 3, which completes the proof. ∎

Theorem 3 implies that we can develop applicable screening rules for Lasso as
long as the dual optimal solution $\theta^{\ast}(\cdot)$ is known for a
certain parameter value $\lambda_{0}$. By simply setting
$\lambda_{0}=\lambda_{\rm max}$ and noting that $\theta^{*}(\lambda_{\rm
max})={\bf y}/\lambda_{\rm max}$ [please refer to Eq. (9)], Theorem 3
immediately leads to the following result.

######  Corollary 4.

Basic DPP: For the Lasso problem (1), let $\lambda_{\rm max}=\max_{i}|{\bf
x}_{i}^{T}{\bf y}|$. If $\lambda\geq\lambda_{\rm max}$, then
$[\beta^{\ast}]_{i}=0,\forall i\in\mathcal{I}$. Otherwise,
$[\beta^{\ast}(\lambda)]_{i}=0$ if

$\left|{\bf x}_{i}^{T}\frac{\bf y}{\lambda_{\rm
max}}\right|<1-\left(\frac{1}{\lambda}-\frac{1}{\lambda_{\rm
max}}\right)\|{\bf x}_{i}\|_{2}\|{\bf y}\|_{2}.$

######  Remark 1.

Notice that, DPP is not the same as ST1 [36] and SAFE [16], which discards the
$i^{th}$ feature if

$\displaystyle|{\bf x}_{i}^{T}{\bf y}|<\lambda-\|{\bf x}_{i}\|_{2}\|{\bf
y}\|_{2}\frac{\lambda_{\rm max}-\lambda}{\lambda_{\rm max}}.$ (15)

From the perspective of the sphere test, the radius of ST1/SAFE and DPP are
the same. But the centers of ST1 and DPP are ${\bf y}/\lambda$ and ${\bf
y}/\lambda_{\rm max}$ respectively, which leads to different formulas, i.e.,
Eq. (15) and Corollary 4.

In real applications, the optimal parameter value of $\lambda$ is generally
unknown and needs to be estimated. To determine an appropriate value of
$\lambda$, commonly used approaches such as cross validation and stability
selection involve solving the Lasso problem over a grid of tuning parameters
$\lambda_{1}>\lambda_{2}>\ldots>\lambda_{\mathcal{K}}$, which is very time
consuming. Motivated by the ideas of [32] and [16], we develop a sequential
version of DPP rules. We first apply the DPP screening rule in Corollary 4 to
discard inactive features for the Lasso problem (1) with parameter being
$\lambda_{1}$. After solving the reduced optimization problem for
$\lambda_{1}$, we obtain the exact solution $\beta^{\ast}(\lambda_{1})$. Hence
by Eq. (3), we can find $\theta^{\ast}(\lambda_{1})$. According to Theorem 3,
once we know the optimal dual solution $\theta^{\ast}(\lambda_{1})$, we can
construct a new screening rule by setting $\lambda_{0}=\lambda_{1}$ to
identify inactive features for problem (1) with parameter being $\lambda_{2}$.
By repeating the above process, we obtain the sequential version of the DPP
rule as in the following corollary.

######  Corollary 5.

Sequential DPP: For the Lasso problem (1), suppose we are given a sequence of
parameter values $\lambda_{\rm
max}=\lambda_{0}>\lambda_{1}>\ldots>\lambda_{m}$. Then for any integer $0\leq
k<m$, we have $[\beta^{\ast}(\lambda_{k+1})]_{i}=0$ if
$\beta^{\ast}(\lambda_{k})$ is known and the following holds:

$\left|{\bf x}_{i}^{T}\frac{{\bf y}-{\bf
X}\beta^{\ast}(\lambda_{k})}{\lambda_{k}}\right|<1-\left(\frac{1}{\lambda_{k+1}}-\frac{1}{\lambda_{k}}\right)\|{\bf
x}_{i}\|_{2}\|{\bf y}\|_{2}.$

######  Remark 2.

From Corollaries 4 and 5, we can see that both of the DPP and sequential DPP
rules discard the inactive features for the Lasso problem with a smaller
parameter value by assuming a known dual optimal solution at a larger
parameter value. This is in fact a standard way to construct screening rules
for Lasso [32, 16, 36, 35].

######  Remark 3.

For illustration purpose, we present both the basic and sequential version of
the DPP screening rules. However, it is easy to see that the basic DPP rule
can be easily derived from its sequential version by simply setting
$\lambda_{k}=\lambda_{\rm max}$ and $\lambda_{k+1}=\lambda$. Therefore, in
this paper, we will focus on the development and evaluation of the sequential
version of the proposed screening rules. To avoid any confusions, DPP and EDPP
all refer to the corresponding sequential versions.

###  2.3 Enhanced DPP Rules for Lasso

In this section, we further improve the DPP rules presented in Section 2.2 by
a more careful analysis of the projection operators. Indeed, from the three
steps by which we develop the DPP rules, we can see that the first step is a
key. In other words, the estimation of the dual optimal solution serves as a
fundamentally important role in developing the DPP rules. Moreover, (R1’)
implies that the more accurate the estimation is, the more effective the
resulting screening rule is in discarding the inactive features. The
estimation of the dual optimal solution in DPP rules is in fact a direct
consequence of the nonexpansiveness of the projection operators. Therefore, in
order to improve the performance of the DPP rules in discarding the inactive
features, we propose two different approaches to find more accurate
estimations of the dual optimal solution. These two approaches are presented
in detail in Sections 2.3.1 and 2.3.2 respectively. By combining the ideas of
these two approaches, we can further improve the estimation of the dual
optimal solution. Based on this estimation, we develop the enhanced DPP rules
(EDPP) in Section 2.3.3. Again, we will follow the three steps in Section 2.1
to develop the proposed screening rules.

####  2.3.1 Improving the DPP rules via Projections of Rays

In the DPP screening rules, the dual optimal solution $\theta^{*}(\lambda)$ is
estimated to be inside the ball
$B\left(\theta^{*}(\lambda_{0}),|1/\lambda-1/\lambda_{0}|\|{\bf
y}\|_{2}\right)$ with $\theta^{*}(\lambda_{0})$ given. In this section, we
show that $\theta^{*}(\lambda)$ lies inside a ball centered at
$\theta^{*}(\lambda_{0})$ with a smaller radius.

Indeed, it is well known that the projection of an arbitrary point onto a
nonempty closed convex set $C$ in a Hilbert space $\mathcal{H}$ always exists
and is unique [3]. However, the converse is not true, i.e., there may exist
${\bf w}_{1},{\bf w}_{2}\in\mathcal{H}$ such that ${\bf w}_{1}\neq{\bf w}_{2}$
and $P_{C}({\bf w}_{1})=P_{C}({\bf w}_{2})$. In fact, it is known that the
following result holds:

######  Lemma 6.

[3] Let $C$ be a nonempty closed convex subset of a Hilbert space
$\mathcal{H}$. For a point ${\bf w}\in\mathcal{H}$, let ${\bf w}(t)=P_{C}({\bf
w})+t({\bf w}-P_{C}({\bf w}))$. Then, the projection of the point ${\bf w}(t)$
is $P_{C}({\bf w})$ for all $t\geq 0$, i.e.,

$\displaystyle P_{C}({\bf w}(t))=P_{C}({\bf w}),\forall t\geq 0.$ (16)

Clearly, when ${\bf w}\neq P_{C}({\bf w})$, i.e., ${\bf w}\notin C$, ${\bf
w}(t)$ with $t\geq 0$ is the ray starting from $P_{C}({\bf w})$ and pointing
in the same direction as ${\bf w}-P_{C}({\bf w})$. By Lemma 6, we know that
the projection of the ray ${\bf w}(t)$ with $t\geq 0$ onto the set $C$ is a
single point $P_{C}({\bf w})$. [When ${\bf w}=P_{C}({\bf w})$, i.e., ${\bf
w}\in C$, ${\bf w}(t)$ with $t\geq 0$ becomes a single point and the statement
in Lemma 6 is trivial.]

By making use of Lemma 6 and the nonexpansiveness of the projection operators,
we can improve the estimation of the dual optimal solution in DPP [please
refer to Theorem 2 and Eq. (12)]. More specifically, we have the following
result:

######  Theorem 7.

For the Lasso problem, suppose the dual optimal solution $\theta^{*}(\cdot)$
at $\lambda_{0}\in(0,\lambda_{\rm max}]$ is known. For any
$\lambda\in(0,\lambda_{0}]$, let us define

$\displaystyle{\bf v}_{1}(\lambda_{0})=\begin{cases}\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0}),\hskip 12.80373pt{\rm if}\hskip
5.69054pt\lambda_{0}\in(0,\lambda_{\rm max}),\\\ {\rm sign}({\bf
x}_{*}^{T}{\bf y}){\bf x}_{*},\hskip 8.53581pt{\rm if}\hskip
5.69054pt\lambda_{0}=\lambda_{\rm max},\end{cases}{\rm where}\hskip
5.69054pt{\bf x}_{*}={\rm argmax}_{{\bf x}_{i}}|{\bf x}_{i}^{T}{\bf y}|,$ (17)
$\displaystyle{\bf v}_{2}(\lambda,\lambda_{0})=\frac{\bf
y}{\lambda}-\theta^{*}(\lambda_{0}),$ (18) $\displaystyle{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})={\bf
v}_{2}(\lambda,\lambda_{0})-\frac{\langle{\bf v}_{1}(\lambda_{0}),{\bf
v}_{2}(\lambda,\lambda_{0})\rangle}{\|{\bf v}_{1}(\lambda_{0})\|_{2}^{2}}{\bf
v}_{1}(\lambda_{0}).$ (19)

Then, the dual optimal solution $\theta^{*}(\lambda)$ can be estimated as
follows:

$\displaystyle\theta^{*}(\lambda)\in B\left(\theta^{*}(\lambda_{0}),\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\right)\subseteq
B\left(\theta^{*}(\lambda_{0}),\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2}\right).$ (20)

###### Proof.

By making use of Lemma 6, we present the proof of the statement for the cases
with $\lambda_{0}\in(0,\lambda_{\rm max})$. We postpone the proof of the
statement for the case with $\lambda_{0}=\lambda_{\rm max}$ after we introduce
more general technical results.

In view of the assumption $\lambda_{0}\in(0,\lambda_{\rm max})$, it is easy to
see that

$\displaystyle\frac{\bf y}{\lambda_{0}}\notin F\Rightarrow\frac{\bf
y}{\lambda_{0}}\neq P_{F}\left(\frac{\bf
y}{\lambda_{0}}\right)=\theta^{*}(\lambda_{0})\Rightarrow\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0})\neq 0.$ (21)

For each $\lambda_{0}\in(0,\lambda_{\rm max})$, let us define

$\displaystyle\theta_{\lambda_{0}}(t)=\theta^{*}(\lambda_{0})+t{\bf
v}_{1}(\lambda_{0})=\theta^{*}(\lambda_{0})+t\left(\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0})\right),\hskip 5.69054ptt\geq 0.$ (22)

By the result in (21), we can see that $\theta_{\lambda_{0}}(\cdot)$ defined
by Eq. (22) is a ray which starts at $\theta^{*}(\lambda_{0})$ and points in
the same direction as ${\bf y}/\lambda_{0}-\theta^{*}(\lambda_{0})$. In view
of Eq. (6), a direct application of Lemma 6 leads to that:

$\displaystyle P_{F}(\theta_{\lambda_{0}}(t))=\theta^{*}(\lambda_{0}),\hskip
5.69054pt\forall\hskip 2.84526ptt\geq 0.$ (23)

By applying Theorem 1 again, we have

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}$
$\displaystyle=\left\|P_{F}\left(\frac{\bf
y}{\lambda}\right)-P_{F}(\theta_{\lambda_{0}}(t))\right\|_{2}$ (24)
$\displaystyle\leq\left\|\frac{\bf
y}{\lambda}-\theta_{\lambda_{0}}(t)\right\|_{2}=\left\|t\left(\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0})\right)-\left(\frac{\bf
y}{\lambda}-\theta^{*}(\lambda_{0})\right)\right\|_{2}$ $\displaystyle=\|t{\bf
v}_{1}(\lambda_{0})-{\bf v}_{2}(\lambda,\lambda_{0})\|_{2},\hskip
5.69054pt\forall\hskip 2.84526ptt\geq 0.$

Because the inequality in (24) holds for all $t\geq 0$, it is easy to see that

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}$
$\displaystyle\leq\min_{t\geq 0}\,\,\|t{\bf v}_{1}(\lambda_{0})-{\bf
v}_{2}(\lambda,\lambda_{0})\|_{2}$ (25) $\displaystyle=\begin{cases}\|{\bf
v}_{2}(\lambda,\lambda_{0})\|_{2},\hskip 14.22636pt\mbox{if }\langle{\bf
v}_{1}(\lambda_{0}),{\bf v}_{2}(\lambda,\lambda_{0})\rangle<0,\\\ \left\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\right\|_{2},\hskip
8.53581pt\mbox{otherwise}.\end{cases}$

The inequality in (25) implies that, to prove the first half of the statement,
i.e.,

$\theta^{*}(\lambda)\in B(\theta^{*}(\lambda_{0}),\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}),$

we only need to show that $\langle{\bf v}_{1}(\lambda_{0}),{\bf
v}_{2}(\lambda,\lambda_{0})\rangle\geq 0$.

Indeed, it is easy to see that $0\in F$. Therefore, in view of Eq. (23), the
distance between $\theta_{\lambda_{0}}(t)$ and $\theta^{*}(\lambda_{0})$ must
be shorter than the one between $\theta_{\lambda_{0}}(t)$ and $0$ for all
$t\geq 0$, i.e.,

$\displaystyle\|\theta_{\lambda_{0}}(t)-\theta^{*}(\lambda_{0})\|_{2}^{2}\leq\|\theta_{\lambda_{0}}(t)-0\|_{2}^{2}$
(26) $\displaystyle\Rightarrow$ $\displaystyle\hskip
5.69054pt0\leq\|\theta^{*}(\lambda_{0})\|_{2}^{2}+2t\left(\left\langle\theta^{*}(\lambda_{0}),\frac{\bf
y}{\lambda_{0}}\right\rangle-\|\theta^{*}(\lambda_{0})\|_{2}^{2}\right),\hskip
5.69054pt\forall\hskip 2.84526ptt\geq 0.$

Since the inequality in (26) holds for all $t\geq 0$, we can conclude that:

$\displaystyle\left\langle\theta^{*}(\lambda_{0}),\frac{\bf
y}{\lambda_{0}}\right\rangle-\|\theta^{*}(\lambda_{0})\|_{2}^{2}\geq
0\Rightarrow\frac{\|{\bf
y}\|_{2}}{\lambda_{0}}\geq\|\theta^{*}(\lambda_{0})\|_{2}.$ (27)

Therefore, we can see that:

$\displaystyle\langle{\bf v}_{1}(\lambda_{0}),{\bf
v}_{2}(\lambda,\lambda_{0})\rangle$ $\displaystyle=\left\langle\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0}),\frac{\bf y}{\lambda}-\frac{\bf
y}{\lambda_{0}}+\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0})\right\rangle$ (28)
$\displaystyle\geq\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right)\left\langle\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0}),{\bf y}\right\rangle$
$\displaystyle=\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right)\left(\frac{\|{\bf
y}\|_{2}^{2}}{\lambda_{0}}-\langle\theta^{*}(\lambda_{0}),{\bf
y}\rangle\right)$
$\displaystyle\geq\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right)\left(\frac{\|{\bf
y}\|_{2}^{2}}{\lambda_{0}}-\|\theta^{*}(\lambda_{0})\|_{2}\|{\bf
y}\|_{2}\right)\geq 0.$

The last inequality in (28) is due to the result in (27).

Clearly, in view of (25) and (28), we can see that the first half of the
statement holds, i.e., $\theta^{*}(\lambda)\in
B(\theta^{*}(\lambda_{0}),\|{\bf v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2})$.
The second half of the statement, i.e., $B(\theta^{*}(\lambda_{0}),\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2})\subseteq
B(\theta^{*}(\lambda_{0}),|1/\lambda-1/\lambda_{0}|\|{\bf y}\|_{2})$, can be
easily obtained by noting that the inequality in (24) reduces to the one in
(12) when $t=1$. This completes the proof of the statement with
$\lambda_{0}\in(0,\lambda_{\rm max})$. ∎

Before we present the proof of Theorem 7 for the case with
$\lambda_{0}=\lambda_{\rm max}$, let us briefly review some technical results
from convex analysis first.

######  Definition 8.

[28] Let $C$ be a nonempty closed convex subset of a Hilbert space
$\mathcal{H}$ and ${\bf w}\in C$. The set

$\displaystyle N_{C}({\bf w}):=\\{{\bf v}:\langle{\bf v},{\bf u}-{\bf
w}\rangle\leq 0,\forall{\bf u}\in C\\}$ (29)

is called the normal cone to $C$ at ${\bf w}$.

In terms of the normal cones, the following theorem provides an elegant and
useful characterization of the projections onto nonempty closed convex subsets
of a Hilbert space.

######  Theorem 9.

[3] Let $C$ be a nonempty closed convex subset of a Hilbert space
$\mathcal{H}$. Then, for every ${\bf w}\in\mathcal{H}$ and ${\bf w}_{0}\in C$,
${\bf w}_{0}$ is the projection of ${\bf w}$ onto $C$ if and only if ${\bf
w}-{\bf w}_{0}\in N_{C}({\bf w}_{0})$, i.e.,

$\displaystyle{\bf w}_{0}=P_{C}({\bf w})\Leftrightarrow\langle{\bf w}-{\bf
w}_{0},{\bf u}-{\bf w}_{0}\rangle\leq 0,\forall{\bf u}\in C.$ (30)

In view of the proof of Theorem 7, we can see that Eq. (23) is a key step.
When $\lambda_{0}=\lambda_{\rm max}$, similar to Eq. (22), let us define

$\displaystyle\theta_{\lambda_{\rm max}}(t)=\theta^{*}(\lambda_{\rm
max})+t{\bf v}_{1}(\lambda_{\rm max}),\hskip 5.69054pt\forall\hskip
2.84526ptt\geq 0.$ (31)

By Theorem 9, the following lemma shows that Eq. (23) also holds for
$\lambda_{0}=\lambda_{\rm max}$.

######  Lemma 10.

For the Lasso problem, let ${\bf v}_{1}(\cdot)$ and $\theta_{\lambda_{\rm
max}}(\cdot)$ be given by Eq. (17) and Eq. (31), then the following result
holds:

$\displaystyle P_{F}(\theta_{\lambda_{\rm max}}(t))=\theta^{*}(\lambda_{\rm
max}),\hskip 2.84526pt\forall\,\,t\geq 0.$ (32)

###### Proof.

To prove the statement, Theorem 9 implies that we only need to show:

$\displaystyle\langle{\bf v}_{1}(\lambda_{\rm
max}),\theta-\theta^{*}(\lambda_{\rm max})\rangle\leq 0,\hskip
5.69054pt\forall\hskip 2.84526pt\theta\in F.$ (33)

Recall that ${\bf v}_{1}(\lambda_{\rm max})={\rm sign}({\bf x}_{*}^{T}{\bf
y}){\bf x}_{*}$, ${\bf x}_{*}={\rm argmax}_{{\bf x}_{i}}|{\bf x}_{i}^{T}{\bf
y}|$ [Eq. (17)], and $\theta^{*}(\lambda_{\rm max})={\bf y}/\lambda_{\rm max}$
[Eq. (9)]. It is easy to see that

$\displaystyle\langle{\bf v}_{1}(\lambda_{\rm max}),\theta^{*}(\lambda_{\rm
max})\rangle=\left\langle{\rm sign}({\bf x}_{*}^{T}{\bf y}){\bf
x}_{*},\frac{\bf y}{\lambda_{\rm max}}\right\rangle=\frac{|{\bf x}_{*}^{T}{\bf
y}|}{\lambda_{\rm max}}=1.$ (34)

Moreover, assume $\theta$ is an arbitrary point of $F$. Then, we have
$|\langle{\bf x}_{*},\theta\rangle|\leq 1$, and thus

$\displaystyle\langle{\bf v}_{1}(\lambda_{\rm max}),\theta\rangle=\langle{\rm
sign}({\bf x}_{*}^{T}{\bf y}){\bf x}_{*},\theta\rangle\leq|\langle{\bf
x}_{*},\theta\rangle|\leq 1.$ (35)

Therefore, the inequality in (33) easily follows by combing the results in
(34) and (35), which completes the proof. ∎

We are now ready to give the proof of Theorem 7 for the case with
$\lambda_{0}=\lambda_{\rm max}$.

###### Proof.

In view of Theorem 1 and Lemma 10, we have

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{\rm max})\|_{2}$
$\displaystyle=\left\|P_{F}\left(\frac{\bf
y}{\lambda}\right)-P_{F}(\theta_{\lambda_{\rm max}}(t))\right\|_{2}$ (36)
$\displaystyle\leq\left\|\frac{\bf y}{\lambda}-\theta_{\lambda_{\rm
max}}(t)\right\|_{2}=\left\|t{\bf v}_{1}(\lambda_{\rm max})-\left(\frac{\bf
y}{\lambda}-\theta^{*}(\lambda_{\rm max})\right)\right\|_{2}$
$\displaystyle=\|t{\bf v}_{1}(\lambda_{\rm max})-{\bf
v}_{2}(\lambda,\lambda_{\rm max})\|_{2},\hskip 5.69054pt\forall\hskip
2.84526ptt\geq 0.$

Because the inequality in (36) holds for all $t\geq 0$, we can see that

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{\rm max})\|_{2}$
$\displaystyle\leq\min_{t\geq 0}\,\,\|t{\bf v}_{1}(\lambda_{\rm max})-{\bf
v}_{2}(\lambda,\lambda_{\rm max})\|_{2}$ (37)
$\displaystyle=\begin{cases}\|{\bf v}_{2}(\lambda,\lambda_{\rm
max})\|_{2},\hskip 14.22636pt\mbox{if }\langle{\bf v}_{1}(\lambda_{\rm
max}),{\bf v}_{2}(\lambda,\lambda_{\rm max})\rangle<0,\\\ \left\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{\rm max})\right\|_{2},\hskip
8.53581pt\mbox{otherwise}.\end{cases}$

Clearly, we only need to show that $\langle{\bf v}_{1}(\lambda_{\rm max}),{\bf
v}_{2}(\lambda,\lambda_{\rm max})\rangle\geq 0$.

Indeed, Lemma 10 implies that ${\bf v}_{1}(\lambda_{\rm max})\in
N_{F}(\theta^{*}(\lambda_{\rm max}))$ [please refer to the inequality in
(33)]. By noting that $0\in F$, we have

$\displaystyle\left\langle{\bf v}_{1}(\lambda_{\rm max}),0-\frac{\bf
y}{\lambda_{\rm max}}\right\rangle\leq 0\Rightarrow\langle{\bf
v}_{1}(\lambda_{\rm max}),{\bf y}\rangle\geq 0.$ (38)

Moreover, because ${\bf y}/\lambda_{\rm max}=\theta^{*}(\lambda_{\rm max})$,
it is easy to see that

$\displaystyle\langle{\bf v}_{1}(\lambda_{\rm max}),{\bf
v}_{2}(\lambda,\lambda_{\rm max})\rangle$ $\displaystyle=\left\langle{\bf
v}_{1}(\lambda_{\rm max}),\frac{\bf y}{\lambda}-\frac{\bf y}{\lambda_{\rm
max}}\right\rangle$ (39)
$\displaystyle=\left(\frac{1}{\lambda}-\frac{1}{\lambda_{\rm
max}}\right)\langle{\bf v}_{1}(\lambda_{\rm max}),{\bf y}\rangle\geq 0.$

Therefore, in view of (37) and (39), we can see that the first half of the
statement holds, i.e., $\theta^{*}(\lambda)\in B(\theta^{*}(\lambda_{\rm
max}),\|{\bf v}_{2}^{\perp}(\lambda,\lambda_{\rm max})\|_{2})$. The second
half of the statement, i.e.,

$B(\theta^{*}(\lambda_{\rm max}),\|{\bf v}_{2}^{\perp}(\lambda,\lambda_{\rm
max})\|_{2})\subseteq B(\theta^{*}(\lambda_{\rm
max}),|1/\lambda-1/\lambda_{\rm max}|\|{\bf y}\|_{2}),$

can be easily obtained by noting that the inequality in (37) reduces to the
one in (12) when $t=0$. This completes the proof of the statement with
$\lambda_{0}=\lambda_{\rm max}$. Thus, the proof of Theorem 7 is completed. ∎

Theorem 7 in fact provides a more accurate estimation of the dual optimal
solution than the one in DPP, i.e., $\theta^{*}(\lambda)$ lies inside a ball
centered at $\theta^{*}(\lambda_{0})$ with a radius $\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}$. Based on this improved estimation
and (R1’), we can develop the following screening rule to discard the inactive
features for Lasso.

######  Theorem 11.

For the Lasso problem, assume the dual optimal solution $\theta^{\ast}(\cdot)$
at $\lambda_{0}\in(0,\lambda_{\rm max}]$ is known. Then, for each
$\lambda\in(0,\lambda_{0})$, we have $[\beta^{\ast}(\lambda)]_{i}=0$ if

$\displaystyle|{\bf x}_{i}^{T}\theta^{\ast}(\lambda_{0})|<1-\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\|{\bf x}_{i}\|_{2}.$

We omit the proof of Theorem 11 since it is very similar to the one of Theorem
3. By Theorem 11, we can easily develop the following sequential screening
rule.

Improvement 1: For the Lasso problem (1), suppose we are given a sequence of
parameter values $\lambda_{\rm
max}=\lambda_{0}>\lambda_{1}>\ldots>\lambda_{\mathcal{K}}$. Then for any
integer $0\leq k<\mathcal{K}$, we have $[\beta^{\ast}(\lambda_{k+1})]_{i}=0$
if $\beta^{\ast}(\lambda_{k})$ is known and the following holds:

$\left|{\bf x}_{i}^{T}\frac{{\bf y}-{\bf
X}\beta^{\ast}(\lambda_{k})}{\lambda_{k}}\right|<1-\|{\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})\|_{2}\|{\bf x}_{i}\|_{2}.$

The screening rule in Improvement 1 is developed based on (R1’) and the
estimation of the dual optimal solution in Theorem 7, which is more accurate
than the one in DPP. Therefore, in view of (R1’), the screening rule in
Improvement 1 are more effective in discarding the inactive features than the
DPP rule.

####  2.3.2 Improving the DPP rules via Firmly Nonexpansiveness

In Section 2.3.1, we improve the estimation of the dual optimal solution in
DPP by making use of the projections of properly chosen rays. (R1’) implies
that the resulting screening rule stated in Improvement 1 is more effective in
discarding the inactive features than DPP. In this Section, we present another
approach to improve the estimation of the dual optimal solution in DPP by
making use of the so called firmly nonexpansiveness of the projections onto
nonempty closed convex subset of a Hilbert space.

######  Theorem 12.

[3] Let $C$ be a nonempty closed convex subset of a Hilbert space
$\mathcal{H}$. Then the projection operator defined in Eq. (5) is continuous
and firmly nonexpansive. In other words, for any ${\bf w}_{1},{\bf
w}_{2}\in\mathcal{H}$, we have

$\displaystyle\|P_{C}({\bf w}_{1})-P_{C}({\bf w}_{2})\|_{2}^{2}+\|({\rm
Id}-P_{C})({\bf w}_{1})-({\rm Id}-P_{C})({\bf w}_{2})\|_{2}^{2}\leq\|{\bf
w}_{1}-{\bf w}_{2}\|_{2}^{2},$ (40)

where ${\rm Id}$ is the identity operator.

In view of the inequalities in (40) and (10), it is easy to see that firmly
nonexpansiveness implies nonexpansiveness. But the converse is not true.
Therefore, firmly nonexpansiveness of the projection operators is a stronger
property than the nonexpansiveness. A direct application of Theorem 12 leads
to the following result.

######  Theorem 13.

For the Lasso problem, let $\lambda,\lambda_{0}>0$ be two parameter values.
Then

$\displaystyle\theta^{*}(\lambda)\in
B\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right){\bf
y},\frac{1}{2}\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2}\right)\subset
B\left(\theta^{*}(\lambda_{0}),\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2}\right).$ (41)

###### Proof.

In view of Eq. (6) and the firmly nonexpansiveness in (40), we have

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}^{2}+\left\|\left(\frac{\bf
y}{\lambda}-\theta^{*}(\lambda)\right)-\left(\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0})\right)\right\|_{2}^{2}\leq\left\|\frac{\bf
y}{\lambda}-\frac{\bf y}{\lambda_{0}}\right\|_{2}^{2}$ (42)
$\displaystyle\Leftrightarrow\hskip 5.69054pt$
$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}^{2}\leq\left\langle\theta^{*}(\lambda)-\theta^{*}(\lambda_{0}),\frac{\bf
y}{\lambda}-\frac{\bf y}{\lambda_{0}}\right\rangle$
$\displaystyle\Leftrightarrow\hskip 5.69054pt$
$\displaystyle\left\|\theta^{*}(\lambda)-\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right){\bf
y}\right)\right\|_{2}\leq\frac{1}{2}\left|\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right|\|{\bf
y}\|_{2},$

which completes the proof of the first half of the statement. The second half
of the statement is trivial by noting that the first inequality in (42)
(firmly nonexpansiveness) implies the inequality in (11) (nonexpansiveness)
but not vice versa. Indeed, it is easy to see that the ball in the middle of
(41) is inside the right one and has only a half radius. ∎

Clearly, Theorem 13 provides a more accurate estimation of the dual optimal
solution than the one in DPP, i.e., the dual optimal solution must be inside a
ball which is a subset of the one in DPP and has only a half radius. Again,
based on the estimation in Theorem 13 and (R1’), we have the following result.

######  Theorem 14.

For the Lasso problem, assume the dual optimal solution $\theta^{\ast}(\cdot)$
at $\lambda_{0}\in(0,\lambda_{\rm max}]$ is known. Then, for each
$\lambda\in(0,\lambda_{0})$, we have $[\beta^{\ast}(\lambda)]_{i}=0$ if

$\displaystyle\left|{\bf
x}_{i}^{T}\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right){\bf
y}\right)\right|<1-\frac{1}{2}\left(\frac{1}{\lambda}-\frac{1}{\lambda_{0}}\right)\|{\bf
y}\|_{2}\|{\bf x}_{i}\|_{2}.$

We omit the proof of Theorem 14 since it is very similar to the proof of
Theorem 3. A direct application of Theorem 14 leads to the following
sequential screening rule.

Improvement 2: For the Lasso problem (1), suppose we are given a sequence of
parameter values $\lambda_{\rm
max}=\lambda_{0}>\lambda_{1}>\ldots>\lambda_{\mathcal{K}}$. Then for any
integer $0\leq k<\mathcal{K}$, we have $[\beta^{\ast}(\lambda_{k+1})]_{i}=0$
if $\beta^{\ast}(\lambda_{k})$ is known and the following holds:

$\left|{\bf x}_{i}^{T}\left(\frac{{\bf y}-{\bf
X}\beta^{\ast}(\lambda_{k})}{\lambda_{k}}+\frac{1}{2}\left(\frac{1}{\lambda_{k+1}}-\frac{1}{\lambda_{k}}\right){\bf
y}\right)\right|<1-\frac{1}{2}\left(\frac{1}{\lambda_{k+1}}-\frac{1}{\lambda_{k}}\right)\|{\bf
y}\|_{2}\|{\bf x}_{i}\|_{2}.$

Because the screening rule in Improvement 2 is developed based on (R1’) and
the estimation in Theorem 13, it is easy to see that Improvement 2 is more
effective in discarding the inactive features than DPP.

####  2.3.3 The Proposed Enhanced DPP Rules

In Sections 2.3.1 and 2.3.2, we present two different approaches to improve
the estimation of the dual optimal solution in DPP. In view of (R1’), we can
see that the resulting screening rules, i.e., Improvements 1 and 2, are more
effective in discarding the inactive features than DPP. In this section, we
give a more accurate estimation of the dual optimal solution than the ones in
Theorems 7 and 13 by combining the aforementioned two approaches together. The
resulting screening rule for Lasso is the so called enhanced DPP rule (EDPP).
Again, (R1’) implies that EDPP is more effective in discarding the inactive
features than the screening rules in Improvements 1 and 2. We also present
several experiments to demonstrate that EDPP is able to identify more inactive
features than the screening rules in Improvements 1 and 2. Therefore, in the
subsequent sections, we will focus on the generalizations and evaluations of
EDPP.

To develop the EDPP rules, we still follow the three steps in Section 2.1.
Indeed, by combining the two approaches proposed in Sections 2.3.1 and 2.3.2,
we can further improve the estimation of the dual optimal solution in the
following theorem.

######  Theorem 15.

For the Lasso problem, suppose the dual optimal solution $\theta^{*}(\cdot)$
at $\lambda_{0}\in(0,\lambda_{\rm max}]$ is known, and $\forall\hskip
2.84526pt\lambda\in(0,\lambda_{0}]$, let ${\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})$ be given by Eq. (19). Then, we have

$\displaystyle\left\|\theta^{*}(\lambda)-\left(\theta^{*}(\lambda_{0})+\frac{1}{2}{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\right)\right\|_{2}\leq\frac{1}{2}\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}.$ (43)

###### Proof.

Recall that $\theta_{\lambda_{0}}(t)$ is defined by Eq. (22) and Eq. (31). In
view of (40), we have

$\displaystyle\left\|P_{F}\left(\frac{\bf
y}{\lambda}\right)-P_{F}\left(\theta_{\lambda_{0}}(t)\right)\right\|_{2}^{2}+\left\|({\rm
Id}-P_{F})\left(\frac{\bf y}{\lambda}\right)-({\rm
Id}-P_{F})\left(\theta_{\lambda_{0}}(t)\right)\right\|_{2}^{2}\leq\left\|\frac{\bf
y}{\lambda}-\theta_{\lambda_{0}}(t)\right\|_{2}^{2}.$ (44)

By expanding the second term on the left hand side of (44) and rearranging the
terms, we obtain the following equivalent form:

$\displaystyle\left\|P_{F}\left(\frac{\bf
y}{\lambda}\right)-P_{F}\left(\theta_{\lambda_{0}}(t)\right)\right\|_{2}^{2}\leq\left\langle\frac{\bf
y}{\lambda}-\theta_{\lambda_{0}}(t),P_{F}\left(\frac{\bf
y}{\lambda}\right)-P_{F}\left(\theta_{\lambda_{0}}(t)\right)\right\rangle.$
(45)

In view of Eq. (6), Eq. (23) and Eq. (32), the inequality in (45) can be
rewritten as

$\displaystyle\|\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\|_{2}^{2}$
$\displaystyle\leq\left\langle\frac{\bf
y}{\lambda}-\theta_{\lambda_{0}}(t),\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\right\rangle$
(46) $\displaystyle=\left\langle\frac{\bf
y}{\lambda}-\theta^{*}(\lambda_{0})-t{\bf
v}_{1}(\lambda_{0}),\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\right\rangle$
$\displaystyle=\langle{\bf v}_{2}(\lambda,\lambda_{0})-t{\bf
v}_{1}(\lambda_{0}),\theta^{*}(\lambda)-\theta^{*}(\lambda_{0})\rangle,\hskip
5.69054pt\forall t\geq 0.$

[Recall that ${\bf v}_{1}(\lambda_{0})$ and ${\bf v}_{2}(\lambda,\lambda_{0})$
are defined by Eq. (17) and Eq. (18) respectively.] Clearly, the inequality in
(46) is equivalent to

$\displaystyle\left\|\theta^{*}(\lambda)-\left(\theta^{*}(\lambda_{0})+\frac{1}{2}({\bf
v}_{2}(\lambda,\lambda_{0})-t{\bf
v}_{1}(\lambda_{0}))\right)\right\|_{2}^{2}\leq\frac{1}{4}\|{\bf
v}_{2}(\lambda,\lambda_{0})-t{\bf v}_{1}(\lambda_{0})\|_{2}^{2},\hskip
5.69054pt\forall t\geq 0.$ (47)

The statement follows easily by minimizing the right hand side of the
inequality in (47), which has been done in the proof of Theorem 7. ∎

Indeed, Theorem 15 is equivalent to bounding $\theta^{*}(\lambda)$ in a ball
as follows:

$\displaystyle\theta^{*}(\lambda)\in
B\left(\theta^{*}(\lambda_{0})+\frac{1}{2}{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0}),\frac{1}{2}\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\right).$ (48)

Based on this estimation and (R1’), we immediately have the following result.

######  Theorem 16.

For the Lasso problem, assume the dual optimal problem $\theta^{*}(\cdot)$ at
$\lambda_{0}\in(0,\lambda_{\rm max}]$ is known, and
$\lambda\in(0,\lambda_{0}]$. Then $[\beta^{*}(\lambda)]_{i}=0$ if the
following holds:

$\displaystyle\left|{\bf
x}_{i}^{T}\left(\theta^{*}(\lambda_{0})+\frac{1}{2}{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\right)\right|<1-\frac{1}{2}\|{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\|{\bf x}_{i}\|_{2}.$

We omit the proof of Theorem 16 since it is very similar to the one of Theorem
3. Based on Theorem 16, we can develop the EDPP rules as follows.

######  Corollary 17.

EDPP: For the Lasso problem, suppose we are given a sequence of parameter
values $\lambda_{\rm
max}=\lambda_{0}>\lambda_{1}>\ldots>\lambda_{\mathcal{K}}$. Then for any
integer $0\leq k<\mathcal{K}$, we have $[\beta^{*}(\lambda_{k+1})]_{i}=0$ if
$\beta^{*}(\lambda_{k})$ is known and the following holds:

$\displaystyle\left|{\bf x}_{i}^{T}\left(\frac{{\bf y}-{\bf
X}\beta^{*}(\lambda_{k})}{\lambda_{k}}+\frac{1}{2}{\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})\right)\right|<1-\frac{1}{2}\|{\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})\|_{2}\|{\bf x}_{i}\|_{2}.$ (49)

It is easy to see that the ball in (48) has the smallest radius compared to
the ones in Theorems 7 and 13, and thus it provides the most accurate
estimation of the dual optimal solution. According to (R1’), EDPP is more
effective in discarding the inactive features than DPP, Improvements 1 and 2.

(a) Prostate Cancer, ${\bf X}\in\mathbb{R}^{132\times 15154}$

(b) PIE, ${\bf X}\in\mathbb{R}^{1024\times 11553}$

(c) MNIST, ${\bf X}\in\mathbb{R}^{784\times 50000}$

Figure 1: Comparison of the family of DPP rules on three real data sets:
Prostate Cancer digit data set (left), PIE data set (middle) and MNIST image
data set (right). The first row shows the rejection ratios of DPP, Improvement
1, Improvement 2 and EDPP. The second row presents the speedup gained by these
four methods.

Comparisons of the Family of DPP rules We evaluate the performance of the
family of DPP screening rules, i.e., DPP, Improvement 1, Improvement 2 and
EDPP, on three real data sets: a) the Prostate Cancer [27]; b) the PIE face
image data set [30]; c) the MNIST handwritten digit data set [21]. To measure
the performance of the screening rules, we compute the following two
quantities:

  1. 1.

the rejection ratio, i.e., the ratio of the number of features discarded by
screening rules to the actual number of zero features in the ground truth;

  2. 2.

the speedup, i.e., the ratio of the running time of the solver with screening
rules to the running time of the solver without screening.

For each data set, we run the solver with or without the screening rules to
solve the Lasso problem along a sequence of $100$ parameter values equally
spaced on the $\lambda/\lambda_{\rm max}$ scale from $0.05$ to $1.0$. Fig. 1
presents the rejection ratios and speedup by the family of DPP screening
rules. Table 1 reports the running time of the solver with or without the
screening rules for solving the $100$ Lasso problems, as well as the time for
running the screening rules.

Data | solver | DPP+solver | Imp.1+solver | Imp.2+solver | EDPP+solver | DPP | Imp.1 | Imp.2 | EDPP
---|---|---|---|---|---|---|---|---|---
Prostate Cancer | 121.41 | 23.36 | 6.39 | 17.00 | 3.70 | 0.30 | 0.27 | 0.28 | 0.23
PIE | 629.94 | 74.66 | 11.15 | 55.45 | 4.13 | 1.63 | 1.34 | 1.54 | 1.33
MNIST | 2566.26 | 332.87 | 37.80 | 226.02 | 11.12 | 5.28 | 4.36 | 4.94 | 4.19
Table 1: Running time (in seconds) for solving the Lasso problems along a
sequence of $100$ tuning parameter values equally spaced on the scale of
${\lambda}/{\lambda_{\rm max}}$ from $0.05$ to $1$ by (a): the solver [22]
(reported in the second column) without screening; (b): the solver combined
with different screening methods (reported in the $3^{rd}$ to the $6^{th}$
columns). The last four columns report the total running time (in seconds) for
the screening methods.

The Prostate Cancer Data Set The Prostate Cancer data set [27] is obtained by
protein mass spectrometry. The features are indexed by time-of-flight values,
which are related to the mass over charge ratios of the constituent proteins
in the blood. The data set has $15154$ measurements of $132$ patients. $69$ of
the patients have prostate cancer and the rest are healthy. Therefore, the
data matrix ${\bf X}$ is of size $132\times 15154$, and the response vector
${\bf y}\in\\{1,-1\\}^{132}$ contains the binary labels of the patients.

The PIE Face Image Data Set The PIE face image data set used in this
experiment111http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html [10]
contains $11554$ gray face images of $68$ people, taken under different poses,
illumination conditions and expressions. Each of the images has $32\times 32$
pixels. Therefore, in each trial, we first randomly pick an image as the
response ${\bf y}\in\mathbb{R}^{1024}$, and then use the remaining images to
form the data matrix ${\bf X}\in\mathbb{R}^{1024\times 11553}$. We run $100$
trials and report the average performance of the screening rules.

The MNIST Handwritten Digit Data Set This data set contains grey images of
scanned handwritten digits, including $60,000$ for training and $10,000$ for
testing. The dimension of each image is $28\times 28$. We first randomly
select $5000$ images for each digit from the training set (and in total we
have $50000$ images) and get a data matrix ${\bf X}\in\mathbb{R}^{784\times
50000}$. Then in each trial, we randomly select an image from the testing set
as the response ${\bf y}\in\mathbb{R}^{784}$. We run $100$ trials and report
the average performance of the screening rules.

From Fig. 1, we can see that both Improvements 1 and 2 are able to discard
more inactive features than DPP, and thus lead to a higher speedup. Compared
to Improvement 2, we can also observe that Improvement 1 is more effective in
discarding the inactive features. For the three data sets, the second row of
Fig. 1 shows that Improvement 1 leads to about $20$, $60$, $70$ times speedup
respectively, which are much higher than the ones gained by Improvement 1
(roughly $10$ times for all the three cases).

Moreover, the EDPP rule, which combines the ideas of both Improvements 1 and
2, is even more effective in discarding the inactive features than Improvement
1. We can see that, for all of the three data sets and most of the $100$
parameter values, the rejection ratios of EDPP are very close to $100\%$. In
other words, EDPP is able to discard almost all of the inactive features.
Thus, the resulting speedup of EDPP is significantly better than the ones
gained by the other three DPP rules. For the PIE and MNIST data sets, we can
see that the speedup gained EDPP is about $150$ and $230$ times, which are two
orders of magnitude. In view of Table 1, for the MNIST data set, the solver
without screening needs about $2566.26$ seconds to solve the $100$ Lasso
problems. In contrast, the solver with EDPP only needs $11.12$ seconds,
leading to substantial savings in the computational cost. Moreover, from the
last four columns of Table 1, we can also observe that the computational cost
of the family of DPP rules are very low. Compared to that of the solver
without screening, the computational cost of the family of DPP rules is
negligible.

In Section 4, we will only compare the performance of EDPP against several
other state-of-the-art screening rules.

##  3 Extensions to Group Lasso

To demonstrate the flexibility of the family of DPP rules, we extend the idea
of EDPP to the group Lasso problem [37] in this section. Although the Lasso
and group Lasso problems are very different from each other, we will see that
their dual problems share a lot of similarities. For example, both of the dual
problems can be formulated as looking for projections onto nonempty closed
convex subsets of a Hilbert space. Recall that, the EDPP rule for the Lasso
problem is entirely based on the properties of the projection operators.
Therefore, the framework of the EDPP screening rule we developed for Lasso is
also applicable for the group Lasso problem. In Section 3.1, we briefly review
some basics of the group Lasso problem and explore the geometric properties of
its dual problem. In Section 3.2, we develop the EDPP rule for the group Lasso
problem.

###  3.1 Basics

With the group information available, the group Lasso problem takes the form
of:

$\inf_{\beta\in\mathbb{R}^{p}}\frac{1}{2}\left\|{\bf
y}-\sum\nolimits_{g=1}^{G}{\bf
X}_{g}\beta_{g}\right\|_{2}^{2}+\lambda\sum\nolimits_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2},$
(50)

where ${\bf X}_{g}\in\mathbb{R}^{N\times n_{g}}$ is the data matrix for the
$g^{th}$ group and $p=\sum_{g=1}^{G}n_{g}$. The dual problem of (50) is (see
detailed derivation in the appendix):

$\displaystyle\sup_{\theta}\quad\left\\{\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{\lambda^{2}}{2}\left\|\theta-\frac{{\bf
y}}{\lambda}\right\|_{2}^{2}:\,\,\|{\bf
X}_{g}^{T}\theta\|_{2}\leq\sqrt{n_{g}},\,g=1,2,\ldots,G\right\\}$ (51)

The KKT conditions are given by

$\displaystyle{\bf y}$ $\displaystyle=\sum\nolimits_{g=1}^{G}{\bf
X}_{g}\beta_{g}^{\ast}(\lambda)+\lambda\theta^{\ast}(\lambda),$ (52)
$\displaystyle(\theta^{\ast}(\lambda))^{T}{\bf X}_{g}$
$\displaystyle\in\begin{cases}\sqrt{n_{g}}\frac{\beta_{g}^{\ast}(\lambda)}{\|\beta_{g}^{\ast}(\lambda)\|_{2}},\hskip
25.60747pt{\rm if}\beta_{g}^{\ast}(\lambda)\neq 0,\\\ \sqrt{n_{g}}{\bf
u},\,\|{\bf u}\|_{2}\leq 1,\hskip 5.69054pt{\rm
if}\beta_{g}^{\ast}(\lambda)=0.\\\ \end{cases}$ (53)

for $g=1,2,\ldots,G$. Clearly, in view of Eq. (53), we can see that

$\displaystyle\|(\theta^{\ast}(\lambda))^{T}{\bf
X}_{g}\|_{2}<\sqrt{n_{g}}\Rightarrow\beta_{g}^{\ast}(\lambda)=0$ (R2)

However, since $\theta^{*}(\lambda)$ is generally unknown, (R2) is not
applicable to identify the inactive groups, i.e., the groups which have $0$
coefficients in the solution vector, for the group Lasso problem. Therefore,
similar to the Lasso problem, we can first find a region
$\overline{\bf\Theta}$ which contains $\theta^{*}(\lambda)$, and then (R2) can
be relaxed as follows:

$\displaystyle\sup_{\theta\in\overline{\bf\Theta}}\|(\theta)^{T}{\bf
X}_{g}\|_{2}<\sqrt{n_{g}}\Rightarrow\beta_{g}^{\ast}(\lambda)=0.$ (R2′)

Therefore, to develop screening rules for the group Lasso problem, we only
need to estimate the region $\overline{\bf\Theta}$ which contains
$\theta^{*}(\lambda)$, solve the maximization problem in (R2′), and plug it
into (R2′). In other words, the three steps proposed in Section 2.1 can also
be applied to develop screening rules for the group Lasso problem. Moreover,
(R2′) also implies that the smaller the region $\overline{\bf\Theta}$ is, the
more accurate the estimation of the dual optimal solution is. As a result, the
more effective the resulting screening rule is in discarding the inactive
features.

Geometric Interpretations For notational convenience, let $\overline{F}$ be
the feasible set of problem (51). Similar to the case of Lasso, problem
(51)implies that the dual optimal $\theta^{\ast}(\lambda)$ is the projection
of ${\bf y}/{\lambda}$ onto the feasible set $\overline{F}$, i.e.,

$\displaystyle\theta^{*}(\lambda)=P_{\overline{F}}\left(\frac{\bf
y}{\lambda}\right),\hskip 5.69054pt\forall\hskip 2.84526pt\lambda>0.$ (54)

Compared to Eq. (6), the only difference in Eq. (54) is that the feasible set
$\overline{F}$ is the intersection of a set of ellipsoids, and thus not a
polytope. However, similar to $F$, $\overline{F}$ is also a nonempty closed
and convex (notice that $0$ is a feasible point). Therefore, we can make use
of all the aforementioned properties of the projection operators, e.g., Lemmas
6 and 10, Theorems 9 and 12, to develop screening rules for the group Lasso
problem.

Moreover, similar to the case of Lasso, we also have a specific parameter
value [32] for the group Lasso problem, i.e.,

$\displaystyle\overline{\lambda}_{\rm max}=\max_{g}\frac{\|{\bf X}_{g}^{T}{\bf
y}\|_{2}}{\sqrt{n_{g}}}.$ (55)

Indeed, $\overline{\lambda}_{\rm max}$ is the smallest parameter value such
that the optimal solution of problem (50) is 0. More specifically, we have:

$\displaystyle\beta^{*}(\lambda)=0,\hskip 5.69054pt\forall\hskip
2.84526pt\lambda\in[\overline{\lambda}_{\rm max},\infty).$ (56)

Combining the result in (56) and Eq. (52), we immediately have

$\displaystyle\theta^{*}(\lambda)=\frac{\bf y}{\lambda},\hskip
5.69054pt\forall\hskip 2.84526pt\lambda\in[\overline{\lambda}_{\rm
max},\infty).$ (57)

Therefore, all through the subsequent sections, we will focus on the cases
with $\lambda\in(0,\overline{\lambda}_{\rm max})$.

###  3.2 Enhanced DPP rule for Group Lasso

In view of (R2′), we can see that the estimation of the dual optimal solution
is the key step to develop a screening rule for the group Lasso problem.
Because $\theta^{*}(\lambda)$ is the projection of ${\bf y}/\lambda$ onto the
nonempty closed convex set $\overline{F}$ [please refer to Eq. (54)], we can
make use of all the properties of projection operators, e.g., Lemmas 6 and 10,
Theorems 9 and 12, to estimate the dual optimal solution. First, let us
develop a useful technical result as follows.

######  Lemma 18.

For the group Lasso problem, let $\overline{\lambda}_{\rm max}$ be given by
Eq. (55) and

$\displaystyle{\bf X}_{*}:={\rm argmax}_{{\bf X}_{g}}\frac{\|{\bf
X}_{g}^{T}{\bf y}\|_{2}}{\sqrt{n_{g}}}.$ (58)

Suppose the dual optimal solution $\theta^{*}(\cdot)$ is known at
$\lambda_{0}\in(0,\overline{\lambda}_{\rm max}]$, let us define

$\displaystyle\overline{\bf v}_{1}(\lambda_{0})$
$\displaystyle=\begin{cases}\frac{\bf
y}{\lambda_{0}}-\theta^{*}(\lambda_{0}),\hskip 5.69054pt{\rm if}\hskip
5.69054pt\lambda_{0}\in(0,\overline{\lambda}_{\rm max}),\\\ {\bf X}_{*}{\bf
X}_{*}^{T}{\bf y},\hskip 24.18483pt{\rm if}\hskip
5.69054pt\lambda_{0}=\overline{\lambda}_{\rm max}.\\\ \end{cases}$ (59)
$\displaystyle\overline{\theta}_{\lambda_{0}}(t)$
$\displaystyle=\theta^{*}(\lambda_{0})+t\overline{\bf
v}_{1}(\lambda_{0}),\hskip 5.69054ptt\geq 0.$ (60)

Then, we have the following result holds

$\displaystyle
P_{\overline{F}}(\overline{\theta}_{\lambda_{0}}(t))=\theta^{*}(\lambda_{0}),\hskip
2.84526pt\forall\,\,t\geq 0.$ (61)

###### Proof.

Let us first consider the cases with $\lambda_{0}\in(0,\overline{\lambda}_{\rm
max})$. In view of the definition of $\overline{\lambda}_{\rm max}$, it is
easy to see that ${\bf y}/\lambda_{0}\notin\overline{F}$. Therefore, in view
of Eq. (54) and Lemma 6, the statement in Eq. (61) follows immediately.

We next consider the case with $\lambda_{0}=\overline{\lambda}_{\rm max}$. By
Theorem 9, we only need to check if

$\displaystyle\overline{\bf v}_{1}(\overline{\lambda}_{\rm max})\in
N_{\overline{F}}(\theta^{*}(\overline{\lambda}_{\rm
max}))\Leftrightarrow\left\langle\overline{\bf v}_{1}(\overline{\lambda}_{\rm
max}),\theta-\theta^{*}(\overline{\lambda}_{\rm max})\right\rangle\leq
0,\hskip 5.69054pt\forall\hskip 2.84526pt\theta\in\overline{F}.$ (62)

Indeed, in view of Eq. (55) and Eq. (57), we can see that

$\displaystyle\langle\overline{\bf v}_{1}(\overline{\lambda}_{\rm
max}),\theta^{*}(\overline{\lambda}_{\rm max})\rangle=\left\langle{\bf
X}_{*}{\bf X}_{*}^{T}{\bf y},\frac{\bf y}{\overline{\lambda}_{\rm
max}}\right\rangle=\frac{\|{\bf X}_{*}^{T}{\bf
y}\|_{2}^{2}}{\overline{\lambda}_{\rm max}}.$ (63)

On the other hand, by Eq. (55) and Eq. (58), we can see that

$\displaystyle{\|{\bf X}_{*}^{T}{\bf y}\|_{2}}=\overline{\lambda}_{\rm
max}\sqrt{n_{*}},$ (64)

where $n_{*}$ is the number of columns of ${\bf X}_{*}$. By plugging Eq. (64)
into Eq. (63), we have

$\displaystyle\langle\overline{\bf v}_{1}(\overline{\lambda}_{\rm
max}),\theta^{*}(\overline{\lambda}_{\rm max})\rangle=\overline{\lambda}_{\rm
max}\cdot n_{*}.$ (65)

Moreover, for any feasible point $\theta\in\overline{F}$, we can see that

$\displaystyle\|{\bf X}_{*}^{T}\theta\|_{2}\leq\sqrt{n_{*}}.$ (66)

In view of the result in (66) and Eq. (64), it is easy to see that

$\displaystyle\left\langle\overline{\bf v}_{1}(\overline{\lambda}_{\rm
max}),\theta\right\rangle=\left\langle{\bf X}_{*}{\bf X}_{*}^{T}{\bf
y},\theta\right\rangle=\left\langle{\bf X}_{*}^{T}{\bf y},{\bf
X}_{*}^{T}\theta\right\rangle\leq\|{\bf X}_{*}^{T}{\bf y}\|_{2}\|{\bf
X}_{*}^{T}\theta\|_{2}=\overline{\lambda}_{\rm max}\cdot n_{*}.$ (67)

Combining the result in Eq. (63) and (67), it is easy to see that the
inequality in (62) holds for all $\theta\in\overline{F}$, which completes the
proof. ∎

By Lemma 18, we can accurately estimate the dual optimal solution of the group
Lasso problem in the following theorem. It is easy to see that the result in
Theorem 19 is very similar to the one in Theorem 15 for the Lasso problem.

######  Theorem 19.

For the group Lasso problem, suppose the dual optimal solution
$\theta^{*}(\cdot)$ at $\theta_{0}\in(0,\overline{\lambda}_{\rm max}]$ is
known, and $\overline{\bf v}_{1}(\lambda_{0})$ is given by Eq. (59). For any
$\lambda\in(0,\lambda_{0}]$, let us define

$\displaystyle\overline{\bf v}_{2}(\lambda,\lambda_{0})=\frac{\bf
y}{\lambda}-\theta^{*}(\lambda_{0}),$ (68) $\displaystyle\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})=\overline{\bf
v}_{2}(\lambda,\lambda_{0})-\frac{\langle\overline{\bf
v}_{1}(\lambda_{0}),\overline{\bf
v}_{2}(\lambda,\lambda_{0})\rangle}{\|\overline{\bf
v}_{1}(\lambda_{0})\|_{2}^{2}}\overline{\bf v}_{1}(\lambda_{0}).$ (69)

Then, the dual optimal solution $\theta^{*}(\lambda)$ can be estimated as
follows:

$\displaystyle\left\|\theta^{*}(\lambda)-\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\right)\right\|_{2}\leq\frac{1}{2}\|\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}.$ (70)

We omit the proof of Theorem 19 since it is exactly the same as the one of
Theorem 15. Indeed, Theorem 19 is equivalent to estimating
$\theta^{*}(\lambda)$ in a ball as follows:

$\displaystyle\theta^{*}(\lambda)\in
B\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0}),\frac{1}{2}\|\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\right).$ (71)

Based on this estimation and (R2′), we immediately have the following result.

######  Theorem 20.

For the group Lasso problem, assume the dual optimal solution
$\theta^{*}(\cdot)$ is known at $\lambda_{0}\in(0,\overline{\lambda}_{\rm
max}]$, and $\lambda\in(0,\lambda_{0}]$. Then $\beta_{g}^{\ast}(\lambda)=0$ if
the following holds

$\left\|{\bf X}_{g}^{T}\left(\theta^{*}(\lambda_{0})+\frac{1}{2}\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\right)\right\|_{2}<\sqrt{n_{g}}-\frac{1}{2}\|\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}\|{\bf X}_{g}\|_{2}.$ (72)

###### Proof.

In view of (R2′), we only need to check if

$\displaystyle\left\|{\bf
X}_{g}^{T}\theta^{\ast}(\lambda)\right\|_{2}<\sqrt{n_{g}}.$

To simplify notations, let

${\bf o}=\theta^{*}(\lambda_{0})+\frac{1}{2}\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0}),\hskip
5.69054ptr=\frac{1}{2}\|\overline{\bf
v}_{2}^{\perp}(\lambda,\lambda_{0})\|_{2}.$

It is easy to see that

$\displaystyle\left\|{\bf X}_{g}^{T}\theta^{*}(\lambda)\right\|_{2}$
$\displaystyle\leq\|{\bf X}_{g}^{T}(\theta^{\ast}(\lambda)-{\bf
o})\|_{2}+\|{\bf X}_{g}^{T}{\bf o}\|_{2}$ (73) $\displaystyle<\|{\bf
X}_{g}\|_{2}\|\theta^{\ast}(\lambda)-{\bf o}\|_{2}+\sqrt{n_{g}}-r\|{\bf
X}_{g}\|_{2}$ $\displaystyle\leq r\|{\bf X}_{g}\|_{2}+\sqrt{n_{g}}-r\|{\bf
X}_{g}\|_{2}=\sqrt{n_{g}},$

which completes the proof. The second and third inequalities in (73) are due
to (72) and Theorem 19, respectively. ∎

In view of Eq. (52) and Theorem 20, we can derive the EDPP rule to discard the
inactive groups for the group Lasso problem as follows.

######  Corollary 21.

EDPP: For the group Lasso problem (50), suppose we are given a sequence of
parameter values $\overline{\lambda}_{\rm
max}=\lambda_{0}>\lambda_{1}>\ldots>\lambda_{\mathcal{K}}$. For any integer
$0\leq k<\mathcal{K}$, we have $\beta_{g}^{\ast}(\lambda_{k+1})=0$ if
$\beta^{\ast}(\lambda_{k})$ is known and the following holds:

$\displaystyle\left\|{\bf X}_{g}^{T}\left(\frac{{\bf y}-\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}^{\ast}(\lambda_{k})}{\lambda_{k}}+\frac{1}{2}\overline{\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})\right)\right\|_{2}<\sqrt{n_{g}}-\frac{1}{2}\|\overline{\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})\|_{2}\|{\bf X}_{g}\|_{2}.$

##  4 Experiments

In this section, we evaluate the proposed EDPP rules for Lasso and group Lasso
on both synthetic and real data sets. To measure the performance of our
screening rules, we compute the rejection ratio and speedup (please refer to
Section 2.3.3 for details). Because the EDPP rule is safe, i.e., no active
features/groups will be mistakenly discarded, the rejection ratio will be less
than one.

In Section 4.1, we conduct two sets of experiments to compare the performance
of EDPP against several state-of-the-art screening methods. We first compare
the performance of the basic versions of EDPP, DOME, SAFE, and strong rule.
Then, we focus on the sequential versions of EDPP, SAFE, and strong rule.
Notice that, SAFE and EDPP are safe. However, strong rule may mistakenly
discard features with nonzero coefficients in the solution. Although DOME is
also safe for the Lasso problem, it is unclear if there exists a sequential
version of DOME. Recall that, real applications usually favor the sequential
screening rules because we need to solve a sequence of of Lasso problems to
determine an appropriate parameter value [32]. Moreover, DOME assumes special
structure on the data, i.e., each feature and the response vector should be
normalized to have unit length.

In Section 4.2, we compare EDPP with strong rule for the group Lasso problem
on synthetic data sets. We are not aware of any safe screening rules for the
group Lasso problem at this point. For SAFE and Dome, it is not
straightforward to extend them to the group Lasso problem.

###  4.1 EDPP for the Lasso Problem

For the Lasso problem, we first compare the performance of the basic versions
of EDPP, DOME, SAFE and strong rule in Section 4.1.1. Then, we compare the
performance of the sequential versions of EDPP, SAFE and strong rule in
Section 4.1.2.

####  4.1.1 Evaluation of the Basic EDPP Rule

In this section, we perform experiments on six real data sets to compare the
performance of the basic versions of SAFE, DOME, strong rule and EDPP. Briefly
speaking, suppose that we are given a parameter value $\lambda$. Basic
versions of the aforementioned screening rules always make use of
$\beta^{*}(\lambda_{\rm max})$ to identify the zero components of
$\beta^{*}(\lambda)$. Take EDPP for example. The basic version of EDPP can be
obtained by replacing $\beta^{*}(\lambda_{k})$ and ${\bf
v}_{2}^{\perp}(\lambda_{k+1},\lambda_{k})$ with $\beta^{*}(\lambda_{0})$ and
${\bf v}_{2}^{\perp}(\lambda_{k},\lambda_{0})$, respectively, in (49) for all
$k=1,\ldots,\mathcal{K}$.

In this experiment, we report the rejection ratios of the basic SAFE, DOME,
strong rule and EDPP along a sequence of $100$ parameter values equally spaced
on the $\lambda/\lambda_{\rm max}$ scale from $0.05$ to $1.0$. We note that
DOME requires that all features of the data sets have unit length. Therefore,
to compare the performance of DOME with SAFE, strong rule and EDPP, we
normalize the features of all the data sets used in this section. However, it
is worthwhile to mention that SAFE, strong rule and EDPP do not assume any
specific structures on the data set. The data sets used in this section are
listed as follows:

  1. a)

Colon Cancer data set [1];

  2. b)

Lung Cancer data set [6];

  3. c)

Prostate Cancer data set [27];

  4. d)

PIE face image data set [30, 10];

  5. e)

MNIST handwritten digit data set [21];

  6. f)

COIL-100 image data set [24, 11].

(a) Colon Cancer, ${\bf X}\in\mathbb{R}^{62\times 2000}$

(b) Lung Cancer, ${\bf X}\in\mathbb{R}^{203\times 12600}$

(c) Prostate Cancer, ${\bf X}\in\mathbb{R}^{132\times 15154}$

(d) PIE, ${\bf X}\in\mathbb{R}^{1024\times 11553}$

(e) MNIST, ${\bf X}\in\mathbb{R}^{784\times 50000}$

(f) COIL-100, ${\bf X}\in\mathbb{R}^{1024\times 7199}$

Figure 2: Comparison of basic versions of SAFE, DOME, Strong Rule and EDPP on
six real data sets.

The Colon Cancer Data Set This data set contains gene expression information
of 22 normal tissues and 40 colon cancer tissues, and each has 2000 gene
expression values.

The Lung Cancer Data Set This data set contains gene expression information of
186 lung tumors and 17 normal lung specimens. Each specimen has 12600
expression values.

The COIL-100 Image Data Set The data set consists of images of 100 objects.
The images of each object are taken every 5 degree by rotating the object,
yielding 72 images per object. The dimension of each image is $32\times 32$.
In each trial, we randomly select one image as the response vector and use the
remaining ones as the data matrix. We run 100 trials and report the average
performance of the screening rules.

The description and the experimental settings for the Prostate Cancer data
set, the PIE face image data set and the MNIST handwritten digit data set are
given in Section 2.3.3.

Fig. 2 reports the rejection ratios of the basic versions of SAFE, DOME,
strong rule and EDPP. We can see that EDPP significantly outperforms the other
three screening methods on five of the six data sets, i.e., the Colon Cancer,
Lung Cancer, Prostate Cancer, MNIST, and COIL-100 data sets. On the PIE face
image data set, EDPP and DOME provide similar performance and both
significantly outperform SAFE and strong rule.

However, as pointed out by Tibshirani et al. [32], the real strength of
screening methods stems from their sequential versions. The reason is because
the optimal parameter value is unknown in real applications. Typical
approaches for model selection usually involve solving the Lasso problems many
times along a sequence of parameter values. Thus, the sequential screening
methods are more suitable in facilitating the aforementioned scenario and more
useful than their basic-version counterparts in practice [32].

####  4.1.2 Evaluation of the Sequential EDPP Rule

In this section, we compare the performance of the sequential versions of
SAFE, strong rule and EDPP by the rejection ratio and speedup. We first
perform experiments on two synthetic data sets. We then apply the three
screening rules to six real data sets.

Synthetic Data Sets

First, we perform experiments on several synthetic problems, which have been
commonly used in the sparse learning literature [7, 39, 31]. We simulate data
from the true model

$\displaystyle{\bf y}={\bf X}\beta^{*}+\sigma\epsilon,\hskip
5.69054pt\epsilon\sim N(0,1).$ (74)

We generate two data sets with $250\times 10000$ entries: Synthetic 1 and
Synthetic 2. For Synthetic 1, the entries of the data matrix ${\bf X}$ are
i.i.d. standard Gaussian with pairwise correlation zero, i.e., ${\rm
corr}({\bf x}_{i},{\bf x}_{i})=0$. For Synthetic 2, the entries of the data
matrix ${\bf X}$ are drawn from i.i.d. standard Gaussian with pairwise
correlation $0.5^{|i-j|}$, i.e., ${\rm corr}({\bf x}_{i},{\bf
x}_{j})=0.5^{|i-j|}$. To generate the response vector ${\bf
y}\in\mathbb{R}^{250}$ by the model in (74), we need to set the parameter
$\sigma$ and construct the ground truth $\beta^{*}\in\mathbb{R}^{10000}$.
Throughout this section, $\sigma$ is set to be $0.1$. To construct
$\beta^{*}$, we randomly select $\overline{p}$ components which are populated
from a uniform $[-1,1]$ distribution, and set the remaining ones as $0$. After
we generate the data matrix ${\bf X}$ and the response vector ${\bf y}$, we
run the solver with or without screening rules to solve the Lasso problems
along a sequence of $100$ parameter values equally spaced on the
$\lambda/\lambda_{\rm max}$ scale from $0.05$ to $1.0$. We then run $100$
trials and report the average performance.

(a) Synthetic 1, $\overline{p}=100$

(b) Synthetic 1, $\overline{p}=1000$

(c) Synthetic 1, $\overline{p}=5000$

(d) Synthetic 2, $\overline{p}=100$

(e) Synthetic 2, $\overline{p}=1000$

(f) Synthetic 2, $\overline{p}=5000$

Figure 3: Comparison of SAFE, Strong Rule and EDPP on two synthetic datasets
with different numbers of nonzero components of the groud truth.

We first apply the screening rules, i.e., SAFE, strong rule and EDPP to
Synthetic 1 with $\overline{p}=100,1000,5000$ respectively. Fig. 3(a), Fig.
3(b) and Fig. 3(c) present the corresponding rejection ratios and speedup of
SAFE, strong rule and EDPP. We can see that the rejection ratios of strong
rule and EDPP are comparable to each other, and both of them are more
effective in discarding inactive features than SAFE. In terms of the speedup,
EDPP provides better performance than strong rule. The reason is because
strong rule is a heuristic screening method, i.e., it may mistakenly discard
active features which have nonzero components in the solution. Thus, strong
rule needs to check the KKT conditions to ensure the correctness of the
screening result. In contrast, the EDPP rule does not need to check the KKT
conditions since the discarded features are guaranteed to be absent from the
resulting sparse representation. From the last two columns of Table 2, we can
observe that the running time of strong rule is about twice of that of EDPP.

Fig. 3(d), Fig. 3(e) and Fig. 3(f) present the rejection ratios and speedup of
SAFE, strong rule and EDPP on Synthetic 2 with $\overline{p}=100,1000,5000$
respectively. We can observe patterns similar to Synthetic 1. Clearly, our
method, EDPP, is very robust to the variations of the intrinsic structures of
the data sets and the sparsity of the ground truth.

Data | $\overline{p}$ | solver | SAFE+solver | Strong Rule+solver | EDPP+solver | SAFE | Strong Rule | EDPP
---|---|---|---|---|---|---|---|---
Synthetic 1 | 100 | 109.01 | 100.09 | 2.67 | 2.47 | 4.60 | 0.65 | 0.36
1000 | 123.60 | 111.32 | 2.97 | 2.71 | 4.59 | 0.66 | 0.37
5000 | 124.92 | 113.09 | 3.00 | 2.72 | 4.57 | 0.65 | 0.36
Synthetic 2 | 100 | 107.50 | 96.94 | 2.62 | 2.49 | 4.61 | 0.67 | 0.37
1000 | 113.59 | 104.29 | 2.84 | 2.67 | 4.57 | 0.63 | 0.35
5000 | 125.25 | 113.35 | 3.02 | 2.81 | 4.62 | 0.65 | 0.36
Table 2: Running time (in seconds) for solving the Lasso problems along a
sequence of $100$ tuning parameter values equally spaced on the scale of
${\lambda}/{\lambda_{\rm max}}$ from $0.05$ to $1$ by (a): the solver [22]
(reported in the third column) without screening; (b): the solver combined
with different screening methods (reported in the $4^{th}$ to the $6^{th}$
columns). The last four columns report the total running time (in seconds) for
the screening methods.

Real Data Sets

In this section, we compare the performance of the EDPP rule with SAFE and
strong rule on six real data sets along a sequence of $100$ parameter values
equally spaced on the $\lambda/\lambda_{\rm max}$ scale from $0.05$ to $1.0$.
The data sets are listed as follows:

  1. a)

Breast Cancer data set [33, 29];

  2. b)

Leukemia data set [2];

  3. c)

Prostate Cancer data set [27];

  4. d)

PIE face image data set [30, 10];

  5. e)

MNIST handwritten digit data set [21];

  6. f)

Street View House Number (SVHN) data set [25].

We present the rejection ratios and speedup of EDPP, SAFE and strong rule in
Fig. 4. Table 3 reports the running time of the solver with or without
screening for solving the $100$ Lasso problems, and that of the screening
rules.

(a) Breast Cancer, ${\bf X}\in\mathbb{R}^{44\times 7129}$

(b) Leukemia, ${\bf X}\in\mathbb{R}^{55\times 11225}$

(c) Prostate Cancer, ${\bf X}\in\mathbb{R}^{132\times 15154}$

(d) PIE, ${\bf X}\in\mathbb{R}^{1024\times 11553}$

(e) MNIST, ${\bf X}\in\mathbb{R}^{784\times 50000}$

(f) SVHN, ${\bf X}\in\mathbb{R}^{3072\times 99288}$

Figure 4: Comparison of SAFE, Strong Rule, and EDPP on six real data sets.

The Breast Cancer Data Set This data set contains $44$ tumor samples, each of
which is represented by $7129$ genes. Therefore, the data matrix ${\bf X}$ is
of $44\times 7129$. The response vector ${\bf y}\in\\{1,-1\\}^{44}$ contains
the binary label of each sample.

The Leukemia Data Set This data set is a DNA microarray data set, containing
$52$ samples and $11225$ genes. Therefore, the data matrix ${\bf X}$ is of
$55\times 11225$. The response vector ${\bf y}\in\\{1,-1\\}^{52}$ contains the
binary label of each sample.

The SVHN Data set The SVHN data set contains color images of street view house
numbers, including $73257$ images for training and $26032$ for testing. The
dimension of each image is $32\times 32$. In each trial, we first randomly
select an image as the response ${\bf y}\in\mathbb{R}^{3072}$, and then use
the remaining ones to form the data matrix ${\bf X}\in\mathbb{R}^{3072\times
99288}$. We run $100$ trials and report the average performance.

The description and the experiment settings for the Prostate Cancer data set,
the PIE face image data set and the MNIST handwritten digit data set are given
in Section 2.3.3.

Data | solver | SAFE+solver | Strong Rule+solver | EDPP+solver | SAFE | Strong Rule | EDPP
---|---|---|---|---|---|---|---
Breast Cancer | 12.70 | 7.20 | 1.31 | 1.24 | 0.44 | 0.06 | 0.05
Leukemia | 16.99 | 9.22 | 1.15 | 1.03 | 0.91 | 0.09 | 0.07
Prostate Cancer | 121.41 | 47.17 | 4.83 | 3.70 | 3.60 | 0.46 | 0.23
PIE | 629.94 | 138.33 | 4.84 | 4.13 | 19.93 | 2.54 | 1.33
MNIST | 2566.26 | 702.21 | 15.15 | 11.12 | 64.81 | 8.14 | 4.19
SVHN | 11023.30 | 5220.88 | 90.65 | 59.71 | 583.12 | 61.02 | 31.64
Table 3: Running time (in seconds) for solving the Lasso problems along a
sequence of $100$ tuning parameter values equally spaced on the scale of
${\lambda}/{\lambda_{\rm max}}$ from $0.05$ to $1$ by (a): the solver [22]
(reported in the second column) without screening; (b): the solver combined
with different screening methods (reported in the $3^{rd}$ to the $5^{th}$
columns). The last three columns report the total running time (in seconds)
for the screening methods.

From Fig. 4, we can see that the rejection ratios of strong rule and EDPP are
comparable to each other. Compared to SAFE, both of strong rule and EDPP are
able to identify far more inactive features, leading to a much higher speedup.
However, because strong rule needs to check the KKT conditions to ensure the
correctness of the screening results, the speedup gained by EDPP is higher
than that by strong rule. When the size of the data matrix is not very large,
e.g., the Breast Cancer and Leukemia data sets, the speedup gained by EDPP are
slightly higher than that by strong rule. However, when the size of the data
matrix is large, e.g., the MNIST and SVHN data sets, the speedup gained by
EDPP are significantly higher than that by strong rule. Moreover, we can also
observe from Fig. 4 that, the larger the data matrix is, the higher the
speedup can be gained by EDPP. More specifically, for the small data sets,
e.g., the Breast Cancer, Leukemia and Prostate Cancer data sets, the speedup
gained by EDPP is about $10$, $17$ and $30$ times. In contrast, for the large
data sets, e.g., the PIE, MNIST and SVHN data sets, the speedup gained by EDPP
is two orders of magnitude. Take the SVHN data set for example. The solver
without screening needs about $3$ hours to solve the $100$ Lasso problems.
Combined with the EDPP rule, the solver only needs less than $1$ minute to
complete the task.

Clearly, the proposed EDPP screening rule is very effective in accelerating
the computation of Lasso especially for large-scale problems, and outperforms
the state-of-the-art approaches like SAFE and strong rule. Notice that, the
EDPP method is safe in the sense that the discarded features are guaranteed to
have zero coefficients in the solution.

EDPP with Least-Angle Regression (LARS)

As we mentioned in the introduction, we can combine EDPP with any existing
solver. In this experiment, we integrate EDPP and strong rule with another
state-of-the-art solver for Lasso, i.e., Least-Angle Regression (LARS) [15].
We perform experiments on the same real data sets used in the last section
with the same experiment settings. Because the rejection ratios of screening
methods are irrelevant to the solvers, we only report the speedup. Table 4
reports the running time of LARS with or without screening for solving the 100
Lasso problems, and that of the screening methods. Fig. 5 shows the speedup of
these two methods. We can still observe a substantial speedup gained by EDPP.
The reason is that EDPP has a very low computational cost (see Table 4) and it
is very effective in discarding inactive features (see Fig. 4).

Data | LARS | Strong Rule+LARS | EDPP+LARS | Strong Rule | EDPP
---|---|---|---|---|---
Breast Cancer | 1.30 | 0.06 | 0.04 | 0.04 | 0.03
Leukemia | 1.46 | 0.09 | 0.05 | 0.07 | 0.04
Prostate Cancer | 5.76 | 1.04 | 0.37 | 0.42 | 0.24
PIE | 22.52 | 2.42 | 1.31 | 2.30 | 1.21
MNIST | 92.53 | 8.53 | 4.75 | 8.36 | 4.34
SVHN | 1017.20 | 65.83 | 35.73 | 62.53 | 32.00
Table 4: Running time (in seconds) for solving the Lasso problems along a
sequence of $100$ tuning parameter values equally spaced on the scale of
${\lambda}/{\lambda_{\rm max}}$ from $0.05$ to $1$ by (a): the solver [15, 23]
(reported in the second column) without screening; (b): the solver combined
with different screening methods (reported in the $3^{rd}$ and $4^{th}$
columns). The last two columns report the total running time (in seconds) for
the screening methods.

(a) Breast Cancer, ${\bf X}\in\mathbb{R}^{44\times 7129}$

(b) Leukemia, ${\bf X}\in\mathbb{R}^{55\times 11225}$

(c) Prostate Cancer, ${\bf X}\in\mathbb{R}^{132\times 15154}$

(d) PIE, ${\bf X}\in\mathbb{R}^{1024\times 11553}$

(e) MNIST, ${\bf X}\in\mathbb{R}^{784\times 50000}$

(f) SVHN, ${\bf X}\in\mathbb{R}^{3072\times 99288}$

Figure 5: The speedup gained by Strong Rule and EDPP with LARS on six real
data sets.

###  4.2 EDPP for the Group Lasso Problem

In this experiment, we evaluate the performance of EDPP and strong rule with
different numbers of groups. The data matrix ${\bf X}$ is fixed to be
$250\times 200000$. The entries of the response vector ${\bf y}$ and the data
matrix ${\bf X}$ are generated i.i.d. from a standard Gaussian distribution.
For each experiment, we repeat the computation $20$ times and report the
average results. Moreover, let $n_{g}$ denote the number of groups and $s_{g}$
be the average group size. For example, if $n_{g}$ is $10000$, then
$s_{g}=p/n_{g}=20$.

(a) $n_{g}=10000$

(b) $n_{g}=20000$

(c) $n_{g}=40000$

Figure 6: Comparison of EDPP and strong rules with different numbers of
groups.

From Figure 6, we can see that EDPP and strong rule are able to discard more
inactive groups when the number of groups $n_{g}$ increases. The intuition
behind this observation is that the estimation of the dual optimal solution is
more accurate with a smaller group size. Notice that, a large $n_{g}$ implies
a small average group size. Figure 6 also implies that compared to strong
rule, EDPP is able to discard more inactive groups and is more robust with
respect to different values of $n_{g}$.

$n_{g}$ | solver | Strong Rule+solver | EDPP+solver | Strong Rule | EDPP
---|---|---|---|---|---
$10000$ | 4535.54 | 296.60 | 53.81 | 13.99 | 8.32
$20000$ | 5536.18 | 179.48 | 46.13 | 14.16 | 8.61
$40000$ | 6144.48 | 104.50 | 37.78 | 13.13 | 8.37
Table 5: Running time (in seconds) for solving the group Lasso problems along
a sequence of $100$ tuning parameter values equally spaced on the scale of
${\lambda}/{\lambda_{\rm max}}$ from $0.05$ to $1.0$ by (a): the solver from
SLEP (reported in the second column) without screening; (b): the solver
combined with different screening methods (reported in the $3^{rd}$ and
$4^{th}$ columns). The last two columns report the total running time (in
seconds) for the screening methods. The data matrix ${\bf X}$ is of size
$250\times 200000$.

Table 5 further demonstrates the effectiveness of EDPP in improving the
efficiency of the solver. When $n_{g}=10000$, the efficiency of the solver is
improved by about $80$ times. When $n_{g}=20000$ and $40000$, the efficiency
of the solver is boosted by about $120$ and $160$ times with EDPP
respectively.

##  5 Conclusion

In this paper, we develop new screening rules for the Lasso problem by making
use of the properties of the projection operators with respect to a closed
convex set. Our proposed methods, i.e., DPP screening rules, are able to
effectively identify inactive predictors of the Lasso problem, thus greatly
reducing the size of the optimization problem. Moreover, we further improve
DPP rule and propose the enhanced DPP rule, which is more effective in
discarding inactive features than DPP rule. The idea of the family of DPP
rules can be easily generalized to identify the inactive groups of the group
Lasso problem. Extensive numerical experiments on both synthetic and real data
demonstrate the effectiveness of the proposed rules. It is worthwhile to
mention that the family of DPP rules can be combined with any Lasso solver as
a speedup tool. In the future, we plan to generalize our ideas to other sparse
formulations consisting of more general structured sparse penalties, e.g.,
tree/graph Lasso, fused Lasso.

## Appendix A.

In this appendix, we give the detailed derivation of the dual problem of
Lasso.

### A1. Dual Formulation

Assuming the data matrix is ${\bf X}\in\mathbb{R}^{N\times p}$, the standard
Lasso problem is given by:

$\inf_{\beta\in\mathbb{R}^{p}}\frac{1}{2}\|{\bf
y-X\beta}\|_{2}^{2}+\lambda\|{\beta}\|_{1}.$ (75)

For completeness, we give a detailed deviation of the dual formulation of (75)
in this section. Note that problem (75) has no constraints. Therefore the dual
problem is trivial and useless. A common trick [8] is to introduce a new set
of variables ${\bf z=y-X\beta}$ such that problem (75) becomes:

$\displaystyle\inf_{\beta}\qquad$ $\displaystyle\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\|{\beta}\|_{1},$ (76) subject to $\displaystyle{\bf
z=y-X\beta}.$

By introducing the dual variables $\eta\in\mathbb{R}^{N}$, we get the
Lagrangian of problem (76):

$L({\beta,{\bf z},\eta})=\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\|{\beta}\|_{1}+\eta^{T}\cdot({\bf y-X\beta-z}).$ (77)

For the Lagrangian, the primal variables are ${\beta}$ and ${\bf z}$. And the
dual function $g(\eta)$ is:

$\displaystyle g(\eta)=\inf_{\beta,{\bf z}}L({\beta,{\bf
z},\eta})=\eta^{T}{\bf y}+\inf_{\beta}(-\eta^{T}{\bf
X\beta}+\lambda\|{\beta}\|_{1})+\inf_{\bf z}\big{(}\frac{1}{2}\|{\bf
z}\|_{2}^{2}-\eta^{T}{\bf z}\big{)}.$ (78)

In order to get $g(\eta)$, we need to solve the following two optimization
problems.

$\inf_{\beta}-\eta^{T}{\bf X\beta}+\lambda\|{\beta}\|_{1},$ (79)

and

$\inf_{\bf z}\frac{1}{2}\|{\bf z}\|_{2}^{2}-\eta^{T}{\bf z}.$ (80)

Let us first consider problem (79). Denote the objective function of problem
(79) as

$f_{1}({\beta})=-\eta^{T}{\bf X\beta}+\lambda\|{\beta}\|_{1}.$ (81)

$f_{1}(\beta)$ is convex but not smooth. Therefore let us consider its
subgradient

$\partial f_{1}({\beta})=-{\bf X}^{T}\eta+\lambda{\bf v},$

in which $\|{\bf v}\|_{\infty}\leq 1$ and ${\bf v^{T}\beta}=\|{\beta}\|_{1}$,
i.e., ${\bf v}$ is the subgradient of $\|\beta\|_{1}$.

The necessary condition for $f_{1}$ to attain an optimum is

$\exists\,{\beta}^{\prime},\mbox{ such that }0\in\partial
f_{1}({\beta}^{\prime})=\\{-{\bf X}^{T}\eta+\lambda{\bf v}^{\prime}\\},$

where ${\bf v}^{\prime}\in\partial\|\beta^{\prime}\|_{1}$. In other words,
${\beta^{\prime},{\bf v}^{\prime}}$ should satisfy

${\bf v^{\prime}}=\frac{{\bf X}^{T}\eta}{\lambda},\|{\bf
v}^{\prime}\|_{\infty}\leq 1,{\bf
v^{\prime}}^{T}{\beta}^{\prime}=\|{\beta}^{\prime}\|_{1},$

which is equivalent to

$|{\bf x}_{i}^{T}\eta|\leq\lambda,i=1,2,\ldots,p.$ (82)

Then we plug ${\bf v^{\prime}}=\frac{{\bf X}^{T}\eta}{\lambda}$ and ${\bf
v^{\prime}}^{T}{\beta}^{\prime}=\|{\beta}^{\prime}\|_{1}$ into Eq. (81):

$f_{1}({\beta}^{\prime})=\inf_{\beta}f_{1}({\beta})=-\eta^{T}{\bf
X}{\beta}^{\prime}+\lambda\big{(}\frac{{\bf
X}^{T}\eta}{\lambda}\big{)}^{T}{\beta}^{\prime}=0.$ (83)

Therefore, the optimum value of problem (79) is $0$.

Next, let us consider problem (80). Denote the objective function of problem
(80) as $f_{2}({\bf z})$. Let us rewrite $f_{2}({\bf z})$ as:

$f_{2}({\bf z})=\frac{1}{2}(\|{\bf z}-\eta\|_{2}^{2}-\|\eta\|_{2}^{2}).$ (84)

Clearly,

${\bf z}^{\prime}=\mathop{\operatorname*{argmin}}_{\bf z}f_{2}({\bf z})=\eta,$

and

$\inf_{\bf z}f_{2}({\bf z})=-\frac{1}{2}\|\eta\|_{2}^{2}.$

Combining everything above, we get the dual problem:

$\displaystyle\sup_{\eta}\quad$ $\displaystyle g(\eta)=\eta^{T}{\bf
y}-\frac{1}{2}\|\eta\|_{2}^{2},$ (85) subject to $\displaystyle|{\bf
x}_{i}^{T}\eta|\leq\lambda,\,i=1,2,\ldots,p.$

which is equivalent to

$\displaystyle\sup_{\eta}\quad$ $\displaystyle g(\eta)=\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{1}{2}\|\eta-{\bf y}\|_{2}^{2},$ (86) subject to
$\displaystyle|{\bf x}_{i}^{T}\eta|\leq\lambda,\,i=1,2,\ldots,p.$

By a simple re-scaling of the dual variables $\eta$, i.e., let
$\theta=\frac{\eta}{\lambda}$, problem (86) transforms to:

$\displaystyle\sup_{\theta}\quad$ $\displaystyle g(\theta)=\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{\lambda^{2}}{2}\|\theta-\frac{{\bf y}}{\lambda}\|_{2}^{2},$
(87) subject to $\displaystyle|{\bf x}_{i}^{T}\theta|\leq 1,\,i=1,2,\ldots,p.$

### A2. The KKT Conditions

Problem (76) is clearly convex and its constraints are all affine. By Slater’s
condition, as long as problem (76) is feasible we will have strong duality.
Denote ${\beta}^{\ast}$, ${\bf z}^{\ast}$ and $\theta^{\ast}$ as optimal
primal and dual variables. The Lagrangian is

$L({\beta,{\bf z},\theta})=\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\|{\beta}\|_{1}+\lambda\theta^{T}\cdot({\bf y-X\beta-z}).$
(88)

From the KKT condition, we have

$0\in\partial_{\beta}L({\beta}^{\ast},{\bf
z}^{\ast},\theta^{\ast})=-\lambda{\bf X}^{T}\theta^{\ast}+\lambda{\bf
v},\mbox{ in which }\|{\bf v}\|_{\infty}\leq 1\mbox{ and }{\bf
v}^{T}{\beta}^{\ast}=\|{\beta}^{\ast}\|_{1},$ (89)

$\nabla_{\bf z}L({\beta}^{\ast},{\bf z}^{\ast},\theta^{\ast})={\bf
z}^{\ast}-\lambda\theta^{\ast}=0,$ (90)

$\nabla_{\theta}L({\beta}^{\ast},{\bf z}^{\ast},\theta^{\ast})=\lambda({\bf
y}-{\bf X}{\beta}^{\ast}-{\bf z}^{\ast})=0.$ (91)

From Eq. (90) and (91), we have:

${\bf y}={\bf X}{\beta}^{\ast}+\lambda\theta^{\ast}.$ (92)

From Eq. (89), we know there exists ${\bf
v}^{\ast}\in\partial\|\beta^{\ast}\|_{1}$ such that

${\bf X}^{T}\theta^{\ast}={\bf v}^{\ast},\,\|{\bf v}^{\ast}\|_{\infty}\leq
1\mbox{ and }({\bf v^{\ast}})^{T}{\beta}^{\ast}=\|{\beta}^{\ast}\|_{1},$

which is equivalent to

$|{\bf x}_{i}^{T}\theta^{\ast}|\leq 1,i=1,2,\ldots,p,\mbox{ and
}(\theta^{\ast})^{T}{\bf X}{\beta}^{\ast}=\|{\beta}^{\ast}\|_{1}.$ (93)

From Eq. (93), it is easy to conclude:

$(\theta^{\ast})^{T}{\bf
x}_{i}\in\begin{cases}{\operatorname*{sign}(\beta^{*}_{i})}\mbox{ if
}\beta_{i}^{\ast}\neq 0,\\\ [-1,1]\hskip 9.95845pt\mbox{ if
}\beta_{i}^{\ast}=0.\\\ \end{cases}$ (94)

## Appendix B.

In this appendix, we present the detailed derivation of the dual problem of
group Lasso.

### B1. Dual Formulation

Assuming the data matrix is ${\bf X}_{g}\in\mathbb{R}^{N\times n_{g}}$ and
$p=\sum_{g=1}^{G}n_{g}$, the group Lasso problem is given by:

$\inf_{\beta\in\mathbb{R}^{p}}\frac{1}{2}\|{\bf y}-\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}\|_{2}^{2}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2}.$
(95)

Let ${\bf z}={\bf y}-\sum_{g=1}^{G}{\bf X}_{g}\beta_{g}$ and problem (95)
becomes:

$\displaystyle\inf_{\beta}\qquad$ $\displaystyle\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2},$ (96) subject
to $\displaystyle{\bf z}={\bf y}-\sum_{g=1}^{G}{\bf X}_{g}\beta_{g}.$

By introducing the dual variables $\eta\in\mathbb{R}^{N}$, the Lagrangian of
problem (96) is:

$L({\beta,{\bf z},\eta})=\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2}+\eta^{T}\cdot({\bf
y}-\sum_{g=1}^{G}{\bf X}_{g}\beta_{g}-{\bf z}).$ (97)

and the dual function $g(\eta)$ is:

$\displaystyle g(\eta)=\inf_{\beta,{\bf z}}L({\beta,{\bf
z},\eta})=\eta^{T}{\bf y}+\inf_{\beta}\bigg{(}-\eta^{T}\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2}\bigg{)}+\inf_{\bf
z}\big{(}\frac{1}{2}\|{\bf z}\|_{2}^{2}-\eta^{T}{\bf z}\big{)}.$ (98)

In order to get $g(\eta)$, let us solve the following two optimization
problems.

$\inf_{\beta}-\eta^{T}\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2},$ (99)

and

$\inf_{\bf z}\frac{1}{2}\|{\bf z}\|_{2}^{2}-\eta^{T}{\bf z}.$ (100)

Let us first consider problem (99). Denote the objective function of problem
(99) as

$\displaystyle\hat{f}({\beta})=-\eta^{T}\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2},$ (101)

Let

$\hat{f}_{g}(\beta_{g})=-\eta^{T}{\bf
X}_{g}\beta_{g}+\lambda\sqrt{n_{g}}\|\beta_{g}\|_{2},\qquad g=1,2,\ldots,G.$

then we can split problem (99) into a set of subproblems. Clearly
$\hat{f}_{g}(\beta_{g})$ is convex but not smooth because it has a singular
point at $0$. Consider the subgradient of $\hat{f}_{g}$,

$\partial\hat{f}_{g}({\beta}_{g})=-{\bf X}_{g}^{T}\eta+\lambda\sqrt{n_{g}}{\bf
v}_{g},\qquad g=1,2,\ldots,G,$

where ${\bf v}_{g}$ is the subgradient of $\|\beta_{g}\|_{2}$:

${\bf
v}_{g}\in\begin{cases}\frac{\beta_{g}}{\|\beta_{g}\|_{2}}\qquad\qquad\mbox{ if
}\beta_{g}\neq 0,\\\ {\bf u},\,\|{\bf u}\|_{2}\leq 1\quad\mbox{ if
}\beta_{g}=0.\\\ \end{cases}$ (102)

Let $\beta_{g}^{\prime}$ be the optimal solution of $\hat{f}_{g}$, then
$\beta_{g}^{\prime}$ satisfy

$\exists{\bf v}_{g}^{\prime}\in\partial\|\beta_{g}^{\prime}\|_{2},\quad-{\bf
X}_{g}^{T}\eta+\lambda\sqrt{n_{g}}{\bf v}_{g}^{\prime}=0.$

If $\beta_{g}^{\prime}=0$, clearly, $\hat{f}_{g}(\beta_{g}^{\prime})=0$.
Otherwise, since $\lambda\sqrt{n_{g}}{\bf v}_{g}^{\prime}={\bf X}_{g}^{T}\eta$
and ${\bf
v}_{g}^{\prime}=\frac{\beta_{g}^{\prime}}{\|\beta_{g}^{\prime}\|_{2}}$, we
have

$\hat{f}_{g}(\beta_{g}^{\prime})=-\lambda\sqrt{n_{g}}\frac{(\beta_{g}^{\prime})^{T}}{\|\beta_{g}^{\prime}\|_{2}}\beta_{g}^{\prime}+\lambda\sqrt{n_{g}}\|\beta_{g}^{\prime}\|_{2}=0.$

All together, we can conclude the

$\inf_{\beta_{g}}\hat{f}_{g}(\beta_{g})=0,\quad g=1,2,\ldots,G$

and thus

$\inf_{\beta}\hat{f}(\beta)=\inf_{\beta}\sum_{g=1}^{G}\hat{f}_{g}(\beta_{g})=\sum_{g=1}^{G}\inf_{\beta_{g}}\hat{f}_{g}(\beta_{g})=0.$

The second equality is due to the fact that $\beta_{g}$’s are independent.

Note, from Eq. (102), it is easy to see $\|{\bf v}_{g}\|_{2}\leq 1$. Since
$\lambda\sqrt{n_{g}}{\bf v}_{g}^{\prime}={\bf X}_{g}^{T}\eta$, we get a
constraint on $\eta$, i.e., $\eta$ should satisfy:

$\|{\bf X}_{g}^{T}\eta\|_{2}\leq\lambda\sqrt{n_{g}},\qquad g=1,2,\ldots,G.$

Next, let us consider problem (100). Since problem (100) is exactly the same
as problem (80), we conclude:

${\bf z}^{\prime}=\mathop{\operatorname*{argmin}}_{\bf z}\frac{1}{2}\|{\bf
z}\|_{2}^{2}-\eta^{T}{\bf z}=\eta,$

and

$\inf_{\bf z}\frac{1}{2}\|{\bf z}\|_{2}^{2}-\eta^{T}{\bf
z}=-\frac{1}{2}\|\eta\|_{2}^{2}.$

Therefore the dual function $g(\eta)$ is:

$g(\eta)=\eta^{T}{\bf y}-\frac{1}{2}\|\eta\|_{2}^{2}.$

Combining everything above, we get the dual formulation of the group Lasso:

$\displaystyle\sup_{\eta}\quad$ $\displaystyle g(\eta)=\eta^{T}{\bf
y}-\frac{1}{2}\|\eta\|_{2}^{2},$ (103) subject to $\displaystyle\|{\bf
X}_{g}^{T}\eta\|_{2}\leq\lambda\sqrt{n_{g}},\,g=1,2,\ldots,G.$

which is equivalent to

$\displaystyle\sup_{\eta}\quad$ $\displaystyle g(\eta)=\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{1}{2}\|\eta-{\bf y}\|_{2}^{2},$ (104) subject to
$\displaystyle\|{\bf
X}_{g}^{T}\eta\|_{2}\leq\lambda\sqrt{n_{g}},\,g=1,2,\ldots,G.$

By a simple re-scaling of the dual variables $\eta$, i.e., let
$\theta=\frac{\eta}{\lambda}$, problem (104) transforms to:

$\displaystyle\sup_{\theta}\quad$ $\displaystyle g(\theta)=\frac{1}{2}\|{\bf
y}\|_{2}^{2}-\frac{\lambda^{2}}{2}\|\theta-\frac{{\bf y}}{\lambda}\|_{2}^{2},$
(105) subject to $\displaystyle\|{\bf
X}_{g}^{T}\theta\|_{2}\leq\sqrt{n_{g}},\,g=1,2,\ldots,G.$

### B2. The KKT Conditions

Clearly, problem (96) is convex and its constraints are all affine. By
Slater’s condition, as long as problem (96) is feasible we will have strong
duality. Denote ${\beta}^{\ast}$, ${\bf z}^{\ast}$ and $\theta^{\ast}$ as
optimal primal and dual variables. The Lagrangian is

$L({\beta,{\bf z},\theta})=\frac{1}{2}\|{\bf
z}\|_{2}^{2}+\lambda\sum_{g=1}^{G}\sqrt{n_{g}}\|\beta_{g}\|_{2}+\lambda\theta^{T}\cdot({\bf
y}-\sum_{g=1}^{G}{\bf X}_{g}\beta_{g}-{\bf z}).$ (106)

From the KKT condition, we have

$0\in\partial_{\beta_{g}}L({\beta}^{\ast},{\bf
z}^{\ast},\theta^{\ast})=-\lambda{\bf
X}_{g}^{T}\theta^{\ast}+\lambda\sqrt{n_{g}}{\bf v}_{g},\mbox{ in which }{\bf
v}_{g}\in\partial\|\beta_{g}^{\ast}\|_{2},\quad g=1,2,\ldots,G,$ (107)

$\nabla_{\bf z}L({\beta}^{\ast},{\bf z}^{\ast},\theta^{\ast})={\bf
z}^{\ast}-\lambda\theta^{\ast}=0,$ (108)

$\nabla_{\theta}L({\beta}^{\ast},{\bf
z}^{\ast},\theta^{\ast})=\lambda\cdot({\bf y}-\sum_{g=1}^{G}{\bf
X}_{g}\beta_{g}^{\ast}-{\bf z}^{\ast})=0.$ (109)

From Eq. (108) and (109), we have:

${\bf y}=\sum_{g=1}^{G}{\bf X}_{g}\beta_{g}^{\ast}+\lambda\theta^{\ast}.$
(110)

From Eq. (107), we know there exists ${\bf
v}_{g}^{\prime}\in\partial\|\beta_{g}^{\ast}\|_{2}$ such that

${\bf X}_{g}^{T}\theta^{\ast}=\sqrt{n_{g}}{\bf v}_{g}^{\prime}$

and

${\bf
v}_{g}^{\prime}\in\begin{cases}\frac{\beta_{g}^{\ast}}{\|\beta_{g}^{\ast}\|_{2}}\qquad\qquad\mbox{
if }\beta_{g}^{\ast}\neq 0,\\\ {\bf u},\,\|{\bf u}\|_{2}\leq 1\quad\mbox{ if
}\beta_{g}^{\ast}=0,\\\ \end{cases}$

Then the following holds:

${\bf
X}_{g}^{T}\theta^{\ast}\in\begin{cases}\sqrt{n_{g}}\frac{\beta_{g}^{\ast}}{\|\beta_{g}^{\ast}\|_{2}}\hskip
29.87538pt\mbox{ if }\beta_{g}^{\ast}\neq 0,\\\ \sqrt{n_{g}}{\bf u},\,\|{\bf
u}\|_{2}\leq 1\mbox{ if }\beta_{g}^{\ast}=0,\\\ \end{cases}$ (111)

for $g=1,2,\ldots,G$. Clearly, if $\|{\bf
X}_{g}^{T}\theta^{\ast}\|_{2}<\sqrt{n_{g}}$, we can conclude
$\beta_{g}^{\ast}=0$.

## References

  * Alon et al. [1999] U. Alon, N. Barkai, D. Notterman, K. Gish, S. Ybarra, D. Mack, and A. Levine.  Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays.  _Cell Biology_ , 96:6745–6750, 1999.
  * Armstrong et al. [2002] S. Armstrong, J. Staunton, L. Silverman, R. Pieters, M. den Boer, M. Minden, S. Sallan, E. Lander, T. Golub, and S. Korsmeyer.  MLL translocations specify a distinct gene expression profile that distinguishes a unique leukemia.  _Nature Genetics_ , 30:41–47, 2002.
  * Bauschke and Combettes [2011] H. H. Bauschke and P. L. Combettes.  _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_.  Springer, 2011.
  * Becker et al. [2010] S. R. Becker, E. Cand$\mathrm{\grave{e}}$s, and M. Grant.  Templates for convex cone problems with applications to sparse signal recovery.  Technical report, Standford University, 2010.
  * Bertsekas [2003] D. P. Bertsekas.  _Convex Analysis and Optimization_.  Athena Scientific, 2003.
  * Bhattacharjee et al. [2001] A. Bhattacharjee, W. Richards, J. Staunton, C. Li, S. Monti, P. Vasa, C. Ladd, J. Beheshti, R. Bueno, M. Gillette, M. Loda, G. Weber, E. Mark, E. Lander, W. Wong, B. Johnson, T. Golub, D. Sugarbaker, and M. Meyerson.  Classification of human lung carcinomas by mrna expression profiling reveals distinct adenocarcinoma subclasses.  _Proceedings of the National Academy of Sciences_ , 98:13790–13795, 2001.
  * Bondell and Reich [2008] H. Bondell and B. Reich.  Simultaneous regression shrinkage, variable selection and clustering of predictors with OSCAR.  _Biometrics_ , 64:115–123, 2008.
  * Boyd and Vandenberghe [2004] S. Boyd and L. Vandenberghe.  _Convex Optimization_.  Cambridge University Press, 2004.
  * Bruckstein et al. [2009] A. Bruckstein, D. Donoho, and M. Elad.  From sparse solutions of systems of equations to sparse modeling of signals and images.  _SIAM Review_ , 51:34–81, 2009.
  * Cai et al. [2007] D. Cai, X. He, and J. Han.  Efficient kernel discriminant analysis via spectral regression.  In _ICDM_ , 2007.
  * Cai et al. [2011] D. Cai, X. He, J. Han, and T. Huang.  Graph regularized non-negative matrix factorization for data representation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 33:1548–1560, 2011.
  * Candès [2006] E. Candès.  Compressive sampling.  In _Proceedings of the International Congress of Mathematics_ , 2006\.
  * Chen et al. [2001] S. S. Chen, D. L. Donoho, and M. A. Saunders.  Atomic decomposition by basis pursuit.  _SIAM Review_ , 43:129–159, 2001.
  * Donoho and Tsaig [2008] D. L. Donoho and Y. Tsaig.  Fast solution of l-1 norm minimization problems when the solution may be sparse.  _IEEE Transactions on Information Theory_ , 54:4789–4812, 2008.
  * Efron et al. [2004] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani.  Least angle regression.  _Annals of Statistics_ , 32:407–499, 2004.
  * El Ghaoui et al. [2012] L. El Ghaoui, V. Viallon, and T. Rabbani.  Safe feature elimination in sparse supervised learning.  _Pacific Journal of Optimization_ , 8:667–698, 2012.
  * Fan and Lv [2008] J. Fan and J. Lv.  Sure independence screening for ultrahigh dimensional feature spaces.  _Journal of the Royal Statistical Society Series B_ , 70:849–911, 2008.
  * Friedman et al. [2007] J. Friedman, T. Hastie, H. H$\mathrm{\ddot{e}}$fling, and R. Tibshirani.  Pathwise coordinate optimization.  _Annals of Applied Statistics_ , 1:302–332, 2007.
  * Friedman et al. [2010] J. Friedman, T. Hastie, and R. Tibshirani.  Regularization paths for generalized linear models via coordinate descent.  _Journal of Statistical Software_ , 33:1–22, 2010.
  * Kim et al. [2007] S. J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky.  An interior-point method for large scale l1-regularized least squares.  _IEEE Journal on Selected Topics in Signal Processing_ , 1:606–617, 2007.
  * Lecun et al. [1998] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  In _Proceedings of the IEEE_ , 1998.
  * Liu et al. [2009] J. Liu, S. Ji, and J. Ye.  _SLEP: Sparse Learning with Efficient Projections_.  Arizona State University, 2009.
  * Mairal et al. [2010] J. Mairal, F. Bach, J. Ponce, and G. Sapiro.  Online learning for matrix factorization and sparse coding.  _Journal of Machine Learning Research_ , 11:19–60, 2010\.
  * Nene et al. [1996] S. Nene, S. Nayar, and H. Murase.  Columbia object image library (coil-100).  Technical report, CUCS-006-96, Columbia University, 1996.
  * Netzer et al. [2001] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Ng.  Reading digits in nature images with unsupervised feature learning.  In _NIPS Workshop on Deep Learning and Unsupervised Feature Learning_ , 2001.
  * Park and Hastie [2007] M. Y. Park and T. Hastie.  L1-regularized path algorithm for generalized linear models.  _Journal of the Royal Statistical Society Series B_ , 69:659–677, 2007.
  * Petricoin et al. [2002] E. Petricoin, D. Ornstein, C. Paweletz, A. Ardekani, P. Hackett, B. Hitt, A. Velassco, C. Trucco, L. Wiegand, K. Wood, C. Simone, P. Levine, W. Linehan, M. Emmert-Buck, S. Steinberg, E. Kohn, and L. Liotta.  Serum proteomic patterns for detection of prostate cancer.  _Journal of National Cancer Institute_ , 94:1576–1578, 2002\.
  * Ruszczyński [2006] A. Ruszczyński.  _Nonlinear Optimization_.  Princeton University Press, 2006.
  * Shevade and Keerthi [2003] S. Shevade and S. Keerthi.  A simple and efficient algorithm for gene selection using sparse logistic regression.  _Bioinformatics_ , 19:2246–2253, 2003.
  * Sim et al. [2003] T. Sim, B. Baker, and M. Bsat.  The CMU pose, illumination, and expression database.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 25:1615–1618, 2003.
  * Tibshirani [1996] R. Tibshirani.  Regression shringkage and selection via the lasso.  _Journal of the Royal Statistical Society Series B_ , 58:267–288, 1996.
  * Tibshirani et al. [2012] R. Tibshirani, J. Bien, J. Friedman, T. Hastie, N. Simon, J. Taylor, and R. Tibshirani.  Strong rules for discarding predictors in lasso-type problems.  _Journal of the Royal Statistical Society Series B_ , 74:245–266, 2012.
  * West et al. [2001] M. West, C. Blanchette, H. Dressman, E. Huang, S. Ishida, R. Spang, H. Zuzan, J. Olson, J. Marks, and J. Nevins.  Predicting the clinical status of human breast cancer by using gene expression profiles.  _Proceedings of the National Academy of Sciences_ , 98:11462–11467, 2001.
  * Wright et al. [2010] J. Wright, Y. Ma, J. Mairal, G. Sapiro, T. Huang, and S. Yan.  Sparse representation for computer vision and pattern recognition.  In _Proceedings of IEEE_ , 2010.
  * Xiang and Ramadge [2012] Z. J. Xiang and P. J. Ramadge.  Fast lasso screening tests based on correlations.  In _IEEE ICASSP_ , 2012.
  * Xiang et al. [2011] Z. J. Xiang, H. Xu, and P. J. Ramadge.  Learning sparse representation of high dimensional data on large scale dictionaries.  In _NIPS_ , 2011.
  * Yuan and Lin [2006] M. Yuan and Y. Lin.  Model selection and estimation in regression with grouped variables.  _Journal of the Royal Statistical Society Series B_ , 68:49–67, 2006.
  * Zhao and Yu [2006] P. Zhao and B. Yu.  On model selection consistency of lasso.  _Journal of Machine Learning Research_ , 7:2541–2563, 2006\.
  * Zou and Hastie [2005] H. Zou and T. Hastie.  Regularization and variable selection via the elastic net.  _Journal of the Royal Statistical Society Series B_ , 67:301–320, 2005.