arXiv:1712.09941v1 [] 28 Dec 2017

Sorted Concave Penalized Regression
Long Feng
Department of Biostatistics, Yale University
and
Cun-Hui Zhang∗
Department of Statistics and Biostatistics, Rutgers University

Abstract
The Lasso is biased. Concave penalized least squares estimation
(PLSE) takes advantage of signal strength to reduce this bias, leading
to sharper error bounds in prediction, coefficient estimation and
variable selection. For prediction and estimation, the bias of the
Lasso can be also reduced by taking a smaller penalty level than
what selection consistency requires, but such smaller penalty level
depends on the sparsity of the true coefficient vector. The sorted
`1 penalized estimation (Slope) was proposed for adaptation to such
smaller penalty levels. However, the advantages of concave PLSE
and Slope do not subsume each other. We propose sorted concave
penalized estimation to combine the advantages of concave and sorted
penalizations. We prove that sorted concave penalties adaptively
choose the smaller penalty level and at the same time benefits from
signal strength, especially when a significant proportion of signals are
stronger than the corresponding adaptively selected penalty levels.
A local convex approximation, which extends the local linear and
quadratic approximations to sorted concave penalties, is developed
to facilitate the computation of sorted concave PLSE and proven to
possess desired prediction and estimation error bounds. We carry out
a unified treatment of penalty functions in a general optimization
setting, including the penalty levels and concavity of the above
mentioned sorted penalties and mixed penalties motivated by Bayesian
considerations. Our analysis of prediction and estimation errors
requires the restricted eigenvalue condition on the design, not beyond,
and provides selection consistency under a required minimum signal
strength condition in addition. Thus, our results also sharpens existing
∗

Research partially supported by NSF Grants IIS-1407939, DMS-1513378, DMS1721495, IIS-1741390 and National Institute on Drug Abuse Grant R01 DA016750.

1

results on concave PLSE by removing the upper sparse eigenvalue
component of the sparse Riesz condition.
Keywords: Penalized least squares, sorted penalties, concave penalties, slope,
local convex approximation, restricted eigenvalue, minimax rate, strong signal
AMS 2000 subject classifications. Primary 62J05, 62J07; secondary 62H12.

1

Introduction

The purpose of this paper is twofold. First, we provide a unified treatment
of prediction, coefficient estimation, and variable selection properties of
concave penalized least squares estimation (PLSE) in high-dimensional
linear regression under the restrictive eigenvalue (RE) condition on the
design matrix. Second, we propose sorted concave PLSE to combine
the advantages of concave and sorted penalties, and to prove its superior
theoretical properties and computational feasibility under the RE condition.
Along the way, we study penalty level and concavity of multivariate penalty
functions, including mixed penalties motivated by Bayesian considerations
as well as sorted and separable penalties. Local convex approximation
(LCA) is proposed and studied as a solution for the computation of sorted
concave PLSE.
Consider the linear model
y “ Xβ ˚ ` ε,

(1.1)

where X “ px1 , ..., xp q P Rnˆp is a design matrix, y P Rn is a response
vector, ε P Rn is a noise vector, and β ˚ P Rp is an unknown coefficient
vector. For simplicity, we assume throughout the paper that the design
matrix is column normalized with }xj }22 “ n.
Our study focuses on local and approximate solutions for the
minimization of penalized loss functions of the form
}y ´ Xβ}22 {p2nq ` Penpβq

(1.2)

with a penalty function Penp¨q satisfying certain minimum penalty level and
maximum concavity conditions as described in Section 2. The PLSE can be
viewed as a statistical choice among local minimizers of the penalized loss.
Among PLSE methods, the Lasso [23] with the `1 penalty Penpβq “
λ}β}1 is the most widely used and extensively studied. The Lasso is
relatively easy to compute as it is a convex minimization problem, but it
is well known that the Lasso is biased. A consequence of this bias is the
2

