OVERCOMING THE LIMITATIONS OF PHASE
TRANSITION BY HIGHER ORDER ANALYSIS OF
REGULARIZATION TECHNIQUES

arXiv:1603.07377v3 [math.ST] 20 Oct 2017

By Haolei Weng∗ , Arian Maleki† and Le Zheng‡
Columbia University∗†‡
We study the problem of estimating a sparse vector β ∈ Rp from
2
the response variables y = Xβ + w, where w ∼ N (0, σw
In×n ), under the following high-dimensional asymptotic regime: given a fixed
number δ, p → ∞, while n/p → δ. We consider the popular class of
`q -regularized least squares (LQLS), a.k.a. bridge estimators, given
by the optimization problem:
1
β̂(λ, q) ∈ arg min ky − Xβk22 + λkβkqq ,
β 2
and characterize the almost sure limit of p1 kβ̂(λ, q) − βk22 , and call
it asymptotic mean square error (AMSE). The expression we derive
for this limit does not have explicit forms and hence is not useful in
comparing LQLS for different values of q, or providing information
in evaluating the effect of δ or sparsity level of β. To simplify the
expression, researchers have considered the ideal “error-free” regime,
i.e. w = 0, and have characterized the values of δ for which AMSE is
zero. This is known as the phase transition analysis.
In this paper, we first perform the phase transition analysis of
LQLS. Our results reveal some of the limitations and misleading features of the phase transition analysis. To overcome these limitations,
we propose the small error analysis of LQLS. Our new analysis framework not only sheds light on the results of the phase transition analysis, but also describes when phase transition analysis is reliable, and
presents a more accurate comparison among different regularizers.

1. Introduction.
1.1. Objective. Consider the linear regression problem where the goal is
to estimate the parameter vector β ∈ Rp from a set of n response variables
y ∈ Rn , under the model y = Xβ + w. This problem has been studied extensively in the last two centuries since Gauss and Legendre developed the least
squares estimate of β. The instability or high variance of the least squares
estimates led to the development of the regularized least squares. One of
MSC 2010 subject classifications: Primary 60K35, 60K35; secondary 60K35
Keywords and phrases: Bridge regression, phase transition, comparison of estimators,
small error regime, second order term, asymptotic mean square error, optimal tuning

1

2

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

the most popular regularization classes is the `q -regularized least squares
(LQLS), a.k.a. bridge regression [1, 2], given by the following optimization
problem:
(1.1)

1
β̂(λ, q) ∈ arg min ky − Xβk22 + λkβkqq ,
β 2

P
where kβkqq = pi=1 |βi |q and 1 ≤ q ≤ 2.1 LQLS has been extensively studied in the literature. In particular, one can prove the consistency of β̂(λ, q)
under the classical asymptotic analysis (p fixed while n → ∞) [4]. However,
this asymptotic regime becomes irrelevant for high-dimensional problems in
which n is not much larger than p. Under this high dimensional setting, if
β does not have any specific “structure”, we do not expect any estimator
to perform well. One of the structures that has attracted attention in the
last twenty years is the sparsity, that assumes only k of the elements of β
are non-zero and the rest are zero. To understand the behavior of the estimators under structured linear model in high dimension, a new asymptotic
iid
framework has been proposed in which it is assumed that Xij ∼ N (0, 1/n),
k, n, p → ∞, while n/p → δ and k/p → , where δ and  are fixed numbers
[5, 6, 7, 8, 9].
One of the main notions that has been widely studied in this asymptotic
framework, is the phase transition [5, 6, 7, 10]. Intuitively speaking, phase
transition analysis assumes the error w equals zero and characterizes the
value of δ above which an estimator converges to the true β (in certain
sense that will be clarified later). While there is always error in the response
variables, it is believed that phase transition analysis provides reliable information when the errors are small. In this paper, we start by studying
the phase transition diagrams of LQLS for 1 ≤ q ≤ 2. Our analysis reveals
several limitations of the phase transition analysis. We will clarify these
limitations in the next section. We then propose a higher-order analysis of
LQLS in the small-error regime. As we will explain in the next section, our
new framework sheds light on the peculiar behavior of the phase transition
diagrams, and explains when we can rely on the results of phase transition
analysis in practice.
1.2. Limitations of the phase transition and our solution. In this section,
we intuitively describe the results of phase transition analysis, its limitations,
and our new framework. Consider the class of LQLS estimators and suppose
1

Bridge regression is a name used for LQLS with any q ≥ 0. In this paper we focus on
1 ≤ q ≤ 2. To analyze the case 0 ≤ q < 1, [3] has used the replica method from statistical
physics.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

3

that we would like to compare the performance of these estimators through
the phase transition diagrams. For the purpose of this section, we assume
that the vector β has only k non-zero elements, where k/p →  with  ∈
(0, 1). Since phase transition analysis is concerned with w = 0 setting, it
considers limλ→0 β̂(λ, q) which is equivalent to the following estimator:
arg min kβkqq ,
β

(1.2)

subject to y = Xβ.

Below we informally state the results of the phase transition analysis. We
will formalize the statement and describe in details the conditions under
which this result holds in Section 3.
Informal Result 1. For a given  > 0 and q ∈ [1, 2], there exists a number
Mq () such that as p → ∞, if δ ≥ Mq () + γ (γ > 0 is an arbitrary number),
then (1.2) succeeds in recovering β, while if δ ≤ Mq () − γ, (1.2) fails.2
The curve δ = Mq () is called the phase transition curve of (1.2). We will
show that Mq () is given by the following formula:

1 if 2 ≥ q > 1,
(1.3) Mq () =
inf χ≥0 (1 − )Eη12 (Z; χ) + (1 + χ2 ) if q = 1,
where η1 (u; χ) = (|u|−χ)+ sign(u) denotes the soft thresholding function and
Z ∼ N (0, 1). While the above phase transition curves can be obtained with
different techniques, such as statistical dimension framework proposed in [7]
and Gordon’s lemma applied in [30, 21], we will derive them as a simple
byproduct of our main results in Section 3 under message passing framework. Also, the phase transition analysis of the regularized least squares
has already been performed in the literature [17, 6, 31]. Hence, we should
emphasize that the presentation of the phase transition results for bridge
regression is not our main contribution here. We rather use it to motivate
our second-order analysis of the asymptotic risk, which will appear later in
this section. Before we proceed further let us mention some of the properties
of M1 () that will be useful in our later discussions.
Lemma 1.

M1 () satisfies the following properties:

(i) M1 () is an increasing function of .
(ii) lim→0 M1 () = 0.
2

Different notions of success have been studied in the phase transition analysis. We will
mention one notion later in our paper.

4

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

(iii) lim→1 M1 () = 1.
(iv) M1 () > , for  ∈ (0, 1).
Proof. Define F (χ, ) , (1−)Eη12 (Z; χ)+(1+χ2 ). It is straightforward
to verify that F (χ, ), as a function of χ over [0, ∞), is strongly convex and
has a unique minimizer. Let χ∗ () be the minimizer. We write it as χ∗ () to
emphasize its dependence on . By employing the chain rule we have
dM1 ()
d

∂F (χ∗ (), ) ∂F (χ∗ (), ) dχ∗ ()
∂F (χ∗ (), )
+
·
=
∂
∂χ
d
∂
∗
2
2
∗
∗
2
= 1 + (χ ()) − Eη1 (Z; χ ()) > 1 + (χ ()) − E|Z|2
=

= (χ∗ ())2 > 0,
which completes the proof of part (i). To prove (ii) note that
0 ≤ lim min(1 − )Eη12 (Z; χ) + (1 + χ2 )
→0 χ≥0

≤ lim (1 − )Eη12 (Z; log(1/)) + (1 + log2 (1/))
→0
Z ∞
= lim 2(1 − )
(z − log(1/))2 φ(z)dz
→0
log(1/)
Z ∞
= lim 2(1 − )
z 2 φ(z + log(1/))dz
→0
0
Z ∞
log2 (1/)
−
2
≤ lim 2(1 − )e
z 2 φ(z)dz = 0,
→0

0

where φ(·) is the density function of standard normal. Regarding the proof
of part (iii), first note that as  → 1, χ∗ () → 0. Otherwise suppose χ∗ () →
χ0 > 0 (taking a convergent subsequence if necessary). Since Eη12 (Z; χ∗ ()) ≤
E|Z|2 = 1, we obtain
lim F (χ∗ (), ) = 1 + χ20 > 1.

→1

On the other hand, it is clear that
lim F (χ∗ (), ) ≤ lim F (0, ) = 1.

→1

→1

A contradiction arises. Hence the fact χ∗ () → 0 as  → 1 leads directly to
lim M1 () = lim F (χ∗ (), ) = 1.

→1

→1

Part (iv) is clear from the definition of M1 ().

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

5

1
0.8

q<1
q=1
q>1

ε

0.6
0.4

0.2

0
0

0.2

0.4

δ

0.6

0.8

1

Fig 1. Phase transition curves of LQLS for (i) q < 1: these results are derived in [3]
by the non-rigorous replica method from statistical physics. We have just included them
for comparison purposes. In this paper we have focused on q ≥ 1. (ii) q = 1: the blue
curve exhibits the phase transition of LASSO. Below this curve LASSO can “successfully”
recover β. (iii) q > 1: The magenta curve represents the phase transition of LQLS for any
q > 1. This figure is based on Informal Result 1 and will be carefully defined and derived
in Section 3.

Figure 1 shows Mq () for different values of q. We observe several peculiar
features: (i) As is clear from both Lemma 1 and Figure 1, q = 1 requires
much fewer observations than all the other values of q > 1 for successful
recovery of β. (ii) The values of the non-zero elements of β do not have any
effect on the phase transition curves. In fact, even the sparsity level does
not have any effect on the phase transition for q > 1. (iii) For every q > 1,
the phase transition of (1.2) happens at exactly the same value.
These features raise the following question: how much and to what extent
are these phase transition results useful in applications, where at least small
amount of error is present in the response variables? For instance, intuitively
speaking, we do not expect to see much difference between the performance
of LQLS for q = 1.01 and q = 1. However, according to the phase transition analysis, q = 1 outperforms q = 1.01 by a wide margin. In fact the
performance of LQLS for q = 1.01 seems to be closer to that of q = 2 than
q = 1. Also, in contrast to the phase transition implication, we may not
expect LQLS to perform the same for β with different values of non-zero
elements. The main goal of this paper is to present a new analysis that will
shed light on the misleading features of the phase transition analysis. It will
also clarify when and under what conditions the phase transition analysis is
reliable for practical guidance.

6

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

2 of the error w is assumed to be
In our new framework, the variance σw
small. We consider (1.1) with the optimal value of λ for which the asymptotic
kβ̂(λ,q)−βk2

2
mean square error, i.e., limp→∞
, is minimized. We first obtain
p
the formula for the asymptotic mean square error (AMSE) characterized
through a series of non-linear equations. Since σw is assumed small, we then
derive the asymptotic expansions for AMSE as σw → 0. As we will describe
later, the phase transition of LQLS for different values of q can be obtained
from the first dominant term in the expansion. More importantly, we will
show that the second dominant term is capable of evaluating the importance
of the phase transition analysis for practical situations and also provides a
much more accurate analysis of different bridge estimators. Here is one of
the results of our paper, presented informally to clarify our claims. All the
technical conditions will be determined in Sections 2 and 3.

Informal Result 2. If λ∗ denotes the optimal value of λ, then for any
q ∈ (1, 2), δ > 1, and  < 1
2
q+1 (1 − )2 (E|Z|q )2
1
σw
2q δ
2q
kβ̂(λ∗ , q) − βk22 =
− σw
+ o(σw
),
p→∞ p
1 − 1/δ
(δ − 1)q+1 E|G|2q−2

lim

where Z ∼ N (0, 1) and G is a random variable whose distribution is specified
by the non-zero elements of β. We will clarify this in the next section. Finally,
the limit notation we have used above is the almost sure limit.
2

σw
As we will discuss in Section 3, the first term 1−1/δ
determines the phase
transition. Moreover, we have further derived the second dominant term in
the expansion of the asymptotic mean square error. This term enables us to
clarify some of the confusing features of the phase transitions. Here are some
important features of this term: (i) It is negative. Hence, the AMSE that is
predicted by the first term (and phase transition analysis) is overestimated
specially when q is close to 1. (ii) Fixing q, the magnitude of the second
dominant term grows as  decreases. Hence, for small values of σw all values
of 1 < q < 2 benefit from the sparsity of β. Also, smaller values of q seem to
benefit more. (iii) Fixing  and δ, the power of σw decreases as q decreases.
This makes the absolute value of the second dominant term bigger. As q
decreases to one, the order of the second dominant term gets closer to that
of the first dominant term and thus the predictions of phase transition analysis become less accurate. We will present a more detailed discussion of the
second order term in Section 3. To show some more interesting features of
our approach, we also informally state a result we prove for LASSO.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

7

Informal Result 3. Suppose that the non-zero elements of β are all larger
than a fixed number µ. If λ∗ denotes the value of λ that leads to the smallest
AMSE, and if δ > M1 (), then
(1.4)

2
1
δM1 ()σw
2
kβ̂(λ∗ , 1) − βk22 −
= O(exp(−µ̃/σw
)),
p→∞ p
δ − M1 ()

lim

where µ̃ is a constant that depends on µ.
As can be seen here, compared to the other values of q, q = 1 has smaller
first order term (according to Lemma 1), but much smaller (in magnitude)
second order term. The first implication of this result is that the first dominant term provides an accurate approximation of AMSE. Hence, phase transition analysis in this case is reliable even if small amount of noise is present;
that is one of the main reasons why the theoretically derived phase transition curve matches the empirical one for LASSO. Furthermore, note that in
order to obtain Informal Result 3, we have made certain assumption about
the non-zero components of β. As will be shown in Section 3, any violation
of this assumption has major impact on the second dominant term.
In the rest of the paper, we first state all the assumptions required for
our analysis. We then present the formal statements of aforementioned and
related results and provide a more comprehensive discussion.
1.3. Organization of the paper. The rest of the paper is organized as
follows: Section 2 presents the asymptotic framework of our analysis. Section
3 discusses the main contributions of our paper. Section 4 compares our
results with the related work. Section 5 shows some simulation results and
discusses some open problems that require further research. Section 6 and
Supplementary material are devoted to the proofs of all the results.
2. The asymptotic framework. The main goal of this section is to
formally introduce the asymptotic setting under which we study LQLS. In
the current and next sections only, we may write vectors and matrices as
β(p), X(p), w(p) to emphasize the dependence on the dimension of β. Similarly, we may use β̂(λ, q, p) as a substitute for β̂(λ, q). Note that since we
assume n/p → δ, we do not include n in our notations. Now we define a
specific type of a sequence known as a converging sequence. Our definition
is borrowed from other papers [11, 12, 13] with some minor modifications.
Definition 1. A sequence of instances {β(p), X(p), w(p)} is called a
converging sequence if the following conditions hold:

8

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

- The empirical distribution3 of β(p) ∈ Rp converges weakly to a probability measure pβ with bounded second moment. Further, p1 kβ(p)k22
converges to the second moment of pβ .
- The empirical distribution of w(p) ∈ Rn converges weakly to a zero
2 . And, 1 kw(p)k2 → σ 2 .
mean distribution with variance σw
w
2
n
- The elements of X(p) are iid with distribution N (0, 1/n).
For each of the problem instances in a converging sequence, we solve the
LQLS problem (1.1) and obtain β̂(λ, q, p) as the estimator. The interest is
to evaluate the accuracy of this estimator. Below we define the asymptotic
mean square error.
Definition 2. Let β̂(λ, q, p) be the sequence of solutions of LQLS for the
converging sequence of instances {β(p), X(p), w(p)}. The asymptotic mean
square error is defined as the almost sure limit of
p

1X
AMSE(λ, q, σw ) , lim
|β̂i (λ, q, p) − βi (p)|2 ,
p→∞ p
i=1

where the subscript i is used to denote the ith component of a vector.
Note that we have suppressed δ and pβ in the notation of AMSE for
simplicity, despite the fact that the asymptotic mean square error depends
on them as well. In the above definition, we have assumed that the almost
sure limit exists. Under the current asymptotic setting, the existence of
AMSE can be proved. In fact we are able to derive the asymptotic limit for
general loss functions as presented in the following theorem.
Theorem 2.1. Consider a converging sequence {β(p), X(p), w(p)}. For
any given q ∈ [1, 2], suppose that β̂(λ, q, p) is the solution of LQLS defined
in (1.1). Then for any pseudo-Lipschitz function4 ψ : R2 → R, almost surely
p

(2.1)


1X 
lim
ψ β̂i (λ, q, p), βi (p) = EB,Z [ψ(ηq (B + σ̄Z; χ̄σ̄ 2−q ), B)],
p→∞ p
i=1

where B and Z are two independent random variables with distributions pβ
and N (0, 1), respectively; the expectation EB,Z (·) is taken with respect to
3

It is the distribution that puts a point mass 1/p at each of the p elements of the vector.
A function ψ : R2 → R is pseudo-Lipschitz of order k if there exists a constant L > 0
such that for all x, y ∈ R2 , we have |ψ(x) − ψ(y)| ≤ L(1 + kxkk−1
+ kykk−1
)kx − yk2 . We
2
2
consider pseudo-Lipschitz functions with order 2 in this paper.
4

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

9

both B and Z; ηq (·; ·) is the proximal operator for the function k · kqq 5 ; and
σ̄ and χ̄ satisfy the following equations:
(2.2)
(2.3)

1
σ̄ 2 = σω2 + EB,Z [(ηq (B + σ̄Z; χ̄σ̄ 2−q ) − B)2 ],
δ


1
λ = χ̄σ̄ 2−q 1 − EB,Z [ηq0 (B + σ̄Z; χ̄σ̄ 2−q )] ,
δ

where ηq0 (·; ·) denotes the derivative of ηq with respect to its first argument.
The result for q = 1 has been proved in [13]. The key ideas of the proof
for generalizing to q ∈ (1, 2] are similar to those of [13]. We describe the
main proof steps in Appendix J of the supplementary material. According
to Theorem 2.1, in order to calculate the asymptotic mean square error (or
any other loss) of β̂(λ, q, p), we have to solve (2.2) and (2.3) for (σ̄, χ̄). The
following lemma shows these two nonlinear equations have a unique solution.
Lemma 2. For any positive values of λ, δ, σw > 0, any random variable
B with finite second moment, and any q ∈ [1, 2], there exists a unique pair
(σ̄, χ̄) that satisfies both (2.2) and (2.3).
The proof of this lemma can be found in Appendix D of the supplementary
material. Theorem 2.1 provides the first step in our analysis of LQLS. We
first calculate σ̄ and χ̄ from (2.2) and (2.3). Then, incorporating σ̄ and χ̄ in
(2.1) gives the following expression for the asymptotic mean square error:
(2.4)

AMSE(λ, q, σw ) = EB,Z (ηq (B + σ̄Z; χ̄σ̄ 2−q ) − B)2 .

Given the distribution of B (the sparsity level  included), the variance of
2 , the number of response variables (normalized by the number
the error σw
of predictors) δ, and the regularization parameter λ, it is straightforward
to write a computer program to find the solution of (2.2) and (2.3) and
then compute the value of AMSE. However, it is needless to say that this
approach does not shed much light on the performance of bridge regression
estimates, since there are many factors involved in the computation and
each affects the result in a non-trivial fashion. In this paper, we would like
to perform an analytical study on the solution of (2.2) and (2.3) and obtain
an explicit characterization of AMSE in the small-error regime.
3. Our main contributions.
5

Proximal operator of k · kqq is defined as ηq (u; χ) , arg minz 21 (u − z)2 + χ|z|q . For
further information on these functions, please refer to the supplementary material.

10

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

3.1. Optimal tuning of λ. The performance of LQLS, as defined in (1.1),
depends on the tuning parameter λ. In this paper, we consider the value of λ
that gives the minimum AMSE. Let λ∗,q denote the value of λ that minimizes
AMSE given in (2.4). Then LQLS is solved with this specific value of λ, i.e.,
(3.1)

1
β̂(λ∗,q , q, p) ∈ arg min ky − Xβk22 + λ∗,q kβkqq .
β 2

Note that this is the best performance that LQLS can achieve in terms of
the AMSE. Theorem 2.1 enables us to evaluate this optimal AMSE of LQLS
for every q ∈ [1, 2]. The key step is to compute the solution of (2.2) and (2.3)
with λ = λ∗,q . Since λ∗,q has to be chosen optimally, it seemingly causes an
extra complication for our analysis. However, as we show in the following
corollary, the study of Equations (2.2) and (2.3) can be simplified to some
extent.
Corollary 1. Consider a converging sequence {β(p), X(p), w(p)}. Suppose that β̂(λ∗,q , q, p) is the solution of LQLS defined in (3.1). Then for any
q ∈ [1, 2]
(3.2)

AMSE(λ∗,q , q, σw ) = min EB,Z (ηq (B + σ̄Z; χ) − B)2 ,
χ≥0

where B and Z are two independent random variables with distributions
pβ and N (0, 1), respectively; and σ̄ is the unique solution of the following
equation:
(3.3)

σ̄ 2 = σω2 +

1
min EB,Z [(ηq (B + σ̄Z; χ) − B)2 ].
δ χ≥0

The proof of Corollary 1 is shown in Appendix E of the supplementary
material. Corollary 1 enables us to focus the analysis on a single equation
(3.3), rather than two equations (2.2) and (2.3). The results we will present
in the next section are mainly based on investigating the solution of (3.3).
3.2. Analysis of AMSE. In this paper since we are focused on the sparsity structure of β, from now on we assume that the distribution, to which
the empirical distribution of β ∈ Rp converges, has the form
pβ (b) = (1 − )δ0 (b) + g(b),
where δ0 (·) denotes a point mass at zero, and g(·) is a generic distribution
that does not have any point mass at 0. Here, the mixture proportion  ∈
(0, 1) is a fixed number that represents the sparsity level of β. The smaller 

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

11

is, the sparser β will be. The distribution g(b) specifies the values of non-zero
components of β. We will use G to denote a random variable having such
a distribution. Since our results and proof techniques look very different for
the case q > 1 and q = 1, we study these cases separately.
3.2.1. Results for q > 1. Our first result is concerned with the optimal
AMSE of LQLS for 1 < q ≤ 2, when the number of response variables is
larger than the number of predictors p, i.e., δ > 1.
Theorem 3.1. Suppose P(|G| ≤ t) = O(t) (as t → 0) and E|G|2 < ∞,
then for 1 < q < 2, δ > 1 and  ∈ (0, 1), we have
(3.4)

AMSE(λ∗,q , q, σw ) =