requirement of a neighborhood stability/strong irrepresentable condition on
the design matrix X for the selection consistency of the Lasso [13, 33, 24, 26].
Fan and Li [9] proposed a concave penalty to remove the bias of the
Lasso and proved an oracle property for one of the local minimizers of
the resulting penalized loss. Zhang [29] proposed a path finding algorithm
PLUS for concave PLSE and proved the selection consistency of the PLUScomputed local minimizer under a rate optimal signal strength condition on
the coefficients and the sparse Riesz condition (SRC) [30] on the design. The
SRC, which requires bounds on both the lower and upper sparse eigenvalues
of the Gram matrix and is closely related to the restricted isometry property
(RIP) [7], is substantially weaker than the strong irrepresentable condition.
This advantage of concave PLSE over the Lasso has since become well
understood.
For prediction and coefficient estimation, the existing literature somehow
presents an opposite story. Consider hard sparse coefficient vectors satisfying
|supppβ ˚ q| ď s with logpp{sq — log p and small ps{nq log p. Although rate
minimax error bounds were proved under the RIP and SRC respectively for
the Dantzig selector and Lasso in [6] and [30], Bickel et al. [4] sharpened their
results by weakening the RIP and SRC to the RE condition, and van de Geer
and Bühlmann [25] proved comparable prediction and `1 estimation error
bounds under an even weaker compatibility or `1 RE condition. Meanwhile,
rate minimax error bounds for concave PLSE still require two-sided sparse
eigenvalue conditions like the SRC [29, 32, 27, 10] or a proper known upper
bound for the `1 norm of the true coefficient vector [12]. It turns out that
the difference between the SRC and RE conditions are quite significant as
Rudelson and Zhou [20] proved that the RE condition is a consequence of a
lower sparse eigenvalue condition alone. This seems to suggest a theoretical
advantage of the Lasso, in addition to its relative computational simplicity,
compared with concave PLSE.
Emerging from the above discussion, an interesting question is whether
the RE condition alone on the design matrix is also sufficient for the above
discussed results for concave penalized prediction, coefficient estimation and
variable selection, provided proper conditions on the true coefficient vector
and the noise. An affirmative answer of this question, which we provide in
this paper, amounts to the removal of the upper sparse eigenvalue condition
on the design matrix and actually also a relaxation of the lower sparse
eigenvalue condition or the restricted strong convexity (RSC) condition
[14] imposed in [12]; or equivalently, to the removal of the remaining
analytical advantage of the Lasso as far as error bounds for the afore
mentioned aims are concerned. Specifically, we prove that when the true
3

β is sparse, concave PLSE achieves rate minimaxity in prediction and
coefficient estimation under the RE condition on the design. Furthermore,
the selection consistency of concave PLSE is also guaranteed under the same
RE condition and an additional uniform signal strength condition on the
nonzero coefficients, and these results also cover non-separable multivariate
penalties imposed on the vector β as a whole, including sorted and mixed
penalties such as the spike-and-slab Lasso [19].
In addition to the above conservative prediction and estimation error
bounds for the concave PLSE that are comparable with those for the Lasso
in both rates and regularity conditions on the design, we also prove faster
rates for concave PLSE when the signal is partially strong. For example,
instead of the prediction error rate ps{nq log p in the worst case scenario,
the prediction rate for concave PLSE is actually σ 2 ps ` s1 log pq{n where
s1 is the number of small nonzero signals under the same RE condition on
the design. Thus, concave PLSE adaptively benefits from signal strength
with no harm to the performance in the worst case scenario where all signals
are just below the radar screen. This advantage of concave PLSE is known
under the sparse Riesz and comparable conditions, but not under the RE
condition as presented in this paper.
The bias of the Lasso can be also reduced by taking a smaller penalty
level than those required for variable selection consistency, regardless of
signal strength. In the literature, PLSE isatypically studied in a standard
setting at penalty level λ ě λ˚ “ pσ{ηq p2{nq log p. This lower bound
has been referred to as the universal penalty level. However, as the bias of
the Lasso is proportional to its penalty level, rate minimaxity
in prediction
a
and coefficient estimation requires smaller λ — σ p2{nq logpp{sq [22, 3].
Unfortunately, this smaller penalty level depends on s “ }β ˚ }0 , which is
typically unknown. For the `1 penalty, a remedy for this issue is to apply
the Slope or a Lepski type procedure [21, 3]. However, it is unclear from the
literature whether the same can be done with concave penalties.
We propose a class of sorted concave penalties to combine the advantages
of concave and sorted penalties. This extends the Slope beyond `1 . Under
an RE condition, we prove that the sorted concave PLSE inherits the
benefits of both concave and sorted PLSE, namely bias reduction through
signal strength and adaptation to the smaller penalty level. This provides
prediction and `2 estimation error bounds of the order σ 2 ps ` s1 logpp{sqq{n
and comparable `1 estimation error bounds. Moreover, our results apply to
approximate local solutions which can be viewed as output of computational
algorithms for sorted concave PLSE.
To prove the computational feasibility of our theoretical results in
4

polynomial time, we develop an LCA algorithm for a large class of
multivariate concave PLSE to produce approximate local solutions to which
our theoretical results apply. The LCA is a majorization-minimization
(MM) algorithm and is closely related to the local quadratic approximation
(LQA) [9] and the local linear approximation (LLA) [34] algorithms. The
development of the LCA is needed as the LLA does not majorize sorted
concave penalties in general. Our analysis of the LCA can be viewed as
extension of the results in [32, 11, 14, 1, 27, 12, 10] where separable penalties
are considered, typically at larger penalty levels.
The rest of this paper is organized as follows. In Section 2 we study
penalty level and concavity of general multivariate penalties in a general
optimization setting, including separable, multivariate mixed and sorted
penalties, and also introduce the LCA for sorted penalties. In Section 3, we
develop a unified treatment of prediction, coefficient estimation and variable
selection properties of concave PLSE under the RE condition at penalty
levels required for variable selection consistency. In Section 4 we provide
error bounds for approximate solutions at smaller and sorted penalty levels
and output of LCA algorithms.
Notation: We denote by β ˚ the true regression coefficient vector, Σ “
T
X X{n the sample Gram matrix, S “ supppβ ˚ q the support set of the
coefficient vector, s “ |S| the size of the support, and Φp¨q the standard
Gaussian cumulativeřdistribution function. For vectors v “ pv1 , ..., vp q, we
denote by }v}q “ j p|vj |q q1{q the `q norm, with }v}8 “ maxj |vj | and
}v}0 “ #tj : vj ‰ 0u. Moreover, x` “ maxpx, 0q.

2

Penalty functions

We consider minimization of penalized loss
Lpβq ` Penpβq,

β P IRp ,

(2.1)

with a general Fréchet differentiable loss function Lpβq and a general
multivariate penalty function Penpβq satisfying certain minimum penalty
level and maximum concavity conditions.
Penalty level and concavity of univariate penalty functions are well
understood as we will briefly describe in our discussion of separable penalties
in Subsection 2.2 below. However, for multivariate penalties, we need to
carefully define their penalty level and concavity in terms of sub-differential.
This is done in Subsection 2.1. We then study in separate subsections three
types of penalty functions, namely separable penalties, multivariate mixed
5

penalties, and sorted penalties. Moreover, we develop the LCA for sorted
penalties in Subsection 2.5.

2.1

Sub-differential, penalty level and concavity

The sub-differential of a penalty Penp¨q at a point b P IRp , denoted by
BPenpbq as a subset of IRp , can be defined as follows. A vector g P IRp
belongs BPenpbq iff
(
lim inf t´1 Penpb ` tuq ´ Penpbq ě g T u, @ u P IRp .
(2.2)
tÑ0`

As g T u is continuous in g, BPenpbq is always a closed convex set.
9
Suppose Lpbq is everywhere Fréchet differentiable with derivative Lpbq.
It follows immediately from the definition of the sub-differential in (2.2) that
(
(ı
1”
p
p
p
p
lim inf
Lpβ ` tuq ` Penpβ ` tuq ´ Lpβq ` Penpβq ě 0
tÑ0` t
p P BPenpβq.
p This includes all local minimizers. Let
9 βq
for all u P IRp iff ´Lp
p is a local solution for
9
Penpbq
denote a member of BPenpbq. We say that β
minimizing (2.1) iff the following estimating equation is feasible:
p “ Penp
p
9 βq
9
´Lp
βq.

(2.3)

As (2.3) characterizes all minimizers of the penalized loss when the penalized
loss is convex, it can be viewed as a KarushKuhnTucker (KKT) condition.
We define the penalty level of Penp¨q at a point b P IRp as
”
ı
(
c
λpbq “ sup λ : g S c : g P BPenpbq Ě r´λ, λs|Sb | .
(2.4)
b

This definition is designed to achieve sparsity for solutions of (2.3). Although
λpbq is a function of b in general, it depends solely on Penp¨q for many
commonly used penalty functions. Thus, we may denote λpbq by λ for
notational simplicity. For example, in the case of the `1 penalty Penpbq “
λ}b}1 , (2.4) holds with λpbq “ λ for all b with |Sb | ă p. We consider a
somewhat weaker penalty level for the sorted penalty in Subsection 2.4.
We define the concavity of Penp¨q at b, relative to an oracle/target
coefficient vector β o , as
`
˘
(
o
9
9
κpbq “ κpb, β o q “ sup pβ o ´ bqT Penpbq
´ Penpβ
q {}b ´ β o }22(2.5)
with the convention 0{0 “ 0, where the supreme is taken over all choices
o
9
9
Penpbq
P BPenpbq and Penpβ
q P BPenpβ o q. We use κ “ κpPenq “
6

supb,rb κpb, r
bq to denote the maximum concavity of Penp¨q. For convex
penalties, ´κpb, β o q}b ´ β o }22 is the symmetric Bregman divergence. A
penalty function Penpbq is convex if and only if κ ď 0. Given s ě }β o }0 and
ξ ą 0, we may consider a relaxed concavity of Penp¨q at b as
(
κ1,2 pb; ξq “ inf κ2 pbq ` p1 ` ξq2 s κ1 pbq ,
(2.6)
where infimum is taken over all nonnegative κ1 pbq and κ2 pbq satisfying
`
˘
o
9
9
hT Penpβ
q ´ Penpbq
ď κ1 pbq}h}21 ` κ2 pbq}h}22
(2.7)
9
9
with h “ b ´ β o for all Penpbq
P BPenpbq and Penpb
` hq P BPenpb ` hq.
This notion of concavity is more relaxed than the `2 one in (2.5) because
κ1,2 pb; ξq ď κpbq^κpβ o q always holds due to the option of picking κ1 pbq “ 0.
The relaxed concavity is quite useful in our study of multivariate mixed
penalties in Subsection 2.3. To include more solutions for (2.3) and also
to avoid sometimes tedious task of fully characterizing the sub-differential,
9
we allow Penpbq
to be a member of the following “completion” of the subdifferential,
¯)
!
´Ť
BPenpvq
(2.8)
,
BPenpbq “ convex.hull limtÑ0` closure
}v´b}2 ďt
in the estimating equation (2.3), as long as BPenpbq is replaced by the
same subset in (2.3), (2.4), (2.5), (2.6) and (2.7). However, for notational
simplicity, we may still use BPenpbq to denote BPenpbq. We may also impose
an upper bound condition on the penalty level of Penp¨q:
›
›
(
9
9
› {λpbq : b P IRp , Penpbq
sup ›Penpbq
P
BPenpbq
ď η˚ . (2.9)
8
It is common to have η˚ “ 1 although η˚ ě 1 by (2.4). Without loss of
generality, we impose the condition Penp0q “ 0.

2.2

Separable penalties

In general, separable penalty functions
ř can be written as a sum of penalties
on individual variables, Penpbq “ pj“1 ρj pbj q. We shall focus on separable
penalties of the form
ř
ρpb; λq “ pj“1 ρpbj ; λq,
(2.10)
where ρpt; λq is a parametric family of penalties with the following properties:
(i) ρpt; λq is symmetric, ρpt; λq “ ρp´t; λq with ρp0; λq “ 0;
7

(ii) ρpt; λq is monotone, ρpt1 ; λq ď ρpt2 ; λq for all 0 ď t1 ă t2 ;
(iii) ρpt; λq is left- and right-differentiable in t for all t;
(iv) ρpt; λq has selection property, ρp0`;
9
λq “ λ ě 0;
9
λq| _ |ρpt`;
9
λq| ď λ for all real t,
(v) |ρpt´;
where ρpt˘;
9
λq denote the one-sided derivatives. Condition (iv) guarantees
that the index λ equals to the penalty level defined in (2.4), and condition
(v) bounds the maximum penalty level with η˚ “ 1 in (2.9). We write
ρpt;
9 λq “ x when x is between the left- and right-derivative of ρpt; λq at t,
9 λq “ x means |x| ď λ, so that ρpt;
9 λq is defined
including t “ 0 where ρp0;
in the sense of (2.8). By (2.5), the concavity of ρpt; λq is defined as
(L
9 1 ; λq ´ ρpt;
κpt; ρ, λq “ supt1 ąt ρpt
9 λq pt ´ t1 q,
(2.11)
where the supreme is taken over all possible choices of ρpt;
9 λq and ρpt
9 1 ; λq
between the left- and right-derivatives. Further, define the overall maximum
concavity of ρpt; λq as
κpρq “ maxtě0,λą0 κpt; ρ, λq.

(2.12)

Because ρpb; λq is a sum in (2.10), the closure in (2.8) is the set of all vectors
ρpb;
9 λq “ pρpb
9 1 ; λq, . . . , ρpb
9 p ; λqqT , so that λ gives the penalty level (2.4), and
κpbq “ κpb; ρ, λq ď max κpbj ; ρ, λq
jďp

(2.13)

gives the concavity (2.5) of the multivariate penalty ρpb; λq.
Many popular penalty functions satisfy conditions (i)–(v) above,
including the `1 penalty ρpt; λq “ λ|t| for the Lasso with κpρq “ 0, the
SCAD (smoothly clipped absolute deviation) penalty [9] with
ż |t|
(
ρpt; λq “
λ ´ κpx ´ λq` ` dx
(2.14)
0

and κpρq “ κ, and the MCP (minimax concave penalty) [29] with
ż |t|
ρpt; λq “
pλ ´ κxq` dx

(2.15)

0

and κpρq “ κ. An interesting way of constructing penalty functions is to
mix penalties ρpt; λq with a distribution Gpdλq and a real rn as follows,
”ş
ı
(
ρG ptq “ ´rn´1 log
exp ´ rn ρpt; λq Gpdλq .
(2.16)
8

This class of mixed penalties has a Bayesian
as we discuss
in
( interpretation
(
ş
Subsection 2.3. If we treat exp ´rn ρpt; λq Gpdλq{ exp ´rn ρpt; xq Gpdxq
as conditional density of λ under a joint probability PG , we have
ˇ‰
“
ρ9 G ptq “ EG ρpt;
9 λqˇżt ,
λG “ ρ9 G p0`q “ λGpdλq (penalty level),
(2.17)
ˇ‰
“
9 λqˇt ,
κpρG q ď κpρq ` rn sup VarG ρpt;
t

due to ρp0`;
9
λq “ λ and tρpt
9 1 ; λq ´ ρpt
9 2 ; λqu{pt2 ´ t1 q ď κpρq for all t1 ‰ t2
and λ ą 0. For example, if G puts the entire mass in a two-point set tλ1 , λ2 u,
κpρG q ď κpρq ` rn pλ1 ´ λ2 q2 {4.
In particular, for ρpt; λq “ λ|t|, rn “ n and two-point distributions G, (2.16)
gives the spike-and-slab Lasso penalty as in [19].

2.3

Multivariate mixed penalties

Let πpb|θq be a parametric family of prior density functions for β. When
ε „ N p0, σ 2 I nˆn q with known σ and θ is given, the posterior mode can be
written as the minimizer of
L
}y ´ Xb}22 p2nq ` Penθ pbq
when Penθ pbq “ ´pσ 2 {nq logpπpb|θq{πp0|θqq. In a hierarchical Bayes model
where θ has a prior distribution πpdθq, the posterior mode corresponds to
(
ş
Penpbq “ ´rn´1 log exp ´ rn Penθ pbq νpdθq
(2.18)
ş
with rn “ n{σ 2 and νpdθq “ πp0|θqπpdθq{ πp0|θqπpdθq. This gives rise to
(2.18) as a general way of mixing penalties Penθ p¨q with suitable rn . When
rn “ n{σ 2 , it corresponds
to the posterior
for a proper hierarchical prior if
(
şş
the integration exp ´ rn Penθ pbq νpdθqdb is finite, and an improper one
otherwise. When 0 ă rn ‰ n{σ 2 , itastill has a Bayesian interpretation with
respect to mis-specified
noise level n{rn or sample size σ 2 rn . While rn “ 0
ş
leads to Penpbq “ Penθ pbqνpdθq as the limit at rn “ 0`, the formulation
does not prohibit rn ă 0.
řp
For λ “ pλ1 , . . . , λp qT P r0, 8qp , let ρpb; λq “
j“1 ρpbj ; λj q be
a separable penalty function with different penalty levels for different

9

coefficients bj , where ρpt; λq is a family of penalties indexed by penalty level
λ as discussed in Subsection 2.2. As in (2.18),
(
ş
ρν pbq “ ´rn´1 log exp ´ rn ρpb; λq νpdλq,
(2.19)
ş
with the convention ρν pbq “ ρpb; λqνpdλq for rn “ 0, is a mixed penalty
for any probability measure νpdλq. We study below the sub-differential,
penalty level and concavity of such mixed penalties.
By definition, the sub-differential of (2.19) can be written as
(
"ş
*
ρpb;
9 λq exp ´ rn ρpb; λq νpdλq
(
ş
9 λq P Bρpb; λq(2.20)
Bρν pbq “
: ρpb;
exp ´ rn ρpb; λq νpdλq
9 λq “ pρpb
9 1 ; λ1 q, . . . , ρpb
9 p ; λp qqT ,
with Bρpb; λq being the set of all vectors ρpb;
provided that the lim inf can be taken under the integration over νpdλq. This
9 λq}8 ă 8. As in (2.17), we may write (2.20) as
is allowed when }ρpt;
ˇ ‰
“
(
9 λqˇb : ρ9 j pb; λq “ pρpb
Bρν pbq “ Eν ρpb;
9 1 ; λ1 q, . . . , ρpb
9 p ; λp qqT (2.21)
,
“ ˇ ‰
(
where the conditional Pν dλˇb is proportional to exp ´ rn ρpb; λq νpdλq.
9 λj q may take any value in r´λj , λj s.
We recall that ρp0;
Proposition 1. Let ρν pbq be a mixed penalty in (2.19) generated from a
family of penalties ρpt; λq satisfying conditions (i)–(v) in Subsection 2.2.
Let Sb “ supppbq with sb “ |Sb | ă p. Then, the concavity of ρν pbq satisfies
ˇ ˘˘
`
`
9
λq, ρpu;
9
λqˇu
κpbq ď κpρq ` supu φmax rn Covν ρpu;
(2.22)
with φmax being the largest eigenvalue, and (2.7) holds with
ˇ ˘
`
9 j ; λj qˇu .
κ2 pbq ď κpρq, κ1 pbq ď prn _ 0q supu max1ďjďp Varν ρpu
If the components of λ are independent given θ, then (2.7) holds with
ˇ ‰
“
ˇ
ρpu
9
κ2 pbq ď κpρq ` prn _ 0q supu max1ďjďp `Eν Varp
;
λ
q|u,
θq
j
j
ˇ
“
‰ˇ ˘u .
ˇ
ˇ
9 j ; λj q u, θq u .
κ1 pbq ď prn _ 0q supu max1ďjďp Varν Eν ρpu
If in addition λ is exchangeable under νpdλq, the penalty level of (2.19) is
“ ˇ ‰
λpbq “ E λj ˇb , @ j R Sb .
(2.23)
Interestingly, (2.22) indicates that mixing ρpb; λq with rn ă 0 makes the
penalty more convex.
10

For the non-separable spike-and-slab Lasso [19], the prior is hierarchical
where βj |λ „ prn λj {2qe´|t|rn λj are independent, λj |θ are iid with πpλj “
λ1 |θq “ θ “ 1 ´ πpλj “ λ2 |θq for some given constants λ1ş and λ2 , and
θ „ πpdθq. As πp0|θq “ tprn {2qpθλ1 ` p1 ´ θqλ2 qup and πp0q “ πp0|θqπpdθq,
the penalty can be written as
´1
πpbq
´1
ρν pbq “
log
log
“
rn
πp0q
rn

"

ż
exp

´ rn

p
ÿ

*
λj |bj | νpdλq,

j“1

where λj P tλ1 , λ2 u are iid given θ with νpλj “ λ1 |θq “ θλ1 {tθλ1 ` p1 ´ θqλ2 u
and νpdθq “ πp0|θqπpdθq{πp0q. The penalty level is given by
(
ş
ř
λθ exp ´ rn jPSb ρθ pbj q νpdθq
(
ř
λpbq “ ş
,
exp ´ rn jPSb ρθ pbj q νpdθq
1

2

with ρθ ptq “ tθλ1 e´rn λ |t| ` p1 ´ θqλ2 e´rn λ |t| u{tθλ1 ` p1 ´ θqλ2 u and λθ “
tθpλ1 q2 ` p1 ´ θqpλ2 q2 u{tθλ1 ` p1 ´ θqλ2 u, and the relaxed concavity in (2.6)–
(2.7) are bounded by κ2 pbq “ 0, κ1 pbq ď rn pλ1 ´ λ2 q2 {4.

2.4

Sorted concave penalties

Given a sequence of sorted penalty levels λ1 ě λ2 ě ¨ ¨ ¨ ě λp ě 0, the sorted
`1 penalty [21] is defined as
Penpbq “

řp

#
j“1 λj bj ,

(2.24)

where b#
j is the j-th largest value among |b1 |, . . . , |bp |.
Here we extend the sorted penalty beyond `1 . Given a family of
univariate penalty functions ρpt; λq and a vector λ “ pλ1 , . . . , λp qT with nonincreasing nonnegative elements, we define the associated sorted penalty as
ř
ρ# pb; λq “ pj“1 ρpb#
(2.25)
j ; λj q.
Although (2.25) seems to be a superficial extension of (2.24), it brings upon
potentially significant benefits and its properties are nontrivial. We say that
the sorted penalty is concave if ρpt; λq is concave in t in r0, 8q. In Section 4,
we prove that under an RE condition, the sorted concave penalty inherits
the benefits of both the concave and sorted penalties, namely bias reduction
for strong signal components and adaptation to the penalty level to the
unknown sparsity of β.

11

The following proposition gives penalty level and an upper bound for the
maximum concavity for a broad class sorted concave penalties, including the
sorted SCAD penalty and MCP. In particular, the construction of the sorted
penalty does not increase the maximum concavity in the class.
Proposition 2. Let ρ# pb; λq be as in (2.25) with λ1 ě ¨ ¨ ¨ ě λp ě 0.
ş|t|
9 λqdx with a certain ρpx;
Suppose ρpt; λq “ 0 ρpx;
9 λq non-decreasing in λ
almost everywhere in positive x. Let Sb “ supppbq and sb “ |Sb |. Then, the
sub-differential of ρ# pb; λq includes all vectors g “ ρ9 # pb; λq satisfying
#
9 kj ; λj q, |bk1 | ě ¨ ¨ ¨ ě |bks | ą 0, j ď sb ,
gkj “ ρpb
(2.26)
|gkj | ď λj , tks`1 , . . . , kp u “ Sbc , j ą sb .
Moreover, the maximum concavity of ρ# pb; λq is no greater than that of the
penalty family ρpt; λq:
!
)
hT ρ9 # pb; λq ´ ρ9 # pb ` h; λq ď κpρq}h}22 , @ b, h.
9 λq holds for the `1 , SCAD and MCP.
The monotonicity condition on ρpx;
It follows from (2.26) that the maximum penalty level at each index j P Sbc
is λs`1 . Although the penalty level does not reach λs`1 simultaneously for
all j P Sbc as in (2.4), we still take λs`1 as the penalty level for the sorted
penalty ρ# pb; λq. This is especially reasonable when λj decreases slowly in
j. In Subsection 4.6, we show that this weaker version of the penalty level
is adequate for Gaussian errors provided that for certain A0 ą 1 ą α
a
λj ě λ˚,j “ A0 σ p2{nq logpp{pαjqq, j “ 1, . . . , p.
(2.27)
More important, (2.26) shows sorted penalties automatically pick penalty
level λs`1 from the sequence tλj u without requiring the knowledge of s.
A key element of the proof of Proposition 2 is to write (2.25) as
!ř
)
p
T
ρ# pb; λq “ max
j“1 ρpbj ; λkj q : pk1 , . . . , kp q P permppq ,(2.28)
where permppq is the set of all vectors generated by permuting p1, . . . , pqT

2.5

Local convex approximation

We develop here LCA for penalized optimization (2.1), especially for sorted
penalties. As a majorization-minimization (MM) algorithm, it is closely
related to and in fact very much inspired by the LQA [9] and LLA [34, 32, 11].
12

Suppose for a certain continuously differentiable convex function
Pen´ pbq,
Pen` pbq “ Penpbq ` Pen´ pbq

(2.29)

is convex. The LCA algorithm can be written as
"
*
pnewq
T 9
poldq
b
“ arg min Lpbq ` Pen` pbq ´ b Pen´ pb
q .

(2.30)

b

This LCA is clearly an MM-algorithm: As
9 ´ pbpoldq q
Penpnewq pbq “ Pen` pbq ´ Pen´ pbpoldq q ´ pb ´ bpoldq qT Pen
is a convex majorization of Penpbq with Penpnewq pbpoldq q “ Penpbpoldq q,
Lpbpnewq q ` Penpbpnewq q ď Lpbpnewq q ` Penpnewq pbpnewq q
ď Lpbpoldq q ` Penpnewq pbpoldq q
“ Lpb

poldq

q ` Penpb

poldq

(2.31)

q.

Let ρ# pb; λq be the sorted concave penalty in (2.25) with a penalty
family ρpt; λq and a vector of sorted penalty levels λ “ pλ1 , . . . , λp qT .
9 λq “ pB{Bxqρpx; λq is non-decreasing in λ almost everywhere in
Suppose ρpx;
positive x, so that Proposition 2 applies. Suppose for a certain continuously
differentiable convex function ρ´ ptq
ρ` pt; λj q “ ρpt; λj q ` ρ´ ptq is convex in t for j “ 1, . . . , p. (2.32)
By (2.28), ρ`,# pb; λq “ ρ# pb; λq ` ρ´ pbq, the sorted penalty with ρ` pt; λq,
is convex in b, so that the LCA algorithm for ρ# pb; λq can be written as
(
bpnewq “ arg minb Lpbq ` ρ`,# pb; λq ´ bT ρ9 ´ pbpoldq q , (2.33)
ř
where ρ9 ´ pbq is the gradient of ρ´ pbq “ pj“1 ρ´ pbj q. The simplest version of
LCA takes ρ´ ptq “ t2 κpρq{2 with the maximum concavity defined in (2.12),
but this is not necessary as (2.32) is only required to hold for the given λ.
Figure 1 demonstrates that for p “ 1, the LCA with ρ´ ptq “ t2 κpρq{2
9 poldq |; λqp|b| ´
also majorizes the LLA with Penpnewq pbq “ ρp|bpoldq |; λq ` ρp|b
poldq
|b
|q. With ρ´ ptq “ λ|t| ´ ρpt; λq in (2.32), the LCA is identical
to an
(
pnewq
poldq
poldq
unfolded LLA with Pen
pbq “ λ|b|`tρpb
9
; λq´λ sgnpb
q pb´bpoldq q.
The situation is the same for separable penalties, i.e. λ1 “ λp . However,
the LLA is not feasible for truly sorted concave penalties with λ1 ą λp .
13

6

4

2

Solution

4

3
2
0

0

1

Penalty

−2

−1

0

1

2

3

4

−2

β

0

2

4

6

x

Figure 1:
Local convex approximation (red dashed), local linear
approximation (blue mixed) and original penalty (black solid) for MCP
with λ “ 1 and κ “ 1{3 at bpoldq “ 1.5. Left: penalty
function and its
(
approximations; Right: arg minb px ´ bq2 {2 ` Penpbq .
As the LCA also majorized the LLA, it imposes larger penalty on solutions
with larger step size compared with the LLA, but this has little effect in our
theoretical analysis in Subsections 4.5 and 4.6.
The LCA (2.33) can be computed by proximal gradient algorithms [15,
`
˘T
2, 18], which approximate Lpbq by Lpxq ` b ´ x ∇Lpxq ` }b ´ x}22 {p2tq
around x. For example, the ISTA [2] for LCA can be written as follows.
Algorithm 1: ISTA for LCA
Initialization: b0 “ bpoldq
`
˘
Iteration:
bk`1 “ prox bk ´ t˚ ∇Lpbk q ` t˚ ρ9 ´ pbpoldq q; t˚ ρ`,# p¨; λq
˘
ř
where ρ`,# pb; λq “ pj“1 ρ` pb#
j ; λj q, t˚ is the reciprocal of a Lipschitz
constant for ∇L or determined in the iteration by backtracking, and
`
(
prox x; Penq “ arg minb }b ´ x}22 {2 ` Penpbq
(2.34)
is the so called proximal mapping for convex Pen, e.g. Penpbq “ tρ`,# pb; λq.
We may also apply FISTA [2] as an accelerated version of Algorithm 1.
Algorithm 2: FISTA for LCA
Initialization: x1 “ b0 “ bpoldq , t1 “ 1
`
˘
Iteration:
bk “ prox xk ´ t˚ ∇Lpxk q ` t˚ ρ9 ´ pbpoldq q; t˚ ρ`,# p¨; λq
tk`1 “ t1 ` p1 ` 4t2k q1{2 u{2
xk`1 “ bk ` tptk ´ 1q{tk`1 upbk ´ bk´1 q

14

For sorted penalties ρ# pb; λq, the proximal mapping is not separable but
still preserves the sign and ordering in absolute value of the input. Thus,
after removing the sign and sorting the input and output simultaneously, it
can be solved with the isotonic proximal mapping,
!
)
`
2
iso.prox x; Penq “ arg minb }b ´ x}2 {2 ` Penpbq : bj Ó in j (, 2.35)
ř
with Penpbq “ pj“1 ρpbj ; λj q. Moreover, similar to the computation of the
proximal mapping for the Slope in [5], this isotonic proximal mapping can
be computed by the following algorithm.
`
˘
Algorithm 3: iso.prox x; ρp¨; λq
Input:
λ Ó, x Ó
Compute bj “ arg minb tpxj ´ bq2 {2 ` ρpb; λj qu
While b is not nonincreasing do
Identify blocks of violators of the monotonicity constraint,
bj 1 ´1 ą bj 1 ď bj 1 `1 ď ¨ ¨ ¨ ď bj 2 ą bj 2 `1 , bj 1 ă bj 2
Replace bj , j 1 ď j ď j 2 , with the solution of
ř2
arg minb jj“j 1 tpxj ´ bq2 {2 ` ρpb; λj qu
We formally state the above discussion in the following proposition.
Proposition 3. For v “ pv1 , . . . , vp qT , let v # “ pv1# , . . . , vp# qT with vj#
being the j-th largest among t|v1 |, . . . , |vp |u. For λ1 ě . . . ě λp ě 0, let
ř
řp
ρ# pb; λq “ pj“1 ρpb#
j ; λj q as in (2.25) and ρpb; λq “
j“1 ρpbj ; λj q. Then,
sgnpbj q “ sgnpxj q, |bj | ě |bk | whenever |xj | ą |xk |, and
`
˘
`
˘(#
“ iso.prox x# ; ρp¨; λq .
prox x; ρ# p¨; λq

(2.36)

Moreover, when x1 ě . .`. ě xp ě ˘0 and pxj ´ bq2 {2 ` ρpb; λj q are convex in
b ě 0 for all j, iso.prox x; ρp¨; λq is solved by Algorithm 3.
For the MCP with ρ` pt; λq “ ρpt; λq ` κt2 {2, the univariate solution is
`
prox x; tρ` p¨; λqq “ sgnpxq min p|x| ´ tλq` , |x|{p1 ` tκqu,
which is a combination of the soft threshold and shrinkage estimators.
Figure 2 plots this univariate proximal mapping for a specific pλ, tq.
Algorithm 3 is more explicitly given as follows.

15

6
0

0

1

1

2

3

Solution

4

5

4
3
2

Penalty

0

1

2

3

4

0

β

1

2

3

4

x

ρpt; λq`κt2 {2

Figure 2: ρ` p¨; λq “
for LCA (red dashed), Lasso (blue mixed)
and MCP (black solid) with λ “ 1 and κ “ 1{3. Left: penalties; Right:
proximal mappings
Algorithm 4: iso.proxpx; t ρ` p¨; λqq for the LCA with sorted MCP
Input:
λ Ó, x Ó, t, κ
Compute bj “ min pxj ´ tλj q` , xj {p1 ` tκqu
While b is not nonincreasing do
Identify blocks of violators of the monotonicity constraint,
bj 1 ´1 ą bj 1 ď bj 1 `1 ď ¨ ¨ ¨ ď bj 2 ą bj 2 `1 , bj 1 ă bj 2
Replace bj , j 1 ď j ď j 2 , with common value b satisfying
˘
řj 2 `
j“j 1 xj ´ tλj Itλj ą κbu
b “ řj 2 `
˘
j“j 1 1 ` tκItλj ď κbu
The computation of the isotonic proximal mapping for SCAD can be carried
out in a similar but more complicated fashion, as the region for shrinkage is
broken by an interval for soft thresholding in each coordinate in the domain.

3

Properties of Concave PLSE

In this section, we present our results for concave PLSE at a sufficiently
high penalty level to allow selection consistency. Smaller penalty levels
are considered in Section 4. We divide the section into three subsections
to describe conditions on the design matrix, the collection of PLSE under
consideration, and error bounds for prediction, coefficient estimation and
variable selection.
16

3.1

The restricted eigenvalue condition

We now consider conditions on the design matrix. The RE condition,
proposed in [4], is arguably the weakest available on the design to guarantee
rate minimax performance in prediction and coefficient estimation for the
Lasso. The RE coefficient for the `2 estimation loss can be defined as follows:
For S Ă t1, . . . , pu and ξ ą 0,
#
+
puT Σuq1{2
RE2 pS; ξq “ inf
: }uS c }1 ă ξ}uS }1
(3.1)
}u}2
with inf H “ 0 for S “ H. The RE condition refers to the property
that RE2 pS; ξq is no smaller than a certain positive constant for all design
matrices under consideration. For prediction and `1 estimation, it suffices to
impose a somewhat weaker compatibility condition [25]. The compatibility
coefficient, also called `1 -RE [25], is defined as
#
+
puT Σuq1{2
RE1 pS; ξq “ inf
: }uS c }1 ă ξ}uS }1 .
(3.2)
}uS }1 {|S|1{2
In addition to the RE coefficients above, we define a relaxed cone invertibility
factor (RCIF) for prediction as
"
*
}Σu}28 |S|
T
c
RCIFpred pS; η, wq “ inf
:
p1
´
ηq}u
}
ă
´w
u
(3.3)
S 1
S S ,
uT Σu
with η P r0, 1q and a vector w P Rp , and a RCIF for the `q estimation as
#
+
}Σu}8 |S|1{q
RCIFest,q pS; η, wq “ inf
: p1 ´ ηq}uS c }1 ă ´wTS uS . (3.4)
}u}q
The RCIF is a relaxation of the cone invertibility coefficient [28] for which
the constraint }uS c }1 ă ξ}uS }1 is imposed.
The choices of ξ, η and w depend on the problem under consideration in
the analysis, but typically we have }w}8 ď p1´ηqξ so that the minimization
in (3.3) and (3.4) is taken over a smaller cone. However, }w}2 can be much
smaller than |S|1{2 p1 ´ ηqξ with partial signal strength. Moreover, it is
feasible to have wS “ 0 under a beta-min condition for selection consistency.
In our analysis, we use an RE condition to prove cone membership of the
estimation error of the concave PLSE and the RCIF to bound the prediction
and coefficient estimation errors. The following proposition, which follows
from the analysis in Section 3.2 of [28], shows that the RCIF may provide
sharper bounds than the RE does.
17

Proposition 4. If }wS }8 ď p1 ´ ηqξ, then
RCIFpred pS; η, wq ě RE21 pS; ξq{p1 ` ξq2 ,
RCIFest,1 pS; η, wq ě RE21 pS; ξq{p1 ` ξq2 ,

(3.5)

RCIFest,2 pS; η, wq ě RE1 pS; ξqRE2 pS; ξq{p1 ` ξq.

3.2

Concave PLSE

As discussed in Subsection 2.1, local minimizers of the penalized loss (1.2)
must satisfy the KKT condition
` ˘
p
p
9
X T py ´ X βq{n
β
(3.6)
“ Pen
` ˘
p of the sub-differential BPenpβq.
p We shall treat
9
for a certain member Pen
β
(3.6) as an estimating equation
` ˘to allow somewhat more general solutions,
p in the completion of the sub-differential
9
including solutions with Pen β
p as defined in (2.8). Local solutions of form (3.6) include
BPenpbq at b “ β
p
all estimators β satisfying
#
p
pλ ´ κ˚ |βpj |q` ď sgnpβpj qX Tj py ´ X βq{n
ď λ,
βpj ‰ 0,
(3.7)
T
p
|X j py ´ X βq{n|
ď λ,
βpj “ 0,
as
řpsolutions of (3.7) can be constructed with separable penalties Penpbq “
j“1 ρj pbj ; λq with a common penalty level λ and potentially different
concavity satisfying κpρj q ď κ˚ . Unfortunately, the more explicit (3.7) does
not cover solutions with sorted penalties and some mixed penalties.
We study solutions of (3.6) by comparing them with an oracle coefficient
vector β o . We assume that for a certain sparse subset S of t1, . . . , pu, λ˚ ą 0
and η P r0, 1q, the oracle β o satisfy the following,
supppβ o q Ď S,

}X T py ´ X T β o q{n}8 ă ηλ˚ .

(3.8)

We may take β o P IRp as the true coefficient vector β ˚ with S “ supppβ ˚ q,
p o given by
or the oracle LSE β
p o “ pX T X S q´1 X T y,
β
S
S
S

p o c “ 0.
β
S

(3.9)

When ε “ y ´ Xβ ˚ „ N p0, V q with φmax pV q _ maxjďp xTj V xj {n ď σ 2 ,
y ´ Xβ o „ N p0, V o q with φmax pV o q _ maxjďp xTj V o xj {n ď
(3.10)
σ2

18

for such β o , so that (3.8) holds with at least probability 1 ´
a
λ˚ “ pσ{ηq p2{nq log p.

a
2{pπ log pq for

Our analysis also applies to approximate local solutions satisfying
` ˘
p
p ` ν approx ,
9
X T py ´ X βq{n
“ Pen
β
(3.11)
including approximate solutions of (3.7), with ν approx an approximation
error satisfying βpj pν approx qj ě 0 and a proper upper bound for }ν approx }8 .
For computational efficiency, many algorithms only provide approximate
solutions. In Subsection 4.1, we consider solutions with less restrictive
approximation errors and provide a brief discussion with some references.
Given an oracle β o satisfying (3.8), we consider solutions of (3.11) with
penalties satisfying the following penalty level and concavity conditions:
p ξq ď κ˚ , }wS }8 ď p1 ´ ηqξ,
λpβ o q ě λ˚ , κ1,2 pβ;
where λ˚ is as in (3.8), κ˚ and ξ are positive constants, and
(L
o
9
w “ Penpβ
q ` ν approx ´ X T py ´ Xβ o q{n λpβ o q.

(3.12)

(3.13)

We recall that for any b, λpbq and κ1,2 pb; ξq are the penalty level and relaxed
o
9
concavity of Penp¨q as defined in (2.4) and (2.6) respectively, and Penpβ
q is
o
a member of the sub-differential BPenpβ q in (2.2) or its completion in (2.8).
o
9
The third inequality in (3.12), assumed to hold for all choices of Penpβ
qP
o
BPenpβ q in (3.13), follows from (3.8) and the penalty level condition (2.9)
when ξ satisfies η˚ λpβ o q ` }pν approx qS }8 ` ηλ˚ ď p1 ´ ηqξλpβ o q, but this
may not be sharp.
For separable penalties ρpb; λq in (2.10), λpbq “ λ, κ1,2 pb; ξq ď κpbq ď
κpρq and }wS }8 ď 1 ` η ` }pν approx qS }8 {λ under conditions (i)–(v) and
(3.8). The penalty level and upper bounds for the concavity are given in
(2.17) for univariate mixed penalties like the spike-and-slab Lasso, and in
multivariate mixed penalties in Proposition 1. These facts leads to more
explicit versions of (3.12).
Let Bpλ˚ , κ˚ q be the set of all approximate local solutions satisfying
(3.11) with different types of penalty functions satisfying (3.12); Given β o ,
!
)
p (3.11) holds with some Penp¨q satisfying (3.12)
Bpλ˚ , κ˚ q “ β:
(3.14)
.
Given a penalty satisfying (3.12), Bpλ˚ , κ˚ q contains all local minimizer of
the penalized loss (1.2). Our theory is applicable to the subclass
!
)
p:β
p and 0 are connected in Bpλ˚ , κ˚ q .
B0 pλ˚ , κ˚ q “ β
(3.15)
19

p and 0 are not connected iff there exist disjoint closed sets B0 and
Here β
p P B1 and Bpλ˚ , κ˚ q Ď B0 Y B1 . However,
B1 in IRp such that 0 P B0 , β
this condition will be relaxed in Proposition 5 below.
By definition, B0 pλ˚ , κ˚ q contains the set of all local solutions (3.6)
computable by path following algorithms starting from the origin, with
constraints on the penalty and concavity levels respectively. This is a
large class of statistical solutions as it includes all local solutions connected
to the origin regardless of the specific algorithms used to compute the
solution and different types of penalties can be used in a single solution
path. For example, the Lasso estimator belongs to the class as it is
connected to the origin through the LARS algorithm [16, 17, 8]. The
SCAD and MCP solutions with λ ě λ˚ and κ ď κ˚ belong to the class
if they are computed by the PLUS algorithm [29] or by a continuous path
p “ 0 is the sparsest
following algorithm from the Lasso solution. As β
solution, B0 pλ˚ , κ˚ q can be viewed as the sparse branch of the solution space
Bpλ˚ , κ˚ q. In Proposition 5, we prove that our theory is also applicable to
approximate local solutions (3.11) computable through a discrete solution
path in Bpλ˚ , κ˚ q from 0 with `1 step size of order λ.

3.3

Error bounds

Let Bpλ˚ , κ˚ q be as in (3.14), B(0 pλ˚ , κ˚ q as in (3.15), S Ě supppβ o q, ξ ą 0,
C pS; ξq “ u : }uS c }1 ď ξ}uS }1 and
(
p P Bpλ˚ , κ˚ q : β
p ´ β o P C pS; ξq(3.16)
B0˚ pλ˚ , κ˚ q “ B0 pλ˚ , κ˚ q Y β
.
Here under an RE condition on the design matrix, we provide prediction and
coefficient estimation error bounds for solutions of (3.11) and conditions for
variable selection consistency for solutions of (3.6) in the set (3.16) above.
Theorem 1. Suppose (3.8) holds for certain β o P IRp and RE22 pS; ξq ě κ˚ .
p be a solution of (3.11) in B ˚ pλ˚ , κ˚ q with }Penp
p 8 ď λ. Then,
9
Let β
βq}
0
2

p ´ Xβ o }2 {n ď
}X β
2

2

λ |S|
p1 ` ξq2 λ |S|
ď
, (3.17)
RCIFpred pS; η, wq
RE21 pS; ξq

20

with λ “ λ ` ηλ˚ ` }ν approx }8 and the w in (3.13), and
p ´ β o }1 ď
}β

λ|S|
p1 ` ξq2 λ|S|
,
ď
RCIFest,1 pS; η, wq
RE21 pS; ξq

p ´ β o }2 ď
}β

λ|S|1{2
p1 ` ξqλ|S|1{2
ď
,
RCIFest,2 pS; η, wq
RE1 pS; ξqRE2 pS; ξq

p ´ β o }q ď
}β

λ|S|1{q
,
RCIFest,q pS; η, wq

(3.18)

@q ě 1.

p is a solution satisfying (3.7), then
Moreover, if β
`

˘ `
˘
p ´ Xβ o }2 {n _ λ}β
p ´ β o }1 ď λ2 |S|{RE2 pS; ξq
}X β
2
1

p ´ β o }2 ď λ2 |S|{tRE1 pS; ξqRE2 pS; ξqu.
and }β
2
Compared with Theorem 1, existing results on statistical solutions of
concave PLSE [29, 27, 10] cover only separable penalties of form (2.10),
require stronger conditions on the design (such as upper sparse eigenvalue)
and offer less explicit error bounds. While the error bounds for concave
penalty in Theorem 1 match existing ones for the Lasso [4, 25], they also
hold when RE1 pS; ξq and RE2 pS; ξq in (3.17) and (3.18) are replaced by the
larger version with the constraint }uS c }1 ď ξ}uS }1 replaced by the more
stringent p1 ´ ηq}uS c }1 ď ´wTS uS in their definition, as ´wTS uS could be
much smaller than p1 ´ ηqξ}uS }1 when significant proportion of the signals
are strong. We describe the benefit of concave PLSE over the Lasso in such
scenarios in the following two theorems.
Theorem 2. Suppose (3.8) holds for an oracle solution β o of (3.6) and
p be a solution of (3.6) in B ˚ pλ˚ , κ˚ q. Then,
RE22 pS; ξq ě κ˚ . Let β
0
p ξq ñ β
p “ βo .
φmin pΣS,S q ą κ1,2 pβ;

(3.19)

where φmin p¨q denotes the minimum eigenvalue for symmetric matrices. If
a separable penalty of the form ρpb; λq is taken as in (2.10), then
p c “ 0 and sgnpβpj qsgnpβ o q ě 0 @ j P S,
β
S
j

(3.20)

and under the additional condition κp0; ρ, λq ă φmin pΣS,S q,
p “ sgnpβ o q.
sgnpβq

21

(3.21)

Theorem 2 provides selection consistency of concave PLSE under the
restricted eigenvalue condition, compared with the required irrepresentable
condition for the Lasso [13, 24, 33]. This is also new as existing results
require the stronger sparse Riesz condition [29] or other combination of lower
and upper sparse eigenvalue conditions on the design [31, 27, 10] for selection
consistency. Theorem 2 also extends the selection consistency theory to nonseparable multivariate concave penalties, e.g. non-separable spike-and-slab
Lasso with suitable choice of tuning parameters.
The proof of Theorem 2 unifies the analysis for prediction, estimation
and variable selection, as the proof of selection consistency is simply done by
inspecting the case of wS “ 0 in the prediction and estimation error bounds.
The condition wS “ 0, a consequence of the feasibility of β o as an oracle
solution of (3.6) in general, holds for the oracle LSE (3.9) under the beta-min
condition minjPS |βpjo | ě γλ when the separable penalty (2.10) is used with
ρpt;
9 λq “ 0 for all |t| ě γλ. As RE22 pS; ξq ď φmin pΣS,S q always holds and
p ξq ď κ˚ ď RE2 pS; ξq by (3.12) and the RE condition, the condition
κ1,2 pβ;
2
in (3.19) holds when ΣS,S c ‰ 0 as it implies RE22 pS; ξq ă φmin pΣS,S q.
p
Theorem 3. Suppose (3.8) holds for β o P IRp and κ˚ ď RE22 pS; ξq. Let β
2
p ξq ď p1 ´ 1{C0 qRE pS; ξq. Then,
and λ be as in Theorem 1 with κ1,2 pβ;
2
“ T
‰2
c }1
u
´
p1
´
ηq}u
w
S
S
S
`
p ´ Xβ o }2 {n ď pC0 λq2 sup
}X β
(3.22)
2
T
u Σu
u‰0
with the w in (3.13), and for any seminorm } ¨ } as a loss function
“
‰
}u} wTS uS ´ p1 ´ ηq}uS c }1
o
p
}β ´ β } ď C0 λ sup
.
uT Σu
u‰0