2
σw
δ q+1 (1 − )2 (E|Z|q )2 2q
2q
).
−
σ + o(σw
1 − 1/δ
(δ − 1)q+1 E|G|2q−2 w

For q = 2, δ > 1 and  ∈ (0, 1), if E|G|2 < ∞, we have
AMSE(λ∗,q , q, σw ) =

4
2
δ 3 σw
σw
4
−
+ o(σw
).
1 − 1/δ (δ − 1)3 E|G|2

Note that Z ∼ N (0, 1) and G ∼ g(·) are independent.
The proof of the result is presented in Appendix F of the supplementary
material. There are several interesting features of this result that we would
like to discuss: (i) The second dominant term of AMSE is negative. This
means that the actual AMSE is smaller than the one predicted by the first
order term, especially for smaller values of q. (ii) Neither the sparsity level
nor the distribution of the non-zero components of β appear in the first
2
σw
dominant term, i.e. 1−1/δ
. As we will discuss later in this section, the first
dominant term is the one that specifies the phase transition curve. Hence,
these calculations show a peculiar feature of phase transition analysis we
discussed in Section 1.2, that the phase transition of q ∈ (1, 2] is neither
affected by non-zero components of β or the sparsity level. However, we see
that both factors come into play in the second dominant term. (iii) For the
fully dense vector, i.e.  = 1, (3.4) may imply that for 1 < q < 2,
AMSE(λ∗,q , q, σw ) =

2
σw
2q
+ o(σw
).
1 − 1/δ

Hence, we require a different analysis to obtain the second dominant term
(with different orders). We refer the interested readers to [14] for further
information about this case. (iv) For  < 1, the choice of q ∈ (1, 2] does

12

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

not affect the first dominant term. That is the reason why all the values of
q ∈ (1, 2] share the same phase transition curve. However, the value of q has a
major impact on the second dominant term. In particular, as q approaches
1, the order of the second dominant term in terms of σw gets closer to
that of the first dominant term. This means that in any practical setting,
phase transition analysis may lead to misleading conclusions. Specifically, in
contrast to the conclusion from phase transition analysis that q ∈ (1, 2] have
the same performance, the second order expansion enables us to conclude
that the closer to 1 the value of q is, the better its performance will be. Our
next theorem discusses the AMSE when δ < 1.
Theorem 3.2.
(3.5)

Suppose E|G|2 < ∞, then for 1 < q ≤ 2 and δ < 1,
lim AMSE(λ∗,q , q, σw ) > 0.

σw →0

The proof of this theorem is presented in Appendix G of the supplementary material. Theorems 3.1 and 3.2 together show a notion of phase
2 ), and hence it will go to
transition. For δ > 1, as σw → 0, AMSE = O(σw
zero, while AMSE 9 0 for δ < 1. In fact, the phase transition curve δ = 1
can be derived from the first dominant term in the expansion of AMSE. If
δ = 1, the first dominant term is infinity and there will be no successful
recovery, while it becomes zero when σw = 0 if δ > 1. A more rigorous
justification can be found in the proof of Theorems 3.1 and 3.2. Therefore,
we may conclude that the first order term contains the phase transition
information. Moreover, the derived second order term offers us additional
important information regarding the accuracy of the phase transition analysis. To provide a comprehensive understanding of these two terms, in Section
5 we will evaluate the accuracy of first and second order approximations to
AMSE through numerical studies.
3.2.2. Results for q = 1. So far we have studied the case 1 < q ≤ 2. In
this section, we study q = 1, a.k.a. LASSO. In Theorems 3.1 and 3.2, we
have characterized the behavior of LQLS with q ∈ (1, 2] for a general class
of G. It turns out that the distribution of G has a more serious impact on
the second dominant term of AMSE for LASSO. We thus analyze it in two
different settings. Our first theorem considers the distributions that do not
have any mass around zero.
Theorem 3.3.

Suppose P(|G| > µ) = 1 with µ being a positive constant

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

13

and E|G|2 < ∞, then for δ > M1 ()6
(3.6)

 
δM1 () 2
AMSE(λ∗,1 , 1, σw ) =
σw + o φ
δ − M1 ()

r

δ − M1 () µ̃ 
,
δ
σw

where µ̃ is any positive constant smaller than µ and φ(·) is the density
function of standard normal.
The proof of Theorem 3.3 is given in Section 6. Different from LQLS with
q ∈ (1, 2], we have not derived the exact analytical expression of second
dominant term for LASSO. However, since it is exponentially small, the
first order term (or phase transition analysis) is sufficient for evaluating
the performance of LASSO in the small-error regime. This will be further
confirmed by the numerical studies in Section 5. Below is our result for the
distributions of G that have more mass around zero.
Theorem 3.4. Suppose that P(|G| ≤ t) = Θ(t` ) (as t → 0) with ` > 0
and E|G|2 < ∞, then for δ > M1 (),
δM1 () 2
σ
δ − M1 () w


  `/2
1
`+2
 ,
& −Θ(σw
) · log log . . . log
|
{z
} σw

`+2
−Θ(σw
) & AMSE(λ∗,1 , 1, σw ) −

m times

where m is an arbitrary but finite natural number, and a & b means a ≥ b
holds for sufficiently small σw .
The proof of this theorem can be found in Appendix H of the supplementary material. It is important to notice the difference between Theorems 3.3
and 3.4. The first point we would like to emphasize is that the first dominant
terms are the same in both cases. The second dominant terms are different
though. As we will show in Section 6 and Appendix H, similar to LQLS
for 1 < q ≤ 2, the second dominant terms are in fact negative. Hence, the
actual AMSE will be smaller than the one predicted by the first dominant
term. Furthermore, note that the magnitude of the second dominant term
in Theorem 3.4 is much larger than that in Theorem 3.3. This seems intuitive. LASSO tends to shrink the parameter coefficients towards zero, and
hence, if the true β has more mass around zero, the AMSE will be smaller.
The more mass the distribution of G has around zero, the better the second
order term will be. Our next theorem discusses what happens if δ < M1 ().
6

Recall M1 () = inf χ≥0 (1 − )Eη12 (Z; χ) + (1 + χ2 ) with Z ∼ N (0, 1).

14

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Theorem 3.5.
(3.7)

Suppose that E|G|2 < ∞. Then for δ < M1 (),
lim AMSE(λ∗,1 , 1, σw ) > 0.

σw →0

The proof is presented in Appendix I of the supplementary material. Similarly as we discussed in Section 3.2.1, Theorems 3.3, 3.4 and 3.5 imply the
phase transition curve of LASSO. Such information can be obtained from
the first dominant term in the expansion of AMSE as well.
4. Related work.
4.1. Other phase transition analyses and n/p → δ asymptotic results.
The asymptotic framework that we considered in this paper evolved in a
series of papers by Donoho and Tanner [15, 16, 5, 17]. This framework was
used before on similar problems in engineering and physics [18, 19, 20].
Donoho and Tanner characterized the phase transition curve for LASSO and
some of its variants. Inspired by this framework, many researchers started
exploring the performance of different algorithms or estimates under this
asymptotic settings [10, 7, 21, 8, 22, 23, 24, 25, 9, 26, 3, 27, 28, 12, 13].
Our paper performs the analysis of LQLS under such asymptotic framework. Also, we adopt the message passing analysis that was developed in a
series of papers [11, 6, 29, 12, 13]. The notion of phase transition we consider is similar to the one introduced in [11]. However, there are three major
differences: (i) The analysis of [11] is performed for LASSO, while we have
generalized the analysis to any LQLS with 1 < q ≤ 2. (ii) The analysis of
[11] is performed on the least favorable distribution for LASSO, while here
we characterize the effect of the distribution of G on the AMSE as well.
(iii) Finally, [11] is only concerned with the first dominant term in AMSE of
LASSO, while we derive the second dominant term whose importance has
been discussed in the last few sections.
Another line of research that has connections with our analysis is presented in a series of papers [30, 31, 21]. In [21] the authors have derived a
minimax formulation that (if it has a unique solution and is solved) can give
an accurate characterization of the asymptotic mean square error. Compared
with Theorem 2.1 in our paper, that result works for more general penalized M-estimators, while Theorem 2.1 holds for general pseudo-Lipschitz loss
functions. When applying the minimax formulation in [21] to bridge regression, the AMSE formula in (2.4) can be recovered. However, the derivation
of phase transition curves for bridge regression under optimal tuning is not
found in [21]. Furthermore, [30, 31] proposed a geometric approach to characterize the risk of penalized least square estimates with general convex

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

15

penalties. In particular, both papers obtained phase transition results based
on a key convex geometry quantity called “Gaussian squared-distences”.
However, [30] only rigorously proved the negative results (equivalent to Theorems 3.2 and 3.5) and left the positive part as a conjecture. The phase
transition results in [31] are concerned with the prediction errors ky − X β̂k22
and kXβ − X β̂k22 , rather than the estimation error kβ̂ − βk22 . Also, neither
of the two papers went beyond the first-order or phase transition analysis of
the risk.
Several researchers have also worked on the analysis of LQLS for q < 1 [32,
3, 27]. These analyses are based on non-rigorous, but widely accepted replica
method from statistical physics. The current paper extends the analysis of
[3] to q ≥ 1 case, makes the analysis rigorous by using the message passing
framework rather than the replica method, and finally provides a higher
order analysis.
4.2. Other analysis frameworks. One of the first papers that compared
the performance of penalization techniques is [33] which showed that there
exists a value of λ with which Ridge regression, i.e. LQLS with q = 2,
outperforms the vanilla least squares estimator. Since then, many more regularizers have been introduced to the literature each with a certain purpose.
For instance, we can mention LASSO [34], elastic net [35], SCAD [36], bridge
regression [1], and more recently SLOPE [37]. There has been a large body
of work on studying all these regularization techniques. We partition all the
work into the following categories and explain what in each category has
been done about the bridge regression:
(i) Simulation results: One of the main motivations for our work comes
from the nice simulation study of the bridge regression presented in
[2]. This paper finds the optimal values of λ and q by generalized cross
validation and compares the performance of the resulting estimator
with both LASSO and ridge. The main conclusion is that the bridge
regression can outperform both LASSO and ridge. Given our results
we see that if sparsity is present in β, then smaller values of q perform
better than ridge (in their second dominant term).
(ii) Asymptotic study: Knight and Fu [4] studied the asymptotic properties of bridge regression under the setting where n → ∞, while p is
fixed. They established the consistency and asymptotic normality of
the estimates under quite general conditions. Huang et al. [38] studied LQLS for q < 1 under a high-dimensional asymptotic setting in
which p grows with n but is still assumed to be less than n. They
not only derived the asymptotic distribution of the estimators, but

16

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

also proved LQLS has oracle properties in the sense of Fan and Li
[36]. They have also considered the case p > n, and have shown that
under partial orthogonality assumption on X, bridge regression distinguishes correctly between covariates with zero and non-zero coefficients. Note that under the asymptotic regime of our paper, both
LASSO and the other bridge estimators have false discoveries [39] and
possibly non-zero AMSE. Hence, they may not provide consistent estimates. We should also mention that the analysis of bridge regression
with q ∈ [0, 1) under the asymptotic regime n/p → δ is presented in
[3]. Finally, the performance of LASSO under a variety of conditions
has been studied extensively. We refer the reader to [40] for the review
of those results.
(iii) Non-asymptotic bounds: One of the successful approaches that has
been employed for studying the performance of regularization techniques such as LASSO is the minimax analysis [41], [42]. We refer the
reader to [40] for a complete list of references on this direction. In this
minimax approach, a lower bound for the prediction error or mean
square error of any estimation technique is first derived. Then a specific estimate, like the one returned by LASSO, is considered and an
upper bound is derived assuming the design matrices satisfy certain
conditions such as restrictive eigenvalue assumption [41, 43], restricted
isometry condition [44], or coherence conditions [45]. These conditions
can be confirmed for matrices with iid subgaussian elements. Based
on these evaluations, if the order of the upper bound for the estimate
under study matches the order of the lower bound, we can claim that
the estimate (e.g. LASSO) is minimax rate-optimal. This approach
has some advantages and disadvantages compared to our asymptotic
approach: (i) It works under more general conditions. (ii) It provides
information for any sample size. The price paid in the minimax analysis is that the constants derived in the results are usually not sharp
and hence many schemes have similar guarantees and cannot be compared to each other. Our asymptotic framework looses the generality
and in return gives sharp constants that can then be used in evaluating
and comparing different schemes as we do in this paper. Along similar
directions, [43] has studied the penalized empirical risk minimization
with `q penalties for the values of q ∈ [1, 1 + log1 p ] and has found upper bounds on the excess risk of these estimators (oracle inequalities).
Similar to minimax analysis, although the results of this analysis enjoy
generality, they suffer from loose constants that impede an accurate
comparisons of different bridge estimators.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

0.45

17

0.08

true value
first order approximation

0.4

true value
first order approximation

0.07

0.35

0.06

0.3

MSE

MSE

0.05
0.25
0.2

0.04
0.03

0.15
0.02

0.1

0.01

0.05
0

0

0.05

0.1

σw

0.15

0.2

0

0.25

0

0.05

(a)

0.1

σw

0.15

0.2

0.25

0.2

0.25

0.2

0.25

(b)

0.16

0.06

true value
first order approximation

0.14

true value
first order approximation

0.05

0.12
0.04

MSE

MSE

0.1
0.08

0.03

0.06
0.02
0.04
0.01
0.02
0

0

0.05

0.1

σw

0.15

0.2

0

0.25

0

0.05

(c)

0.15

0.06

true value
first order approximation

0.1

true value
first order approximation

0.05

0.04

MSE

0.08

MSE

σw

(d)

0.12

0.06

0.03

0.04

0.02

0.02

0.01

0

0.1

0

0.05

0.1

σw

(e)

0.15

0.2

0.25

0

0

0.05

0.1

σw

0.15

(f)

Fig 2. Plots of actual AMSE and its approximations for (a) δ = 1.1 and  = 0.7, (b)
δ = 1.1 and  = 0.25, (c) δ = 1.5 and  = 0.7, (d) δ = 1.5 and  = 0.25, (e) δ = 2 and
 = 0.7, (f ) δ = 2 and  = 0.25.

18

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

5. Numerical results and discussions.
5.1. Summary. The analysis of AMSE we presented in Section 3.2 is performed as σw → 0. For such asymptotic analysis, it would be interesting to
check the approximation accuracy of the first and second order expansions
of AMSE over a reasonable range of σw . Towards this goal, this section performs several numerical studies to (i) evaluate the accuracy of the first and
second order expansions discussed in Section 3.2, (ii) discover situations in
which the first order approximation is not accurate (for reasonably small
noise levels) while the second order expansion is, and (iii) identify situations
where both first and second orders are inaccurate and propose methods for
improving the approximations. Sections 5.2 and 5.3 study the performance
of LASSO and other bridge regression estimators with q > 1 respectively.
Finally, we should also mention that all the results presented in this paper
are concerned with the asymptotic setting n, p → ∞ and n/p → δ. To evaluate the accuracy of these results for finite sample sizes, we have performed
additional simulations whose results are presented in Appendix B of the
supplementary material.
5.2. LASSO. One of the conclusions from Theorem 3.3 is that the first
dominant term provides a good approximation of AMSE for the LASSO
problem when the distribution of G does not have a large mass around 0.
To test this claim we conduct the following numerical experiment. We set
the parameters of our problem instances in the following way:
1.
2.
3.
4.

δ can take any value in {1.1, 1.5, 2}.
 can take values in {0.25, 0.7}.
σw ranges within the interval [0, 0.25].
the distribution of G is specified as g(b) = 0.5δ1 (b) + 0.5δ−1 (b), where
δa (·) denotes a point mass at point a.

We then use the formula in Corollary 1 to calculate AMSE(λ∗,1 , 1, σw ). Finally, we compare AMSE(λ∗,1 , 1, σw ), computed numerically from (3.2) and
(3.3), with its first order approximation provided in Theorem 3.3. The results of this experiment are summarized in Figure 2. As is clear in this figure,
the first order expansion gives a very good approximation for AMSE over a
large range of σw .
5.3. Bridge regression estimators with q > 1. In this numerical experiment, we would like to vary σw and see under what conditions our first order
or second order expansions can lead to accurate approximation of AMSE for
a wide range of σw . Throughout this section, we set the distribution of G

19

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

0.08

0.08

true value
first order approximation
second order approximation

0.08

true value
first order approximation
second order approximation

0.07

0.06

0.05

0.05

MSE

0.06

0.05
0.04

0.04

0.04

0.03

0.03

0.03

0.02

0.02

0.02

0.01

0.01

0

0

0.05

0.1

σw

0.15

0.2

0.25

(a)

0

true value
first order approximation
second order approximation

0.07

0.06

MSE

MSE

0.07

0.01

0

0.05

0.1

σw

(b)

0.15

0.2

0.25

0

0

0.05

0.1

σw

0.15

0.2

0.25

(c)

Fig 3. Plots of actual AMSE and its approximations for (a) δ = 5,  = 0.7, q = 1.5, (b)
δ = 4,  = 0.7, q = 1.6, (c) δ = 5,  = 0.6, q = 1.8.

to g(b) = 0.5δ1 (b) + 0.5δ−1 (b), as we did in Section 5.2. We then investigate different conditions by specifying various values of other parameters in
our problem instances. The expansion of AMSE for q > 1 is presented in
Theorem 3.1. For q ∈ (1, 2), recall the two terms in the expansion below
(5.1) AMSE(λ∗,q , q, σw ) =

2
σw
δ q+1 (1 − )2 (E|Z|q )2 2q
2q
−
σ + o(σw
).
1 − 1/δ
(δ − 1)q+1 E|G|2q−2 w

We expect the first order term to present a good approximation over a
reasonably large range of σw , when the second order term is sufficiently
small. According to the analytical form of the second order term in (5.1),
it is small if the following three conditions hold simultaneously: (i) δ is
not close to 1, (ii)  is not small, and (iii) q is not close to 1. Our first
numerical result shown in Figure 3 is in agreement with this claim. In this
simulation we have set three different cases for δ,  and q so that they satisfy
the above three conditions. The non-zero elements of β are independently
drawn from 0.5δ1 (b) + 0.5δ−1 (b). As demonstrated in this figure, the first
order term approximates AMSE accurately. Another interesting finding is
that the second order expansion provides an even better approximation.
To understand the limitation of the first order approximation, we consider
the cases in which the second order term is large and suggests that at least
the first order approximation is not necessarily good. This happens when
either δ decreases to 1,  decreases to 0 or q decreases to 1. The settings of
our experiments and the results are summarized below.
1. We keep q = 1.5 and  = 0.7 fixed and study different values of
δ ∈ {5, 2, 1.5, 1.1}. Figure 4 summarizes the results of this simulation. As is clear in this figure (and is consistent with the message of
the second dominant term), as we decrease δ the first order approximation becomes less accurate. The second order approximation in these

20

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

0.08

0.14

true value
first order approximation
second order approximation

0.07

true value
first order approximation
second order approximation

0.12

0.06

0.1

MSE

MSE

0.05
0.04

0.08

0.06

0.03
0.04

0.02

0.02

0.01
0

0

0.05

0.1

σw

0.15

0.2

0

0.25

0

0.05

(a)

0.1

σw

0.15

0.2

0.25

0.2

0.25

(b)

0.2

true value
first order approximation
second order approximation

0.18
0.16

0.5

0.14

MSE

0.12

MSE

true value
first order approximation
second order approximation

0.6

0.1
0.08
0.06

0.4

0.3

0.2

0.04
0.1
0.02
0

0

0.05

0.1

σw

(c)

0.15

0.2

0.25

0

0

0.05

0.1

σw

0.15

(d)

Fig 4. Plots of actual AMSE and its approximations for q = 1.5,  = 0.7 with (a) δ = 5,
(b) δ = 2, (c) δ = 1.5 and (d) δ = 1.1.

cases is more accurate than the first order approximation. However
interestingly, the second order approximation becomes less accurate
as δ decreases too. These observations suggest that to have a good
approximation for the values of δ that are very close to 1, although
the second order approximation outperforms the first order, it may
not be sufficient and higher order terms are required. Such terms can
be derived with strategies similar to the ones we used in the proof of
Theorem 3.1. Note that the insufficiency of the second order expansion
partially results from the wide range of σw ∈ [0, 0.25]. If we evaluate
the approximation when σw is small enough, we will expect the success
of the second order expansion.
2. In our second simulation, we fix δ = 5,  = 0.4 and let q ∈ {1.8, 1.5, 1.1}.
All the simulation results are summarized in Figure 5. As we expected,
the first order approximation becomes less accurate when q decreases.
Furthermore, we notice that when q is very close to 1 (check q = 1.1
in the figure), even the second order approximation is not necessarily
good. This again calls for higher order approximation of the AMSE.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

0.03

0.03

true value
first order approximation
second order approximation

0.025

MSE

0.02

0.015

0.015

0.01

0.01

0.01

0.005

0.005

0.005

0

0

0.05

σw

(a)

0.1

0.15

0

true value
first order approximation
second order approximation

0.025

0.02

MSE

0.02

MSE

0.03

true value
first order approximation
second order approximation

0.025

0.015

21

0

0.05

σw

(b)

0.1

0.15

0

0

0.05

σw

0.1

0.15

(c)

Fig 5. Plots of actual AMSE and its approximations for δ = 5,  = 0.4 with (a) q = 1.8,
(b) q = 1.5, and (c) q = 1.1.

3. For the last simulation, we fix δ = 5, q = 1.8, and let  ∈ {0.7, 0.5, 0.3, 0.1}.
Our simulation results are presented in Figure 6. We see that as  decreases the first order approximation becomes less accurate. The second order approximation is always better than the first one. Moreover,
we observe that when  is very close to 0 (check  = 0.1 in the figure),
even the second order approximation is not necessarily sufficient. As
we discussed in the previous two simulations, we might need higher
order approximation of the AMSE in such cases.
5.4. Discussion. Firstly, our numerical studies confirm that the first order term gives good approximations of AMSE for LASSO in the case where
the distribution of non-zero elements of β is bounded away from zero. Secondly, as the numerical results for q > 1 demonstrate, while the second order
approximation always improves over the first order term and works well in
many cases, in the following situations it may not provide very accurate
evaluation of AMSE: (i) when δ is close to 1, (ii)  is close to zero, and (iii)
q is close to 1. In such cases, the value of the second order term becomes
large and hence the approximation is only accurate for very small value of
σw . The remedy that one can propose is to derive higher order expansions.
Such terms can be calculated with the same strategy that we used to obtain
the second dominant term.
6. Proof of Theorem 3.3. Due to the limited space in the main text,
we only present the proof of Theorem 3.3, one of our main results for LASSO,
in this section. The proofs of all the other results are deferred to the supplementary material. Although some techniques used in the proofs are quite
different for LASSO and LQLS with q ∈ (1, 2], the roadmap remains the
same. Hence we suggest readers to first read the proof in this section. Once

22

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

0.03

0.03

true value
first order approximation
second order approximation

0.025

0.02

MSE

MSE

0.02

0.015

0.015

0.01

0.01

0.005

0.005

0

true value
first order approximation
second order approximation

0.025

0

0.05

σw

0.1

0

0.15

0

0.05

(a)

0.15

0.03

true value
first order approximation
second order approximation

true value
first order approximation
second order approximation

0.025

0.02

MSE

0.02

MSE

0.1

(b)

0.03

0.025

0.015

0.015

0.01

0.01

0.005

0.005

0

σw

0

0.05

σw

(c)

0.1

0.15

0

0

0.05

σw

0.1

0.15

(d)

Fig 6. Plots of actual AMSE and its approximations for δ = 5 and q = 1.8 with (a)
 = 0.7, (b)  = 0.5, (c)  = 0.3, and (d)  = 0.1.

this relatively simple proof is clear, the other more complicated proofs will
be easier to read.
6.1. Roadmap of the proof. Since the proof of this result has several steps
and is long, we lay out the roadmap of the proof here to help readers navigate through the details. According to Corollary 1 (let us accept Corollary
1 for the moment; its proof will be fully presented in Appendix E of the
supplement), in order to evaluate AMSE(λ∗,1 , 1, σw ) as σw → 0, the crucial
step is to characterize σ̄ from the following equation
(6.1)

σ̄ 2 = σω2 +

1
min EB,Z [(η1 (B + σ̄Z; χ) − B)2 ].
δ χ≥0

To study (6.1), the key part is to analyze the term minχ≥0 EB,Z [(η1 (B +
σ̄Z; χ)−B)2 ]. A useful fact that we will prove in Section 6.4 can simplify the
analysis of (6.1): The condition δ > M1 () implies that σ̄ → 0, as σw → 0.
Hence one of the main steps of this proof is to derive the convergence rate of
minχ≥0 EB,Z [(η1 (B + σZ; χ) − B)2 ], as σ → 0. Once we obtain that rate, we
then characterize the convergence rate for σ̄ as σw → 0 from (6.1). Finally
we connect σ̄ to AMSE(λ∗,1 , 1, σw ) based on Corollary 1, and derive the

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

23

expansion for AMSE(λ∗,1 , 1, σw ) as σw → 0. We introduce the following
notations:
R(χ, σ) = EB,Z [(η1 (B/σ + Z; χ) − B/σ)2 ],

χ∗ (σ) = arg min R(χ, σ),
χ≥0

where we have suppressed the subscript B, Z in E for notational simplicity.
According to [46], R(χ, σ) is a quasi-convex function of χ and has a unique
global minimizer. Hence χ∗ (σ) is well defined. It is straightforward to confirm
min EB,Z [(η1 (B + σZ; χ) − B)2 ] = σ 2 R(χ∗ (σ), σ).
χ≥0

Throughout the proof, we may write χ∗ for χ∗ (σ) when no confusion is
caused, and we use F (g) to denote the distribution function of |G|. The rest
of the proof of Theorem 3.3 is organized in the following way:
1. We first prove R(χ∗ (σ), σ) → M1 (), as σ → 0 in Section 6.2.
2. We further bound the convergence rate of R(χ∗ (σ), σ) in Section 6.3.
3. We finally utilize the convergence rate bound derived in Section 6.3 to
characterize the convergence rate of σ̄ and then derive the expansion
for AMSE(λ∗,1 , 1, σw ) in Section 6.4.
6.2. Proof of R(χ∗ (σ), σ) → M1 (), as σ → 0. Our goal in this section
is to prove the following lemma.
Lemma 3.

Suppose E|G|2 < ∞, then limσ→0 χ∗ (σ) = χ∗∗ and

lim R(χ∗ (σ), σ) = (1 − )E(η1 (Z; χ∗∗ ))2 + (1 + (χ∗∗ )2 ),

σ→0

where χ∗∗ is the unique minimizer of (1 − )E(η1 (Z; χ))2 + (1 + χ2 ) over
[0, ∞), and Z ∼ N (0, 1).
Proof. By taking derivatives, it is straightforward to verify that (1 −
)E(η1 (Z; χ))2 + (1 + χ2 ), as a function of χ over [0, ∞), is strongly convex
and has a unique minimizer. Hence χ∗∗ is well defined.
We first claim that χ∗ (σn ) is bounded for any given sequence σn → 0.
Otherwise there exists an unbounded subsequence χ∗ (σnk ) → +∞ with
σnk → 0. Since the distribution of G does not have point mass at zero and
η1 (G/σnk + Z; χ∗ (σnk )) = sign(G/σnk + Z)(|G/σnk + Z| − χ∗ (σnk ))+ ,
it is not hard to conclude that
|η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk | → +∞, a.s.

24

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

By Fatou’s lemma, we then have
(6.2) R(χ∗ (σnk ), σnk ) ≥ E(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk )2 → +∞.
On the other hand, the optimality of χ∗ (σnk ) implies
R(χ∗ (σnk ), σnk ) ≤ R(0, σnk ) = 1,
contradicting the unboundedness in (6.2).
We next show the sequence χ∗ (σn ) converges to a finite constant, for any
σn → 0. Taking a convergent subsequence χ∗ (σnk ), due to the boundedness
of χ∗ (σn ), the limit of the subsequence is finite. Call it χ̃. Note that
E(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk )2
= 1 + E(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk − Z)2 +
2EZ(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk − Z).
Since η1 (u; χ) = sign(u)(|u| − χ)+ , we have the following three inequalities:
|η1 (Z; χ∗ (σnk ))|2 ≤ |Z|2 ,
(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk − Z)2 ≤ (χ∗ (σnk ))2 ,
|Z(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk − Z)| ≤ |Z|χ∗ (σnk ).
Furthermore, all the terms on the right hand side of the above inequalities
are integrable. Therefore we can apply the Dominated Convergence Theorem
(DCT) to obtain
lim R(χ∗ (σnk ), σnk )

nk →∞

= lim (1 − )E(η1 (Z; χ∗ (σnk )))2 + E(η1 (G/σnk + Z; χ∗ (σnk )) − G/σnk )2
nk →∞

= (1 − )E(η1 (Z; χ̃))2 + (1 + χ̃2 ).
Moreover, since χ∗ (σnk ) is the optimal threshold value for R(χ, σnk ),
lim R(χ∗ (σnk ), σnk ) ≤ lim R(χ∗∗ , σnk ) = (1−)E(η1 (Z; χ∗∗ ))2 +(1+(χ∗∗ )2 )

nk →∞

nk →∞

Combining the last two limiting results, we can conclude χ̃ = χ∗∗ . Since
χ∗ (σnk ) is an arbitrary convergent subsequence, this implies that the sequence χ∗ (σn ) converges to χ∗∗ as well. This is true for any σn → 0, hence
χ∗ (σ) → χ∗∗ , as σ → 0. limσ→0 R(χ∗ (σ), σ) can then be directly derived.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

25

6.3. Bounding the convergence rate of R(χ∗ (σ), σ). In Section 6.2 we
have shown R(χ∗ (σ), σ) → M1 () as σ → 0. Our goal in this section is to
bound the difference R(χ∗ (σ), σ) − M1 (). For that purpose, we first bound
the convergence rate of χ∗ (σ).
Lemma 4. Suppose P(|G| ≥ µ) = 1 with µ being a positive constant and
E|G|2 < ∞, then as σ → 0
|χ∗ (σ) − χ∗∗ | = O(φ(−µ/σ + χ∗∗ )),
where φ(·) is the density function of the standard normal.
Proof. Since χ∗ (σ) minimizes R(χ, σ), we have
gives the following expression for χ∗ (σ):
χ∗ (σ) =

∂R(χ∗ (σ),σ)
∂χ

= 0, which

2(1 − )φ(χ∗ ) + Eφ(χ∗ − G/σ) + Eφ(χ∗ + G/σ)
.
R −χ∗ −G/σ
R∞
R∞
φ(z)dz
2(1 − ) χ∗ φ(z)dz + E χ∗ −G/σ φ(z)dz + E −∞

Letting σ go to zero on both sides in the above equation, we then obtain
χ∗∗ =

2(1 − )φ(χ∗∗ )
R∞
,
2(1 − ) χ∗∗ φ(z)dz + 

where we have applied Dominated Convergence Theorem (DCT). To bound
|χ∗ (σ) − χ∗∗ |, we first bound the convergence rate of the terms in the expression of χ∗ (σ). A direct application of the mean value theorem leads to
φ(χ∗ ) − φ(χ∗∗ ) = (χ∗∗ − χ∗ )χ̃φ(χ̃),
Z ∞
Z ∞
˜
φ(z)dz −
φ(z)dz = (χ∗∗ − χ∗ )φ(χ̃),

(6.3)
(6.4)

χ∗

χ∗∗

˜ being two numbers between χ∗ and χ∗∗ . We now consider the
with χ̃, χ̃
other four terms. By the condition P(|G| ≥ µ) = 1, we can conclude that for
sufficiently small σ
(6.5)

Eφ(χ∗ − G/σ) ≤ Eφ(χ∗ − |G|/σ) ≤ φ(µ/σ − χ∗ ),

(6.6)

Eφ(χ∗ + G/σ) ≤ Eφ(χ∗ − |G|/σ) ≤ φ(µ/σ − χ∗ ).

Moreover, it is not hard to derive
Z ∞
Z
(6.7) 1 − E
φ(z)dz − E
Z

∞Z

χ∗ −G/σ
χ∗ −g/σ

−χ∗ −G/σ

φ(z)dz

−∞

Z

χ∗ −µ/σ

φ(z)dzdF (g) ≤

=
0

−χ∗ −g/σ

−χ∗ −µ/σ

φ(z)dz ≤ 2χ∗ φ(µ/σ − χ∗ ),

26

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

where to obtain the last two inequalities we have used the condition P(|G| ≥
µ) = 1 and the fact χ∗ − µ/σ < 0 for σ small enough. We are now in the
position to bound |χ∗ (σ) − χ∗∗ |. Define the following notations:
Z
e1 , E

∞

Z

−χ∗ −G/σ

φ(z)dz − ,

φ(z)dz + E
χ∗ −G/σ
∗

−∞
∗

e2 , Eφ(χ − G/σ) + Eφ(χ + G/σ),
Z ∞
S , 2(1 − )φ(χ∗∗ ), T , 2(1 − )
φ(z)dz + .
χ∗∗

Using the new notations and Equations (6.3) and (6.4), we obtain
χ∗ (σ) =

S + 2(1 − )(χ∗∗ − χ∗ )χ̃φ(χ̃) + e2
,
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ )φ(χ̃)

χ∗∗ =

S
.
T

Hence we can do the following calculations:
χ∗ (σ) − χ∗∗ =
=

=
(6.8)

S + 2(1 − )(χ∗∗ − χ∗ )χ̃φ(χ̃) + e2
S
−
∗∗
∗
˜ + e1
T
T + 2(1 − )(χ − χ )φ(χ̃)
∗∗
∗
2(1 − )(χ − χ )χ̃φ(χ̃) + e2
−
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ )φ(χ̃)
˜ + e1 )
S(2(1 − )(χ∗∗ − χ∗ )φ(χ̃)
˜ + e1 )
T (T + 2(1 − )(χ∗∗ − χ∗ )φ(χ̃)
˜
2(1 − )(χ∗∗ − χ∗ )(χ̃φ(χ̃) − χ∗∗ φ(χ̃))
+
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ )φ(χ̃)
e2 − χ∗∗ e1
.
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ )φ(χ̃)