(3.23)

Corollary
1. Suppose conditions of Theorem 3 with λ “ λ˚ “
a
p o being the oracle
pσ{ηq p2{nq log p, C02 {RE22 pS; ξq “ Op1q, and β o “ β
o
9
estimator in (3.9). Let s “ |S| and s1 “ }pPenpβ
q ` ν approx qS {λ}2 . Then,
p ´ Xβ
p o }2 {n ` }β
p ´β
p o }2 ` }β
p ´β
p o }2 {s “ OP pσ 2 {nqs1 log p,
}X β
2
2
1
p“β
p o when s1 “ 0, and for the true β ˚
implying β
p ´ Xβ ˚ }2 {n ` }β
p ´ β ˚ }2 ` } β
p ´ β ˚ }2 {s
}X β
2
1
` 2
˘
2
“ OP pσ {nq s1 log p ` s .

(3.24)

9 λqq Ď r´γλ, γλs,
For ν approx “ 0 and penalties (2.10) with supppρpt;
s1 ď #tj P S : |βpjo | ă λγu,
22

(3.25)

Theorem 3 and Corollary 1 demonstrate the benefits of concave PLSE,
as s1 “ s “ |S| in (3.24) for the Lasso but s1 could be much smaller than
s for concave penalties. For separable concave penalties, (3.25) holds with
γ “ 1 ` 1{κ for the SCAD (2.14) and γ “ 1{κ for the MCP (2.15).
For the exact Lasso solution with κpbq “ 0, C0 “ 1 and }wS }8 ď
1`η, Theorem 3 yields the sharpest possible prediction and estimation error
bounds based on the basic inequality uT Σu ` p1 ´ ηq}uS c }1 ď p1 ` ηq}uS }1
p ´ β o q{λ, as stated in the following corollary.
with u “ pβ
p be the Lasso estimator with penalty level λ ě λ˚ . If
Corollary 2. Let β
(3.8) holds for a coefficient vector β o P IRp , then
p ´ Xβ o }2
}X β
ψ 2 puq
|S|p1 ´ tq2
2
ď sup T
“ max
2
2
0ătă1 RE2
np1 ` ηq λ
u‰0 u Σu
1 pS; tξq
“
‰
with ψpuq “ }uS }1 ´ }uS c }1 {ξ ` and ξ “ p1 ` ηq{p1 ´ ηq,
p ´ β o }2
}β
}u}2 ψpuq
|S|1{2 p1 ´ tq
ď sup
“
max
0ătă1 RE2
p1 ` ηqλ
u‰0 uT Σu
1,2 pS; tξq
with RE1,2 pS; ξq “ inf }uS c ăξ}uS }1 uT Σu{p}u}2 }uS }1 {|S|1{2 q, and
p ´ β o }1
}β
}u}1 ψpuq
|S|1{2 p1 ` tξqp1 ´ tq
.
ď sup
“
max
0ătă1
p1 ` ηqλ
RE21 pS; tξq
u‰0 uT Σu
As Theorems 1–3 deal with the same estimator under the same RE
conditions on the design, they give a unified treatment of the prediction,
coefficient estimation and variable selection performance of the PLSE,
including the `1 and concave penalties. For prediction and coefficient
estimation, (3.17) and (3.18) match those of state-of-art for the Lasso
in both the convergence rate and the regularity condition on the design,
while (3.22), (3.23) and Corollary 1 demonstrate the advantages of concave
penalization when s1 is much smaller than s. Meanwhile, for selection
consistency, Theorem 2 weakens existing conditions on the design to the
same RE condition as required for `2 estimation with the Lasso. These REbased results are significant as the existing theory for concave penalization,
which requires substantially stronger conditions on the design, leaves a
false impression that the Lasso has a technical advantage in prediction and
parameter estimation by requiring much weaker conditions on the design
than the concave PLSE.
The following lemma, which can be viewed as a basic inequality for
analyzing concave PLSE, is the beginning point of our analysis.
23

p a solution of (3.11), h “ β
p ´β o ,
Lemma 1. Let λ “ λpβ o q be as in (2.4), β
(L
o
o
T
9
and w “ Penpβ q ` ν approx ´ X py ´ Xβ q{n λ. Then,
2 ` κ pβq}h}
2
p
p
hT Σh ď ´λhT w ` κ1 pβq}h}
2
1
2

p Moreover, for
for all choices of tκ1 pbq, κ2 pbqu satisfying (2.7) at b “ β.
o
o
o
9
9
S Ě supppβ q and a proper choice of Penpβ
q P B Penpβ
q,
(
hT Σh ` λ ´ }X TS c py ´ Xβ o q{n}8 }hS c }1
(3.26)
T
2
2
p
p
ď ´λh wS ` κ1 pβq}h}
` κ2 pβq}h}
.
S

1

2

Next, we prove that the solutions in B0˚ pλ˚ , κ˚ q in (3.16) and other
approximate local solutions (3.11) in Bpλ˚ , κ˚ q are separated by a gap of
p P B0 pλ˚ , κ˚ q
size a0 λ˚ in the `1 distance for some a0 ą 0. Consequently, β
o
p ´ β P C pS; ξq for the B0 pλ˚ , κ˚ q in (3.15) and C pS; ξq in (3.16).
implies β
Proposition 5. Let κj pbq be as in (2.7), Bpλ˚ , κ˚ q as in (3.14) and C pS; ξq
as in (3.16). Suppose RE22 pS; ξq ě κ˚ . Let a1 “ η ´ }z S c }8 {λ˚ , a2 “
r ` κ2 pβqus
r
a1 ξ{r2pξ ` 1qtκ1 pβq
and a3 “ a1 p1 ´ ηqξ{tp1 ´ ηqpξ ` 1q ` a1 u. Let
p P Bpλ˚ , κ˚ q with penalty level λ, and β
r P Bpλ˚ , κ˚ q with λ.
r Then,
β
›
›
p › ď λa
r 0 imply β
r ´ β o P C pS; ξq,
p ´ β o P C pS; ξq and ›r
β´β
β
1
“
‰
with a0 “ min a2 , a2 a3 {tp1 ´ ηqpξ _ 1qu . Consequently,
(
p P Bpλ˚ , κ˚ q : β
p ´ β o P C pS; ξq .
B0˚ pλ˚ , κ˚ q “ β
It follows from Proposition 5 that our theoretical results are applicable to
statistical choices of approximate local solutions (3.11) computable through
p ptq ´ β
p pt´1q }1 ď a0 λptq and
a discrete path of solutions βpptq satisfying }β
beginning from 0 or the Lasso solution, as t0u and the Lasso solution both
p ´ β o P C pS; ξq.
satisfy the condition β

4

Smaller penalty levels, sorted penalties and
LCA

We have studied in Section 3 exact solutions (3.6) and approximate solutions
(3.11) for no smaller penalty level than λ˚ in the event where λ˚ is a
strict upper bound of the supreme norm of z “ X T py ´ Xβ o q{n as in
(3.8). Such penalty or threshold levels are commonly used in the literature
24

to study regularized methods in high-dimensional regression, but this is
conservative and may yield poor numerical results.
a Under the normality
assumption (3.10), (3.8) requires λ ě λ˚ “ pσ{ηq
p2{nq log p, but the rate
a
optimal penalty level is the smaller λ ě σ p2{nq logpp{sq for prediction
and coefficient estimation with s “ |S|. It is known that for logpp{sq !
log p, rate optimal performance in prediction and coefficient estimation can
be guaranteed by the Lasso with the nonadaptive smaller penalty level
depending on s [22, 3] or the Slope to achieve adaptation in the smaller
penalty level [21, 3]. However, it is unclear from the literature whether
the same can be done with concave penalties to also take advantage of
noise strength, and under what conditions on the design. Moreover, for
computational considerations, it is desirable to relax the condition imposed
in Section 3 on the supreme norm of the approximation error ν approx
in (3.11). In this section, we consider approximate solutions for general
penalties with nonadaptive penalty levels which are allowed to be smaller,
concave slopes, and solutions produced by the LCA algorithm. Our analysis
imposes a somewhat stronger RE condition, but that is the only condition
required on the design matrix.

4.1

Approximate local solutions

As in (3.11), we write
p
p ` ν approx
9
X T py ´ X βq{n
“ Penp
βq

(4.1)

as approximate solution of (3.6), including (3.7) for separable penalties.
However, instead of imposing `8 bounds on the approximation error as
in Section 3, we will impose in this section a more practical `8 -`2 split
bound as in (4.10) below. Solutions of form (4.1) are called approximate
local solutions in [31] where their uniqueness, variable selection properties
and relationship to the global solution were studied. Computational
algorithms for approximate solutions and statistical properties of the
resulting estimators have been considered in [14, 1, 27, 12, 10] among others.
However, these studies of approximate solutions all focus on separable
penalties with penalty level (3.8) or higher.
Let β o be the oracle coefficient vector as in Section 3 and S Ă supppβ o q.
o
p ´ Penpβ
9
9
Let ν div “ Penp
βq
q. It follows from (4.1) that
o
p
9
X T py ´ X βq{n
“ Penpβ
q ` ν div ` ν approx .

With z “ X T py ´ Xβ o q{n, (4.2) leads to the identity
(
o
9
hT Σh “ hT z ´ Penpβ
q ´ hT ν div ´ hT ν approx
25

(4.2)

p ´ β o . While upper bounds for ´hT ν div and ´hT ν approx can be
with h “ β
obtained via the maximum concavity of the penalty and the size restriction
o
9
on ν approx , a favorable choice of the sub-derivative Penpβ
q must be used to
control the noise z. When the penalty function is endowed with a constant
penalty level λ “ λpβ o q on S c as in (2.4) and concavity level as in (2.5),
›
›
2
p
hT Σh ` p1 ´ ηqλ›hS c ›1 ´ κpβq}h}
(4.3)
2
` T
˘
ď hS c z S c ´ ηλ}hS c }1 ´ λhTS wS ´ hT ν approx .
This can be viewed as a basic inequality in our analysis of (4.1). We may
use the relaxed concavity (2.7) as in Lemma 1, but (4.3) provides notational
simplicity for a unified treatment with sorted concave penalties.

4.2

Sorted concave penalized estimation

Approximate solutions for sorted concave penalties are still defined by (4.1),
so that (4.2) also holds. However, as sorted penalties are defined in (2.25)
with a sequence of penalty levels λ1 ě ¨ ¨ ¨ ě λp ě 0, they do not provide
`1 control of the noise as in (4.3). Instead, sorted concave penalties control
the noise through a sorted `1 norm. More precisely, they regularize the
correlation of the noise and design vectors in S c with the norm
ř
#
}b}#,s “ p´s
@ b P IRp´s , s “ |S|,
(4.4)
j“1 pλs`j {λs`1 qbj ,
a standardized dual norm induced by the set of g S c given in (2.26). Here
b#
j is the j-th largest value among |b1 |, . . . , |bp´s |.
o
9
As (4.2) holds, taking the most favorable Penpβ
q and the concavity
bound in Proposition 2 in the derivation of (4.3), we find that
›
›
2
p
hT Σh ` p1 ´ ηqλ›hS c ›#,s ´ κpβq}h}
(4.5)
2
›
› ˘
` T
T
T
ď hS c z S c ´ ηλ›hS c ›#,s ´ λhS wS ´ h ν
o
9
with S Ě supppβ o q, z “ X T py ´ Xβ o q{n, w “ tPenpβ
q ´ zu{λ, ν “
p
ν approx , λ “ λs`1 , and κpβq “ κpρq. This includes (4.3) as a special case,
because }bS c }#,s “ }bS c }1 when λs`1 “ ¨ ¨ ¨ “ λp . More important, (4.5) is
adaptive to the penalty level λs`1 without the knowledge of s.
We outline our analysis of (4.5) as follows. For r ą 0 and γ ą 0, define

∆pr, w, νq “ sup
u‰0

uTS c z S c {λ ´ η}uS c }#,s ´ uTS wS ´ uT ν{λ
a
(
. (4.6)
r max }u}2 , }Xu}2 γ{n
26

We assume that for a certain constant ξ ą 0,
∆pp1 ´ ηqξ|S|1{2 , w, νq ă 1

(4.7)

for all approximate solutions (4.1) under consideration. This and (4.5) yield
›
›
2
p
hT Σh ` p1 ´ ηqλ›hS c ›#,s ´ κpβq}h}
(4.8)
2
a
(
ď p1 ´ ηqξ|S|1{2 λ max }h}2 , }Xh}2 γ{n .
2 ď hT Σh, (4.8) provides the membership of h in the cone
p
When κpβq}h}
2
`
˘(
C# pS; ξ, γq “ u : }uS c }#,s ď ξ|S|1{2 max }u}2 , pγuT Σuq1{2 (. 4.9)

On the other hand, when h P C# pS; ξ, γq, a suitable RE condition provides
2 ď hT Σh. A key step in our analysis is to break this vicious circle,
p
κpβq}h}
2
which will be done in Subsection 4.4.
The seemingly complicated (4.6), which summarizes conditions in our
analysis on the noise vector ε, the penalty level λ and approximation error
ν, is actually not hard to decipher. Consider ν satisfying
uT ν ď η1 λs`1 }uS c }#,s ` r2 λs`1 }u}2 @ u P IRp

(4.10)

with η1 P p0, ηq and r2 ą 0. The above condition on ν is fulfilled when
#
ν “ ν 1 ` ν 2 with ν1,j
ď η1 λj and }ν 2 }2 ` η1 }λ1:s }2 ď λs`1 r2 ,

ř
as this implies uT ν ď η1 pj“1 u#
j λj ` }u}2 }ν 2 }2 ď η1 λs`1 }uS c }#,s `
pη1 }λ1:s }2 ` }ν 2 }2 q}u}2 . Suppose λj are bounded from below, λj ě λ˚,j , 1 ď
j ď p, such as (2.27). Let
∆pr, η, w, r2 q “

" p´s
ÿ
j“1

tzj# ´ ηλ˚,s`j u2
r2 λ2˚,s`1

w2
` 2
r