From (6.8) we obtain

˜
2(1 − )(χ̃φ(χ̃) − χ∗∗ φ(χ̃))
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ (σ))φ(χ̃)
∗∗
e2 − χ e1
.
˜ + e1
T + 2(1 − )(χ∗∗ − χ∗ (σ))φ(χ̃)


(χ (σ) − χ ) 1 +
∗

(6.9)
=

∗∗

˜ → χ∗∗ since
Note that in the above expression we have χ̃ → χ∗∗ and χ̃
∗
∗∗
∗∗
˜
χ (σ) → χ . Therefore, we conclude that χ̃φ(χ̃) − χ φ(χ̃) → 0 and (χ∗∗ −
˜ → 0. Moreover, since (6.5), (6.6) and (6.7) together show both
χ∗ (σ))φ(χ̃)
e1 and e2 go to 0 exponentially fast, we conclude from (6.9) that (χ∗ (σ) −

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

27

χ∗∗ )/σ → 0. This enables us to proceed
|e2 − χ∗∗ e1 |
|χ∗ (σ) − χ∗∗ |
|χ∗ (σ) − χ∗∗ | (a)
=
lim
=
lim
σ→0 T φ(µ/σ − χ∗ )
σ→0 φ(µ/σ − χ∗∗ )
σ→0 φ(µ/σ − χ∗ )
lim

(b)

≤

2(1 + χ∗ (σ)χ∗∗ )φ(µ/σ − χ∗ )
2(1 + (χ∗∗ )2 )
=
.
σ→0
T φ(µ/σ − χ∗ )
T
lim

We have used (6.9) to obtain (a). We derived (b) by the following steps:
1. According to (6.7), |e1 | ≤ 2χ∗ φ(µ/σ − χ∗ ).
2. According to (6.5) and (6.6), |e2 | ≤ 2φ(µ/σ − χ∗ ).
This completes the proof of Lemma 4.
The next step is to bound the convergence rate of R(χ∗ (σ), σ) based on
the convergence rate of χ∗ (σ) we have derived in Lemma 4.
Lemma 5. Suppose P(|G| ≥ µ) = 1 with µ being a positive constant and
E|G|2 < ∞, then as σ → 0
|R(χ∗ (σ), σ) − M1 ()| = O(φ(µ/σ − χ∗∗ )),
where φ(·) is the density function of the standard normal.
Proof. We recall the two quantities:
M1 () = (1 − )E(η1 (Z; χ∗∗ ))2 + (1 + (χ∗∗ )2 ),

(6.10)

R(χ∗ (σ), σ) = (1 − )E(η1 (Z; χ∗ ))2 +
[1 + E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 ]
+2EZ(η1 (G/σ + Z; χ∗ ) − G/σ − Z).

(6.11)

We bound |R(χ∗ (σ), σ) − M1 ()| by bounding the difference between the
corresponding terms in (6.11) and (6.10). From the proof of Lemma 4 we
know e1 < 0 and e2 > 0. Hence (6.9) implies χ∗ (σ) > χ∗∗ for small enough
σ. We start with
|E(η1 (Z; χ∗ ))2 − E(η1 (Z; χ∗∗ ))2 |

(6.12)
=

|E(η1 (Z; χ∗ ) − η1 (Z; χ∗∗ ))(η1 (Z; χ∗ ) + η1 (Z; χ∗∗ ))|

≤

E[|χ∗ − χ∗∗ + χ∗ I(|Z| ∈ (χ∗∗ , χ∗ ))| · |η1 (Z; χ∗ ) + η1 (Z; χ∗∗ )|]

(a)

≤

2(χ∗ − χ∗∗ ) · E|Z| + 2χ∗ E[I(|Z| ∈ (χ∗∗ , χ∗ ))|Z|]

≤

2(χ∗ − χ∗∗ ) · E|Z| + 4χ∗ (χ∗ − χ∗∗ )χ̃φ(χ̃) = O(φ(µ/σ − χ∗∗ )),

28

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

where we have used the fact |η1 (u; χ)| ≤ |u| to obtain (a); χ̃ is a number
between χ∗ (σ) and χ∗∗ ; and the last equality is due to Lemma 4. We next
bound the difference between E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 and (χ∗∗ )2 :
(6.13)

|(χ∗∗ )2 − E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 |
≤ |(χ∗ )2 − E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 | + |(χ∗∗ )2 − (χ∗ )2 |.

To bound the two terms on the right hand side of (6.13), first note that
0 ≤ (χ∗ )2 − E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2
= E[I(|G/σ + Z| ≤ χ∗ ) · ((χ∗ )2 − (G/σ + Z)2 )]
Z ∞ Z −g/σ+χ∗
φ(z)dzdF (g)
≤ (χ∗ )2
0
(b)

≤ (χ∗ )2

(6.14)

Z

−g/σ−χ∗
−µ/σ+χ∗

φ(z)dz ≤ 2(χ∗ )3 φ(µ/σ − χ∗ )

−µ/σ−χ∗
∗∗

= O(φ(µ/σ − χ )),

where (b) is due to the condition P(|G| ≥ µ) = 1, and the last equality holds
since (χ∗ − χ∗∗ )/σ → 0 implied by Lemma 4. Furthermore, Lemma 4 yields
(6.15)

(χ∗ )2 − (χ∗∗ )2 = O(φ(µ/σ − χ∗∗ )).

Combining (6.13), (6.14), and (6.15), we obtain
(6.16)

|(χ∗∗ )2 − E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 | = O(φ(µ/σ − χ∗∗ )).

Regarding the remaining term in R(χ∗ (σ), σ), we can derive
0 ≤ EZ(G/σ + Z − η1 (G/σ + Z; χ∗ ))
(c)

= E(1 − ∂1 η1 (G/σ + Z; χ∗ ))

(6.17)

(d)

= P(|G/σ + Z| ≤ χ∗ ) = O(φ(µ/σ − χ∗∗ )).

We have employed Stein’s lemma (see Lemma 11 in the supplement) to
obtain (c). Equality (d) holds due to (6.7). Putting the results (6.12), (6.16),
and (6.17) together finishes the proof.
6.4. Deriving the expansion of AMSE(λ∗,1 , 1, σw ). In this section we utilize the convergence rate result of R(χ∗ (σ), σ) from Section 6.3 to derive the
expansion of AMSE(λ∗,1 , 1, σw ) in (3.6), and thus finish the proof of Theorem 3.3. Towards that goal, we first prove a useful lemma.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

Lemma 6.
(6.18)

29

Let σ̄ be the solution to the following equation:
σ̄ 2 = σω2 +

1
min EB,Z [(η1 (B + σ̄Z; χ) − B)2 ].
δ χ≥0

Suppose δ > M1 (), then
2
σw
δ − M1 ()
=
.
2
σw →0 σ̄
δ

lim

Proof. We first claim that E(η1 (α + Z; χ) − α)2 is an increasing function
of α, because
d
E(η1 (α + Z; χ) − α)2 = 2E(αI(|α + Z| ≤ χ)) ≥ 0.
dα
Hence we obtain
(6.19) E(η1 (α + Z; χ) − α)2 ≤ lim E(η1 (α + Z; χ) − α)2 = 1 + χ2 .
α→∞

Inequality (6.19) then yields
R(χ, σ̄) = (1 − )E(η1 (Z; χ))2 + E(η1 (G/σ̄ + Z; χ) − G/σ̄)2
≤ (1 − )E(η1 (Z; χ))2 + (1 + χ2 ).
Taking minimum over χ on both sides above gives us
R(χ∗ (σ̄), σ̄) ≤ M1 ().

(6.20)

Moreover, since σ̄ is the solution of (6.18), it satisfies
2
σ̄ 2 = σw
+

(6.21)

σ̄ 2
R(χ∗ (σ̄), σ̄).
δ

Combining (6.20) and (6.21) with the condition δ > M1 (), we have
σ̄ 2 ≤

2
σw
,
1 − M1 ()/δ

which leads to σ̄ → 0, as σw → 0. Then applying Lemma 3 shows
lim R(χ∗ (σ̄), σ̄) = lim R(χ∗ (σ̄), σ̄) = M1 ().

σw →0

σ̄→0

Diving both sides of (6.21) by σ̄ 2 and letting σw → 0 finishes the proof.

30

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

To complete the proof of Theorem 3.3, first note that Corollary 1 tells us
AMSE(λ∗,1 , 1, σw ) = σ̄ 2 R(χ∗ (σ̄), σ̄),

2
σw
= σ̄ 2 −

σ̄ 2
R(χ∗ (σ̄), σ̄).
δ

We then have
(6.22)

δM1 () 2
σ
δ − M1 () w


δM1 ()
σ̄ 2
2
∗
2
∗
= σ̄ R(χ (σ̄), σ̄) −
· σ̄ − R(χ (σ̄), σ̄)
δ − M1 ()
δ
δ(R(χ∗ (σ̄), σ̄) − M1 ()) 2 (a)
σ̄ = O(σ̄ 2 φ(µ/σ̄ − χ∗∗ )),
=
δ − M1 ()
AMSE(λ∗,1 , 1, σw ) −

2

where (a) is due to Lemma 5. Finally, since limσw →0 σσ̄w2 = δ−Mδ 1 () according
to Lemma 6, it is not hard to see
r
  δ − M () µ̃ 
1
(6.23) O(σ̄ 2 φ(µ/σ̄ − χ∗∗ )) = o(φ(µ̄/σ̄)) = o φ
,
δ
σw
where µ̄ and µ̃ are any constants satisfying 0 ≤ µ̃ < µ̄ < µ. Results (6.22)
and (6.23) together close the proof of Theorem 3.3.
Remark: (6.20) and (6.22) together imply that the second dominant term
of AMSE(λ∗,1 , 1, σw ) is in fact negative.
Acknowledgements. This work is supported by NSF grant CCF-1420328.
References.
[1] L. Frank and J. Friedman. A statistical view of some chemometrics regression tools.
Technometrics, 35(2):109–135, 1993.
[2] W. Fu. Penalized regressions: the bridge versus the lasso. J. Comp. Graph. Stat,
7(3):397–416, 1998.
[3] L. Zheng, A. Maleki, H. Weng, X. Wang, and T. Long. Does `p -minimization outperform `1 -minimization? Preprint. arXiv:1501.03704v2, 2016.
[4] K. Knight and W. Fu. Asymptotics for lasso-type estimators. Annals of statistics,
pages 1356–1378, 2000.
[5] D. Donoho and J. Tanner. Sparse nonnegative solution of underdetermined linear
equations by linear programming. Proc. Natl. Acad. Sci., 102(27):9446–9451, 2005.
[6] D. Donoho, A. Maleki, and A. Montanari. Message-passing algorithms for compressed
sensing. Proc. Natl Acad. Sci., 106(45):18914–18919, 2009.
[7] D. Amelunxen, M. Lotz, M. McCoy, and J. Tropp. Living on the edge: Phase transitions in convex programs with random data. Info. Infer., 2014.
[8] N. El Karoui, D. Bean, P. Bickel, C. Lim, and B. Yu. On robust regression with
high-dimensional predictors. Proc. Natl Acad. Sci., 110(36):14557–14562, 2013.
[9] J. Bradic and J. Chen. Robustness in sparse linear models: relative efficiency based
on robust approximate message passing. arXiv preprint arXiv:1507.08726, 2015.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

31

[10] M. Stojnic. Various thresholds for `1 -optimization in compressed sensing. arXiv
preprint arXiv:0907.3666, 2009.
[11] D. L. Donoho, A. Maleki, and A. Montanari. Noise sensitivity phase transition. IEEE
Trans. Inform. Theory, 57(10):6920–6941, Oct. 2011.
[12] M. Bayati and A. Montanri. The dynamics of message passing on dense graphs, with
applications to compressed sensing. IEEE Trans. Inform. Theory, 57(2), Feb. 2011.
[13] M. Bayati and A. Montanari. The LASSO risk for Gaussian matrices. IEEE Trans
Inform Theory, 58(4):1997–2017, 2012.
[14] H. Weng, A. Maleki, and L. Zheng. Overcoming The Limitations of Phase Transition
by Higher Order Analysis of Regularization Techniques. ArXiv e-prints, March 2016.
[15] D. Donoho. For most underdetermined systems of linear equations, the minimal `1 norm approximates the sparsest near-solution. Comm. Pure and Appl. Math, 2004.
[16] D. Donoho. High-dimensional centrally symmetric polytopes with neighborliness
proportional to dimension. Discrete & Computational Geometry, 35(4):617–652, 2006.
[17] D. Donoho and J. Tanner. Neighborliness of randomly projected simplices in high
dimensions. Proc. Natl Acad. Sci., 102(27):9452–9457, 2005.
[18] D. Guo and S. Verdú. Randomly spread cdma: Asymptotics via statistical physics.
IEEE Trans. Inform. Theory, 51(6):1983–2010, 2005.
[19] T. Tanaka. A statistical-mechanics approach to large-system analysis of cdma multiuser detectors. IEEE Trans. Info. Theory, 48(11):2888–2910, 2002.
[20] A. Coolen. The Mathematical Theory of Minority Games: Statistical Mechanics of
Interacting Agents (Oxford Finance Series). Oxford University Press, Inc., 2005.
[21] C. Thrampoulidis, E. Abbasi, and B. Hassibi. Precise error analysis of regularized
m-estimators in high-dimensions. arXiv preprint arXiv:1601.06233, 2016.
[22] N. Karoui. Asymptotic behavior of unregularized and ridge-regularized highdimensional robust regression estimators: rigorous results.
arXiv preprint
arXiv:1311.2445, 2013.
[23] D. Donoho and A. Montanari. High dimensional robust m-estimation: Asymptotic
variance via approximate message passing. Prob. Theo. Rel. Fields, pages 1–35, 2013.
[24] D. Donoho, M. Gavish, and A. Montanari. The phase transition of matrix recovery
from gaussian measurements matches the minimax mse of matrix denoising. Proceedings of the National Academy of Sciences, 110(21):8405–8410, 2013.
[25] D. Donoho and A. Montanari. Variance breakdown of huber (m)-estimators: n/p →
m. 2015.
[26] D. Donoho, A. Maleki, and A. Montanari. The noise-sensitivity phase transition in
compressed sensing. IEEE Trans. Info. Theory, 57(10), 2011.
[27] S. Rangan, V. Goyal, and A. Fletcher. Asymptotic analysis of map estimation via
the replica method and compressed sensing. In Advances in Neural Information
Processing Systems, pages 1545–1553, 2009.
[28] F. Krzakala, M. Mézard, F. Sausset, Y. Sun, and L. Zdeborová. Statistical-physicsbased reconstruction in compressed sensing. Physical Review X, 2(2):021005, 2012.
[29] A. Maleki. Approximate message passing algorithms for compressed sensing. Ph.D.
thesis, Stanford University, 2010.
[30] Samet Oymak, Christos Thrampoulidis, and Babak Hassibi. The squared-error of
generalized lasso: A precise analysis. In Communication, Control, and Computing
(Allerton), 2013 51st Annual Allerton Conference on, pages 1002–1009. IEEE, 2013.
[31] Samet Oymak and Babak Hassibi. Sharp mse bounds for proximal denoising. Foundations of Computational Mathematics, 16(4):965–1029, 2016.
[32] Y. Kabashima, T. Wadayama, and T. Tanaka. A typical reconstruction limit for
compressed sensing based on lp-norm minimization. Journal of Statistical Mechanics:

32

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Theory and Experiment, 2009(09):L09003, 2009.
[33] A. Hoerl and R. Kennard. Ridge regression: Biased estimation for nonorthogonal
problems. Technometrics, 12(1):55–67, 1970.
[34] R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal
Statistical Society. Series B, pages 267–288, 1996.
[35] H. Zou and T. Hastie. Regularization and variable selection via the elastic net.
Journal of the Royal Statistical Society: Series B, 67(2):301–320, 2005.
[36] J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle
properties. Journal of the American statistical Association, 96(456):1348–1360, 2001.
[37] M. Bogdan, E. van den Berg, C. Sabatti, W. Su, and E. Candès. Slope:adaptive
variable selection via convex optimization. Annals App. Stat., 9(3):1103, 2015.
[38] J. Huang, J. Horowitz, and S. Ma. Asymptotic properties of bridge estimators in
sparse high-dimensional regression models. Annals Stat., pages 587–613, 2008.
[39] W. Su, M. Bogdan, and E. Candes. False discoveries occur early on the lasso path.
arXiv preprint arXiv:1511.01957, 2015.
[40] P. Bühlmann and S. Van De Geer. Statistics for high-dimensional data: methods,
theory and applications. Springer Science & Business Media, 2011.
[41] P. Bickel, Y. Ritov, and A. Tsybakov. Simultaneous analysis of lasso and dantzig
selector. Annals Stat., pages 1705–1732, 2009.
[42] G. Raskutti, M. Wainwright, and B. Yu. Minimax rates of estimation for highdimensional linear regression over-balls. IEEE Trans. Info. Theory, 57(10), 2011.
[43] V. Koltchinskii. Sparsity in penalized empirical risk minimization. In Annales de
l’IHP Probabilités et statistiques, volume 45, pages 7–57, 2009.
[44] E. Candès. The restricted isometry property and its implications for compressed
sensing. Comptes Rendus Mathematique, 346(9):589–592, 2008.
[45] F. Bunea, A. Tsybakov, and M. Wegkamp. Sparsity oracle inequalities for the lasso.
Electronic Journal of Statistics, 1:169–194, 2007.
[46] Ali Mousavi, Arian Maleki, and Richard G Baraniuk. Consistent parameter estimation for lasso and approximate message passing. Annals of Statistics. To appear.
[47] N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3):127–239, 2014.
[48] C. Stein. Estimation of the mean of a multivariate normal distribution. The Annals
of Statistics, pages 1135–1151, 1981.
[49] ZD Bai and YQ Yin. Limit of the smallest eigenvalue of a large dimensional sample
covariance matrix. The annals of Probability, pages 1275–1294, 1993.
[50] Boris Sergeevich Kashin. Diameters of some finite-dimensional sets and classes of
smooth functions. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya,
41(2):334–351, 1977.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

33

Supplementary material
APPENDIX A: ORGANIZATION
This supplement contains simulations and all the proof of lemmas and
theorems that have not been covered in the main text. We outline the structure of the supplement to help readers find the materials they are interested
in. The organization is as follows:
1. Appendix B contains additional simulation results. These numerical
experiments evaluate the accuracy of AMSE(λ∗,q , q, σw ) as an asymptotic prediction for finite-sample mean square error (MSE). Along this
line, the convergence rate of MSE is empirically verified.
2. Appendix C covers several important properties of the proximal operator function ηq (u; χ). These properties will later be used in our proofs.
It includes Lemmas 7, 8, 9, 10 and their proofs.
3. Appendix D proves Lemma 2 from the main text. This lemma is concerned with the uniquesness of the solution of (2.2) and (2.3). Lemmas
7, 8, 9, 10 from Appendix C are extensively used here.
4. Appendix E proves Corollary 1 in the main text. This corollary characterizes AMSE when the regularization parameter λ is optimally tuned.
This appendix uses Lemma 12 from Appendix D.
5. Appendix F includes the proof of Theorem 3.1, one of the main results in this paper. The theorem derives the second order expansion of
AMSE(λ∗,q , q, σw ) for q ∈ (1, 2]. We recommend interested readers to
read the proof in Section 6 before Appendix F.
6. Appendix G contains the proof of Theorem 3.2. This theorem identifies
the necessary condition for successful recovery with q ∈ (1, 2]. Phase
transition is implied by this theorem together with Theorem 3.1.
7. Appendix H proves Theorem 3.4. The proof of this theorem is along
the same lines as the proof of Theorem 3.3 presented in Section 6 of the
main text. We suggest the reader to study Section 6 before studying
this section.
8. Appendix I proves Theorem 3.5. The proof is essentially the same as
the proof of Theorem 3.2. Since we do not repeat the detailed arguments, readers may want to study Appendix G first.

34

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

9. Appendix J includes the proof of Theorem 2.1. Though Theorem 2.1
lays the first step towards analyzing the AMSE, we postpone the proof
to the end of the supplement. That is because the focus of this paper
is on the second order dominant term of AMSE and we do not want to
move the proof of this theorem ahead to potentially digress from the
highlights. Moreover, since the key ideas of this proof are similar to
those of [13], we will not detail out the entire proof and rather describe
several key steps. Note that in this proof we will use some results we
have developed in Appendices C and D.
APPENDIX B: ADDITIONAL NUMERICAL RESULTS
This section contains additional numerical studies to examine the relation
between AMSE and its finite-sample version. Throughout the simulations,
we fix the sparsity level  = 0.4 and the distribution of G to g(b) = 0.5δ1 (b)+
0.5δ−1 (b). We also let the elements of X be i.i.d from N (0, 1/n), and the
i.i.d