*1{2
`

r2
.
r

(4.11)

It follows from the monotonicity of (4.11) in λ˚,s`j and some algebra that
∆pr, w, νqI}wS }2 ďw ď ∆pr, η ´ η1 , w, r2 q
when (4.10) holds. In Subsection 4.6, we derive upper bound for the median
of ∆ by combing the arguments in [3, 22], and then apply concentration
inequality to ∆. In the simpler
a case with unsorted smaller penalty, λ “
σL{tn1{2 pη ´ η1 qu with L “ 2 logpp{sq,
!a
)
E ∆pr, η ´ η1 , w, r2 q ď r´1
4spη ´ η1 q2 {pL4 ` 2L2 q ` w2 ` r2
27

“ op1q ` pw ` r2 q{r
by Proposition 10 in [22] under the normality assumption (3.10). Thus, (4.7)
holds with high probability when }wS }8 ď p1 ´ ηqξ 1 with ξ 1 ă ξ, s “ |S|
and r2 {s1{2 is sufficiently small, in view of the third condition in (3.12).
The idea of including }Xu}
` ?2 , by
˘ setting γ ą 0 in (4.6), comes from [3].
It provides upper bound 1{ rλ γn for the Lipschitz norm of ∆pr, w, νq in
the noise y ´ Xβ o , and thus large deviation bounds for (4.6).

4.3

Approximate solutions of the LCA

As in (4.1), we consider approximate solutions of the LCA (2.30) of the form
9 pnewq q ` Pen
9 ` pbpnewq q ´ Pen
9 ´ pbpoldq q ` ν approx .
0 “ Lpb

(4.12)

Such approximate solutions can be viewed as output of iterative algorithms
such as those discussed in Subsection 2.5. The following lemma provides the
LCA version of the basic inequality (4.5).
9 o q. Then,
Lemma 2. Let h “ bpnewq ´ β o and z “ ´Lpβ
DL pbpnewq , β o q ` D` pbpnewq , β o q
(
9 ` pβ o q ` Pen
9 ´ pbpoldq q ´ ν approx
“ hT z ´ Pen
(
o
9
“ hT z ´ Penpβ
q ` ν carry ´ ν approx ,
9
9
9 ` pbq´
where DL pb, βq “ pb´βqT tLpbq´
Lpβqu
and D` pb, βq “ pb´βqT tPen
9Pen` pβqu are respectively the symmetric Bregman divergence for the loss
Lpbq and the majorization penalty Penpnewq pbq in (2.31), and ν carry “
9 ´ pbpoldq q ´ Pen
9 ´ pβ o q is the carryover error in gradient.
Pen
In linear regression, Lpbq “ }y ´ Xb}22 {p2nq and (4.12) can be written
as
9 ` pbpnewq q ´ Pen
9 ´ pbpoldq q ` ν approx(4.13)
X T py ´ Xbpnewq q{n “ Pen
as an approximate solution to the convex minimization problem of LCA
penalized LSE. As in the derivation of (4.2), (4.3) and (4.5), this leads to
o
9
X T py ´ Xbpnewq q{n “ Penpβ
q ` ν div ´ ν carry ` ν approx , (4.14)

9 ` pbpnewq q ´ Pen
9 ` pβ o q and ν carry as in Lemma 2, and then
with ν div “ Pen
›
›
(4.15)
hT Σh ` p1 ´ ηqλ›hS c ›#,s
›
›
ď hT Σh ` p1 ´ ηqλ›hS c ›#,s ` D` pbpnewq , β o q
›
› ˘
`
ď hTS c z S c ´ ηλ›hS c ›#,s ´ λhTS wS ´ hT ν
28

o
9
when the favorable Penpβ
q is taken as in (2.26), where h “ bpnewq ´ β o ,
pnewq
o
T
D` pb
, β q “ h ν div is the symmetric Bregman divergence as in
p “ 0 and an
Lemma 2 and ν “ ν approx ´ ν carry . Thus, (4.5) holds with κpβq
T
extra carryover term h ν carry on the right-hand side.
For the sorted penalty ρ# pb; λq in (2.25), we can always take ρ´ ptq with
|pB{Btq2 ρ´ ptq| ď κpρq, so that the carryover error is bounded by
›
›
›
›
›
›
›ν carry › ď ›ρ9 ´ pbpoldq q ´ ρ9 ´ pβ o q› ď κpρq›hpoldq ›
(4.16)
2
2
2

with hpoldq “ bpoldq ´ β o in the analysis of (4.13) through (4.5).

4.4

Good solutions

We define here a set of “good solutions” to which our error bounds in the
following two subsections apply.
First, as in (3.12), we need to impose in addition to (4.7) a condition on
the concavity of the penalty in (4.1). This leads to the solution set
!
)
p (4.1) and (4.7) hold, κpβq
p ď κ˚ . (4.17)
Bpλ˚ , κ˚ , γq “ β:
Here λ˚ is a minimum penalty level requirement implicit in (4.7), e.g.
λ ě λ˚ “ pη ´ η1 q´1 σL{n1{2
(4.18)
a
with Φp´Lq ď s{p, e.g. L “ 2 logpp{sq for fixed penalty levels or λ˚ “
λ˚,s`1 for sorted ones satisfying (2.27). We note that Bpλ˚ , κ˚ , γq contains
p “ 0 although (4.17)
all solutions in the set Bpλ˚ , κ˚ q in (3.14) with κ1 pβq
allows approximate solutions with smaller minimum penalty
a
( level λ˚ .
1{2
Let }u}#,˚ “ }uS c }#,s ` |S| max }u}2 , }Xu}2 γ{n . We say that
p and β
r in B# pλ˚ , κ˚ , γq are connected by an a0 -chain if
two solutions β
pkq
pkq
pkq
p
there exist β
P B# pλ˚ , κ˚ , γq with sorted penalty levels tλ , . . . , λp u
1

such that
p p0q “ β,
r β
p pk
β

˚q

› pkq
›
pkq
p ›p
p pk´1q ›
“ β,
β ´β
ď a0 |S|λs`1 ,
#,˚

(4.19)

k “ 1, . . . , k ˚ with the a0 specified in Proposition 6 below. This condition
p and β
r are connected through a continuous path in Bpλ˚ , κ˚ , γq.
holds if β
Similar to (3.15), we define
(
p P Bpλ˚ , κ˚ , γq : (4.19) holds with β
r “ 0(4.20)
B0 pλ˚ , κ˚ , γq “ β
.

29

As the solutions are connected to 0 though a chain, B0 pλ˚ , κ˚ , γq can be
viewed as the sparse branch of the solution set Bpλ˚ , κ˚ , γq.
With the cone (4.9), we define a set of “good solutions” as follows,
B0˚ pλ˚ , κ˚ , γq
(4.21)
(
o
p P Bpλ˚ , κ˚ , γq : β
p ´ β P C# pS; ξ, γq Y B0 pλ˚ , κ˚ , γq
“ β
(
p “ bpnewq : (4.13) and (4.7) hold with the ν in (4.15) .
Y β
This is the set of approximate solutions (4.1) with estimation error inside
the cone or connected to the origin through a chain, or approximate LCA
solutions (4.13) with a reasonably small carryover component hT ν carry in
the hT ν in (4.15). Iterative applications of the LCA do provide a chain of
good solutions to the final output without having to specify the step size.
We note that for sorted penalties, (4.16) can be used to bound hT ν carry .
We prove below that good solutions all belong to the cone (4.9) when
the following restricted eigenvalue is no smaller than the κ˚ in (4.17),
" T
*
pu Σuq1{2
RE# pS; ξ, γq “ inf
: 0 ‰ u P C# pS; ξ, γq . (4.22)
}u}2
As the cone C# pS; ξ, γq in (4.9) depends on the sorted λ “ pλ1 , . . . , λp qT ,
the infimum in (4.22) is taken over all λ under consideration. We note that
#
+
„
puT Σuq1{2
1
RE# pS; ξ, γq ě inf
: }uS c }#,s ă ξ|S|1{2 }u}2
^ .
}u}2
γ
When the cone is confined to λ1 “ λp , i.e. }uS c }#,s “ }uS c }1 , the RE
condition on RE2# pS; ξ, γq is equivalent to the restricted strong convexity
condition [14] as }uS c }1 ă ξ|S|1{2 }u}2 implies }u}1 ă pξ ` 1q|S|1{2 }u}2 .
Compared with (3.1), the RE in (4.22) is smaller due to the use of a larger
cone. However, this is hard to avoid because the smaller penalty does not
control the `8 measure of the noise as in (3.8) and we do not wish to impose
uniform bound on the approximation error ν.
Proposition 6. Let κpbq be as in (2.5), Bpλ˚ , κ˚ , γq as in (4.17), and
C# pS; ξ, γq as in (4.9). Suppose RE2# pS; ξ, γq ě κ˚ and
∆pp1 ´ η ´ a1 qξ|S|1{2 , w, νq ď 1,

0 ă a1 ă 1 ´ η,

(4.23)

as in (4.7) for all tλ, w, νu associated with solutions in Bpλ˚ , κ˚ , γq. Let
r
a2 ““ a1 ξ 2 {t2κpβqu,
a3 “ a1 p1
‰ ´ ηqξ{tp1 ´ η ´ a1 qpξ ` 1q ` a1 u and a0 “
min a2 , a2 a3 {tp1 ´ ηqpξ _ 1qu . Then,
(
p P Bpλ˚ , κ˚ , γq : β
p ´ β o P C# pS; ξ, γq .
B0˚ pλ˚ , κ˚ , γq “ β
30

4.5

Analytic error bounds

In this subsection we provide prediction and estimation error bounds for the
set of approximate solutions in (4.21). While (4.7) is imposed on the entire
B0˚ pλ˚ , κ˚ , γq, it can be sharpened to
∆pr1 , w, νq ď 1

(4.24)

p with r1 ď p1 ´ ηqξ|S|1{2 , in view of our discussion below (4.10).
for a given β
Theorem 4. Let B0˚ pλ˚ , κ˚ , γq be the solution set given through (4.17),
(4.20) and (4.21), including approximate solutions for concave and sorted
penalties and the LCA, with S Ě supppβ o q. Suppose κ˚ ď RE2# pS; ξ, γq. Let
p P B ˚ pλ˚ , κ˚ , γq satisfying κpβq
p ď p1 ´ 1{C0 qRE2 pS; ξ, γq and (4.24). Let
β
0
#
(
F puq “ max }u}2 , pγuT Σuq1{2 . Then, for any semi-norm } ¨ },
}u}tr1 F puq ´ p1 ´ ηq}uS c }#,s u
uT Σu
u‰0

}h} ď C0 λ sup

(4.25)

p ´ β o for (4.1) and h “ bpnewq ´ β o for (4.13). In particular,
with h “ β
}hS }1 ` }hS c }#,s
phT Σhq1{2
C0 r1 λ
.
ď
F
phq
ď
ď
2
1{2
RE
pS;
ξ,
γq
p1 ` ξq|S|
RE# pS; ξ, γq
#
As an extension of Theorem 3, Theorem 4 provides prediction and `2
estimation error bounds in the same form along with a comparable sorted
`1 error bound. It demonstrate the benefit of sorted concave penalization
as r12 — s1 ` s{ log2 pp{sq ` r22 in standard settings as described in Theorem
6 and Corollary 3, where s “ |S|, s1 can be viewed as the number of small
nonzero coefficients, and r2 is the `2 component of the approximation error
as in (4.10).
Theorem 4 applies to approximate solutions at smaller penalty levels,
for penalties with fixed penalty level (λ1 “ ¨ ¨ ¨ “ λp ), for sorted penalties
adaptive choice of penalty level λs`1 from assigned sorted sequence λ1 ě
¨ ¨ ¨ ě λp , and for general LCA with possibly sorted penalties. However,
selection consistency of (4.1) is not guaranteed as false positive cannot be
ruled out at the smaller penalty level or with general approximation errors.
On the other hand, as properties of the Lasso at smaller penalty levels and
the Slope have been studied in [22, 21, 3] among others, Theorem 4 can be
viewed as an extension of their results to concave and/or sorted penalties
discussed in Section 2 and to the LCA.
31

It is also possible to derive error bounds in the case of C0 “ 8 as in
Theorem 1 if the `8 norm in the definition of the RCIF is replaced by the
norm } ¨ }#,˚ in (4.19). We omit details for the sake of space.
Next we apply Theorem 4 to iterative application of the LCA:
`
˘
ptq
bptq Ð LCA bpt´1q , Penptq , ν approx
(4.26)
`
˘
where bpnewq Ð LCA bpoldq , Pen, ν is the one-step LCA as in (4.13) with a
ptq

ptq

decomposition Penptq pbq “ Pen` pbq ´ Pen´ pbq as in (2.29).
ptq

Theorem 5. Let bptq generated in (4.26) with penalty levels λptq “ λs`1 for
9 ptq pbq ´ Pen
9 ptq pβ o q}2 ď κ0 }b ´ β o }2 for all b and
Penptq . Suppose }Pen
´
´
´
¯
ptq
ptq
∆ r1 , wptq , ν approx
ď 1, t “ 1, . . . , tf in ,
(4.27)
ptq