2 ). The other parameters of our problem instances are
noise wi ∼ N (0, σw
set in the following way:

1.
2.
3.
4.

δ takes values in {1.5, 3, 5}
p takes any value in {20, 50, 200, 400}
q is chosen to be one of {1, 1.5, 1.8, 2}
σw ranges over [0, 0.15]

Given the values of , G, δ, σw and q, we compute AMSE(λ∗,q , q, σw ) according to the formulas in Corollary 1 from the main text. We also generate sami.i.d
ples from linear models by setting n = δp, {βi }pi=1 ∼ (1−)δ0 +G. We then
calculate the finite-sample MSE (under optimal tuning): inf λ≥0 kβ̂(λ, q) −
βk22 /p. The same experiment is repeated 200 times. For completeness, we
have included the first-order and second-order expansions of AMSE. The results are shown in Figures 7-15. We summarize our observations and findings
below.
• Figures 7-9 are about the case δ = 5. Figure 7 shows that the averaged
MSE is well matched with AMSE even when p is around 200 or 400.
This is true for different values of q as σw varies over [0, 0.15]. Even
for p = 20, the averaged MSE is already quite close to AMSE when
σw < 0.075. As confirmed by the simulations of Section 5 in the main
text, we see again that the first-order approximation for LASSO is very
accurate, and so is the second-order approximation for other values of
q.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

35

2 over the
• Figure 8 draws the standard deviation of MSE against σw
2
range [0, 0.15 ]. The plots with different values of q and p all indicate
that the standard deviation scales linearly with the noise variance
2 . Intuitively speaking, due to the quadratic form of MSE, its linear
σw
2 is somewhat expected.
scaling with σw
p
• In Figure 9, we multiply the standard deviation (SD) by p/20 and
2 . Interestingly, all the adjusted SD’s
plot the adjusted SD against σw
(with the same value of q) are aligned around the same straight line.
√
It implies that the scaling of SD on the dimension p is 1/ p, and the
√
convergence rate of MSE is n (recall n = δp). We leave a rigorous
proof of this empirical result for future research.

• Figures 10-12 are concerned with the case δ = 3. Compared with
Figures 7-9, it is seen that the observations we have made for δ = 5
still hold in δ = 3. We hence do not repeat the details.
• Figures 13-15 are for the scenario δ = 1.5. As the value of δ is decreased
to 1.5, the main messages we reveal in the case δ = 5 carry over. But
some details may change. For instance, only when p = 400 the difference between the averaged MSE and AMSE is negligible throughout
all the values of q and σw . Also, the linear pattern between SD (or
2 is less significant than when δ = 5. Given that
adjusted SD) and σw
for a fixed p smaller values of δ lead to smaller number of observations
(and hence less number of random elements in the design matrix),
these changes should not come as a surprise. In the language of statistical physics, since the the number of random elements in the system
decreases self averaging has not happened yet.
APPENDIX C: PRELIMINARIES ON ηq (u; χ)
This section is devoted to the properties of ηq (u; χ) defined as
1
ηq (u; χ) , arg min (u − z)2 + χ|z|q .
2
z
We start with some basic properties of these functions. Since the explicit
forms of ηq (u; χ) for q = 1 and 2 are known: η1 (u; χ) = (|u|−χ)sign(u)I(|u| >
u
χ), η2 (u; χ) = 1+2χ
, we focus our study on the case 1 < q < 2.
Lemma 7.

ηq (u; χ) satisfies the following properties:

(i) u − ηq (u; χ) = χqsign(u)|ηq (u; χ)|q−1 .
(ii) |ηq (u; χ)| ≤ |u|.

36

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

MSE

0.020

0.020
0.015

0.010

0.010

0.000

0.000

0.005

MSE

q=1.5
0.030

q=1
true value
first order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.00

0.05

σw

0.10

0.15

0.00

0.05

q=1.8

0.15

0.10

0.15

0.000

0.010

MSE

0.020

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.010

0.020

0.10

q=2

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.000

MSE

σw

0.00

0.05

σw

0.10

0.15

0.00

0.05

σw

Fig 7. Plots of actual AMSE, its approximations, and finite-sample MSE. The MSE is
averaged over 200 times. The setup is δ = 5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

(iii)
(iv)
(v)
(vi)

limχ→0 ηq (u; χ) = u and limχ→∞ ηq (u; χ) = 0.
ηq (−u; χ) = −ηq (u; χ).
For α > 0, we have ηq (αu; α2−q χ) = αηq (u; χ).
|ηq (u; χ) − ηq (ũ, χ)| ≤ |u − ũ|.

Proof. To prove (i), we should take the derivative of 21 (u − z)2 + χ|z|q
and set it to zero. Proofs of parts (ii), (iii) and (iv) are straightforward and

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

q=1.5
0.008

p=20
p=50
p=200
p=400

SD

0.006

p=20
p=50
p=200
p=400

0.000

0.000

0.002

0.004

0.004
0.002

SD

0.006

0.008

q=1

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

0.015

0.020

0.015

0.020

q=2
p=20
p=50
p=200
p=400

SD

0.000

0.000

0.002

0.002

0.004

0.004

0.006

0.008

p=20
p=50
p=200
p=400

0.006

0.008

q=1.8

SD

37

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 8. Plots of the standard deviation of finite-sample MSE. The same experiment is
repeated 200 times. The setup is δ = 5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

are hence skipped. To prove (v), note that

(C.1)

1
ηq (αu; α2−q χ) = arg min (αu − z)2 + χα2−q |z|q
z 2
α2
= arg min (u − z/α)2 + χα2 |z/α|q
z
2
1
= α arg min (u − z̃)2 + χ|z̃|q = αηq (u; χ).
z̃ 2

(vi) is a standard property of proximal operators of convex functions [47].
In many proofs, we will be dealing with derivatives of ηq (u; χ). For notational simplicity, we may use ∂1 ηq (u; χ), ∂12 ηq (u; χ), ∂2 ηq (u; χ), ∂22 ηq (u; χ)

38

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

q=1.5
0.008
0.006

p=20
p=50
p=200
p=400

0.000

0.000

0.002

0.004

Adjusted SD

0.006
0.004
0.002

Adjusted SD

0.008

q=1
p=20
p=50
p=200
p=400

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.015

0.020

0.015

0.020

q=2

0.004

0.006

p=20
p=50
p=200
p=400

0.002

0.004

Adjusted SD

0.006

0.008

p=20
p=50
p=200
p=400

0.000

0.000

0.002

Adjusted SD

0.008

q=1.8

0.010
σ2w

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 9. Plots of the adjusted standard deviation of finite-sample MSE. The same experiment
is repeated 200 times. The setup is δ = 5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

∂η (u,χ) ∂ 2 η (u,χ) ∂η (u,χ) ∂ 2 η (u,χ)

q
q
to represent q∂u , ∂u
, q∂χ , ∂χ
, respectively. Our next two
2
2
lemmas are concerned with differentiability of ηq (u; χ) and its derivatives.

Lemma 8. For every 1 < q < 2, ηq (u; χ) is a differentiable function of
(u, χ) for u ∈ R and χ > 0 with continuous partial derivatives. Moreover,
∂2 ηq (u; χ) is differentiable with respect to u, for any given χ > 0.
Proof. We start with the case u0 , χ0 > 0. The goal is to prove that
ηq (u; χ) is differentiable at (u0 , χ0 ). Since u0 > 0, ηq (u0 ; χ0 ) will be positive.
Then Lemma 7 part (i) shows ηq (u0 ; χ0 ) must satisfy
(C.2)

ηq (u0 ; χ0 ) + χ0 qηqq−1 (u0 ; χ0 ) = u0 .

39

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

q=1

MSE

0.030

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.010

0.020

0.020
0.015
0.010

0.000

0.000

0.005

MSE

q=1.5

true value
first order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.00

0.05

σw

0.10

0.15

0.00

0.05

q=1.8

0.15

0.10

0.15

0.000

0.000

0.010

MSE

0.030

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.020

0.030
0.020

0.10

q=2

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.010

MSE

σw

0.00

0.05

σw

0.10

0.15

0.00

0.05

σw

Fig 10. Plots of actual AMSE, its approximations, and finite-sample MSE. The MSE is
averaged over 200 times. The setup is δ = 3,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

Define the function F (u, χ, v) = u−v−χqv q−1 . Equation (C.2) says F (u, χ, v)
is equal to zero at (u0 , χ0 , ηq (u0 ; χ0 )). It is straightforward to confirm that
the derivative of F (u, χ, v) with respect to v is nonzero at (u0 , χ0 , ηq (u0 ; χ0 )).
By implicit function theorem, we can conclude ηq (u; χ) is differentiable at
(u0 , χ0 ). Lemma 7 part (iv) implies that the same result holds when u0 < 0.
We now focus on the point (0, χ0 ). Since ηq (0, χ0 ) = 0, we obtain
|ηq (u; χ0 )|
|u|1/(q−1)
≤ lim
= 0.
u→0
u→0 (χ0 q)1/(q−1) |u|
|u|

∂1 ηq (0; χ0 ) = lim

where the last inequality comes from (C.2). It is straightforward to see that
the partial derivative of ηq (u; χ) with respect to χ at (0, χ0 ) exists and

40

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

0.008
SD
0.004
0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

q=1.8

0.010
σ2w

0.015

0.020

0.015

0.020

q=2
p=20
p=50
p=200
p=400

0.008

p=20
p=50
p=200
p=400

SD
0.000

0.000

0.004

0.004

SD

0.008

0.012

q=1.5
p=20
p=50
p=200
p=400

0.000

SD

0.000 0.002 0.004 0.006 0.008 0.010

q=1
p=20
p=50
p=200
p=400

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 11. Plots of the standard deviation of finite-sample MSE. The same experiment is
repeated 200 times. The setup is δ = 3,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

is equal to zero as well. So far we have proved that ηq (u, χ) has partial
derivatives with respect to both u and χ for every u ∈ R, χ > 0. We next
show the partial derivatives are continuous. For u 6= 0, the result comes
directly from the implicit function theorem, because F (u, χ, v) is a smooth
function when v 6= 0. We now turn to the proof when u = 0. By taking
derivative with respect to u on both sides of (C.2), we obtain
(C.3)

∂1 ηq (u; χ) + χq(q − 1)ηqq−2 (u; χ)∂1 ηq (u; χ) = 1,

for any u, χ > 0. Moreover, it is clear from (C.2) that ηq (u; χ) → 0, as

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

0.008
0.004
0.000

Adjusted SD

p=20
p=50
p=200
p=400

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

q=1.8

0.015

0.020

0.015

0.020

q=2
p=20
p=50
p=200
p=400

Adjusted SD

0.004

0.000

0.000

0.008

p=20
p=50
p=200
p=400

0.008

0.012

0.000

Adjusted SD

q=1.5

p=20
p=50
p=200
p=400

0.004

Adjusted SD

0.000 0.002 0.004 0.006 0.008 0.010

q=1

41

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 12. Plots of the adjusted standard deviation of finite-sample MSE. The same experiment is repeated 200 times. The setup is δ = 3,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

(u, χ) → (0+ , χ0 ). This fact combined with (C.3) yields
lim

(u,χ)→(0+ ,χ

0)

∂1 ηq (u; χ) =

1

lim

(u,χ)→(0+ ,χ

0)

1 + χq(q − 1)ηqq−2 (u; χ)

= 0.

Since ∂1 ηq (u; χ) = ∂1 ηq (−u; χ) implied by Lemma 7 part (iv), we conclude
lim
(u,χ)→(0,χ0 )

∂1 ηq (u; χ) = 0.

The same approach can prove that the partial derivative ∂2 ηq (u; χ) is continuous at (0, χ0 ). For simplicity we do not repeat the arguments.

42

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

q=1

0.06

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

MSE

0.00

0.000

0.02

0.04

0.030
0.020
0.010

MSE

q=1.5

true value
first order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.00

0.05

σw

0.10

0.15

0.00

0.05

q=1.8

0.15

0.10

0.15

0.04

0.06

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.00

0.00

0.02

MSE

0.04

0.06

0.10

q=2

true value
first order approximation
second order approximation
empirical (p=20)
empirical (p=50)
empirical (p=200)
empirical (p=400)

0.02

MSE

σw

0.00

0.05

σw

0.10

0.15

0.00

0.05

σw

Fig 13. Plots of actual AMSE, its approximations, and finite-sample MSE. The MSE is
averaged over 200 times. The setup is δ = 1.5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

We now prove the second part of the lemma. Because F (u, χ, v) is infinitely many times differentiable in any open set with v 6= 0, implicit function theorem further implies ∂2 ηq (u; χ) is differentiable at any u 6= 0. The
rest of the proof is to show its differentiability at u = 0. This follows by
noting ∂2 ηq (0; χ) = 0, and
∂2 ηq (u; χ)
u→0
u
lim

(a)

=

=

−q|ηq (u; χ)|q−1
u→0 |u|(1 + χq(q − 1)|ηq (u; χ)|q−2 )
−(|u| − |ηq (u; χ)|)
= 0,
lim
u→0 χ|u|(1 + χq(q − 1)|ηq (u; χ)|q−2 )
lim

where (a) is by taking derivative with respect to χ on both sides of (C.2),

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

q=1.5

SD

0.000

0.000

0.005

0.010

0.010
0.005

SD

p=20
p=50
p=200
p=400

0.015

0.020

p=20
p=50
p=200
p=400

0.015

0.020

q=1

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

0.015

0.020

0.015

0.020

q=2
p=20
p=50
p=200
p=400

SD

0.010

0.000

0.000

0.005

0.005

0.010

0.015

0.020

p=20
p=50
p=200
p=400

0.015

0.020

q=1.8

SD

43

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 14. Plots of the standard deviation of finite-sample MSE. The same experiment is
repeated 200 times. The setup is δ = 1.5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

and the last two equalities above are due to Lemma 7 part (i) and (iii).
Lemma 9. Consider a given χ > 0, then for every 1 < q < 3/2,
∂1 ηq (u; χ) is a differentiable function of u for u ∈ R with continuous derivative; for q = 3/2, it is a weakly differentiable function of u; for 3/2 < q < 2,
∂1 ηq (u; χ) is differentiable at u 6= 0, but is not differentiable at zero.
Proof. As is clear from the proof of Lemma 8, the implicit function
theorem guarantees that ∂1 ηq (u; χ) is differentiable at u 6= 0 with continuous
derivative for 1 < q < 2. Hence we will be focused on u = 0. In the proof of

44

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

q=1.5
0.020
0.015

p=20
p=50
p=200
p=400

0.000

0.000

0.005

0.010

Adjusted SD

0.015
0.010
0.005

Adjusted SD

0.020

q=1
p=20
p=50
p=200
p=400

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.015

0.020

0.015

0.020

q=2

0.015

p=20
p=50
p=200
p=400

0.000

0.000

0.005

0.010

0.010

Adjusted SD

0.015

0.020

p=20
p=50
p=200
p=400

0.005

Adjusted SD

0.020

q=1.8

0.010
σ2w

0.000

0.005

0.010
σ2w

0.015

0.020

0.000

0.005

0.010
σ2w

Fig 15. Plots of the adjusted standard deviation of finite-sample MSE. The same experiment is repeated 200 times. The setup is δ = 1.5,  = 0.4, g(b) = 0.5δ1 (b) + 0.5δ−1 (b).

Lemma 8, we have derived
(C.4)

∂1 ηq (u; χ) =

1
,
1 + χq(q − 1)|ηq (u; χ)|q−2

for u 6= 0,

and ∂1 ηq (0; χ) = 0. We thus know
1
.
u→0 u + χq(q − 1)u|ηq (u; χ)|q−2

∂12 ηq (0; χ) = lim

(C.5)

Moreover, Lemma 7 part (i) implies
(C.6)

|ηq (u; χ)|2−q
u
= 1.
=
1
+
lim
u→0 χq|ηq (u; χ)|q−1 sign(u)
u→0
χq
lim

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

45

For 1 < q < 3/2, (C.5) and (C.6) together give us
∂12 ηq (0; χ) = lim

u→0

1
q−2

= 0.

u + χq(q − 1)u(|u|/(χq)) q−1

We can also calculate the limit of ∂12 ηq (u; χ) (this second derivative can be
obtained from (C.4)) as follows.
−χq(q − 1)(q − 2)|ηq (u; χ)|q−3 sign(u)
= 0.
u→0
(1 + χq(q − 1)|ηq (u; χ)|q−2 )3

lim ∂12 ηq (u; χ) = lim

u→0

Therefore, ∂1 ηq (u; χ) is continuously differentiable on (−∞, +∞) for 1 <
q < 3/2. Regarding 3/2 < q < 2, Similar calculations yield
lim ∂12 ηq (0; χ) = +∞,

lim ∂12 ηq (0; χ) = −∞.

u→0−

u→0+

Finally to prove the weak differentiability for q = 3/2, we show ∂1 ηq (u; χ)
is a Lipschitz continuous function on (−∞, +∞). Note that for u 6= 0,
|∂12 ηq (u; χ)| =

χq(q − 1)(2 − q)|ηq (u; χ)|q−3
8
≤
,
(1 + χq(q − 1)|ηq (u; χ)|q−2 )3
9χ2

and ∂12 ηq (0+ ; χ) = −∂12 (0− ; χ) =

8
.
9χ2

Mean value theorem leads to

|∂1 ηq (u; χ) − ∂1 ηq (ũ; χ)| ≤

8
|u − ũ|,
9χ2

for uũ ≥ 0.

When uũ < 0, we can have
|∂1 ηq (u; χ) − ∂1 ηq (ũ; χ)| = |∂1 ηq (u; χ) − ∂1 ηq (−ũ; χ)|
8
8
≤
|u + ũ| ≤
|u − ũ|.
2
9χ
9χ2
This completes the proof of the lemma.
The last lemma in this section presents some additional properties regarding the derivatives of ηq (u; χ).
Lemma 10.

The derivatives of ηq (u; χ) satisfy the following properties:

(i) ∂1 ηq (u; χ) =

1
.
1+χq(q−1)|ηq (u;χ)|q−2
q−1
−q|ηq (u;χ)|
sign(u)
.
1+χq(q−1)|ηq (u;χ)|q−2

(ii) ∂2 ηq (u; χ) =
(iii) 0 ≤ ∂1 ηq (u; χ) ≤ 1.

46

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

(iv) For u > 0, ∂12 ηq (u; χ) > 0.
(v) |ηq (u; χ)| is a decreasing function of χ.
(vi) limχ→∞ ∂1 ηq (u; χ) = 0.
Proof. Parts (i) (ii) have been derived in the proof of Lemma 8. Part
(iii) is a simple conclusion of part (i). Part (iv) is clear from the proof of
Lemma 9. Part (v) is a simple application of part (ii). Finally, part (vi) is
an application of part(i) of Lemma 10 and part (iii) of Lemma 7.
APPENDIX D: PROOF OF LEMMA 2
D.1. Roadmap. The goal of this section is to show that Equations
(2.2) and (2.3) (rewritten below) have a unique solution (σ̄, χ̄):
1
σ̄ 2 = σω2 + EB,Z [(ηq (B + σ̄Z; χ̄σ̄ 2−q ) − B)2 ],
δ

1
0
2−q
2−q
λ = χ̄σ̄
1 − EB,Z [ηq (B + σ̄Z; χ̄σ̄ )] .
δ
Towards the goal we pursue the following two main steps:
1. We show the existence of the solution in Section D.2. In order to do
that, we first study the solution of Equation (2.2), and demonstrate
that for any χ ∈ (χmin , ∞) (χmin is a constant we will clarify later),
there exists a unique σχ such that (σχ , χ) satisfies (2.2). The proof will
be presented in Section D.2.1. We then show that by varying χ over
(χmin , ∞), the range of the value of the following term

1
χσχ 2−q 1 − EB,Z [ηq0 (B + σχ Z; χσχ2−q )]
δ
covers the number λ from Equation (2.3). That means Equations (2.2)
and (2.3) share at least one common solution pair (σχ , χ). We detail
out the proof in Section D.2.2.
2. We prove the uniqueness of the solution in Section D.3. The key idea
is to apply Theorem 2.1 to evaluate the asymptotic loss of the LQLS
estimates under two different pseudo-Lipschitz functions. These two
quantities determine the uniqueness of both σχ and χ in the common
solution pair (σχ , χ). Note that we have denoted this unique pair by
(σ̄, χ̄).
Before we start the details of the proof, we present Stein’s lemma [48]
that will be used several times in this paper.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

47

Lemma 11. Let g : R → R denote a weakly differentiable function. If
Z ∼ N (0, 1) and E|g 0 (Z)| < ∞, we have
E(Zg(Z)) = E(g 0 (Z)),
where g 0 denotes the weak-derivative of g.
D.2. Proving the existence of the solution of (2.2) and (2.3).
D.2.1. Studying the solution of (2.2). We first define a function that is
closely related to Equation (2.2):
Rq (χ, σ) , EB,Z [ηq (B/σ + Z; χ) − B/σ]2 .

(D.1)

Note that we have used the same definition for LASSO in Section 6. Here we
adopt a general notation Rq (χ, σ) to represent the function defined above
for any q ∈ [1, 2].
Lemma 12.

For 1 ≤ q ≤ 2, Rq (χ, σ) is a decreasing function of σ > 0.

Proof. We consider four different cases: (i) q = 1, (ii) q = 2, (iii) 1 <
q ≤ 3/2, (iv) 3/2 < q < 2.
(i) q = 1: Since R1 (χ, σ) is a differentiable function of σ, we will prove
(χ,σ)
this case by showing that ∂R1∂σ
< 0. We have
∂R1 (χ, σ)
∂σ

2
E [B(I(|B/σ + Z| > χ) − 1)(η1 (B/σ + Z; χ) − B/σ)]
σ2

2 
= − 2 E I(|B/σ + Z| ≤ χ)(B 2 /σ) < 0.
σ
= −

The first equality above is due to Dominated Convergence Theorem.
u
(ii) q = 2: Since η2 (u; χ) = 1+2χ
, we have
∂R2 (χ, σ)
8χ2 E|B|2
=−
< 0.
∂σ
(1 + 2χ)2 σ 3
(iii) 1 < q ≤ 3/2: The strategy for this case is similar to that of the last
∂R (χ,σ)
two cases. We show that the derivative q∂σ
< 0.


∂Rq (χ, σ) (a)
= 2E (ηq (B/σ + Z; χ) − B/σ)(∂1 ηq (B/σ + Z; χ) − 1)(−B/σ 2 )
∂σ


= 2E (ηq (B/σ + Z; χ) − B/σ − Z)(∂1 ηq (B/σ + Z; χ) − 1)(−B/σ 2 )


(D.2) +2E Z(∂1 ηq (B/σ + Z; χ) − 1)(−B/σ 2 ) .

48

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

To obtain Equality (a), we have used Dominated Convergence Theorem (DCT); We employed Lemma 7 part (vi) to confirm the conditions
of DCT. Our goal is to show that the two terms in (D.2) are both negative. Regarding the first term, we first evaluate it by conditioning on
B = b for a given constant b > 0 (note that B and Z are independent):
EZ [(ηq (b/σ + Z; χ) − b/σ − Z)(∂1 ηq (b/σ + Z; χ) − 1)]
Z +∞
(b)
(ηq (z; χ) − z)(∂1 ηq (z; χ) − 1)φ(z − b/σ)dz
=
−∞
Z ∞
(ηq (z; χ) − z)(∂1 ηq (z; χ) − 1)φ(z − b/σ)dz +
=
0
Z 0
(ηq (z; χ) − z)(∂1 ηq (z; χ) − 1)φ(z − b/σ)dz
−∞
Z ∞
(d)
(c)
=
(ηq (z; χ) − z)(∂1 ηq (z; χ) − 1)(φ(z − b/σ) − φ(z + b/σ))dz > 0,
0

where φ(·) is the density function of standard normal; (b) is obtained
by a change of variables; (c) is due to the fact ∂1 ηq (−z; χ) = ∂1 ηq (z; χ)
implied by Lemma 7 part (iv); (d) is based on the following arguments:
According to Lemmas 7 part (ii) and Lemma 10 part (iii), ηq (z; χ) < z
and ∂1 ηq (z; χ) < 1 for z > 0. Moreover, φ(z − b/σ) − φ(z + b/σ) > 0
for z, b/σ > 0. Hence we have


EZ (ηq (b/σ + Z; χ) − b/σ − Z)(∂1 ηq (b/σ + Z; χ) − 1)(−b/σ 2 ) < 0.
Similarly we can show the above inequality holds for b < 0. It is clear
that the term on the left hand side equals zero when b = 0. Thus we
have proved the first term in (D.2) is negative. Now we should discuss
the second term. Again we condition on B = b for a given b > 0:
(e)

EZ [Z(∂1 ηq (b/σ + Z; χ) − 1)] = E(∂12 ηq (b/σ + Z; χ))
Z ∞
(D.3) =
[∂12 ηq (z; χ)(φ(z − b/σ) − φ(z + b/σ))]dz > 0.
0

Equality (e) is the result of Stein’s lemma, i.e. Lemma 11. Note that the
weak differentiability condition required in Stein’s lemma is guaranteed
by Lemma 9. To obtain the last inequality, we have used Lemma 10
part (iv) and the fact that φ(z − b/σ) − φ(z + b/σ) > 0 for z, b/σ > 0.
Hence we obtain that


EZ Z(∂1 ηq (b/σ + Z; τ ) − 1)(−b/σ 2 ) < 0.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

49

The same approach would work for b < 0, and clearly the left hand side
term of the above inequality equals zero for b = 0. We can therefore
conclude the second term in (D.2) is negative as well.
(iv) 3/2 < q < 2: The proof of this case is similar to the last one. The only
difference is that the proof steps we presented in (D.3) may not work,
due to the non-differentiability of ∂1 ηq (u; χ) for q > 3/2 as shown in
Lemma 9. Our goal here is to use an alternative approach to prove:
EZ [Z(∂1 ηq (b/σ + Z; χ) − 1)] > 0 for b > 0. We have
Z ∞
z(∂1 ηq (b/σ + z; χ) − 1)φ(z)dz
EZ [Z(∂1 ηq (b/σ + Z; χ) − 1)] =
−∞
Z ∞
z(∂1 ηq (b/σ + z; χ) − ∂1 ηq (b/σ − z; χ))φ(z)dz
=
Z0 ∞
(D.4) =
z(∂1 ηq (|b/σ + z|; χ) − ∂1 ηq (|b/σ − z|; χ))φ(z)dz,
0

where the last equality is due to the fact ∂1 ηq (u; χ) = ∂1 ηq (|u|; χ) for
any u ∈ R. Since |b/σ − z| < |b/σ + z| for z, b/σ > 0 and according to
Lemma 10 part (iv), we obtain
(D.5)

∂1 ηq (|b/σ + z|; χ) − ∂1 ηq (|b/σ − z|; χ) > 0.

Combining (D.4) and (D.5) completes the proof.

Lemma 12 paves our way in the study of the solution of (2.2). Define
(D.6)


1
χmin = inf χ ≥ 0 : E(ηq2 (Z; χ)) ≤ 1 ,
δ

where Z ∼ N (0, 1). The following corollary is a conclusion from Lemma 12.
Corollary 2.

For a given 1 ≤ q ≤ 2, Equation (2.2):

1
σ 2 = σω2 + EB,Z [(ηq (B + σZ; χσ 2−q ) − B)2 ],
δ

σw > 0

has a unique solution σ = σχ for any χ ∈ (χmin , ∞), and does not have any
solution if χ ∈ (0, χmin ).
Proof. First note that since σw > 0, σ = 0 is not a solution of (2.2).
Hence we can equivalently write Equation (2.2) in the following form:
(D.7)

1=

2
σw
1
+ Rq (χ, σ) , F (σ, χ).
σ2
δ

50

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

According to Lemma 12, F (σ, χ) is a strictly decreasing function of σ over
(0, ∞). We also know that F (σ, χ) is a continuous function of σ from the
proof of Lemma 12. Moreover, it is straightforward to confirm that
(D.8)

1
lim F (σ, χ) = E(ηq2 (Z; χ)).
σ→∞
δ

lim F (σ, χ) = ∞,

σ→0

Thus Equation (2.2) has a solution (the uniqueness is automatically guaranteed by the monotonicity of F (σ, χ)) if and only if 1δ E(ηq2 (Z; χ)) < 1. Recall
the definition of χmin given in (D.6). Since E(ηq2 (Z; χ)) is a strictly decreasing and continuous function of χ, 1δ E(ηq2 (Z; χ)) < 1 holds if χ ∈ (χmin , ∞)
and fails when χ ∈ (0, χmin ).
D.2.2. Studying the common solution of (2.2) and (2.3). Corollary 2
from Section D.2.1 characterizes the existence and uniqueness of solution
for Equation (2.2). Our next goal is to prove that (2.2) and (2.3) share at
least one common solution. Our strategy is: among all the pairs (σχ , χ) that
satisfy (2.2), we show that at least one of them satisfies (2.3). We do this in
the next few lemmas.
Lemma 13. Let δ < 1.
the value of σ that satisfies

2−q
lim χσχ
1−
(D.9)
χ→∞

2−q
lim χσχ
1−
χ→χ+
min

For each value of χ ∈ (χmin , ∞), define σχ as
(2.2). Then,

1
2−q
E[∂1 ηq (B + σχ Z; χσχ )]
= ∞,
δ

1
2−q
E[∂1 ηq (B + σχ Z; χσχ )]
= −∞.
δ

Proof. We first show that
2
lim σχ2 = σw
+

(D.10)

χ→∞

E|B|2
,
δ

lim σχ = ∞.

χ→χ+
min

2

2 + E|B| for any sequence
For the first part, we only need to show σχ2 k → σw
δ
χk → ∞. For that purpose, we first prove σχ = O(1). Otherwise, there exists
a sequence χn → ∞ such that σχn → ∞. Because

(ηq (B/σχn + Z; χn ) − B/σχn )2 ≤ 2(B/σχn + Z)2 + 2B 2 /σχ2 n ≤ 6B 2 + 4Z 2
for large enough n, we can apply Dominated Convergence Theorem (DCT)
to conclude
lim Rq (χn , σχn ) = E lim [ηq (B/σχn + Z; χn ) − B/σχn ]2 = 0.

n→∞

n→∞

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

51

On the other hand, since the pair (σχn , χn ) satisfies (2.2) we obtain
lim Rq (χn , σχn ) = lim δ 1 −

n→∞

n→∞

2 
σw
= δ.
σχ2 n

This is a contradiction. We next consider any convergent subsequence {σχkn }
of {σχk }. The facts σxk ≥ σw and σχk = O(1) imply σχkn → σ ∗ ∈ (0, ∞).
Moreover, since
) − B)2 ≤ 6B 2 + 5(σ ∗ )2 Z 2 ,
(ηq (B + σχkn Z; χkn σχ2−q
kn
when n is large enough. We can apply DCT to obtain,
2
2 1
2
2 EB
(σ ∗ )2 = lim σχ2 kn = σw
+ E lim (ηq (B+σχkn Z; χkn σχ2−q
)−B)
=
σ
+
.
w
kn
n→∞
δ n→∞
δ

Thus, we have showed any convergent subsequence of {σχ2 k } converges to
2 + EB 2 . Hence the sequence converges to that limit as well.
the same limit σw
δ
Regarding the second part in (D.10), if it is not the case, then there exists
a sequence χn → χ+
min such that σχn = O(1). Equation (D.7) shows,
1=

2
(a) σ 2
σw
1
1
σ2
1
+ Rq (χn , σχn ) ≥ 2w + Rq (χn , ∞) = 2w + E(ηq2 (Z; χn )),
2
σ χn
δ
σ χn
δ
σχn
δ

where (a) is due to Lemma 12. From the definition of χmin in (D.6), it is clear
that 1δ E(ηq2 (Z; χmin )) = 1 when δ < 1. Hence letting n → ∞ on the both
sides of the above inequaitiy leads to 1 ≥ Ω(1) + 1, which is a contradiction.
We are in position to derive the two limiting results in (D.9). To obtain
2
2 + E|B| , as χ → ∞. Therefore, Lemma 10
the first one, note that σχ2 → σw
δ
part (vi) combined with DCT gives us
lim E∂1 ηq (B + σχ Z; χσχ2−q ) = 0.

χ→∞

The first result of (D.9) can then be trivially derived. Regarding the second
result, we have showed that as χ → χ+
min , σχ → ∞. We also have
(b)

E∂1 ηq (B + σχ Z; χσχ2−q ) =
(c)

1
E(Zηq (B + σχ Z; χσχ2−q ))
σχ

= E(Zηq (B/σχ + Z; χ)),

52

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

where (b) holds by Lemma 11 and (c) is due to Lemma 7 part (v). Hence
lim E∂1 ηq (B + σχ Z; χσχ2−q )

χ→χ+
min

=

lim E(Zηq (B/σχ + Z; χ)) = E(Zηq (Z; χmin ))

χ→χ+
min

(d)

=

E(ηq2 (Z; χmin )) + χmin qE(|ηq (Z; χmin )|q )

=

δ + χmin qE(|ηq (Z; χmin )|q ),

where (d) is the result of Lemma 7 part (i). We thus obtain


1
1
2−q
(D.11) lim
1 − E∂1 ηq (B + σχ Z; χσχ ) = − χmin qE|ηq (Z; χmin )|q .
+
δ
δ
χ→χmin
Combining (D.11) and the fact that χmin > 0, σχ → ∞ finishes the proof.
Lemma 14. Let δ ≥ 1. For each value of χ ∈ (χmin , ∞), define σχ as
the value of σ that satisfies (2.2). Then,


1
lim χσχ2−q 1 − E[∂1 ηq (B + σχ Z; χσχ2−q )]
(D.12)
= ∞,
χ→∞
δ


1
2−q
2−q
= 0.
lim χσχ
1 − E[∂1 ηq (B + σχ Z; χσχ )]
δ
χ→χ+
min
Proof. The exactly same arguments presented in the proof of Lemma
13 can be applied to prove the first result in (D.12). We now focus on the
proof of the second one. Since E|∂1 ηq (B + σχ Z; χσχ2−q )| ≤ 1, our goal will
be to show χσχ2−q = o(1), as χ → 0+ (note that χmin = 0 when δ ≥ 1).
We first consider the case δ > 1. To prove χσχ2−q = o(1), it is sufficient
to show σχ = O(1). Suppose this is not true, then there exists a sequence
χn → 0 such that σχn → ∞. Recall that (χn , σχn ) satisfies (2.2):
(D.13)

1
2
σχ2 n = σw
+ E(ηq (B + σχn Z; χn σχ2−q
) − B)2 .
n
δ

Dividing both sides of the above equation by σχ2 n and letting n → ∞ yields
1 = 1δ < 1, which is a contradiction.
Regarding the case δ = 1, we first claim that σχ → ∞, as χ → 0. Otherwise, there exists a sequence χn → 0 such that σχn → σ ∗ ∈ (0, ∞). However,
2 + (σ ∗ )2
taking the limit n → ∞ on both sides of (D.13) gives us (σ ∗ )2 = σw
where contradiction arises. Hence, if we can show χσχ2 = O(1), then χσχ2−q =

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

53

o(1) will be proved. Starting from (D.13) (replacing χn by χ) with δ = 1,
we can have for q ∈ (1, 2]
2
0 = σw
+ σχ2 E(ηq (B/σχ + Z; χ) − B/σχ − Z)2 +

2σχ2 EZ(ηq (B/σχ + Z; χ) − B/σχ − Z)
(a)

2
= σw
+ χσχ2 · E(χq 2 |ηq (B/σχ + Z; χ)|2q−2 ) +
|
{z
}
A

−2q(q − 1)|ηq (B/σχ + Z; χ)|q−2
,
χσχ2 · E
1 + χq(q − 1)|ηq (B/σχ + Z; χ)|q−2
|
{z
}
B

where to obtain (a) we have used Lemma 7 part (i), Lemma 10 part (i) and
Lemma 11. Therefore we obtain
2
χσχ2 = −σw
· (A + B)−1 .

(D.14)

Because σχ → ∞ as χ → 0, it is easily seen that
(D.15)

lim A = 0,

χ→0+

lim inf |B| ≥ 2q(q − 1)E|Z|q−2 .
χ→0+

Combining results (D.14) and (D.15) we can conclude that χσχ2 = O(1).
Finally for the case q = 1, we do similar calculations and have
1
E(ηq (B/σχ + Z; χ) − B/σχ − Z)2 ≤ χ → 0,
χ
2
4
|B| = P (|B/σχ + Z| ≤ χ) → √ .
χ
2π
|A| =

This completes the proof.
According to the results presented in
 Lemmas 13 and 14, if the function
χσχ2−q 1 − 1δ E[∂1 ηq (B + σχ Z; χσχ2−q )] , is continuous with respect to χ ∈
(χmin , ∞), then we can conclude that Equations (2.2) and (2.3) share at least
one common solution pair. To confirm the continuity, it is straightforward
to employ implicit function theorem to show σχ is continuous about χ.
Moreover, According to Lemma 8, ∂1 ηq (u; χ) is also a continuous function
of its arguments.
D.3. Proving the uniqueness of the solution of (2.2) and (2.3).
The proof of uniqueness is motivated by the idea presented in [13]. Suppose there are two different solutions denoted by (σχ1 , χ1 ) and (σχ2 , χ2 ),

54

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

respectively. By applying Theorem 2.1 with ψ(a, b) = (a − b)2 , we have
AMSE(λ, q, σw )

=

) − B]2
E[ηq (B + σχ1 Z; χ1 σχ2−q
1

(a)

2
δ(σχ2 1 − σw
),

=

where (a) is due to (2.2). The same equations hold for the other solution pair
(σχ2 , χ2 ). Since they have the same AMSE, it follows that σχ1 = σχ2 . Next
we choose a different pseudo-Lipschitz function ψ(a, b) = |a| in Theorem 2.1
to obtain
p

1X
)|
|β̂i (λ, q, p)| = E|ηq (B + σχ1 Z; χ1 σχ2−q
1
p→∞ p
lim

i=1

= E|ηq (B + σχ2 Z; χ2 σχ2−q
)| = E|ηq (B + σχ1 Z; χ2 σχ2−q
)|
2
1
Since E|ηq (B + σχ1 Z; χ)|, as a function of χ ∈ (0, ∞), is strictly decreasing
based on Lemma 10 part (v), we conclude χ1 = χ2 .
APPENDIX E: PROOF OF COROLLARY 1
According to Theorem 2.1, the key of proving Corollary 1 is to analyze
the following equations:

(E.1)
(E.2)

1
σ 2 = σω2 + E[(ηq (B + σZ; χσ 2−q ) − B)2 ],
δ

1
λ∗,q = χσ 2−q 1 − E[ηq0 (B + σZ; χσ 2−q )] ,
δ

where λ∗,q = arg minλ≥0 AMSE(λ, q, σw ). We present the main result in the
following lemma.
Lemma 15. For every 1 ≤ q ≤ 2 and a given optimal tuning λ∗,q , there
exists a unique solution pair (σ̄, χ̄) that satisfies (E.1) and (E.2). Furthermore, σ̄ is the unique solution of
(E.3)

2
σ 2 = σw
+

1
min E(ηq (B + σZ; χ) − B)2 ,
δ χ≥0

and
(E.4)

χ̄ ∈ arg min E[(ηq (B + σ̄Z; χσ̄ 2−q ) − B)2 ].
χ≥0

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

55

Proof. The first part of this lemma directly comes from Lemma 2. We
focus on the proof of the second part. Recall the definition of Rq (χ, σ) in
(D.1). Define
σ2
1
Gq (σ) , w2 + min Rq (χ, σ).
σ
δ χ≥0
Then (E.3) is equivalent to Gq (σ) = 1. We first show that Gq (σ) is a strictly
decreasing function of σ over (0, ∞). For any given σ1 > σ2 > 0, we can
choose χ1 , χ2 such that
χ1 = arg min E(ηq (B/σ1 + Z; χ) − B/σ1 )2 ,
χ≥0

χ2 = arg min E(ηq (B/σ2 + Z; χ) − B/σ2 )2 .
χ≥0

Applying Lemma 12 we have
Rq (χ1 , σ1 ) = min Rq (χ, σ1 ) ≤ Rq (χ2 , σ1 ) ≤ Rq (χ2 , σ2 ) = min Rq (χ, σ2 ).
χ≥0

χ≥0

Hence we obtain that Gq (σ1 ) < Gq (σ2 ). We next show
lim Gq (σ) = ∞,

(E.5)

σ→0

lim Gq (σ) < 1.

σ→∞

The first result in (E.5) is obvious. To prove the second one, we know
2
1
1
σw
+ Rq (χ, σ) = Eηq2 (Z; χ),
σ→∞ σ 2
δ
δ

lim Gq (σ) ≤ lim

σ→∞

for any given χ ≥ 0. Choosing a sufficiently large χ completes the proof for
the second inequality in (E.5). Based on (E.5) and the fact that Gq (σ) is a
strictly decreasing and continuous function of σ over (0, ∞), we can conclude
(E.3) has a unique solution. Call it σ ∗ , and denote
χ∗ ∈ arg min E[(ηq (B + σ ∗ Z; χ(σ ∗ )2−q ) − B)2 ].
χ≥0

Note that χ∗ may not be unique. Further define


1
λ∗ = χ∗ (σ ∗ )2−q 1 − E[∂1 ηq (B + σ ∗ Z; χ∗ (σ ∗ )2−q )] .
δ
It is straightforward to see that the pair (σ ∗ , χ∗ ) satisfies (2.2) and (2.3)
with λ = λ∗ . According to Theorem 2.1, we obtain
(E.6)

2
AMSE(λ∗ , q, σw ) = δ((σ ∗ )2 − σw
).

56

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Also we already know for the optimal tuning λ∗,q
2
AMSE(λ∗,q , q, σw ) = δ(σ̄ 2 − σw
) ≤ AMSE(λ∗ , q, σw ).

Therefore σ̄ ≤ σ ∗ . On the other hand,
1
2
σ̄ 2 = σw
+ E(ηq (B + σ̄Z; χ̄σ̄ 2−q ) − B)2
δ
1
2
≥ σw + min E(ηq (B + σ̄Z; χ) − B)2 = σ̄ 2 · Gq (σ̄).
δ χ≥0
Thus Gq (σ̄) ≤ 1 = Gq (σ ∗ ). Since Gq (σ) is a strictly decreasing function, we
then obtain σ̄ ≥ σ ∗ . Consequently, we conclude σ̄ = σ ∗ . Finally we claim
(E.4) has to hold. Otherwise,
AMSE(λ∗,q , q, σw ) = E(ηq (B + σ̄Z; χ̄σ̄ 2−q ) − B)2
> min E(ηq (B + σ̄Z; χ) − B)2 = E(ηq (B + σ ∗ Z; χ∗ ) − B)2
χ≥0

= AMSE(λ∗ , q, σw ),
contradicts the fact that λ∗,q is the optimal tuning.
Remark: Lemma 15 leads directly to the result of Corollary 1. Furthermore, from the proof of Lemma 15, we see that if E[(ηq (B+σZ; χσ 2−q )−B)2 ],
as a function of χ, has a unique minimizer for any given σ > 0, then χ̄ = χ∗ .
That means the optimal tuning value λ∗,q is unique. [46] has proved that
E[(ηq (B + σZ; χσ 2−q ) − B)2 ] is quasi-convex and has a unique minimizer for
q = 1. We conjecture it is true for q ∈ (1, 2] as well and leave it for future
research.
APPENDIX F: PROOF OF THEOREM 3.1
F.1. Roadmap of the proof. Different from the result of Theorem
3.3 that bounds the second order term in AMSE(λ∗,1 , 1, σw ), Theorem 3.1
characterizes the precise analytical expression of the second dominant term
for AMSE(λ∗,q , q, σw ) with q ∈ (1, 2]. However, the idea of this proof is
similar to the one for Theorem 3.3 presented in Section 6 of the main text,
though the detailed proof steps are more involved here. We suggest interested
readers first going over the proof of Theorem 3.3 and then this section so
that both the proof idea and technical details are smoothly understood.
Recall the definition we introduced in (D.1):
Rq (χ, σ) = E(ηq (B/σ + Z; χ) − B/σ)2 ,

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

57

where Z ∼ N (0, 1) and B with the distribution pβ (b) = (1 − )δ0 (b) + g(b)
are independent. Define
χ∗q (σ) = arg min Rq (χ, σ).

(F.1)

χ≥0

Based on Lemma 8 of Appendix C, it is straightforward to show Rq (χ, σ) is
a differentiable function of χ. It is also easily seen that
lim Rq (χ, σ) =

χ→∞

E|B|2
,
σ2

lim Rq (χ, σ) = 1.

χ→0

Therefore, the minimizer χ∗q (σ) exists at least for sufficiently small σ. If it
is not unique, we will consider the one having smallest value itself. As like
the proof of Theorem 3.3, the key is to characterize the convergence rate for
Rq (χ∗q (σ), σ) as σ → 0. After having that convergence rate result, we can
then obtain the convergence rate for σ̄ from Equation (3.3) and finally derive
the expansion of AMSE(λ∗,q , q, σw ) based on Corollary 1. We organize our
proof steps as follows:
1. We first characterize the convergence rate of χ∗q (σ) in Section F.2.
2. We then obtain the convergence rate of Rq (χ∗q (σ), σ) in Section F.3.
3. We finally derive the second order expansion for AMSE(λ∗,q , q, σw ) in
Section F.4.
As a final remark, once we show the proof for q ∈ (1, 2), since η2 (u; χ) =
has a nice explicit form, the proof for q = 2 can be easily derived. We
hence skip it for simplicity.
u
1+2χ

F.2. Characterizing the convergence rate of χ∗q (σ). The goal of
this section is to derive the convergence rate of χ∗q (σ) as σ → 0. We will
make use of the fact that χ∗q (σ) is the minimizer of Rq (χ, σ), to first show
χ∗q (σ) → 0 and then obtain the rate χ∗q (σ) ∝ σ 2q−2 . This is done in the
following three lemmas.
Lemma 16. Let χ∗q (σ) denote the minimizer of Rq (χ, σ) as defined in
(F.1). Then for every b 6= 0 and z ∈ R,
|ηq (b/σ + z; χ∗q (σ))| → ∞,

as σ → 0.

Proof. Suppose this is not the case. Then there exist a value of b 6=
0, z ∈ R and a sequence σk → 0, such that |ηq (b/σk + z; χ∗q (σk ))| is bounded.
Combined with Lemma 7 part (i) we obtain
1
|b/σk + z| − |ηq (b/σk + z; χ∗q (σk ))|
(F.2) χ∗q (σk ) =
=
Ω
.
q|ηq (b/σk + z; χ∗q (σk ))|q−1
σk

58

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

We next show that the result (F.2) implies for any other b̃ 6= 0 and z̃ ∈ R,
|ηq (b̃/σk + z̃; χ∗q (σk ))| is bounded as well. From Lemma 7 part (i) we know
(F.3) |b̃/σk + z̃| = |ηq (b̃/σk + z̃; χ∗q (σk ))| + χ∗q (σk )q|ηq (b̃/σk + z̃; χ∗q (σk ))|q−1 .
If |ηq (b̃/σk + z̃; χ∗q (σk ))| is unbounded, then the right hand side of equation
(F.3) (take a subsequence if necessary) has the order larger than 1/σk . Hence
(F.3) can not hold for all the values of k. We thus have reached the conclusion
that |ηq (b/σk + z; χ∗q (σk ))| is bounded for every b 6= 0 and z ∈ R. Therefore,
|ηq (G/σk + Z; χ∗q (σk )) − G/σk | → ∞ a.s., as k → ∞,
where G has the distribution g(·). We then use Fatou’s lemma to obtain
Rq (χ∗q (σk ), σk ) ≥ E|ηq (G/σk + Z; χ∗q (σk )) − G/σk |2 → ∞.
On the other hand, since χ∗q (σk ) minimizes Rq (χ, σk ),
Rq (χ∗q (σk ), σk ) ≤ Rq (0, σk ) = 1.
Such contradiction completes the proof.
Lemma 16 enables us to derive χ∗q (σ) → 0 as σ → 0. We present it in the
next lemma.
Lemma 17. Let χ∗q (σ) denote the minimizer of Rq (χ, σ) as defined in
(F.1). Then χ∗q (σ) → 0 as σ → 0.
Proof. First note that
Rq (χ, σ)

=

(1 − )E(ηq (Z; χ))2 + E(ηq (G/σ + Z; χ) − G/σ − Z)2 +
2EZ(ηq (G/σ + Z; χ) − G/σ − Z) + 

(a)

=

(1 − )E(ηq (Z; χ))2 + χ2 q 2 E|ηq (G/σ + Z; χ)|2q−2 +
2E(∂1 ηq (G/σ + Z; χ) − 1) + 

(b)

=

(F.4)

(1 − )E(ηq (Z; χ))2 + χ2 q 2 E|ηq (G/σ + Z; χ)|2q−2 +


1
2E
− 1 + .
1 + χq(q − 1)|ηq (G/σ + Z; χ)|q−2

We have employed Lemma 7 part (i) and Lemma 8 to obtain (a); (b) is due to
Lemma 10 part (i). According to Lemma 16, |ηq (G/σ + Z; χ∗q (σ))| → ∞ a.s.,
as σ → 0. Hence, if χ∗q (σ) 9 0, the second term in (F.4) (with χ = χ∗q (σ))
goes off to infinity, while the other terms remain finite, and consequently
Rq (χ∗q (σ), σ) → ∞. This is a contradiction with the fact Rq (χ∗q (σ), σ) ≤
Rq (0, σ) = 1.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

59

So far we have shown χ∗q (σ) → 0 as σ → 0. Our next lemma further
characterizes the convergence rate of χ∗q (σ).
Lemma 18. Suppose P(|G| ≤ t) = O(t) (as t → 0) and E|G|2 < ∞.
Then for q ∈ (1, 2) we have
χ∗q (σ)
(1 − )E|Z|q
lim 2q−2 =
.
σ→0 σ
qE|G|2q−2
Proof. We first claim that χ∗q (σ) = Ω(σ 2q−2 ). Otherwise there exists a
sequence σk → 0 such that χ∗q (σk ) = o(σk2q−2 ). According to Lemma 19 (we
postpone Lemma 19 since it deals with Rq (χ, σ)),
lim

k→∞

Rq (χ∗q (σk ), σk ) − 1
σk2q−2

= 0.

On the other hand, by choosing χ(σk ) = Cσk2q−2 with C =
19 implies that
Rq (χ(σk ), σk ) − 1
< 0,
lim
k→∞
σk2q−2

(1−)E|Z|q
,
qE|G|2q−2

Lemma

which contradicts with the fact that χ∗q (σk ) is the minimizer of Rq (χ, σk ).
Moreover, this choice of C shows that for sufficiently small σ there exists
χ(σ) such that
Rq (χ∗q (σ), σ) ≤ Rq (χ(σ), σ) < Rq (0, σ) = 1.
∂Rq (χ∗ (σ),σ)

q
That means χ∗q (σ) is a non-zero finite value. Hence it satisfies
=
∂χ
∗
∗
0. From now on we use χ to denote χq (σ) for notational simplicity. That
equation can be detailed out as follows:

0 = (1 − )Eηq (Z; χ∗ )∂2 ηq (Z; χ∗ ) + E(ηq (G/σ + Z; χ∗ ) − G/σ)∂2 ηq (G/σ + Z; χ∗ )
−q|ηq (Z; χ∗ )|q
(a)
= (1 − ) E
+ E(Z∂2 ηq (G/σ + Z; χ∗ ))
1 + χ∗ q(q − 1)|ηq (Z; χ∗ )|q−2
|
{z
}
|
{z
}
H2
H1

(F.5)

q 2 |ηq (G/σ + Z; χ∗ )|2q−2
+χ∗ E
,
1 + χ∗ q(q − 1)|ηq (G/σ + Z; χ∗ )|q−2
|
{z
}
H3

where we have used Lemma 7 part (i) and Lemma 10 part (ii) to obtain (a).
We now analyze the three terms H1 , H2 and H3 , respectively. According to

60

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Lemma 17, we have that ηq (Z; χ∗ ) → Z as σ → 0. Lemma 7 part (ii) enables
us to bound the expression inside the expectation of H1 by q|Z|q . Hence we
can employ Dominated Convergence Theorem (DCT) to obtain
lim H1 = −qE|Z|q .

(F.6)

σ→0

For the term H3 , we first note that
lim ηq (G + σZ; σ 2−q χ∗ ) = G,

σ→0

|ηq (G + σZ; σ 2−q χ∗ )| ≤ |B| + σ|Z|.
We also know that |ηq (G/σ + Z; χ∗ )| → ∞, a.s. by Lemma 16. We therefore
can apply DCT to conclude
q 2 |ηq (G + σZ; σ 2−q χ∗ )|2q−2
H3
=
E
lim
= q 2 E|G|2q−2 .
σ→0 σ 2−2q
σ→0 1 + χ∗ q(q − 1)|ηq (G/σ + Z; χ∗ )|q−2

(F.7) lim

We now study the remaining term H2 . According to Lemma 8, ∂2 ηq (G/σ +
Z; χ∗ ) is differentiable with respect to its first argument. So we can apply
Lemma 11 to get
|ηq (G/σ + Z; χ∗ )|q−2
H2 = q(1 − q) E
(1 + χ∗ q(q − 1)|ηq (G/σ + Z; χ∗ )|q−2 )3
|
{z
}
+q 2 (1 − q) E
(1 +
|

J1
∗
χ |ηq (G/σ + Z; χ∗ )|2q−4
χ∗ q(q − 1)|ηq (G/σ + Z; χ∗ )|q−2 )3

{z

.

}

J2

It is straightforward to see that
J1 ≤ E
J2

1

,
+ χ∗ q(q − 1)
1/(q(q − 1))
≤ E
.
|ηq (G/σ + Z; χ∗ )|2−q + χ∗ q(q − 1)
|ηq (G/σ +

Z; χ∗ )|2−q

We would like to prove H2 → 0 by showing
(F.8)

lim E

σ→0

1
|ηq (G/σ +

Z; χ∗ )|2−q

+ χ∗ q(q − 1)

= 0.

Note that DCT may not be directly applied here, because the function inside the expectation cannot be easily bounded. Alternatively, we prove (F.8)

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

61

by breaking the expectation into different parts and showing each part con1
verges to zero. Let α1 be a number that satisfies ηq (α1 ; χ∗ ) = (χ∗ ) 2−q , α2 =
1
(χ∗ ) 2 , and α3 a fixed positive constant that does not depend on σ. Denote
the distribution of |G| by F (g). Note the following simple fact about α1
according to Lemma 7 part (i):
1

α1 = ηq (α1 ; χ∗ ) + χ∗ qηqq−1 (α1 ; χ∗ ) = (q + 1)(χ∗ ) 2−q .
So α1 < α2 < α3 when σ is small. Define the following three nested intervals:
Ii (x) , [−x − αi , −x + αi ],

i = 1, 2, 3.

With these definitions, we start the proof of (F.8). We have
1
E
|ηq (G/σ + Z; χ∗ )|2−q + χ∗ q(q − 1)
Z ∞Z
1
φ(z)dzdF (g) +
=
∗
2−q + χ∗ q(q − 1)
0
z∈I1 (g/σ) |ηq (g/σ + z; χ )|
Z ∞Z
1
φ(z)dzdF (g) +
∗
2−q + χ∗ q(q − 1)
0
z∈I2 (g/σ)\I1 (g/σ) |ηq (g/σ + z; χ )|
Z ∞Z
1
φ(z)dzdF (g) +
∗ )|2−q + χ∗ q(q − 1)
|η
(g/σ
+
z;
χ
q
0
z∈I3 (b/σ)\I2 (g/σ)
Z ∞Z
1
φ(z)dzdF (g)
∗
2−q + χ∗ q(q − 1)
0
R\I3 (b/σ) |ηq (g/σ + z; χ )|
, G 1 + G2 + G3 + G4 ,
where φ(·) is the density function of standard normal. We now bound each
of the four integrals in (F.9) respectively.
Z ∞Z
1
G1 ≤
φ(z)dzdF (g)
∗ q(q − 1)
χ
0
z∈I1 (g/σ)
1

≤

2α1 φ(0)
2(q + 1)(χ∗ ) 2−q φ(0)
≤
→ 0, as σ → 0.
χ∗ q(q − 1)
χ∗ q(q − 1)

The last step is due to the fact that χ∗ → 0 by Lemma 17. For G2 we have
Z ∞Z
1
G2 ≤
φ(z)dzdF (g)
∗ 2−q
0
z∈I2 (g/σ)\I1 (g/σ) |ηq (g/σ + z; χ )|
Z ∞Z
(b)
1
≤
φ(z)dzdF (g)
∗
χ
0
z∈I2 (g/σ)\I1 (g/σ)

62

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Z
≤

σ log(1/σ) Z

1
φ(z)dzdF (g) +
∗
χ
0
z∈I2 (g/σ)\I1 (g/σ)
Z ∞
Z
1
φ(z)dzdF (g)
∗
σ log(1/σ) z∈I2 (g/σ)\I1 (g/σ) χ

2φ(0)α2 2φ(log(1/σ) − α2 )α2
+
χ∗
χ∗
2φ(0)
2φ(log(1/σ) − α2 )
= P(|G| ≤ σ log(1/σ)) ∗ 1/2 +
(χ )
(χ∗ )1/2
≤ P(|G| ≤ σ log(1/σ))

(c)

≤ O(1) · σ 2−q log(1/σ) + O(1) ·

φ((log(1/σ))/2)
→ 0, as σ → 0.
σ q−1

In the above derivations, (b) is because
|ηq (g/σ + z; χ∗ )| ≥ ηq (α1 ; χ∗ ) = (χ∗ )1/(2−q) for z ∈
/ I1 (g/σ).
To obtain (c), we have used the condition P(|G| ≤ σ log(1/σ)) = O(σ log(1/σ))
and the result χ∗ = Ω(σ 2q−2 ) we proved at the beginning. Regarding G3 ,
Z ∞Z
1
φ(z)dzdF (g)
G3 ≤
∗ 2−q
0
z∈I3 (g/σ)\I2 (g/σ) |ηq (α2 ; χ )|
Z σ log 1/σ Z
1
≤
φ(z)dzdF (g)
∗ 2−q
|η
(α
;
q
2 χ )|
0
z∈I3 (g/σ)\I2 (g/σ)
Z ∞
Z
1
+
φ(z)dzdF (g)
∗ 2−q
|η
(α
;
q
2 χ )|
σ log 1/σ z∈I3 (g/σ)\I2 (g/σ)
≤
(d)

≤

P(|G| ≤ σ log(1/σ))
O(1) · σ q

2 −3q+3

2φ(0)α3
2φ(log(1/σ) − α3 )α3
+
∗
2−q
|ηq (α2 ; χ )|
|ηq (α2 ; χ∗ )|2−q

log(1/σ) + O(1) ·

φ((log(1/σ))/2)
→ 0, as σ → 0.
σ (q−1)(2−q)

The calculations above are similar to those for G2 . In (d) we have used the
following result:
ηq (α2 ; χ∗ )
ηq ((χ∗ )1/2 ; χ∗ )
=
lim
= lim ηq (1; (χ∗ )q/2 ) = 1.
σ→0 (χ∗ )1/2
σ→0
σ→0
(χ∗ )1/2
lim

Finally we can apply DCT to obtain
lim G4 = E lim

σ→0

σ→0

I(|G/σ + Z| > α3 )
= 0.
|ηq (G/σ + Z; χ∗ )|2−q + χ∗ q(q − 1)

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

63

We have finished the proof of limσ→0 H2 = 0. This fact together with (F.5),
(F.6) and (F.7) gives us
χ∗

lim

σ→0 σ 2q−2

=

−(1 − )H1 − H2
(1 − )E|Z|q
=
.
2−2q
H3 /σ
qE|G|2q−2

F.3. Characterizing the convergence rate of Rq (χ∗q (σ), σ). Having derived the convergence rate of χ∗q (σ) in Section F.2, we aim to obtain
the convergence rate for Rq (χ∗q (σ), σ) in this section. Towards that goal, we
first present a useful lemma.
Lemma 19. Suppose P(|G| ≤ t) = O(t) (as t → 0) and E|G|2 < ∞. If
χ(σ) = Cσ 2q−2 with a fixed number C > 0, then for 1 < q < 2 we have
(F.9)

Rq (χ(σ), σ) − 1
= −2C(1 − )qE|Z|q + C 2 q 2 E|G|2q−2 .
σ→0
σ 2q−2
lim

Moreover, if χ(σ) = o(σ 2q−2 ) then
Rq (χ(σ), σ) − 1
= 0.
σ→0
σ 2q−2

(F.10)

lim

Proof. We first focus on the case χ(σ) = Cσ 2q−2 . According to (F.4),
Rq (χ, σ) − 1 = (1 − )E(ηq2 (Z; χ) − Z 2 ) + χ2 q 2 E|ηq (G/σ + Z; χ)|2q−2
{z
}
|
{z
} |
R2

R1

Z; χ)|q−2

|ηq (G/σ +
−2χq(q − 1)E
.
1 + χq(q − 1)|ηq (G/σ + Z; χ)|q−2
|
{z
}
R3

Now we calculate the limit of each of the terms individually. We have
R1

=

(1 − )E(ηq (Z; χ) + Z)(ηq (Z; χ) − Z)

(a)

=

−(1 − )E(ηq (Z; χ) + Z)(χq|ηq (Z; χ)|q−1 sign(Z))

=

−(1 − )χq(E|ηq (Z; χ)|q + E|Z||ηq (Z; χ)|q−1 ),

where (a) is due to Lemma 7 part (i). Hence we obtain
(F.11)

lim

σ→0

R1
σ 2q−2

= −C(1 − )q lim (E|ηq (Z; χ)|q + E|Z||ηq (Z; χ)|q−1 )
σ→0

= −2C(1 − )qE|Z|q .

64

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

The last equality is by Dominated Convergence Theorem (DCT). For R2 ,
lim

(F.12)

σ→0

R2
σ 2q−2

χ2 q 2 E|ηq (G/σ + Z; χ)|2q−2
σ→0
σ 2q−2
2 2
= C q lim E|ηq (G + σZ; χσ 2−q )|2q−2
=

lim

σ→0

= C 2 q 2 E|G|2q−2 .
Regarding the term R3 , we would like to show that if χ(σ) = O(σ 2q−2 ), then
(F.13)

lim

σ→0

χ
σ 2q−2

E

1
= 0.
|ηq (G/σ + Z; χ)|2−q + χq(q − 1)

Define α1 = 1 if 1 < q < 3/2 and α1 = σ 2q−3+c if 3/2 ≤ q < 2, where c > 0
is a sufficiently small constant that we will specify later. Let F (g) be the
distribution function of |G| and α2 > 1 a fixed constant. So α1 < α2 for
small σ. Define the following two nested intervals
Ii (x) , [−x − αi , −x + αi ],

i = 1, 2.

Then the expression in (F.13) can be written as

=

χ
σ 2q−2
χ
σ 2q−2
χ
2q−2
σ

χ
1
E
σ 2q−2 |ηq (G/σ + Z; χ)|2−q + χq(q − 1)
Z ∞Z
1
φ(z)dzdF (g) +
2−q + χq(q − 1)
0
z∈I1 (g/σ) |ηq (g/σ + z; χ)|
Z ∞Z
1
φ(z)dzdF (g) +
2−q + χq(q − 1)
|η
(g/σ
+
z;
χ)|
q
0
z∈I2 (g/σ)\I1 (g/σ)
Z ∞Z
1
φ(z)dzdF (g)
2−q + χq(q − 1)
0
R\I2 (g/σ) |ηq (g/σ + z; χ)|

, G 1 + G2 + G3 .
We will bound each of the three integrals above. The idea is similar as the

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

65

one presented in the proof of Lemma 18. For the first integral,
Z ∞ Z −g/σ+α1
1
χ
G1 ≤
φ(z)dzdF (g)
σ 2q−2 0
χq(q
− 1)
−g/σ−α1
Z σ log 1/σ Z −g/σ+α1
χ
1
≤
φ(z)dzdF (g)
2q−2
σ
0
−g/σ−α1 χq(q − 1)
Z ∞
Z −g/σ+α1
1
χ
φ(z)dzdF (g)
+ 2q−2
σ
σ log 1/σ −g/σ−α1 χq(q − 1)
(b)

≤
≤

2α1 φ(0)
2α1 φ(log 1/σ − α1 )
+
q(q − 1)σ 2q−2
q(q − 1)σ 2q−2
α1
α1 φ((log 1/σ)/2)
O(1) · σ c log(1/σ) 2q−3+c + O(1) ·
σ
σ 2q−2
P(|G| ≤ σ log 1/σ)

(c)

→ 0, as σ → 0.
To obtain (b), we have used the following inequalities when σ is small:
Z

−g/σ+α1

φ(z)dz ≤ 2φ(0)α1 ,

for g ≤ σ log(1/σ),

−g/σ−α1
Z −g/σ+α1

φ(z)dz ≤ 2α1 φ(log(1/σ) − α1 ),

for g > σ log(1/σ).

−g/σ−α1

The limit (c) holds due to the choice of α1 . Regarding the second term G2 ,
Z ∞Z
χ
1
φ(z)dzdF (g)
G2 ≤
2q−2
2−q
σ
0
z∈I2 (g/σ)\I1 (g/σ) |ηq (g/σ + z; χ)|
Z σ log 1/σ Z
χ
1
=
φ(z)dzdF (g)
2q−2
2−q
σ
0
z∈I2 (g/σ)\I1 (g/σ) |ηq (g/σ + z; χ)|
Z ∞
Z
χ
1
+ 2q−2
φ(z)dzdF (g)
2−q
σ
σ log 1/σ z∈I2 (g/σ)\I1 (g/σ) |ηq (g/σ + z; χ)|
Z σ log 1/σ Z
(d)
χ
1
≤
φ(z)dzdF (g)
2q−2
2−q
σ
0
z∈I2 (g/σ)\I1 (g/σ) |ηq (α1 ; χ)|
Z ∞
Z
χ
1
+ 2q−2
φ(z)dzdF (g)
2−q
σ
σ log 1/σ z∈I2 (g/σ)\I1 (g/σ) |ηq (α1 ; χ)|
(e)

≤
(f )

≤

P(|G| ≤ σ log 1/σ)
O(1) · σ c log(1/σ)

2α2 φ(0)χ
2q−2
σ
|ηq (α1 ; χ)|2−q
1

α12−q σ c−1

+ O(1) ·

+

2α2 φ(log 1/σ − α2 )χ
σ 2q−2 |ηq (α1 ; χ)|2−q

φ((log 1/σ)/2)
α12−q

(g)

→ 0, as σ → 0,

66

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

where (d) is due to the fact |ηq (g/σ + z; χ)| ≥ ηq (α1 ; χ) for z ∈
/ I1 (g/σ); The
argument for (e) is similar to that for (b); (f ) holds based on two facts:
η (α ;χ)

1. limσ→0 q α11
= limσ→0 ηq (1; α1q−2 χ) = 1, since α1q−2 χ → 0. This is
obvious for the case α1 = 1. When α1 = σ 2q−3+c , we have α1q−2 χ =
2
O(1) · σ 2q +(c−5)q+4−2c and 2q 2 + (c − 5)q + 4 − 2c > 0 if c is chosen
small enough.
2. P(|G| ≤ σ log 1/σ) = O(σ log 1/σ). This is one of the conditions.
And finally (g) works as follows: it is clear that σ c log(1/σ)

1
σ c−1
α2−q
1

goes to

zero when α1 = 1; when α1 = σ 2q−3+c , we can sufficiently small c such that
2
α1q−2 σ 1−c = σ 2q +(c−7)q+7−3c = o(1). For the third integral G3 , we are able
to invoke DCT to obtain
I(|G/σ + Z| > α2 )
lim G3 = O(1) · lim E
= 0.
σ→0
σ→0 |ηq (G/σ + Z; χ)|2−q + χq(q − 1)
Note that DCT works because for small σ
I(|G/σ + Z| > α2 )
|ηq (G/σ + Z; χ)|2−q + χq(q − 1)
1
1
I(|G/σ + Z| > α2 )
≤
≤
.
≤
2−q
2−q
|ηq (G/σ + Z; χ)|
|ηq (α2 ; χ)|
|ηq (α2 ; 1)|2−q
We hence have showned that
R3
= 0.
σ 2q−2
Combining the results (F.11), (F.12), and (F.14) establishes (F.9).
To prove (F.10), first note that (F.14) has been derived in the general
setting χ(σ) = O(σ 2q−2 ). Moreover, we can use similar arguments to show
for χ(σ) = o(σ 2q−2 ),
R1
R2
lim 2q−2 = lim 2q−2 = 0.
σ→0 σ
σ→0 σ
This completes the proof.
(F.14)

lim

σ→0

We are in position to derive the convergence rate of Rq (χ∗q (σ), σ).
Lemma 20. Suppose P(|G| ≤ t) = O(t) (as t → 0) and E|G|2 < ∞.
Then for q ∈ (1, 2) we have
Rq (χ∗q (σ), σ) − 1
(1 − )2 (E|Z|q )2
=−
.
2q−2
σ→0
σ
E|G|2q−2
lim

Proof. According to Lemma 18, choosing C =
finishes the proof.

(1−)E|Z|q
qE|G|2q−2

in Lemma 19

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

67

F.4. Deriving the expansion of AMSE(λ∗,q , q, σw ). According to
Corollary 1 we know
AMSE(λ∗,q , q, σw ) = σ̄ 2 · Rq (χ∗q (σ̄), σ̄),

(F.15)

where σ̄ satisfies the following equation:
2
σ̄ 2 = σw
+

(F.16)

σ̄ 2
Rq (χ∗q (σ̄), σ̄).
δ

Since χ∗q (σ̄) minimizes Rq (χ, σ̄) we obtain
Rq (χ∗q (σ̄), σ̄) ≤ Rq (0, σ̄) = 1.
Therefore, under the condition δ > 1,
δ
1
2
σ2 ,
σ̄ 2 ≤ σw
+ σ̄ 2 ⇒ σ̄ 2 ≤
δ
δ−1 w

(F.17)

which implies that σ̄ → 0 as σw → 0. Accordingly, we combine Equation
(F.16) with the fact Rq (χ∗q (σ̄), σ̄) → 1 as σ̄ → 0 from Lemma 20 to conclude

 δ−1
2
2
σw
1
σw
∗
1
−
=
lim
=
lim
R
(χ
(σ̄),
σ̄)
=
.
q
q
σw →0 σ̄ 2
σ̄→0 σ̄ 2
σ̄→0
δ
δ

(F.18) lim

We now derive the expansion of AMSE(λ∗,q , q, σw ) presented in (3.4). From
(F.15) and (F.16) we can compute that
AMSE(λ∗,q , q, σw ) −

=

2
σw
1−1/δ

2q
σw
σ̄ 2 δ(Rq (χ∗q (σ̄), σ̄) − 1)
2q
(δ − 1)
σw

=
=

σ̄ 2 Rq (χ∗q (σ̄), σ̄) −
σ̄ 2q
2q
σw

1
1−1/δ

· (σ̄ 2 −

σ̄ 2
∗
δ Rq (χq (σ̄), σ̄))

2q
σw
Rq (χ∗q (σ̄), σ̄) − 1
δ
·
·
.
δ−1
σ̄ 2q−2

Letting σw → 0 on both sides of the above equation and using the results
from (F.18) and Lemma 20 completes the proof.
APPENDIX G: PROOF OF THEOREM 3.2
From (F.15) and (F.16) we see that
2
AMSE(λ∗,q , q, σw ) = δ(σ̄ 2 − σw
).

Hence Theorem 3.2 can be proved by showing
lim σ̄ > 0.

σw →0

68

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

For that purpose we first prove the following under the condition E|G|2 < ∞.
lim Rq (χ∗q (σ), σ) = 1.

(G.1)

σ→0

When q = 2, Rq (χ∗q (σ); σ) admits a nice explicit expression and can be
easily shown to converge to 1. For 1 < q < 2, since χ∗q (σ) is the minimizer
of Rq (χ, σ) we know
Rq (χ∗q (σ), σ) ≤ Rq (0, σ) = 1,
hence lim supσ→0 Rq (χ∗q (σ), σ) ≤ 1. On the other hand, (F.4) gives us
Rq (χ∗q (σ), σ) ≥ (1 − )E(ηq (Z; χ∗ ))2 − 


1
+2E
1 + χ∗ q(q − 1)|ηq (G/σ + Z; χ∗ )|q−2
where we have used χ∗ to denote χ∗q (σ) for simplicity. Based on Lemmas
16 and 17, we can apply Fatou’s lemma to the above inequality to obtain
lim inf σ→0 Rq (χ∗q (σ), σ) ≥ 1.
Next it is clear that
(G.2)

lim Rq (χ∗q (σ), σ) ≤ lim lim Rq (χ, σ) = 0.

σ→∞

σ→∞ χ→∞

We now consider an arbitrary convergent sequence σ̄n → σ ∗ . We claim
σ ∗ 6= 0. Otherwise Equation (F.16) tells us
Rq (χ∗q (σ̄n ), σ̄n ) < δ < 1,
and letting n → ∞ above contradicts (G.1). Now that σ ∗ > 0 we can take
n → ∞ in (F.16) to obtain
Rq (χ∗q (σ ∗ ), σ ∗ ) = δ < 1.
According to Lemma 12, it is not hard to confirm Rq (χ∗q (σ), σ) is a strictly
decreasing and continuous function of σ. Results (G.1) and (G.2) then imply
that σ ∗ is the unique solution to Rq (χ∗q (σ), σ) = δ. Since this is true for any
sequence, we have proved limσw →0 σ̄ exists and larger than zero.
APPENDIX H: PROOF OF THEOREM 3.4
H.1. Roadmap. Theorem 3.4 differs from Theorem 3.3 in that the order of the second dominant term of AMSE(λ∗,1 , 1, σw ) becomes polynomial
(ignore the logarithm term) when the distribution of G has mass around zero.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

69

However, the proof outline remains the same. We hence stick to the same
notations used in the proof of Theorem 3.3. In particular, R(χ, σ), χ∗ (σ)
represent Rq (χ, σ), χ∗q (σ) with q = 1, respectively. We characterize the convergence rate of χ∗ (σ) in Section H.2, and bound the convergence rate of
R(χ∗ (σ), σ) in Section H.3. After we characterize R(χ∗ (σ), σ), the rest of
the proof is similar to that in Section 6.4 from the main text. We therefore
do not repeat it here.
H.2. Bounding the convergence rate of χ∗ (σ).
Lemma 21. Suppose P(|G| ≤ t) = Θ(t` ) with ` > 0 (as t → 0) and
E|G|2 < ∞, then for sufficiently small σ

`
v
 
u
1 
u
αm σ ` ≤ χ∗ (σ) − χ∗∗ ≤ βm σ ` · tlog log . . . log
,
|
{z
} σ 
m times

where m > 0 is an arbitrary integer number, αm , βm > 0 are two constants
depending on m, and χ∗∗ is the unique minimizer of (1 − )E(η1 (Z; χ))2 +
(1 + χ2 ) over [0, ∞).
Proof. According to Lemma 3, χ∗ (σ) → χ∗∗ as σ → 0. To characterize
the convergence rate, we follow the same line of proof that we presented for
Lemma 4 and adopt the same notations. For simplicity we do not detail out
the entire proof and instead highlight the differences. The key difference is
that neither e1 or e2 are exponentially small in the current setting. We now
start by bounding e2 . Let F (g) be the distribution function of |G| and define
logm (a) , log log . . . log(a).
|
{z
}
m times

Given an integer m > 0 and a constant c > 0, we then have
Eφ(χ∗ − |G|/σ)
m−1
X Z cσ(logm−i (1/σ))1/2
=
φ(χ∗ − g/σ)dF (g) +
i=1

Z

cσ(logm−i+1 (1/σ))1/2

cσ(logm (1/σ))1/2

∗

Z

∞

φ(χ − g/σ)dF (g) +
0

≤

m−1
X

φ(χ∗ − g/σ)dF (g)

cσ(log(1/σ))1/2

φ(c(logm−i+1 (1/σ))1/2 − χ∗ ) · P(|G| ≤ cσ(logm−i (1/σ))1/2 ) +

i=1

(H.1)

φ(0) · P(|G| ≤ cσ(logm (1/σ))1/2 ) + φ(c(log(1/σ))1/2 − χ∗ ).

70

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

The condition P(|G| ≤ t) = Θ(t` ) leads to
m−1
X

φ(c(logm−i+1 (1/σ))1/2 − χ∗ ) · P(|G| ≤ cσ(logm−i (1/σ))1/2 )

i=1

≤

∗ 2
m−1
e(χ ) /2 X −(c2 logm−i+1 (1/σ))/4
√
e
· Θ(σ ` (logm−i (1/σ))`/2 )
2π i=1

= O(1) ·

m−1
X

σ ` (logm−i (1/σ))`/2−c

2 /4

,

i=1
2 /2

where we have used the simple inequality e−(a−b)
also clear that

≤ e−b

2 /4

2 /2

· ea

. It is

1
∗ 2
2
φ(c(log(1/σ))1/2 − χ∗ ) ≤ √ e(χ ) /2 · σ c /4 .
2π
Therefore, by choosing a sufficiently large c we can conclude that the dominant term in (H.1) is φ(0)P(|G| ≤ cσ(logm (1/σ))1/2 ) = Θ(σ ` (logm (1/σ))`/2 ).
Furthermore, choosing a fixed constant C > 0 we have the following lower
bound
Z Cσ
∗
Eφ(χ +|G|/σ) ≥
φ(χ∗ +g/σ)dF (g) ≥ φ(C +χ∗ )·P(|G| ≤ Cσ) = Θ(σ ` ).
0

Because
Eφ(χ∗ + |G|/σ) ≤ Eφ(χ∗ ± G/σ) ≤ Eφ(χ∗ − |G|/σ),
We are able to derive
Θ(σ ` ) ≤ Eφ(χ∗ ± G/σ) ≤ Θ(σ ` (logm (1/σ))`/2 ).
As a result we obtain the bound for e2 :
(H.2)

Θ(σ ` ) ≤ e2 ≤ Θ(σ ` (logm (1/σ))`/2 )

To bound e1 , recall that
Z −G/σ+χ∗
e1 = −E
φ(z)dz = −2χ∗ Eφ(aχ∗ − G/σ),
−G/σ−χ∗

where |a| ≤ 1 depends on G. We can find two positive constants C1 , C2 > 0
such that for small σ
C1 Eφ(χ∗ + |G|/σ) ≤ Eφ(aχ∗ − G/σ) ≤ C2 Eφ(χ∗ − |G|/σ).

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

71

Hence we have
Θ(σ ` ) ≤ −e1 ≤ Θ(σ ` (logm (1/σ))`/2 ).

(H.3)

Based on the results from (H.2) and (H.3) and Equation (6.9), we can use
similar arguments as in the proof of Lemma 4 to conclude
Θ(σ ` ) ≤ χ∗ (σ) − χ∗∗ ≤ Θ(σ ` (logm (1/σ))`/2 ).

H.3. Bounding the convergence rate of R(χ∗ (σ), σ).
Lemma 22. Suppose P(|G| ≤ t) = Θ(t` ) with ` > 0 (as t → 0) and
E|G|2 < ∞, then for sufficiently small σ
`

v
 
u
1 
u
≤ R(χ∗ (σ), σ) − M1 () ≤ −αm σ ` ,
−βm σ ` · tlog log . . . log
|
{z
} σ 
m times

where m > 0 is an arbitrary integer number and αm , βm > 0 are two constants depending on m.
Proof. We recall the two quantities:
M1 () = (1 − )E(η1 (Z; χ∗∗ ))2 + (1 + (χ∗∗ )2 )
R(χ∗ (σ), σ) = (1 − )E(η1 (Z; χ∗ ))2 + (1 + E(η1 (G/σ + Z; χ∗ ) − G/σ − Z)2 )
+2EZ(η1 (G/σ + Z; χ∗ ) − G/σ − Z).
Since χ∗ (σ) is the minimizer of R(χ, σ),
R(χ∗ (σ), σ) − M1 () ≤ R(χ∗∗ , σ) − M1 ()
=

[E(η1 (G/σ + Z; χ∗∗ ) − G/σ − Z)2 − (χ∗∗ )2 ] +
2EZ(η1 (G/σ + Z; χ∗∗ ) − G/σ − Z)

(a)

(H.4)

≤

(b)

−2EI(|G/σ + Z| ≤ χ∗∗ ) ≤ −Θ(σ ` ).

To obtain (a), we have used Lemma 11 and the fact |η1 (u; χ) − u| ≤ χ. (b)
is due to the similar arguments for bounding e1 in Lemma 21. To derive the
lower bound for R(χ∗ (σ), σ)−M1 (), we can follow the same reasoning steps
as in the proof of Lemma 5 and utilize the bound we derived for |χ∗ (σ)−χ∗∗ |
in Lemma 21. We will obtain
(H.5)

|R(χ∗ (σ), σ) − M1 ()| ≤ Θ(σ ` (logm (1/σ))`/2 ).

Putting (H.4) and (H.5) together completes the proof.

72

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

APPENDIX I: PROOF OF THEOREM 3.5
The proof of Theorem 3.5 is essentially the same as that of Theorem 3.2.
We do not repeat the details. Note the key argument limσ→0 R(χ∗ (σ), σ) =
M1 () has been shown in Lemma 3.
APPENDIX J: PROOF OF THEOREM 2.1
J.1. Roadmap of the proof. This appendix contains the proof of
Theorem 2.1. The proof for LASSO (q = 1) has been shown in [13]. We aim
to extend the results to 1 < q ≤ 2. We will follow similar proof strategy
as the one proposed in [13]. However, as will be described later some of the
steps are more challenging for 1 < q ≤ 2 (and some are easier). Motivated
by [13] we construct an approximate message passing (AMP) algorithm for
solving LQLS. We then establish an asymptotic equivalence between the
output of AMP and the bridge regression estimates. We finally utilize the
existing asymptotic results from AMP framework to prove Theorem 2.1. The
rest of the material is organized as follows. In Section J.2, we briefly review
approximate message passing algorithms and state some relevant results that
will be used later in our proof. Section J.3 collects two useful results to be
applied in the later proof. We describe the main proof steps in Section J.4.
J.2. Approximate message passing algorithms. For a function f :
R → R and a vector v ∈ Rm , we use f (v) ∈ Rm to denote the vector
(f (v1 ), . . . , f (vm )). Recall ηq (u; χ) is the proximal operator for the function
k·kqq . We are in the linear regression model setting: y = Xβ +w. To estimate
β, we adapt the AMP algorithm in [29] to generate a sequence of estimates
β t ∈ Rp , based on the following iterations (initialized at β 0 = 0, z 0 = y):
β t+1 = ηq (X T z t + β t ; θt ),
1
z t = y − Xβ t + z t−1 h∂1 ηq (X T z t−1 + β t−1 ; θt−1 )i,
(J.1)
δ
1 Pp
where hvi = p i=1 vi denotes the average of a vector’s components and
{θt } is a sequence of tuning parameters specified during the iterations. A
remarkable phenomenon about AMP is that the asymptotics of the sequence
{β t } can be characterized by one dimensional parameter, known as the state
of the system. The following theorem clarifies this claim.
Theorem J.1. Let {β(p), X(p), w(p)} be a converging sequence and ψ :
→ R be a pseudo-Lipschitz function. For any iteration number t > 0,

R2

p

1X
lim
ψ(βit+1 , βi ) = E[ψ(ηq (B + τt Z; θt ), B)],
p→∞ p
i=1

a.s.,

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

73

where B ∼ pβ and Z ∼ N (0, 1) are independent and {τt }∞
t=0 can be tracked
through the following recursion (τ02 = σ 2 + 1δ E|B|2 ):
(J.2)

1
2
2
τt+1
= σw
+ E[ηq (B + τt Z; θt ) − B]2 , t ≥ 0.
δ

Proof. According to Lemma 7 part (vi), ηq (u; χ) is a Lipschitz continuous function of u. We can then directly apply Theorem 1 in [12] to complete
the proof.
Equation (J.2) is called state evolution. Theorem J.1 demonstrates that
the general asymptotic performance of {β t } is sharply predicted by the state
evolution. From now on, we will consider the AMP estimates {β t } with
θt = χτt2−q in (J.1). The positive constant χ is the solution of (2.2) and
(2.3). Note we have proved in Section D.2 that the solution exists. We next
present a useful lemma that characterizes the convergence of {τt }. Recall
the definition in (D.6):

1
χmin = inf χ ≥ 0 : E(ηq2 (Z; χ)) ≤ 1 .
δ
Lemma 23. For any given χ ∈ (χmin , ∞), the sequence {τt }∞
t=0 generated
from (J.2) with θt = χτt2−q converges to a finite number as t → ∞.
2 + 1 E[η (B + τ Z; χτ 2−q ) − B]2 . According to
Proof. Denote H(τ ) = σw
q
δ
Corollary 2, we know H(τ ) = τ 2 has a unique solution. Furthermore, since
H(0) > 0 and H(τ ) < τ 2 when τ is large enough, it is straightforward to
confirm the result stated in the above lemma.

Denote τt → τ∗ as t → ∞. Lemma 23 and (J.2) together yield
(J.3)

1
2
τ∗2 = σw
+ E[ηq (B + τ∗ Z; χτ∗2−q ) − B]2 .
δ

This is the same as Equation (2.2). We hence see the connection between
AMP estimates and bridge regression. The main part of the proof for Theorem 2.1 is to rigorously establish such connection. In particular we will
show the sequence {β t } converges (in certain asymptotic sense) to β̂(λ, q) as
t → ∞ in Section J.4. Towards that goal, we present the next theorem that
shows asymptotic characterization of other quantities in the AMP algorithm.
2−q
)i. Under the
Theorem J.2. Define wt , 1δ h∂1 ηq (X T z t−1 + β t−1 ; χτt−1
conditions of Theorem J.1, we have almost surely

74

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG
kβ t+1 −β t k22
p
t→∞p→∞

= 0.

kz t+1 −z t k22
p

= 0.

(i) lim lim
(ii) lim lim
(iii)

t→∞p→∞
kz t k2
lim n 2
p→∞

= τt2 .

2−q
(iv) lim wt = 1δ E[∂1 ηq (B+τt−1 Z; χτt−1
)], where B, Z are the same random
p→∞

variables as in Theorem J.1.
Proof. All the results for q = 1 have been derived in [13]. We here
generalize them to the case 1 < q ≤ 2. Since the proof is mostly a direct
modification of that in [13], we only highlight the differences and refer the
reader to [13] for detailed arguments. According to the proof of Lemma 4.3
in [13], we have almost surely
kβ t+1 − β t k22
kz t+1 − z t k22
= lim
p→∞
p→∞
p
p
lim

2−q
χ)]2 ,
= E[ηq (B + Zt ; τt2−q χ) − ηq (B + Zt−1 ; τt−1

where (Zt , Zt−1 ) is jointly zero-mean gaussian, independent from B ∼ pβ ,
with covariance matrix defined by the recursion (4.13) in [13]. From Lemma
8, we know ηq (u; χ) is a differentiable function over (−∞, +∞) × (0, ∞).
Hence we can apply mean value theorem to obtain
2−q
E[ηq (B + Zt ; τt2−q χ) − ηq (B + Zt−1 ; τt−1
χ)]2

≤

2−q
)χ]2
E[∂1 ηq (a; b) · (Zt − Zt−1 ) + ∂2 ηq (a; b) · (τt2−q − τt−1

≤

2−q 2 2
) χ ]
2E[(∂1 ηq (a; b))2 · (Zt − Zt−1 )2 ] + 2E[(∂2 ηq (a; b))2 · (τt2−q − τt−1

(a)

≤

2−q 2 2 2
) χ q E|a|2q−2 ,
2E[(Zt − Zt−1 )2 ] + 2(τt2−q − τt−1

where (a, b) is a point on a line that connects the two points (B + Zt , τt2−q χ)
2−q
and (B + Zt−1 , τt−1
χ); we have used Lemma 7 part (ii) and Lemma 10 part
(i)(ii) to obtain (a). Note that Lemma 23 implies the second term on the
right hand side of the last inequality goes to zero, as t → ∞. Regarding the
first term, we can follow similar proof steps as for Lemma 5.7 in [13] to show
E(Zt − Zt−1 )2 → 0, as t → ∞.
The proof of part (iii) is the same as that of Lemma 4.1 in [13]. We
do not repeat the proof here. For (iv), Lemma F.3(b) in [13] implies the
empirical distribution of {((X T z t−1 +β t−1 )i , βi )}pi=1 converges weakly to the
2−q
distribution of (B + τt−1 Z, B). Since the function J(y, z) , ∂1 ηq (y; χτt−1
) is
bounded and continuous with respect to (y, z) according to Lemma 7 part
(i) and Lemma 8, (iv) follows directly from the Portmanteau theorem.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

75

J.3. Two useful theorems. In this section, we refer to two useful
theorems that have also been applied and cited in [13]. The first one is
regarding the limit of the singular values of random matrices taken from
[49].
Theorem J.3. (Bai and Yin, 1993). Let X ∈ Rn×p be a matrix having
i.i.d. entries with EXij = 0, EXij2 = 1/n. Denote by σmax (X), σmin (X) the
largest and smallest non-zero singular values of X, respectively. If n/p →
δ > 0, as p → ∞, then
1
lim σmax (X) = √ + 1, a.s.,
δ
1
lim σmin (X) = √ − 1 , a.s.
p→0
δ
p→0

The second theorem establishes the relation between `1 and `2 norm for
vectors from random subspace, showed in [50].
Theorem J.4. (Kashin, 1977). For a given constant 0 < v ≤ 1, there
exists a universal constant cv such that for any p ≥ 1 and a uniformly
random subspace V of dimension p(1 − v),


1
P ∀β ∈ V : cv kβk2 ≤ √ kβk1 ≥ 1 − 2−p .
p
J.4. The main proof steps. As mentioned before we will use similar
arguments as the ones shown in [13]. To avoid redundancy, we will not
present all the details and rather emphasize on the differences. We suggest
interested readers going over the proof in [13] before studying this section.
Similar to [13], we start with a lemma that summarizes several structural
properties of LQLS formulation. Define F(β) , 12 ky − Xβk22 + λkβkqq .
Suppose β, r ∈ Rp satisfy the following conditions:
√
krk2 ≤ c1 p
F(β + r) ≤ F(β)
√
k∇F (β)k2 P
≤ p
sup0≤µi ≤1 pi=1 |βi + µi ri |2−q ≤ pc2
0 < c3 ≤ σmin (X), where σmin (X) is defined in Theorem J.3

Lemma 24.
(i)
(ii)
(iii)
(iv)
(v)

(vi) krk k22 ≤ c4
7

krk k21
p .

The vector rk ∈ Rp is the projection of r onto ker(X)7

It is the nullspace of X defined as ker(X) = {β ∈ Rp | Xβ = 0}.

76

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Then there exists a function f (, c1 , c2 , c3 , c3 , c4 , λ, q) such that
krk2 ≤

√

pf (, c1 , c2 , c3 , c4 , λ, q).

Moreover, f (, c1 , c2 , c3 , c4 , λ, q) → 0 as  → 0.
Proof. First note that
∇F(β) = −X T (y − Xβ) + λq(|β1 |q−1 sign(β1 ), . . . , |βp |q−1 sign(βp ))T .
Combining it with Condition (ii) we have
0 ≥ F(β + r) − F(β)
1
1
= ky − Xβ − Xrk22 + λkβ + rkqq − ky − Xβk22 − λkβkqq
2
2
1
2
T T
= kXrk2 − r X (y − Xβ) + λ(kβ + rkqq − kβkqq )
2
p
X
1
2
T
= kXrk2 + r ∇F(β) + λ
(|βi + ri |q − |βi |q − qri |βi |q−1 sign(βi ))
2
i=1

p

(a)

(J.4)

λq(q − 1) X
1
≥ kXrk22 + rT ∇F(β) +
|βi + µi ri |q−2 ri2 ,
2
2
i=1

where (a) is obtained by Lemma 25 that we will prove shortly and {µi } are
numbers between 0 and 1. Note that we can decompose r as r = rk + r⊥
such that rk ∈ ker(X), r⊥ ∈ ker(X)⊥ . Accordingly Condition (v) yields
c23 kr⊥ k22 ≤ kXr⊥ k22 . This fact combined with Inequality (J.4) implies
c23 ⊥ 2 1
1
kr k2 ≤ kXr⊥ k22 = kXrk22 ≤ −rT ∇F(β) ≤ krk2 · k∇F(β)k2 ≤ c1 p,
2
2
2
where the last inequality is derived from Condition (i) and (iii). Hence we
can obtain
2c1 p
kr⊥ k22 ≤
.
c23
Our next step is to bound krk k22 . By Cauchy-Schwarz inequality we know
p
X
i=1

p
q
X
p
|ri | =
|βi + µi ri |2−q · ri2 |βi + µi ri |q−2 ,
i=1

v
v
u p
u p
uX
uX
t
2−q
≤
|βi + µi ri |
·t
ri2 |βi + µi ri |q−2 .
i=1

i=1

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

77

So
p
X

(J.5)

krk21
.
2−q
i=1 |βi + µi ri |

ri2 |βi + µi ri |q−2 ≥ Pp

i=1

Combining Inequality (J.4) and (J.5) gives us
krk21 ≤

p
(b) 2c c 
−2rT ∇F(β) X
1 2
·
|βi + µi ri |2−q ≤
p2 ,
λq(q − 1)
λq(q − 1)
i=1

where we have used Conditions (i), (iii), and (iv) to derive (b). Using the
upper bounds we obtained for krk21 and kr⊥ k22 , together with Condition (vi),
it is straightforward to verify the following chains of inequalities
krk k22 ≤
≤

c4 k 2 2c4
2c4
kr k1 ≤
(krk21 + kr⊥ k21 ) ≤
(krk21 + pkr⊥ k22 )
p
p
p
2c4  2c1 c2  2 2c1  2   4c1 c2 c4
4c1 c4 
· p.
·
p + 2 p =
+ 2
p
λq(q − 1)
λq(q − 1)
c3
c3

We are finally able to derive
krk22 = krk k22 + kr⊥ k22 ≤

 4c c c
4c1 c4 2c1 
1 2 4
+ 2 + 2 · p.
λq(q − 1)
c3
c3

This completes the proof.
Note that Lemma 24 is a non-asymptotic and deterministic result. It
sheds light on the behavior of the cost function F(β) around its global
minimum. Suppose β + r is the global minimizer (a reasonable assumption
according to Condition (ii)), and if there is another point β having small
function value (indicated by its gradient from Condition (iii)), then the
distance krk2 between β and the optimal solution β + r should also be
small. This interpretation should not sound surprising, since we already
know F(β) is a strictly convex function. However, Lemma 24 enables us
to characterize this property in a precise way, which is crucial in the high
dimensional asymptotic analysis. Based on Lemma 24, we will set β + r =
β̂(λ, q), β = β t and then verify all the conditions in Lemma 24 to conclude
krk2 = kβ̂(λ, q) − β t k2 is small. In particular that small distance will vanish
as t → ∞, thus establishing the asymptotic equivalence between β̂(λ, q) and
β t . We perform the analysis in a sequel of lemmas and Proposition 1.
Lemma 25. Given a constant q satisfying 1 < q ≤ 2, for any x, r ∈ R,
there exists a number 0 ≤ µ ≤ 1 such that
(J.6)

|x + r|q − |x|q − rq|x|q−1 sign(x) ≥

q(q − 1)
|x + µr|q−2 r2 .
2

78

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Proof. Denote fq (x) = |x|q . When q = 2, since f2 (x) is a smooth function over (−∞, +∞), we can apply Taylor’s theorem to obtain (J.6). For any
1 < q < 2, note that fq00 (0) = ∞, hence Taylor’s theorem is not applicable
to all the values of x ∈ R. We prove the inequality above in separate cases.
First observe that if (J.6) holds for any x > 0, r ∈ R, then it is true for any
x < 0, r ∈ R as well. It is also straightforward to confirm that when x = 0,
we can always choose µ = 1 to satisfy Inequality (J.6) for any r ∈ R. We
therefore focus on the case x > 0, r ∈ R.
a. When x + r > 0, since fq (x) is a smooth function over (0, ∞), we can
apply Taylor’s theorem to obtain (J.6).
b. If x+r = 0, choosing µ = 0, Inequality (J.6) is simplified to (q−1)xq ≥
q(q−1) q
2 x , which is clearly valid.
c. When x + r < 0, we consider two different scenarios.
i. First suppose −x − r ≥ x. We apply (J.6) to the pair −r − x and
x. Then we know there exists 0 ≤ µ̃ ≤ 1 such that
|x + r|q − |x|q ≥

q(q − 1)
|µ̃(−x − r) + (1 − µ̃)x|q−2 (2x + r)2
2
−(2x + r)q|x|q−1

It is also straightforward to verify that there is 0 ≤ µ ≤ 1 so that
µ(x + r) + (1 − µ)x = −µ̃(−x − r) − (1 − µ̃)x. Denote
g(y) =

q(q − 1)
|µ̃(−x − r) + (1 − µ̃)x|q−2 y 2 + q|x|q−1 y.
2

If we can show g(−2x − r) ≥ g(r), we can obtain the Inequality
(J.6). It is easily seen that the quadratic function g(y) achieves
global minimum at
y0 =

−1
−1
|x|q−1 |µ̃(−x − r) + (1 − µ̃)x|2−q ≤
|x| < −x.
q−1
q−1

Moreover, note that −2x − r ≥ 0, r < 0 and they are symmetric
around y = −x, hence g(−2x − r) ≥ g(r).
ii. Consider 0 < −x−r < x. We again use (J.6) for the pair −x−−r
and x to obtain
q(q − 1)
|µ̃(x + r) − (1 − µ̃)x|q−2 (2x + r)2
2
q(q − 1) q−2
−(2x + r)q|x|q−1 ≥ (−2x − r)q|x|q−1 +
|x| (2x + r)2 .
2

|x + r|q − |x|q ≥

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

79

q−2 y 2 + q|x|q−1 y. If we can show h(−2x −
Denote h(y) = q(q−1)
2 |x|
r) ≥ h(r), Inequality (J.6) will be established with µ = 0. Since
−1
h(x) achieves global minimum at y0 = q−1
|x| < −x and −2x−r >
r, we can get h(−2x − r) ≥ h(r).

The next lemma is similar to Lemma 3.2 in [13]. The proof is adapted
from there.
Lemma 26. Let {β(p), X(p), w(p)} be a converging sequence. Denote the
solution of LQLS by β̂(λ, q), and let {β t }t≥0 be the sequence of estimates
generated from the AMP algorithm. There exists a positive constant C s.t.
kβ t k22
≤ C,
t→∞ p→∞
p
lim lim

lim sup
p→∞

a.s.,

kβ̂(λ, q)k2
≤ C,
p

a.s.

Proof. To show the first inequality, according to Theorem J.1 and Lemma
23, choosing a particular pseudo-Lipschitz function ψ(x, y) = x2 we obtain
kβ t k22
= EB,Z [ηq (B + τ∗ Z; χτ∗2−q )]2 < ∞,
t→∞ p→∞
p
lim lim

a.s.,

where B ∼ pβ and Z ∼ N (0, 1) are independent. For the second inequality,
first note that since β̂(λ, q) is the optimal solution we have

(J.7)

1
λkβ̂(λ, q)kqq ≤ F(β̂(λ, q)) ≤ F(0) = kyk22
2
1
2
2
2
2
=
kXβ + wk2 ≤ kXβk2 + kwk2 ≤ σmax (X)kβk22 + kwk22 .
2

We then consider the decomposition β̂(λ, q) = β̂(λ, q)⊥ + β̂(λ, q)k , where
β̂(λ, q)⊥ ∈ ker(X)⊥ and β̂(λ, q)k ∈ ker(X). Since ker(X) is a uniformly
random subspace with dimension p(1 − δ)+ , we can apply Theorem J.4 to
conclude that, there exists a constant c(δ) > 0 depending on δ such that the
following holds with high probability,
kβ̂(λ, q)k22 = kβ̂(λ, q)k k22 + kβ̂(λ, q)⊥ k22 ≤

(J.8)

kβ̂(λ, q)k k21
+ kβ̂(λ, q)⊥ k22
c(δ)p

≤

2kβ̂(λ, q)⊥ k21 + 2kβ̂(λ, q)k21
+ kβ̂(λ, q)⊥ k22
c(δ)p

≤

2kβ̂(λ, q)k21 2 + c(δ)
+
kβ̂(λ, q)⊥ k22 .
c(δ)p
c(δ)

80

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

Moreover, Hölder’s inequality combined with Inequality (J.7) yields
(J.9)

kβ̂(λ, q)k1
≤
p

kβ̂(λ, q)kqq
p

!1/q
≤

2 (X)kβk2 + kwk2
σmax
2
2
λp

!1/q
.

Using the results from (J.8) and (J.9), we can then upper bound kβ̂(λ, q)k22 :
kβ̂(λ, q)k22 (a) 2
≤
p
c(δ)

2 (X)kβk2 + kwk2
σmax
2
2
λp

!2/q
+

2 + c(δ)
⊥ 2
2 (X) kX β̂(λ, q) k2 .
pc(δ)σmin

2 (X)kβ̂(λ, q)⊥ k2 .
To obtain (a) we have used the fact kX β̂(λ, q)⊥ k22 ≥ σmin
2
We can further bound
(b)

(c)

(d)

2
kX β̂(λ, q)⊥ k22 ≤ 2ky − X β̂(λ, q)k22 + 2kyk22 ≤ 4kyk22 ≤ 8σmax
(X)kβk22 + 8kwk22 .

(b) is due to the simple fact X β̂(λ, q)⊥ = X β̂(λ, q); (c) and (d) hold since
ky − X β̂(λ, q)k22 ≤ 2F(β̂(λ, q)) and inequalities in (J.7). Combining the last
two chains of inequalities we obtain with probability larger than 1 − 2−p
kβ̂(λ, q)k22
2
≤
p
c(δ)
+

2 (X)kβk2 + kwk2
σmax
2
2
λp

!2/q

2 (X)kβk2 + kwk2
16 + 8c(δ) σmax
2
2
·
.
2 (X)
p
c(δ)σmin

Finally, because both σmin (X) and σmax (X) converge to non-zero constants by Theorem J.3 and (β, X, w) is a converging sequence, the right
hand side of the above inequality converges to a finite number.
Lemma 27. Let {β(p), X(p), w(p)} be a converging sequence. Denote the
solution of LQLS by β̂(λ, q), and let {β t }t≥0 be the sequence of estimates
generated from the AMP algorithm.There exists a positive constant C̃ s.t.
Pp
t 2−q
i=1 |µi β̂i (λ, q) + (1 − µi )βi |
lim sup lim sup sup
< C̃, a.s.
p
p→∞ 0≤µi ≤1
t→∞
Proof. For any given 0 ≤ µi ≤ 1, it is straightforward to see
|µi β̂i (λ, q)+(1−µi )βit |2−q ≤ max{|β̂i (λ, q)|2−q , |βit |2−q } ≤ |β̂i (λ, q)|2−q +|βit |2−q .

81

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

Hence using Hölder’s inequality gives us
p

1X
|µi β̂i (λ, q) + (1 − µi )βit |2−q
p
0≤µi ≤1
sup

i=1

≤

1
p

p
X

p
p
p
 2−q  1 X
 2−q
1 X t 2−q  1 X
2
2
+
.
|βi |
≤
|β̂i (λ, q)|2
|βit |2
p
p
p

|β̂i (λ, q)|2−q +

i=1

i=1

i=1

i=1

Applying Lemma 26 to the above inequality finishes the proof.
The next lemma is similar to Lemma 3.3 in [13]. The proof is adapted
from there.
Lemma 28. Let {β(p), X(p), w(p)} be a converging sequence. Let {β t }t≥0
be the sequence of estimates generated from the AMP algorithm. We have
k∇F(β t )k22
= 0,
t→∞ p→∞
p
lim lim

a.s.

Proof. Recall the AMP updating rule (J.1):
2−q
β t = ηq (X T z t−1 + β t−1 ; τt−1
χ).

According to Lemma 7 part (i) we know β t satisfies
2−q
χq(|β1t |q−1 sign(β1t ), . . . , |βpt |q−1 sign(βpt ))T .
X T z t−1 + β t−1 = β t + τt−1

The rule (J.1) also tells us
z t = y − Xβ t + wt z t−1 ,
where wt is defined in Theorem J.2. Note
∇F(β t ) = −X T (y − Xβ t ) + λq(|β1t |q−1 sign(β1t ), . . . , |βpt |q−1 sign(βpt ))T .
We can then upper bound ∇F(β t ) in the following way:
1
1
2−q
√ k∇F(β t )k2 = √ k − X T (y − Xβ t ) + λ(τt−1 χ)−1 X T z t−1 + β t−1 − β t k2
p
p
1
2−q −1
= √ k − X T (z t − wt z t−1 ) + λ(τt−1
χ) (X T z t−1 + β t−1 − β t )k2
p
≤

2−q
λkβ t−1 − β t k2 kX T (z t−1 − z t )k2 |λ + τt−1 χ(wt − 1)| · kX T z t−1 k2
+
+
√
2−q √
2−q √
p
τt−1
χ p
τt−1
χ p

≤

2−q
λkβ t−1 − β t k2 σmax (X)kz t−1 − z t k2 σmax (X)|λ + τt−1 χ(wt − 1)| · kz t−1 k2
+
+
.
√
2−q √
2−q √
p
τt−1
χ p
τt−1
χ p

82

HAOLEI WENG, ARIAN MALEKI AND LE ZHENG

By Lemma 23, Theorem J.2 part (i)(ii) and Theorem J.3, it is straightforward to confirm that the first two terms on the right hand side of the
last inequality vanish almost surely, as p → ∞, t → ∞. For the third term,
Lemma 23 and Theorem J.2 part (iii)(iv) imply
2−q
|λ + τt−1
χ(wt − 1)| · kz t−1 k2
2−q √
t→∞ p→∞
τt−1
χ p
√


1 0
δτ∗
2−q
2−q
λ
−
τ
χ
1
−
= 0,
=
Eη
(B
+
τ
Z;
τ
χ)
∗
∗
∗
δ q
τ∗2−q χ

lim lim

a.s.

To obtain the last equality, we have used Equation (2.3).
We are in position to prove the asymptotic equivalence between AMP
estimates and bridge regression.
Proposition 1. Let {β(p), X(p), w(p)} be a converging sequence. Denote the solution of LQLS by β̂(λ, q), and let {β t }t≥0 be the sequence of
estimates generated from the AMP algorithm. We then have
(J.10)

lim lim

t→∞ p→∞

1
kβ̂(λ, q) − β t k22 = 0,
p

a.s.

Proof. We utilize Lemma 24. Let β +r = β̂(λ, q), β = β t . If this pair of β
krk2

t

k2
and r satisfies the conditions in Lemma 24, we will have p 2 = kβ̂(λ,q)−β
p
being very small. In the rest of the proof, we aim to verify that the conditions in Lemma 24 hold with high probability and establish the connection
between the iteration numbers t and  in Lemma 24.

a. Condition (i) follows from Lemma 26:
√
krk2
kβ̂(λ, q)k2
kβ t k2
lim lim sup √ ≤ lim sup
+ lim lim √ ≤ 2 C,
√
t→∞ p→∞
t→∞p→∞
p
p
p
p→∞
b.
c.
d.
e.
f.

Condition
Condition
Condition
Condition
Condition

a.s.

(ii) holds since β̂(λ, q) is the optimal solution of F(β).
(iii) holds by Lemma 28. Note that  → 0, as t → ∞.
(iv) is due to Lemma 27.
(v) is the result of Theorem J.3.
(vi) is a direct application of Theorem J.4.

Note all the claims made above hold almost surely as p → ∞; and  → 0 as
t → ∞. Hence the result (J.10) follows.

HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

83

Based on the results from Theorem J.1, Lemma 23 and Proposition 1, we
can use exactly the same arguments as in the proof of Theorem 1.5 from [13]
to finish the proof of Theorem 2.1. Since the arguments are straightforward,
we do not repeat it here.
H. Weng
Department of Statistics
Columbia University
1255 Amsterdam Avenue
New York, NY, 10027
USA
E-mail: hw2375@columbia.edu

A. Maleki
Department of Statistics
Columbia University
1255 Amsterdam Avenue
New York, NY, 10027
USA
E-mail: arian@stat.columbia.edu

L. Zheng
Department of Electrical Engineering
Columbia University
1300 S. W. Mudd Building, MC 4712
500 W. 120th Street
New York, NY 10027
USA
E-mail: le.zheng.cn@gmail.com