with the ∆pr, w, νq in (4.6) and certain r1 ą 0. Let hptq “ bptq ´ β o and
ν0 “ κ0 }hp0q }2 be the initial carryover error. Suppose the RE condition
ptq

RE# pS; ξ, γq ě κ0 tλptq {λpt`1q utr1 λp1q {ν0 ` 1u
ptq

with p1 ´ ηqξs1{2 ą ν0 {λp1q ` r1 , t “ 1, . . . , tf in . Then, for t ď tf in
pkq
t
ÿ
› pt´1q ›
›
›
` ptq ˘ r1ptq λptq
θ0t´k r1 λpkq
t › p0q ›
›
›
h
F h
ď
pS;
ξ,
γq
`
θ
`
θ
h
ď
0
0
2
2
RE2#
RE2# pS; ξ, γq
k“1

(
with F puq “ max }u}2 , pγuT Σuq1{2 and θ0 “ κ0 {RE2# pS; ξ, γq.
To find an approximate solution of PLSE with sorted penalty ρ# pb; λ˚ q,
we may implement (4.26) with a fixed penalty family ρpx; λq and λptq Ñ λ˚ ,
ptq
X T py ´ Xbptq q{n “ ρ9 `,# pbptq ; λptq q ´ ρ9 ´ pbpt´1q q ` ν approx
, (4.28)

t “ 1, . . . , t˚ . For example, we may change the penalty levels proportionally
by taking λptq “ Aptq λ˚ with sufficiently large Ap0q to ensure bp0q “ 0 and
decreasing Aptq .
Alternatively, we may move gradually from the Lasso to ρ# pb; λ˚ q,
`
˘
ptq
λj “ max λ˚,j , θt λ˚,1 , j ď p,
Penptq pbq “ θt λ˚,1 }b}1 ` p1 ´ θt qρ# pb; λptq q,
32

(4.29)

with suitable θ ă 1. The prediction and squared `2 estimation error bounds
are of the order pσ 2 {nqs log p for the Lasso and pσ 2 {nqts ` s1 logpp{squ for
sorted concave penalties, where s1 can be understood as the number of small
nonzero coefficients. Thus, if we implement (4.29) for a total of t˚ steps, we
˚
need θ0t ď t1 ` ps1 {sq logpp{squ{ log p to achieve the better rate. This and
parallel calculation for the weight for the Lasso and penalty level in (4.29)
lead to the following requirement on t˚ :
` ˚
˚˘
max θ0t , θ2t ď t1 ` ps1 {sq logpp{squ{ log p,
as λ2˚,1 {λ2˚,s`1 « logpp{sq{ log p is of no smaller order.

4.6

Probabilistic error bounds

Here we prove conditions of Theorems 4 and 5 holds with high probability
under the normality assumption (3.10) and the minimum penalty level
condition (4.18) and (2.27) respectively for fixed and sorted penalty levels.
In addition to (3.10) we assume (4.10) holds with 0 ă η1 ă η and r2 ě 0
and (4.18) holds for fixed penalty level. For sorted penalty levels we assume
(2.27) holds with α P p0, 1{4q and A0 “ A{pη ´ η1 q for some A ą 1. For
ř
pA´1qAk ,
nonnegativea
integer s and the above tα, Au,adefine pα,A “ 2α 8
k“0 α
qα,A “ p1 ´ 2pα,A q` , x1 “ s{qα,A , Lx “ 2 logpp{pαxqq and
"
µ#,s “

2

2spx1 {pqA ´1 p2{qα,A q2
A2 L2s`1 pA2 L2x1 ` 2q

*1{2
Its“0u .

(4.30)

We assume here that x1 ď p. This is reasonable when p{s is large.
Theorem 6. Suppose (2.9), (3.10) and (4.10) with η1 P p0, ηq and r2 ą 0.
p o be the oracle LSE as in (3.9) with S “ supppβ ˚ q and s “ |S|.
Let β o “ β
“
Let B0˚ pλ˚ , κ˚ , γq be the solution set in (4.21), ξ “ tp1´1{aqp1´ηqu´1 pη´
(1{2
‰
η1 q2 µ2#,s ` η˚2
` r2 {s1{2 with the µ#,s in (4.30) and a P p0, 1q. Let
(
F puq “ max }u}2 , pγuT Σuq1{2 . Suppose κ˚ ď p1 ´ 1{C ˚ qRE2# pS; ξ, γq.
Then, there exists an event Ω such that PtΩu ě 1 ´ e´ξ˚ s logpp{pαps`1qqq with
ξ˚ “ p1 ´ ηq2 ξ 2 γ{tapη ´ η1 qu2 , and that in the event Ω
1{2
›
›
p o › ď p1 ´ ηqC ˚ λ sup }u}tξs F puq ´ }uS c }#,s u (4.31)
›p
β´β
uT Σu
u‰0

p P B ˚ pλ˚ , κ˚ , γq and seminorms } ¨ }, where
for all approximate solutions β
0
λ “ λs`1 for sorted penalties and λ “ λpβ o q as in (2.4) otherwise. In
33

o
9
addition, for all sorted or unsorted penalties satisfying }Penpβ
q{λ}2 ď s1 ,

›
›
p o › ď C ˚ λ sup }u}tr1 F puq ´ p1 ´ ηq}uS c }#,s u
›p
β´β
uT Σu
u‰0

(4.32)

“
(1{2
‰
with r1 “ p1 ´ 1{aq´1 pη ´ η1 q2 µ2#,s ` s21
` r2 and at least probability
1
PtΩu ´ e´ξ˚ r1 logpp{pαps`1qqq with ξ˚1 “ γ{tapη ´ η1 qu2 .
a
p ď
Corollary 3. Suppose λ “ λs`1 — σ p2{nq logpp{sq in (4.32) and κpβq
2
2
2
p1 ´ 1{C0 qRE# pS; ξ, γq with C0 {RE2 pS; ξq “ OP p1q. Then,
p ´ Xβ
p o }2 {n ` }β
p ´β
p o }2 ` }β
p ´β
p o }2 {s “ OP pσ 2 {nqr2 logpp{sq
}X β
1
2
2
#,s
o
9
q{λ}22 , and
with r12 “ s1 ` s{ log2 pp{sq ` r22 , where s1 “ }Penpβ

p ´ Xβ ˚ }2 {n ` }β
p ´ β ˚ }2 ` }β
p ´β
p ˚ }2 {s
}X β
2
2
#,s
(
2
2
“ OP pσ {nq ps1 ` r2 q logpp{sq ` s .

(4.33)

For sorted concave penalty (2.25) with supppρp¨;
9 λqq Ď r´γλ, γλs,
(
s1 ď # j ď |S| : pβ o q#
j ď γλj .
Corollary
3 extends Corollary 1 to smaller penalty levels λ “ λs`1 ě
a
A0 σ p2{nq logpp{αps ` 1qq, sorted penalties, one-step application of the
LCA, and their approximate solutions. In the worst case scenario where
s1 — s, the error bounds in Corollary 3 attain the minimax rate [28, 3].
Theorem 6 and Corollary 3 provide sufficient conditions to guarantee
simultaneous adaptation of sorted concave PLSE: (a) picking level λs`1
automatically from tλ1 , . . . , λp u, and (b) partially removing the bias of the
Slope [21, 3] when s1 ! s, without requiring the knowledge of s or s1 .
Theorem 6 is a direct consequence of Theorem 4 and the following
proposition.
Proposition 7. Suppose the normality assumption (3.10) holds. Let
η ą η1 and tλj u be as in (2.27) for all sorted penalties. Let s “ |S|
and a
tqα,A , µ#,s u be as in (4.30) with qα,A ą 0. Let a ą 0, w ą 0 and
L “ 2 logpp{pαps ` 1qqq. Suppose supppzq Ď S c . Then,
ˆ
? ˙
!
)
r1 L γ
P (4.10) and }wS }2 ď w imply (4.24) ě Φ
(4.34)
apη ´ η1 q

34

(1{2
when p1 ´ 1{aqr1 ě pη ´ η1 q2 µ2#,s ` w2
` r2 . In particular, when (4.1)
is also confined to penalties satisfying (2.9),
˙
ˆ
!
)
p1 ´ ηqξs1{2 L
1{2
(4.35)
,
P (4.10) and }wS }2 ď η˚ s imply (4.7) ě Φ
apη ´ η1 qγ ´1{2
“
(1{2
‰
with ξ ě tp1 ´ 1{aqp1 ´ ηqu´1 pη ´ η1 q2 µ2#,s {s ` η˚2
` r2 {s1{2 , where
µ#,s is as in (4.30). Moreover, when (4.1) is confined to penalties with the
minimum fixed penalty level λpβ o q “ λ ě λ˚ as in
a (2.4) and (4.18), (4.34)
and (4.35) hold with the L in (4.18) and µ#,s “ 4s{pL4 ` 2L2 q.

References
[1] Agarwal, A., Negahban, S., and Wainwright, M. J. (2012). Fast global
convergence of gradient methods for high-dimensional statistical recovery.
The Annals of Statistics, pages 2452–2482.
[2] Beck, A. and Teboulle, M. (2009). A fast iterative shrinkage-thresholding
algorithm for linear inverse problems. SIAM journal on imaging sciences,
2(1):183–202.
[3] Bellec, P. C., Lecué, G., and Tsybakov, A. B. (2016). Slope meets lasso:
improved oracle bounds and optimality. arXiv preprint arXiv:1605.08651.
[4] Bickel, P. J., Ritov, Y., and Tsybakov, A. B. (2009). Simultaneous
analysis of lasso and dantzig selector. The Annals of Statistics, pages
1705–1732.
[5] Bogdan, M., van den Berg, E., Sabatti, C., Su, W., and Candès, E. J.
(2015). Slopeadaptive variable selection via convex optimization. The
annals of applied statistics, 9(3):1103.
[6] Candés, E. and Tao, T. (2007). The dantzig selector: statistical
estimation when p is much larger than n. The Annals of Statistics, pages
2313–2351.
[7] Candés, E. J. and Tao, T. (2005). Decoding by linear programming.
Information Theory, IEEE Transactions on, 51(12):4203–4215.
[8] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R., et al. (2004). Least
angle regression. The Annals of statistics, 32(2):407–499.

35

[9] Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized
likelihood and its oracle properties. Journal of the American statistical
Association, 96(456):1348–1360.
[10] Fan, J., Liu, H., Sun, Q., and Zhang, T. (2015). Tac for sparse
learning: Simultaneous control of algorithmic complexity and statistical
error. arXiv preprint arXiv:1507.01037.
[11] Huang, J. and Zhang, C.-H. (2012). Estimation and selection via
absolute penalized convex minimization and its multistage adaptive
applications. Journal of Machine Learning Research, 13:1809–1834.
[12] Loh, P.-L. and Wainwright, M. J. (2015). Regularized m-estimators
with nonconvexity: Statistical and algorithmic theory for local optima.
Journal of Machine Learning Research, 16:559–616.
[13] Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs
and variable selection with the lasso. The Annals of Statistics, pages
1436–1462.
[14] Negahban, S. N., Ravikumar, P., Wainwright, M. J., and Yu, B. (2012).
A unified framework for high-dimensional analysis of m-estimators with
decomposable regularizers. Statistical Science, pages 538–557.
[15] Nesterov, Y. et al. (2007). Gradient methods for minimizing composite
objective function.
[16] Osborne, M. R., Presnell, B., and Turlach, B. A. (2000a). A new
approach to variable selection in least squares problems. IMA Journal
of Numerical Analysis-Institute of Mathematics and its Applications,
20(3):389–404.
[17] Osborne, M. R., Presnell, B., and Turlach, B. A. (2000b). On the
lasso and its dual. Journal of Computational and Graphical statistics,
9(2):319–337.
[18] Parikh, N. and Boyd, S. (2013). Proximal algorithms, in foundations
and trends in optimization.
[19] Ročková, V. and George, E. I. (2016). The spike-and-slab lasso. Journal
of the American Statistical Association, (just-accepted).
[20] Rudelson, M. and Zhou, S. (2013). Reconstruction from anisotropic
random measurements. Information Theory, IEEE Transactions on,
59(6):3434–3447.
36

[21] Su, W. and Candes, E. (2016). Slope is adaptive to unknown sparsity
and asymptotically minimax. The Annals of Statistics, 44(3):1038–1068.
[22] Sun, T. and Zhang, C.-H. (2013). Sparse matrix inversion with scaled
lasso. The Journal of Machine Learning Research, 14(1):3385–3418.
[23] Tibshirani, R. (1996). Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society. Series B (Methodological), pages
267–288.
[24] Tropp, J. et al. (2006). Just relax: Convex programming methods
for identifying sparse signals in noise. Information Theory, IEEE
Transactions on, 52(3):1030–1051.
[25] van de Geer, S. A. and Bühlmann, P. (2009). On the conditions used to
prove oracle results for the lasso. Electronic Journal of Statistics, 3:1360–
1392.
[26] Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and
noisy sparsity recovery using-constrained quadratic programming (lasso).
Information Theory, IEEE Transactions on, 55(5):2183–2202.
[27] Wang, Z., Liu, H., and Zhang, T. (2014). Optimal computational and
statistical rates of convergence for sparse nonconvex learning problems.
Annals of statistics, 42(6):2164.
[28] Ye, F. and Zhang, C.-H. (2010). Rate minimaxity of theLasso and
Dantzig selector for the `q loss in `r balls. Journal of Machine Learning
Research, 11:3481–3502.
[29] Zhang, C.-H. (2010a). Nearly unbiased variable selection under
minimax concave penalty. The Annals of Statistics, pages 894–942.
[30] Zhang, C.-H. and Huang, J. (2008). The sparsity and bias of the lasso
selection in high-dimensional linear regression. The Annals of Statistics,
pages 1567–1594.
[31] Zhang, C.-H. and Zhang, T. (2012). A general theory of concave
regularization for high-dimensional sparse estimation problems. Statistical
Science, pages 576–593.
[32] Zhang, T. (2010b). Analysis of multi-stage convex relaxation for sparse
regularization. Journal of Machine Learning Research, 11:1087–1107.

37

[33] Zhao, P. and Yu, B. (2006). On model selection consistency of lasso.
The Journal of Machine Learning Research, 7:2541–2563.
[34] Zou, H. and Li, R. (2008). One-step sparse estimates in nonconcave
penalized likelihood models. Annals of statistics, 36(4):1509.

38

A

Appendices

We provide proofs in the following order: Proposition 1, Proposition 2,
Proposition 3, Lemma 1, Proposition 5, Theorem 1–3, Proposition 6,
Theorem 4, Theorem 5, and Proposition 7 along with an additional lemma.
We omit proofs of Proposition 4, Lemma 2 and Theorem 6 as explained
above or below their statements.
Proof of Proposition 1. For t0 “ 0 ă t1 ă . . . ă tK “ 1, (2.20)
yields
ˇ
ˇ ‰
‰(
“
“
9 ` h; λqˇb ` h
9 λqˇb ´ Eν ρpb
hT Eν ρpb;
ˇ
ˇ ‰(
“
‰
“
řK T
9 tk´1 ; λqˇbtk´1 ´ Eν ρpb
9 tk ; λqˇbtk
Eν ρpb
“
k“1 h
ˇ
ˇ ‰(
“
‰
“
ř
9 tk´1 ; λqˇbtk´1 ´ Eν ρpb
9 tk´1 ; λqˇbtk
ď κpρq}h}22 ` K
hT Eν ρpb
k“1
ˇ ˘
`
ş1
9 t ; λqˇbt dt
Ñ κpρq}h}22 ` rn 0 Varν hT ρpb
with bt “ b ` th, where the limit
( is taken as maxkďK |tk ´ tk´1 | Ñ 0. Note
9 tk´1 ; λq ´ ρpb
9 tk ; λq ď ptk ´ tk´1 qκpρq}h}22 by the definition
that hT ρpb
of κpρq in (2.12). This gives the upper bound for κpbq and tκ1 pbq, κ2 pbqu
pˆp
as hT` M h ď }h}21 }M
ˇ }max
˘ for all matrices M P IR . We note that
9
Covν ρpu;
λq, ρpu;
9
λqˇu, θ is a diagonal matrix when the components of
λ are independent given θ.
9 j ; λj q “ δj λj for j P Sbc . When λ is an
Let δ P t´1, 1up and take ρpb
exchangeable random vector under νpdλq,
´ “
ˇ ‰¯
“ ˇ ‰
9 λqˇb
Eν ρpb;
“ δ Sbc E λj ˇb , @ j P Sbc .
c
Sb

As BPenpbq is convex, this gives λpbq “ Erλj |bs for ρν pbq, j P Sbc .

˝

Proof of Proposition 2. We omit the proof of (2.26) as it follows
directly from the definition in (2.2). For λ ě λ1 and t ě t1 ě 0,
żt
(
9 λq ´ ρpx;
ρpx;
9 λ1 q dx ě 0.
ρpt; λq ` ρpt1 ; λ1 q ´ ρpt; λ1 q ´ ρpt1 ; λq “
t1

Thus, (2.28) follows. By the convexity of ρpt; λj q ` κpρqt2 {2 in t,
ρ# pb; λq `

κpρq}b}22 {2

“ max

„ÿ
p


ρpbj ; λkj q ` κpρq|bj | {2 : k P permppq
2

(

j“1

is convex, as the maximum of convex functions is convex.
maximum concavity of ρ# pb; λq is no greater than κpρq.
39

Hence, the
˝

Proof of Proposition 3. Because ρ# pb; λq depends only on b# , we
have sgnpbj q “ sgnpxj q, and the problem is to minimize
p
p
2
ÿ
ÿ
p|x`j | ´ b#
p|x` | ´ |b` |q2
j q
` ρ# pb; λq “
` ρ# pb; λq.
2
2
j“1
`“1
# 2
# 2
# 2
2
By algebra, p|x`j | ´ b#
j q ` p|x`k | ´ bk q ´ p|x`k | ´ bj q ´ p|x`j | ´ bk q “
#
#
#
p|x`j | ´ |x`k |qpb#
k ´ bj q. Thus, when p|x`j | ´ |x`k |qpbk ´ bj q ą 0, the solution
can be improved by switching x`j and x`k . This implies the monotonicity of
|bj | in |xj | and (2.36).
Now consider x1 ě . . . ě xp ě 0. Let rbj “ arg mintpxj ´ bq2 {2 ` ρpb; λj qu
be the univariate solution and b “ iso.proxpx; ρp¨; λqq the multivariate
isotonic solution. If bj ą bj`1 and bj ą rbj , then we can improve b by
decreasing bj . If bj ą bj`1 and bj`1 ă rbj`1 , then we can improve b by
increasing bj`1 . Thus, we must have rbj ą rbj`1 . Moreover, when

rbj 1 ´1 ą rbj 1 ď rbj 1 `1 ď ¨ ¨ ¨ ď rbj 2 ą rbj 2 `1 ,

rbj 1 ă rbj 2 ,

we must have bj 1 “ bj 1 `1 “ ¨ ¨ ¨ “ bj 2 . This groups the optimization problem
in the first round of Algorithm 3. The argument also applies to the grouped
optimization problem in the second round, so on and so forth.
˝
p ´ βo
Proof of Lemma 1. Let z (L
“ X T py ´ Xβ o q{n. Recall that h “ β
o
p
9
9
and w “ Penpβ q ` ν approx ´ z λ. By (3.11), Penpβq ` ν approx “ z ´ Σh,
so that
(
o
p
9
9
hT Σh “ hT ´ λw ` Penpβ
q ´ Penp
βq
2
2
p
p
ď ´λhT w ` κ1 pβq}h}
1 ` κ2 pβq}h}2
by the definition of κ1 pbq and κ2 pbq in (2.7). As hTS c pν approx qS c ě 0, this
o
o
9
9
9 j pβ o q “ sgnphj qλ, j P
gives (3.26) with Penpβ
q P B Penpβ
q satisfying Pen
S c.
˝
o
o
p ´ β and h
r“β
r ´ β . We want
Proof of Proposition 5. Let h “ β
to prove that
r 1 ď a0 λ
r and h P C pS; ξq imply h
r P C pS; ξq.
}h ´ h}

(A.1)

r Lemma 1 and (3.12) imply that
As }z S c }8 ď pη ´ a1 qλ˚ ď pη ´ a1 qλ,
r ` p1 ´ η ` a1 qλ}
r h
r S c }1
r T Σh
h
2
2
r h
r S }1 ` κ1 pβq}h}
r
r
ď p1 ´ ηqξ λ}
1 ` κ2 pβq}h}2 .
40

(A.2)

(
r
r ´ h}1 ď a2 λ,
Recall a2 “ a1 ξ{r2pξ ` 1q κ1 pbq ` κ2 pbq s. When }h}1 _ }h
(
r h}
r 1 κ1 pβq
r h}
r 2 ` κ2 pβq}
r h}
r 2 ď 2a2 λ}
r ` κ2 pβq
r ď a1 ξ λ}
r h}
r 1 {pξ ` 1q,
κ1 pβq}
1
2
so that (A.2) implies
`
˘
`
˘
r S c }1 ď p1 ´ ηqξ}h
r S }1 ` ta1 ξ{pξ ` 1qu }h
r S }1 ` }h
r S c }1 ,
1 ´ η ` a1 }h
r S c }1 ď ξ}h
r S }1 by algebra.
which is equivalent to }h
p ξq ď κ˚ and }h}1 ď p1 ` ξq}hS }1 ď p1 ` ξq|S|1{2 }h}2 , the
Because κ1,2 pβ;
th, λu version of (A.2) implies
hT Σh ` p1 ´ η ` a1 qλ}hS c }1 ď p1 ´ ηqξλ}hS }1 ` κ˚ }h}22 .
By the RE condition, we have κ˚ }h}22 ď hT Σh, so that
`
˘
1 ´ η ` a1 }hS c }1 ď p1 ´ ηqξ}hS }1 .

(A.3)

r and
Recall that a3 “ a1 p1 ´ ηqξ{tp1 ´ ηqpξ ` 1q ` a1 u. If }h}1 ą a2 λ
r
r
}h ´ h}1 ď λa2 a3 {tp1 ´ ηqpξ _ 1qu, (A.3) implies
`
˘
r c } ´ p1 ´ ηqξ}h
r S }1
1 ´ η }h
`
˘ S 1
r ´ h}1
ď `1 ´ η ˘}hS c }1 ´ p1 ´ ηqξ}hS }1 ` tp1 ´ ηqpξ _ 1qu}h
ď `1 ´ η }hS c˘}1 ´ p1 ´ ηqξ}hS }1 ` a3 }h}1
c
“ 1` ´ η ` a3 }h
˘ S }1 ´ tp1 ´ ηqξ ´ a3 u}hS }1
1 ´ η ` a1 }hS c }1 ´ p1 ´ ηqξ}hS }1
ď0
“
tp1 ´ ηqpξ ` 1q ` a1 u{tp1 ´ ηqpξ ` 1qu
by algebra. Thus, (A.1) holds in either cases.
˝
o
p ´ β . By Proposition 5, h P
Proof of Theorem 1–3. Let h “ β
2
2
C pS; ξq. It follows that }h}1 ď p1 ` ξq |S|}hS }22 , so that by Lemma 1 and
(3.8)
p ξq}h}2 ď κ˚ }h}2 .
hT Σh ` p1 ´ ηqλ}hS c }1 ` λwTS hS ď κ1,2 pβ;
2
2
Let C0 be as in Theorem 3. As hT Σh ě RE2 pS; ξq}h}22 , Lemma 1 implies
C0´1 hT Σh ` p1 ´ ηqλ}hS c }1 ď ´λwTS hS ď λ}wS }2 }h}2 . (A.4)
This immediately implies (3.22) and (3.23). For (3.17) and (3.18), we set
C0 “ 8. However, by (A.4) and the definition of RCIF,
RCIFpred pS; η, wqhT Σh ď }Σh}28 |S|.
41

Consequently, the first inequality in (3.17) follows from the fact that
T
o
p
}Σh}8 ď }X T py ´ X βq{n}
8 ` }X py ´ Xβ q{n}8
ď λ ` }ν approx }8 ` ηλ˚ “ λ,

and the second inequality follows from the first inequality in Proposition 4.
Similarly, the first inequality in (3.18) follows from
RCIFest,q pS; η, wq}h}q ď }Σh}8 |S|1{q ď λ|S|1{q ,
and the second from the second and third inequalities in Proposition 4.
p of
Finally we consider selection consistency for exact local solutions β
˚
(3.6) in B0 pλ˚ , κ˚ q under the assumption wS “ 0. In this case, ν approx “ 0,
β o is a solution of (3.6), and }hS c }1 “ 0 by (A.4). Moreover, because both
p are solutions of (3.6) with support in S,
β o and β
(
o
p ď κ1,2 pβ;
p ξq}hS }2 .
9
9
hTS ΣS hS “ hT Penpβ
q ´ Penp
βq
2
p ξq implies h “ 0.
Thus, φmin pΣS,S q ą κ1,2 pβ;
ř
For separable penalties of the form ρpβ; λq “ pj“1 ρpbj ; λq in (2.10),
(
(
o
p “ ř pβpj ´ β o q ρpβ
9
9
9 jo ; λq ´ ρp
9 βpj ; λq .
κ˚ }hS }22 ď hT Penpβ
q ´ Penp
βq
j
jPS
(
9 jo ; λq ´ ρp
As pβpj ´ βjo q ρpβ
9 βpj ; λq ď mintκpβjo ; ρ, λq, κpβpj ; ρ, λquh2j ď κ˚ h2j ,
equality must attain for every j. This is possible only when sgnpβpj qsgnpβjo q ě
0 for all j P S. Furthermore, sgnpβpj qsgnpβjo q ą 0 for all j P S when
κp0; ρ, λq ă φmin pΣS,S q.
˝
p P Bpλ˚ , κ˚ , γq with penalty level λ “
Proof of Proposition 6. Let β
o
p
r
r“λ
rs`1 . We first
λs`1 and β ´ β P C# pS; ξ, γq, and β P Bpλ˚ , κ˚ , γq with λ
r P B0 pλ˚ , κ˚ , γq implies β
r ´ β o P C# pS; ξ, γq, or equivalently
prove that β
o
r ´ β}
p #,˚ ď λ|S|a
r
r
}β
(A.5)
0 ñ β ´ β P C# pS; ξ, γq.
a
(
p ´ β o and h
r“β
r ´ β o . Assume
Let F puq “ max }u}2 , }Xu}2 γ{n , h “ β
r S c }#,s ě ξ|S|1{2 }h}
r 2 . By (4.5), (4.6) and (4.23)
without loss of generality }h
1{2
r T Σh
r ` p1 ´ ηqλ}
r h
r S c }#,s ´ κpβq}
r h}
r 2 ď p1 ´ η ´ a1 qλξ|S|
r
r
h
F (A.6)
phq.
2

r
r ´ h}#,˚ ď a2 |S|λ
r and
Recall that a2 “ a1 ξ 2 {t2κpβqu.
When }h}#,˚ _ }h
r S c }#,s , so
r S c }#,s ě ξ|S|1{2 }h}
r 2 , κpβq}
r h}
r 2 ď κpβq}
r h
r S c }2 {pξ 2 |S|q ď a1 }h
}h
2
#,s
r S c }#,s ď ξ|S|1{2 F phq
r by (A.6).
that }h
42

p ď κ˚ , the th, λu version of (A.6) implies
Because κpβq
hT Σh ` p1 ´ ηqλ}hS c }#,s ď p1 ´ η ´ a1 qξλ|S|1{2 F phq ` κ˚ F 2 phq.
By the RE condition in C# pS; ξ, γq, we have κ˚ F 2 phq ď hT Σh, so that
`

˘
1 ´ η }hS c }#,s ď p1 ´ η ´ a1 qξ|S|1{2 F phq.

r and
Recall that a3 “ a1 p1 ´ ηqξ{tp1 ´ η ´ a1 qpξ ` 1q ` a1 u. If }h}#,˚ ą a2 λ
r ´ h}#,˚ ď λa
r 2 a3 {tp1 ´ ηqpξ _ 1qu, we have
}h

ď
ď
“
“

`
˘
r c } ´ p1 ´ ηqξ|S|1{2 F phq
r
1 ´ η }h
`
˘ S #,s
1{2
r ´ h}#,˚
1 ´ η }hS c }#,s ´ p1 ´ ηqξ|S| F phq ` tp1 ´ ηqpξ _ 1qu}h
`
˘
1 ´ η }hS c }#,s ´ p1 ´ ηqξ|S|1{2 F phq ` a3 }h}#,˚
`
˘
1 ´ η ` a3 }hS c }#,s ´ p1 ´ η ´ a3 {ξqξ|S|1{2 F phq
`
˘
1 ´ η }hS c }#,s ´ p1 ´ η ´ a1 qξ|S|1{2 F phq
ď0
tp1 ´ ηqpξ ` 1q ` a1 u{tp1 ´ ηqpξ ` 1qu

due to p1´η `a3 q{p1´η ´a3 {ξq “ p1´ηq{p1´η ´a1 q. Hence, (A.5) holds in
either cases. The proof for the approximate LCA solution is straightforward
p “ 0.
as (4.13) corresponds to (4.5) with κpβq
˝
Proof of Theorem 4. By (4.5), (4.6) and (4.24) that
2
p
hT Σh ` p1 ´ ηqλ}hS c }#,s ´ κpβq}h}
(A.7)
2 ď r1 λF phq.
a
(
with F puq “ max }u}2 , }Xu}2 γ{n . By Proposition 6, h P C# pS; ξ, γq,
p ď p1 ´ 1{C0 qRE2 pS; ξ, γq,
so that RE2# pS; ξ, γqF 2 phq ď hT Σh. As κpβq
#

C0´1 hT Σh ` p1 ´ ηqλ}hS c }#,s ď r1 λF phq,
which implies (4.25).

˝

Proof of Theorem 5. We begin induction by assuming
κ0 }hpt´1q }2 {λptq ď ν0 {λp1q ,
which holds for t “ 1. By (4.6), (4.27) and the condition on ξ,
´
¯
ptq
pt´1q
pt´1q
1 ě ∆ r1 ` }ν carry
}2 {λptq , wptq , ν ptq
approx ´ ν carry
´
¯
ptq
pt´1q
ě ∆ r1 ` κ0 }hpt´1q }2 {λptq , wptq , ν ptq
approx ´ ν carry
43

´
¯
ptq
pt´1q
ą ∆ p1 ´ ηqξs1{2 , wptq , ν approx
´ ν carry
,
p “ 0 in
so that Theorem 4 applies. As LCA is convex minimization, κpβq
this application of Theorem 4. Thus,
ptq
p1q
`
˘ rptq λptq ` κ0 }hpt´1q }2
ptq r1 ` ν0 {λ
ď
λ
.
F hptq ď 1
RE2# pS; ξ, γq
RE2# pS; ξ, γq
ptq

As RE2# pS; ξ, γq ě κ0 tλptq {λpt`1q utr1 λp1q {ν0 ` 1u,
`
˘
ptq
κ0 F hptq
λptq r1 ` ν0 {λp1q
ď
κ
ď ν0 {λp1q .
0 pt`1q
λpt`1q
λ
RE2# pS; ξ, γq
`
˘
ptq
This completes the induction as }ν carry }2 ď κ0 }hptq }2 ď κ0 F hptq .

˝

We need the following lemma in the proof of Proposition 7.
Lemma 3. Let zj be normal variables with E zj “ 0 and Varpzj q ď σn2 . Let
s, A, Lx , qα,A , x1 and µ#,s be as in (4.30). Then, for s ą 0 and qα,A ą 0
"
P

max

x1 ďjďp

#
zj´s

Aσn Lj

ă 1,

` #
˘2
zj´s ´ Aσn Lj `

ÿ
săjăx1

pAσn Ls`1 q2

*
ă

µ2#,s

ą 1{2,

and the right-hand side is greater than p1 ` qα,A q{2 for s “ 0.
Proof of Lemma 3. Set σn “ 1 without loss of generality. As in [3],
(
2
Ptzj# ą t ď p2p{jqe´t {2 .
a
ř
pA´1qAk , q
Recall that pα,A “ 2α 8
2pα,A and x1 “ s{qα,A ď
α,A “ 1 ´
k“0 α
p. Define xk by L2xk “ A1´k L2x1 , 2 ď k ď k ˚ , with AL2p ą L2jk˚ ě L2p . Let jk
a
be the solution of jk ´ 1 ă xk ď jk . Let y “ 1 ´ s{x1 “ 2pα,A . Because
#
zj# ě zj`1
and xk {pxk ´ sq ď 1{p1 ´ s{x1 q “ 1{y “ y{p2pα,A q,
!
(
#
P max zj´s
{Lj ě A
x1 ďjďp
ÿ
(
ď
P zj#k ´s ě ALxk`1 “ A1{2 Lxk
jk ăjk`1

44

ÿ
ď
jk ăjk`1

ÿ
ď
jk ăjk`1

ď

´
¯
2p
2
exp ´ ALxk {2
jk ´ s
ˆ
˙
´
¯
2p
αxk
˚
exp ´ pA ´ 1qAk ´k L2p {2
xk ´ s
p

(A.8)

1 ÿ
k˚ ´k
2α1`pA´1qA
“ pα,A {y “ y{2.
y kďk˚

This completes the proof for s “ 0, which gives x1 “ 0. For s ą 0,
Proposition 10 in [22] gives
` #
˘2
›
›2
2
ÿ
zj´s ´ ALj `
E›p|z| ´ ALx1 q` ›2
4ppx1 {pqA
E
ď
ď
.
2 L2
2 L2
2 L2 pA2 L2 ` 2q
A
A
A
x
s`1
s`1
s`1
1
săjăx
1

As the right-hand side above equals to µ2#,s qα,A {2, by Markov’s inequality
*
" ÿ
` #
˘2
2 2
2
P
zj´s ´ ALj ` ą A Ls`1 µ#,s ď qα,A {2 “ 1{2 ´ y{2.
săjăx1

This and (A.8) completes the proof with the union bound.

˝

Proof of Proposition 7. Let η 1 “ η ´ η1 , λ˚,j be as in (2.27) and
T
r η, w, r2 q “ sup uS c z S c {λ˚,s`1 ´ η}uS c }#,s `aw}uS(}2 ` r2
∆pr,
r max }u}2 {a, }Xu}2 γ{n
}u}2 “1

where } ¨ }#,s is defined as in (4.4) with λj “ λ˚,j . By Lemma 3,
¯
´
˘
(
`
r η, w, r2 q ď η 2 µ2 ` w2 1{2 ` r2 pa{rq.
median ∆pr,
#,s
r η, w, r2 q is convex and unit Lipschitz in y ´ Xβ o ,
As supppzq Ď S c , tσ ∆pr,
so that by the Gaussian concentration inequality
!
´
¯
)
r η, w, r2 q ě median ∆pr,
r η, w, r2 q ` 1 ď Φp´tq.
P ∆pr,
We first prove (4.34) and (4.35). Let r “ r1 . Although ∆pr, η, w, r2 q in
r η, w, r2 q are defined with λ˚,j and ∆pr1 , w, νq is defined in
(4.11) and ∆pr,
(4.6) with λj ě λ˚,j , (4.10) and the monotonicity of pz{λ ´ 1q` in λ still
provide
L
`
˘
r η 1 , w, r2 q ` 1
∆pr1 , w, νqIt}wS }2 ďwu ď ∆pr1 , η 1 , w, r2 q median ∆pr,
45

when
ˆ

1

ě max
`
˘
r η 1 , w, r2 q ` 1
median ∆pr,

1
tσ
,
?
a r1 λ γn

˙

ˆ
“ max

˙
1
η1t
,
? ,
a r1 L γ

`
˘1{2
(
?
Setting t “ r1 L γ{paη 1 q and pη 1 q2 µ2#,s ` w2
` r2 {r1 ` 1{a “ 1, we
have (4.34). Moreover, (4.35) follows with r1 “ p1 ´ ηqξs1{2 . For constant λ
with }uS c }#,s “ }uS c }1 , we replace the median with
r η, w, r2 q ď
E ∆pr,

`

η 2 4s{pL4 ` 2L2 q ` w2

so that µ2#,s can be replaced by 4s{pL4 ` 2L2 q.

46

˘1{2

(
` r2 pa{rq,
˝

