Relaxed Lasso

doi:10.1016/j.csda.2006.12.019

Computational Statistics & Data Analysis

Volume 52, Issue 1, 15 September 2007, Pages 374-393

https://doi.org/10.1016/j.csda.2006.12.019 Get rights and content

Abstract

The Lasso is an attractive regularisation method for high-dimensional regression. It combines variable selection with an efficient computational procedure. However, the rate of convergence of the Lasso is slow for some sparse high-dimensional data, where the number of predictor variables is growing fast with the number of observations. Moreover, many noise variables are selected if the estimator is chosen by cross-validation. It is shown that the contradicting demands of an efficient computational procedure and fast convergence rates of the $ℓ_{2}$ -loss can be overcome by a two-stage procedure, termed the relaxed Lasso. For orthogonal designs, the relaxed Lasso provides a continuum of solutions that include both soft- and hard-thresholding of estimators. The relaxed Lasso solutions include all regular Lasso solutions and computation of all relaxed Lasso solutions is often identically expensive as computing all regular Lasso solutions. Theoretical and numerical results demonstrate that the relaxed Lasso produces sparser models with equal or lower prediction loss than the regular Lasso estimator for high-dimensional data.

Keywords

High dimensionality

Bridge estimation

Lasso

ℓ_{q}

-norm penalisation

Dimensionality reduction

1. Introduction

The current work is motivated by linear prediction for high-dimensional data, where the number of predictor variables p is very large, possibly very much larger than the number of observations n (e.g. van de Geer and van Houwelingen, 2004). Regularisation is clearly of central importance for these high-dimensional problems.

There are many criteria to consider when choosing an appropriate regularisation method. First, not all regularisation procedures are adequate for the high-dimensional case. The non-negative Garotte (Breiman, 1995) is for example a promising regularisation method. However, it is not suited for the case $p > n$ as it requires computation of the OLS-estimator, which is unavailable in this case. An important criterion in the presence of many predictor variables is the computational complexity of the procedure. Many regularisation procedures with otherwise attractive features involve, unfortunately, minimisation of a non-convex function (e.g. Fan and Li, 2001, Tsybakov and van de Geer, 2005). For high-dimensional problems, it is in general very costly to find an (approximate) solution in this case, due to the presence of local minima in the objective function.

For Bridge estimators, which were proposed in Frank and Friedman (1993), we study in the following the tradeoff between computational complexity on the one hand and (asymptotic) properties of the estimators on the other hand. Let $X = (X^{1}, \dots, X^{p})$ be a p-dimensional predictor variable and Y a response variable of interest. For n independent observations $(Y_{i}, X_{i})$ , $i = 1, \dots, n$ , of $(Y, X)$ , Bridge estimators are defined for $λ, γ \in [0, \infty)$ as(1) $\hat{β}^{λ, γ} = \arg \min_{β} n^{- 1} \sum_{i = 1}^{n} (Y_{i} - X_{i}^{T} β)^{2} + λ ∥ β ∥_{γ},$ where $∥ β ∥_{γ} = \sum_{k \in {1, \dots, p}} | β_{k} |^{γ}$ is the $ℓ_{γ}$ -norm of the vector of coefficients, and $γ$ is typically in the range $[0, 2]$ .

For $γ = 0$ , Bridge estimation corresponds to ordinary model selection. Ridge regression is obtained for $γ = 2$ , while $γ = 1$ is equivalent to the Lasso proposed in Tibshirani (1996). Computation of the estimator (1) involves minimisation of a non-convex function if $γ < 1$ , while the function is convex for $γ ⩾ 1$ . Since optimisation of a non-convex function in a high-dimensional setting is very difficult, Bridge estimation with $γ ⩾ 1$ is an attractive choice. However, for values of $γ > 1$ , the shrinkage of estimators towards zero increases with the magnitude of the parameter being estimated (Knight and Fu, 2000). For the Lasso ( $γ = 1$ ), the shrinkage is constant irrespective of the magnitude of the parameter being estimated (at least for orthogonal designs, where regularisation with the Lasso is equivalent to soft-thresholding of the estimates). It was recognised in Fan and Li (2001) that this leads to undesirable properties (in terms of prediction) of the resulting estimator. It was first suggested by Huber (1973) to examine the asymptotic properties for a growing number $p = p_{n}$ of predictor variables as a function of the number of observations n, see as well Fan and Peng (2004). It will be shown below that the shrinkage of the Lasso leads to a low convergence rate of the $ℓ_{2}$ -loss for high-dimensional problems where the number of parameters $p = p_{n}$ is growing almost exponentially fast with n, so that $p_{n} ⪢ n$ .

For $γ < 1$ , the shrinkage of estimates decreases with increasing magnitude of the parameter being estimated and faster convergence rates can thus in general be achieved (see e.g. Knight and Fu, 2000 and, for classification, Tsybakov and van de Geer, 2005). However, the fact remains that for $γ < 1$ a non-convex optimisation problem has to be solved.

There is no value of $γ$ for which an entirely satisfactory compromise is achieved between low computational complexity on the one hand and fast convergence rates on the other hand. In this paper, it is shown that a two-stage procedure, termed relaxed Lasso, can work around this problem. The method has low computational complexity (the computational burden is often identical to that of an ordinary Lasso solution) and, unlike the Lasso, convergence rates are fast, irrespective of the growth rate of the number of predictor variables. Moreover, relaxed Lasso leads to consistent variable selection under a prediction-optimal choice of the penalty parameters, which does not hold true for ordinary Lasso solutions in a high-dimensional setting.

2. Relaxed Lasso

We define relaxed Lasso estimation and illustrate the properties of the relaxed Lasso estimators for an orthogonal design. A two-stage algorithm for computing the relaxed Lasso estimator is then proposed, followed by a few remarks about extending the procedure to generalised linear models (McCullagh and Nelder, 1989).

Recall that the Lasso estimator under a squared error loss is defined in Tibshirani (1996) for $λ \in [0, \infty)$ as(2) $\hat{β}^{λ} = \arg \min_{β} n^{- 1} \sum_{i = 1}^{n} (Y_{i} - X_{i}^{T} β)^{2} + λ ∥ β ∥_{1} .$ The Lasso estimator is a special case of the Bridge estimator (1), obtained by setting $γ = 1$ . The set of predictor variables selected by the Lasso estimator $\hat{β}^{λ}$ is denoted by $M_{λ}$ ,(3) $M_{λ} = {1 ⩽ k ⩽ p | \hat{β}_{k}^{λ} \neq 0} .$ For sufficiently large penalties $λ$ (e.g. for $λ > 2 \max_{k} n^{- 1} \sum_{i = 1}^{n} Y_{i} X_{i}^{k}$ ), the selected model is the empty set, $M_{λ} = \emptyset$ , as all components of the estimator (2) are identical to zero. In the absence of a $ℓ_{1}$ -penalty and if the number of variables p is smaller than the number of observations n, all predictor variables are in general selected, so that $M_{0} = {1, \dots, p}$ in this case.

The $ℓ_{1}$ -penalty for the ordinary Lasso estimator (2) has two effects, model selection and shrinkage estimation. On the one hand, a certain set of coefficients is set to zero and hence excluded from the selected model. On the other hand, for all variables in the selected model $M_{λ}$ , coefficients are shrunken towards zero compared to the least-squares solution. These two effects are clearly related and can be best understood in the context of orthogonal design as soft-thresholding of the coefficients. Nevertheless, it is not immediately obvious whether it is indeed optimal to control these two effects, model selection on the one hand and shrinkage estimation on the other hand, by a single parameter only. As an example, it might be desirable in some situations to estimate the coefficients of all selected variables without shrinkage, corresponding to a hard-thresholding of the coefficients.

As a generalisation of both soft- and hard-thresholding, we control model selection and shrinkage estimation by two separate parameters $λ$ and $φ$ with the relaxed Lasso estimator.

Definition 1

The relaxed Lasso estimator is defined for $λ \in [0, \infty)$ and $φ \in (0, 1]$ as(4) $\hat{β}^{λ, φ} = \arg \min_{β} n^{- 1} \sum_{i = 1}^{n} (Y_{i} - X_{i}^{T} {β \cdot 1_{M_{λ}}})^{2} + φ λ ∥ β ∥_{1},$ where $1_{M_{λ}}$ is the indicator function on the set of variables $M_{λ} \subseteq {1, \dots, p}$ so that for all $k \in {1, \dots, p}$ , ${β \cdot 1_{M_{λ}}}_{k} = \{\begin{matrix} 0, & k \notin M_{λ}, \\ β_{k}, & k \in M_{λ} . \end{matrix}$

Note that only predictor variables in the set

M_{λ}

are considered for the relaxed Lasso estimator. The parameter

λ

controls thus the variable selection part, as in ordinary Lasso estimation. The relaxation parameter

φ

controls on the other hand the shrinkage of coefficients. If

φ = 1

, the Lasso and relaxed Lasso estimators are identical. For

φ < 1

, the shrinkage of coefficients in the selected model is reduced compared to ordinary Lasso estimation. The case of

φ = 0

needs special consideration, as the definition above would produce a degenerate solution. In the following, we define the relaxed Lasso estimator for

φ = 0

as the limit of the above definition for

φ \to 0

. In this case, all coefficients in the model

M_{λ}

are estimated by the OLS-solution. This estimator (for

φ = 0

) was already proposed in Efron et al. (2004) as Lars–OLS hybrid, “using Lars to find the model but not to estimate the coefficients” (Efron et al., 2004). The reduction of the sum of squared residuals of this hybrid method over the ordinary Lasso estimator was found to be small for the studied data set, which contained 10 predictor variables only.

We will show further below that the gains with relaxed Lasso estimation (adaptive $φ$ ) compared to ordinary Lasso estimation ( $φ = 1$ ) can be very large. Moreover, relaxed Lasso is producing in most cases better results than the Lars–OLS hybrid ( $φ = 0$ ), as relaxed Lasso can adapt the amount of shrinkage to the structure of the underlying data.

An algorithm is developed to compute the exact solutions of the relaxed Lasso estimator. The parameters $λ$ and $φ$ can then be chosen e.g. by cross-validation. The algorithm is based on the Lars-algorithm by Efron et al. (2004). As the relaxed Lasso estimator is parameterised by two parameters, a two-dimensional manifold has to be covered to find all solutions. The computational burden of computing all relaxed Lasso estimators is in the worst case identical to that of the Lars–OLS hybrid and in the best case identical to that of the Lars-algorithm. The method is thus very well suited for high-dimensional problems.

2.1. Orthogonal design

To illustrate the properties of the relaxed Lasso estimator, it is instructive to consider an orthogonal design. The shrinkage of various regularisation methods are shown in Fig. 1 for this case. The set of solutions of the relaxed Lasso estimator is given for all $k = 1, \dots, p$ by $\hat{β}_{k}^{λ, φ} = \{\begin{matrix} \hat{β}_{k}^{0} - φ λ, & \hat{β}_{k}^{0} > λ, \\ 0, & | \hat{β}_{k}^{0} | ⩽ λ, \\ \hat{β}_{k}^{0} + φ λ, & \hat{β}_{k}^{0} < - λ, \end{matrix}$ where $\hat{β}^{0}$ is the OLS-solution. For $φ = 0$ , hard-thresholding is achieved, while $φ = 1$ results—as mentioned above—in soft-thresholding, which corresponds to the Lasso solution. The relaxed Lasso provides hence a continuum of solutions that includes soft- and hard-thresholding, much like the set of solutions provided by the Bridge estimators (1) when varying $γ$ in the range $[0, 1]$ . It can be seen in Fig. 1 that the solutions to the Bridge estimators and the relaxed Lasso solutions are indeed very similar.

2.2. Algorithm

The main advantage of the relaxed Lasso estimator over Bridge estimation is the low computational complexity. We propose in the following a naive, easy to implement, algorithm for computing relaxed Lasso estimators as in (4). Based on some more insight, a modification is proposed further below so that—for many data sets—the computational effort of computing all relaxed Lasso solutions is identical to that of solving the ordinary Lasso solutions.

Simple Algorithm.

Step 1: Compute all ordinary Lasso solutions e.g. with the Lars-algorithm in Efron et al. (2004) under the Lasso modification. Let $M_{1}, \dots, M_{m}$ be the resulting set of m models. Let $λ_{1} > \dots > λ_{m} = 0$ be a sequence of penalty values so that $M_{λ} = M_{k}$ if and only if $λ \in (λ_{k}, λ_{k - 1}]$ , where $λ_{0} ≔ \infty$ . (The models are not necessarily distinct, so it is always possible to obtain such a sequence of penalty parameters.)

Step 2: For each $k = 1, \dots, m$ , compute all Lasso solutions on the set $M_{k}$ of variables, varying the penalty parameter between 0 and $λ_{k}$ . The obtained set of solutions is identical to the set of relaxed Lasso solutions $\hat{β}^{λ, φ}$ for $λ \in Λ_{k}$ . The relaxed Lasso solutions for all penalty parameters are given by the union of these sets.

It is obvious that this algorithm produces all relaxed Lasso solutions, for all values of the penalty parameters $φ \in [0, 1]$ and $λ > 0$ . The computational complexity of this algorithm is identical to that of Lars–OLS hybrid, as the Lars iterations in Step 2 are about as computationally intensive as ordinary least-squares estimation (Efron et al., 2004).

However, this naive algorithm is not optimal in general. The computation of the ordinary Lasso solutions contains information that can be exploited in the second stage, when finding Lasso solutions for all subsets $M_{k}$ , $k = 1, \dots, m$ of variables. Fig. 2 serves as an illustration. The “direction” in which relaxed Lasso solutions are found is identical to the directions of ordinary Lasso solutions. These directions do not have to be computed again. Indeed, by extrapolating the path of the ordinary Lasso solutions, all relaxed Lasso solutions can often be found. There is an important caveat. Extrapolated Lasso solutions are only valid relaxed Lasso solutions if and only if the extrapolations do not cross the value zero. This is e.g. fulfilled if the ordinary Lasso estimators are monotonously increasing for a decreasing penalty parameter $λ$ . If, however, the extrapolations do cross zero for a set $M_{k}$ , then the Lasso has to be computed again explicitly for this set, using e.g. again the Lars-algorithm of Efron et al. (2004).

Refined Algorithm.

Step 1: Identical to Step 1 of the simple algorithm. Compute all ordinary Lasso solutions.

Step 2: For each $k = 1, \dots, m$ , let $δ (k) = (\hat{β}^{λ_{k}} - \hat{β}^{λ_{k - 1}}) / (λ_{k - 1} - λ_{k})$ . This is the direction in which solutions are found for ordinary Lasso solutions and is hence known from Step 1. Let $\tilde{β} = \hat{β}^{λ_{k}} + λ_{k} δ (k) .$ If there is at least one component l so that $sign ({\tilde{β}}_{l}) \neq sign (\hat{β}_{l}^{λ_{k}})$ , then relaxed Lasso solutions for $λ \in Λ_{k}$ have to be computed as in Step 2 of the simple algorithm. Otherwise all relaxed Lasso solutions for $λ \in Λ_{k}$ and $φ \in [0, 1]$ are given by linear interpolation between $\hat{β}^{λ_{k - 1}}$ (which corresponds to $φ = 1$ ) and $\tilde{β}$ (which corresponds to $φ = 0$ ).

In the worst case, the refined algorithm is no improvement over the simple algorithm. In the best case, all relaxed Lasso solutions are found at no extra cost, once the ordinary Lasso solutions are computed. If Lasso solutions are e.g. monotonously increasing (for a decreasing value of $λ$ ), then the condition about sign-equality in Step 2 of the refined algorithm is fulfilled, and the relaxed Lasso solutions are found at no extra cost.

The computational complexity of the ordinary Lasso is $O (np \min {n, p})$ , as there are $m = O (\min {n, p})$ steps, each of complexity $O (np)$ . In the worst case, the computational complexity of the relaxed Lasso is $O (m^{2} np)$ , which is, for high-dimensional problems with $p > n$ , identical to $O (n^{3} p)$ , and hence slightly more expensive than the $O (n^{2} p)$ of the ordinary Lasso (but equally expensive as the Lars–OLS hybrid if the least-squares estimator is computed explicitly). However, the linear scaling with the number p of variables is identical. Moreover, as mentioned above, the scaling $O (n^{3} p)$ is really a worst case scenario. Often all relaxed Lasso solutions can be found at little or no extra cost compared to the ordinary Lasso solutions, using the refined algorithm above.

2.3. Extensions

The method can be easily generalised to more general loss functions and generalised linear models (McCullagh and Nelder, 1989). Let $ℓ (β)$ be the negative log-likelihood under parameter $β$ . The relaxed Lasso estimator is then defined in analogy to (4) as(5) $\hat{β}^{λ, φ} = \arg \min_{β \in M_{λ}} ℓ (β) + φ λ ∥ β ∥_{1},$ where $β \in M_{λ}$ is understood to be equivalent to requiring that $β_{k} = 0$ , for all $k \notin M_{λ}$ . The algorithm for computing the solutions for all parameter values $λ, φ$ has the same two-stage characteristic as for the quadratic loss function. The computational effort is again identical to that of ordinary Lasso estimation. For this case, no exact solutions for ordinary Lasso estimators are in general available, and the same is true for the relaxed Lasso estimators. However, only optimisation of convex functions are required as long as the log-likelihood is a concave function. For the Lasso, a solution has been proposed e.g. in Zhao and Yu (2004) and could be generalised to compute all relaxed Lasso solutions.

3. Asymptotic results

For the asymptotic results, we consider a random design. Let $X = (X^{1}, \dots, X^{p})$ be a $p = p_{n}$ -dimensional random variable with a gaussian distribution with covariance matrix $Σ$ , so that $X \sim N (0, Σ)$ . The response variable Y is a linear combination of the predictor variables,(6) $Y = X^{T} β + ɛ,$ where $ɛ \sim N (0, σ^{2})$ . We compare the risk of the Lasso estimator and the relaxed Lasso estimator. The minimal achievable squared error loss is given by the variance $σ^{2}$ of the noise term. The random loss $L (λ)$ of the Lasso estimator is defined by(7) $L (λ) = E (Y - X^{T} \hat{β}^{λ})^{2} - σ^{2},$ where the expectation is with respect to a sample that is independent of the sample which is used to determine the estimator. The loss $L (λ, φ)$ of the relaxed Lasso estimator under parameters $λ, φ$ is defined analogously as(8) $L (λ, φ) = E (Y - X^{T} \hat{β}^{λ, φ})^{2} - σ^{2} .$ It is shown in the following that convergence rates for the relaxed Lasso estimator are largely unaffected by the number of predictor variables for sparse high-dimensional data. This is in contrast to the ordinary Lasso estimator, where the convergence rate drops dramatically for large growth rates of the number $p_{n}$ of predictor variables.

3.1. Setting and assumptions

We make a few assumptions about sparse high-dimensional data. The number of predictor variables $p = p_{n}$ is assumed to be growing very fast with the number of observations.

Assumption 2

For some $c > 0$ and $0 < ξ < 1$ ,(9) $\log p_{n} \sim {cn}^{ξ} .$

In the following, a matrix is said to be diagonally dominant at value $ν$ if the row-wise sum of the absolute values of its non-diagonal entries are bounded by $ν$ times the corresponding absolute value of the diagonal element.

Assumption 3

There exists some $ν < 1$ so that both $Σ$ and $Σ^{- 1}$ are diagonally dominant at value $ν$ for all $n \in N$ .

Note that a diagonal dominant matrix (for any value $ν > 0$ ) is positive definite. The existence of $Σ^{- 1}$ is hence already implied by the assumption about $Σ$ . The assumption is not of critical importance for the results, but shortens the proofs considerably.

The coefficient vector $β$ is assumed to be sparse. For simplicity of exposition, we assume sparseness in the $ℓ_{0}$ -norm: there are a finite number q of non-zero components of $β$ and these are fix for all $n \in N$ . W.l.o.g., the non-zero components are first in order.

Assumption 4

The vector $β \in R^{p_{n}}$ of coefficients is given for all $n \in N$ by $β = (β_{1}, \dots, β_{q}, 0, 0, \dots)$ .

The true model is hence $M_{⋆} = {1, \dots, q}$ . The $p_{n} - q$ noise variables with zero coefficients are nevertheless possibly correlated with the response variable. This setting is similar to some numerical examples in Fan and Peng (2004).

As the number of non-zero coefficients is given by a finite and fixed number q, we restrict the penalty parameter $λ$ in the following to the range $Λ$ , for which the number of selected variables is less than or equal to $d \log n$ with an arbitrary large $d > 0$ ,(10) $Λ ≔ {λ ⩾ 0 :# M_{λ} ⩽ d \log n} .$ This range includes all sequences $λ_{n}$ for which the Lasso or relaxed Lasso estimates are consistent for variable selection, as the number of true non-zero coefficients is finite and fixed.

3.2. Slow rates with the ordinary Lasso

It is shown that the rate of convergence of ordinary Lasso estimators is slow if the number of noise variables is growing fast.

Theorem 5

Under Assumptions 2–4 and independent predictor variables, that is $Σ = 1$ , it holds for the risk under the ordinary Lasso estimator that for any $c > 0$ and $n \to \infty$ $P (\inf_{λ \in Λ} L (λ) > {cn}^{- r}) \to 1 \forall r > 1 - ξ .$

A proof is given in the appendix.

It is hence shown that the rate of convergence of the risk is critically determined by the rate $n^{ξ}$ with which the logarithm $\log p_{n}$ of the number of predictor variables is growing to infinity. It follows that it is impossible to have both consistent variable selection and optimal rates for independent predictor variables with the ordinary Lasso estimator.

Adding many noise predictor variables slows down the rate of convergence for the Lasso estimator, no matter how the penalty parameter $λ$ is chosen. The reason for this slow convergence in the high-dimensional setting is that a large value of the penalty parameter $λ$ is necessary to keep the estimates of coefficients of noise predictor variables at low values. The shrinkage of the non-zero components is then very large, leading to less than optimal prediction; for a further discussion of this phenomenon see as well Fan and Li (2001).

3.3. Fast rates with the relaxed Lasso

A faster rate of convergence is achieved with the relaxed Lasso estimator than with ordinary Lasso in this sparse high-dimensional setting. Noise variables can be prevented from entering the estimator with a high value of the penalty parameter $λ$ , while the coefficients of selected variables can be estimated at the usual $\sqrt{n}$ -rate, using a relaxed penalty. It is shown in other words that the rate of convergence of the relaxed Lasso estimator is not influenced by the presence of many noise variables.

Theorem 6

Under Assumptions 2–4, for $n \to \infty$ , it holds for the loss under the relaxed Lasso estimator that $\inf_{λ \in Λ, φ \in [0, 1]} L (λ, φ) = O_{p} (n^{- 1}) .$

A proof is given in the appendix.

The rate of convergence of the relaxed Lasso estimator (under oracle choices of the penalty parameters) is thus shown to be uninfluenced by a fast growing number of noise variables. The results are illustrated in Fig. 3.

3.4. Choice of the penalty parameters by cross-validation

It was shown above that the rate of convergence of the relaxed Lasso estimate is not influenced by the presence of many noise variables under an oracle choice of the penalty parameters $λ$ and $φ$ (which are unknown). We show that the parameters $λ, φ$ can be chosen by cross-validation while still retaining the fast rate.

For K-fold cross-validation, each observation belongs to one of K partitions, each consisting of $\tilde{n}$ observations, where $\tilde{n} / n \to 1 / K$ for $n \to \infty$ . Let $L_{S, \tilde{n}} (λ, φ)$ be for $S = 1, \dots, K$ the empirical loss on the observations in partition S when constructing the estimator on the set of observations different from S. Let $L_{cv} (λ, φ)$ be the empirical loss under K-fold cross-validation, $L_{cv} (λ, φ) = K^{- 1} \sum_{S = 1}^{K} L_{S, \tilde{n}} (λ, φ) .$ The penalty parameters $\hat{λ}$ and $\hat{φ}$ are chosen as minimisers of $L_{cv} (λ, φ)$ , $(\hat{λ}, \hat{φ}) = \arg \min_{(λ, φ) \in Λ \times [0, 1]} L_{cv} (λ, φ) .$ In practice, a value of K between 5 and 10 is recommended, even though the following result is valid for a broader range.

Theorem 7

Let $L (\hat{λ}, \hat{φ})$ be the loss of the relaxed Lasso estimate and $(\hat{λ}, \hat{φ})$ chosen by K-fold cross-validation with $2 ⩽ K < \infty$ . Under Assumptions 2–4, it holds that $L (\hat{λ}, \hat{φ}) = O_{p} (n^{- 1} \log^{2} n) .$

The optimal rates under oracle choices of the penalty parameters are thus almost obtained if the penalty parameters are chosen by cross-validation. We conjecture that the cross-validated penalty parameters lead for the relaxed Lasso estimator to consistent variable selection; this is not the case for the Lasso, see Meinshausen and Bühlmann (2006). This conjecture is supported by the following numerical examples.

4. Numerical examples

We illustrate the asymptotic results of Section 3 with a few numerical examples. The response variable follows the linear model (6). The predictor variable X follows a normal distribution with covariance matrix $Σ$ , where $Σ_{ij} = ρ^{| i - j |}$ for some value of $0 ⩽ ρ < 1$ . For $ρ = 0$ , this corresponds to independent predictor variables. The variance of $ɛ$ in (6) is chosen so that the signal-to-noise ratio is $0 < η < 1$ (e.g. the variance of the response variable Y due to $ɛ$ is $1 / η$ of the variance of Y due to $X^{T} β$ ).

We consider the case where there are q variables (with $q ⩽ p$ ) that “carry signal” in the sense that $β_{k} \neq 0$ for all $k ⩽ q$ and $β_{k} = 0$ for all k with $k > q$ . All components $β_{k}$ with $k ⩽ q$ are double-exponentially distributed.

For various values of n between 50 and 200 and p between 50 and 800, the ordinary Lasso estimator ( $φ = 1$ ), the Lars–OLS hybrid estimator ( $φ = 0$ ), and the relaxed Lasso estimator (adaptive $φ$ ) are computed. The penalty parameters are chosen by 5-fold cross-validation. The signal-to-noise ratio is chosen from the set $η \in {0.2, 0.8}$ . The correlation between predictor variables is chosen once as $ρ = 0$ (independent predictor variables) and once as $ρ = 0.3$ , while the number of relevant predictor variables is chosen from the set $q \in {5, 15, 25, 50}$ . For each of these settings, the three mentioned estimators are computed 100 times each. Let $L_{rel}$ be the average loss of relaxed Lasso over these 100 simulations, in the sense of (7), and likewise $L_{ols}$ and $L_{lasso}$ for Lars–OLS hybrid and Lasso, see (8).

For small q, the setting is resembling that of the theoretical considerations above and of the numerical examples in Fan and Peng (2004). For small q, the theorems above suggest that the relaxed Lasso and Lars–OLS hybrid outperform Lasso estimation in terms of predictive power. On the other hand, for $q = p$ , the Lasso is the ML estimator and one expects it to do very well compared with the Lars–OLS hybrid for large values of q. (In a Bayesian setting, if the prior for $β$ is chosen to be the actual double-exponential distribution of the components of $β$ , the Lasso solution is the MAP estimator if $q = p$ .)

If we knew beforehand the value of q (the number of relevant predictor variables), then we would for optimal prediction either choose Lasso (if q is large), that is $φ = 1$ , or Lars–OLS hybrid (if q is small), that is $φ = 0$ . However, we do not know the value of q. The numerical examples illustrate how well relaxed Lasso adapts to the unknown sparsity of the underlying data.

4.1. Number of selected variables

The number of selected variables is shown in Table 1 for the Lasso estimator and in Table 2 for the relaxed Lasso. As expected, the relaxed Lasso selects roughly the correct number of variables (or less, if the noise is high or the number of observations n is low, with the Lars–OLS hybrid selecting even fewer variables in these cases, as can be seen from Table 3). In contrast, ordinary Lasso often selects too many noise variables (with the cross-validated choice of $λ$ ). For $q = 5$ , it selects e.g. up to 34 variables. For $q = 50$ , up to 121. Using the considerations in the proof of Theorem 5, these numbers can be expected to grow even higher if a larger number n of observations would be considered.

Table 1. Average number of selected variables with the Lasso for $ρ = 0$

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	17	18	20	22	25	9	9	8	9	8
100	13	23	24	27	31	10	12	15	14	17
200	11	13	27	31	34	11	13	19	22	24
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	27	30	30	27	24	10	8	8	6	7
100	26	39	44	52	53	13	15	14	16	17
200	27	35	51	59	69	18	21	26	29	30
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	36	30	23	16	12	9	7	8	7	6
100	47	65	66	61	54	15	19	16	14	11
200	48	71	96	112	121	27	30	34	31	27

Table 2. Average number of selected variables with the relaxed Lasso for $ρ = 0$

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	7	6	7	5	5	6	5	6	6	4
100	5	6	6	5	5	6	8	7	6	9
200	5	4	6	5	5	5	6	12	8	8
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	19	18	18	15	12	8	6	6	6	6
100	17	19	16	17	16	10	12	10	9	12
200	15	15	16	15	13	12	14	18	18	15
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	34	25	19	12	9	8	6	6	6	5
100	44	57	55	45	34	13	17	13	11	9
200	46	57	64	71	66	23	26	29	24	19

Table 3. Average number of selected variables with the Lars–OLS hybrid for $ρ = 0$

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	5	5	6	5	5	3	3	2	4	2
100	4	5	5	4	5	4	4	3	3	5
200	4	4	5	4	4	3	3	7	4	4
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	17	16	17	13	11	3	3	3	3	3
100	14	16	16	16	15	5	6	4	4	7
200	13	13	14	14	13	7	6	8	6	4
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	31	23	16	12	7	3	3	2	2	3
100	42	49	48	37	30	5	5	2	5	1
200	46	47	52	58	57	16	10	9	5	4

4.2. Comparison with Lasso

Lasso and relaxed Lasso estimators produce nearly identical results (in terms of predictive power) if the number q of relevant predictor variables is large, as can be seen from Table 4, which shows the relative improvement of relaxed Lasso over ordinary Lasso,(11) $100 \cdot (L_{lasso} / L_{rel} - 1) .$ There is no harm when using the relaxed Lasso on such data instead of the Lasso, but there is not much to be gained either. However, for data where there is a very large number of noise variables (e.g. small q), the relaxed Lasso estimator produces a much smaller MSE, as expected from the previous theoretical results. The extent to which the relaxed Lasso outperforms Lasso in this setting depends strongly on the signal-to-noise ratio $η$ . The improvements are larger for large $η$ , where shrinkage of the selected components is not necessary. For small $η$ , shrinkage of the selected components is useful and an optimal procedure chooses thus $φ$ close to 1 for noisy problems. Indeed, the average chosen value of $φ$ for the relaxed Lasso is large if $η$ is low, as can be seen from Table 6.

Table 4. The relative improvement of relaxed Lasso over ordinary Lasso for $ρ = 0$ (upper half) and $ρ = 0.3$ (lower half)

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	41	55	49	49	52	−1	0	−2	−2	1
100	95	88	89	110	146	5	6	5	11	9
200	106	88	84	169	171	24	14	11	21	22
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	−5	−3	−2	−3	−2	−3	−3	−4	−4	−4
100	7	17	18	18	12	−3	0	−1	3	−1
200	28	32	43	58	60	−3	2	2	3	4
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	−3	−4	−3	−2	−3	−4	−3	−3	−4	−3
100	−3	−2	−4	−4	−3	−3	−1	−1	−1	−1
200	0	−1	3	1	−2	−4	−1	−1	−1	0
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	40	98	104	85	103	−2	2	0	−3	1
100	83	95	114	180	186	9	8	6	10	15
200	119	128	89	166	202	24	32	10	19	41
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	−3	3	5	−1	7	−3	−5	−3	−2	−2
100	14	31	36	33	49	0	−1	−3	1	0
200	50	48	72	77	114	−4	−1	5	7	3
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	−7	−2	−3	−2	−3	−4	−4	−2	−2	−4
100	−2	−1	0	−2	−3	−3	−1	−1	−3	−1
200	2	7	8	12	11	−2	−3	−1	−2	−1

In the worst case, relaxed Lasso is performing only marginally worse than ordinary Lasso and is slightly more expensive to compute. For many sparse high-dimensional problems, however, the computation of the relaxed Lasso solutions comes at no extra computational cost and leads to sparser estimators and more accurate predictions.

4.3. Comparison with Lars–OLS hybrid

The theoretical conclusions suggest that Lars–OLS hybrid should do equally well for sparse high-dimensional data as relaxed Lasso. However, there are two caveats. First, the argument holds only for data with sparse structure. If the data do not have sparse structure, Lars–OLS hybrid is in general performing worse than Lasso. Relaxed Lasso can adapt to the amount of sparseness (as seen from Table 6) by varying $φ$ between 1 (for not so sparse data) to 0 (for sparse data). Table 5 shows the relative improvement of relaxed Lasso over Lars–OLS hybrid, analogously to (11). For large values of q, relaxed Lasso is indeed performing better than Lars–OLS in general.

Table 5. The relative improvement of relaxed Lasso over Lars–OLS hybrid for $ρ = 0$ (upper half) and $ρ = 0.3$ (lower half)

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	0	3	2	−3	−2	38	29	21	28	20
100	−4	6	1	1	5	18	46	34	19	23
200	8	1	−4	5	0	2	−4	55	5	9
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	8	5	2	2	3	28	21	20	9	9
100	6	3	0	0	0	32	42	31	26	29
200	3	−2	2	−2	0	22	20	48	23	22
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	18	8	7	7	6	20	14	9	3	4
100	6	11	6	6	6	35	33	16	20	8
200	3	6	3	2	2	41	46	52	31	30
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	−3	2	−1	3	−1	42	33	24	30	26
100	−6	−4	−7	−1	3	11	39	20	21	22
200	−3	−1	−2	2	2	1	−4	81	4	−6
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	0	0	−1	1	1	37	29	23	18	9
100	0	2	−2	1	1	29	39	39	33	32
200	−2	2	1	−1	−1	14	13	34	9	16
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	18	1	5	4	5	29	17	10	5	3
100	5	9	8	4	3	46	43	28	17	13
200	4	1	2	1	0	39	36	46	41	31

What is more striking than the dependence on the sparseness, however, is the dependence on the signal-to-noise ratio. Consider the case where only five variables carry signal ( $q = 5$ ). For a high signal-to-noise ratio ( $η = 0.8$ ), relaxed Lasso and Lars–OLS hybrid perform approximately equally well (and both much better than ordinary Lasso). For a low signal-to-noise ratio ( $η = 0.2$ ), however, relaxed Lasso is considerably better than Lars–OLS. The reason for this is intuitively easy to understand. For noisy problems, it pays off to shrink the coefficients of selected variables, while this is less important for less noisy data. Relaxed Lasso adapts the amount of shrinkage to the noise level.

In general, it is not optimal to do no shrinkage at all for the selected variables ( $φ = 0$ ) or do full shrinkage ( $φ = 1$ ). This is the reason why relaxed Lasso is performing better than both ordinary Lasso and Lars–OLS hybrid for noisy problems, especially when just a few variables carry signal. Given that the computational cost of relaxed Lasso is not higher than that for Lars–OLS hybrid (and sometimes equal to that of Lasso), relaxed Lasso seems to be well suited for high-dimensional problems as the sparseness and signal-to-noise ratio is in general unknown and relaxed Lasso is adaptive to both (Table 6).

Table 6. The average value of $\hat{φ}$ for the relaxed Lasso, for $ρ = 0$

$p$	50	100	200	400	800	50	100	200	400	800
$n$	$q = 5, η = 0.8$					$q = 5, η = 0.2$
50	0.14	0.09	0.08	0.04	0.03	0.66	0.50	0.49	0.51	0.46
100	0.09	0.11	0.08	0.03	0.04	0.52	0.68	0.53	0.45	0.51
200	0.08	0.08	0.07	0.06	0.06	0.29	0.39	0.71	0.47	0.41
$n$	$q = 15, η = 0.8$					$q = 15, η = 0.2$
50	0.24	0.15	0.13	0.19	0.20	0.67	0.50	0.45	0.47	0.45
100	0.21	0.17	0.05	0.05	0.04	0.66	0.72	0.61	0.61	0.64
200	0.17	0.12	0.10	0.06	0.02	0.54	0.63	0.75	0.70	0.61
$n$	$q = 50, η = 0.8$					$q = 50, η = 0.2$
50	0.55	0.38	0.39	0.45	0.43	0.65	0.47	0.45	0.41	0.33
100	0.44	0.54	0.45	0.41	0.40	0.72	0.77	0.71	0.64	0.58
200	0.40	0.44	0.30	0.29	0.19	0.77	0.84	0.89	0.79	0.75

5. Conclusions

We have proposed the relaxed Lasso as a generalisation of Lasso estimation. The main motivation are very high-dimensional regression problems, where the Lasso has two shortcomings:

•
Selection of noise variables: If the penalty parameter is chosen by cross-validation, the number of selected variables is often very large. Many noise variables are potentially selected.
•
Low accuracy of predictions: The accuracy of prediction (in terms of squared error loss) was shown to be negatively affected by the presence of many noise variables, particularly for high signal-to-noise ratios.

The advantages of relaxed Lasso over ordinary Lasso in this high-dimensional setting are twofold.

•
Sparser estimates: The number of selected coefficients is in general very much smaller for relaxed Lasso, without compromising on the accuracy of predictions. The models produced by relaxed Lasso are thus more amenable to interpretation.
•
More accurate predictions: If the signal-to-noise ratio is very low, the predictive accuracy of both Lasso and relaxed Lasso is comparable. For a high signal-to-noise ratio, relaxed Lasso achieves often much more accurate predictions.

For high signal-to-noise ratios, both advantages of relaxed Lasso—sparser estimates and more accurate predictions—can be achieved alternatively by using the Lars–OLS hybrid. However, Lars–OLS hybrid is not adaptive to the signal-to-noise ratio, as seen in the numerical examples and is performing very much worse than ordinary Lasso for low signal-to-noise ratios. Relaxed Lasso is adaptive to the signal-to-noise ratio and achieves near-optimal performance on a wide variety of data sets.

6. Proofs

6.1. Proof of Theorem 6

It was assumed that the set of non-zero coefficients of $β$ is given by $M_{⋆} = {1, \dots, q}$ . Denote by $E$ the event(12) $\exists λ : M_{λ} = M_{⋆} .$ Let $c > 0$ be any positive constant. Then $P (\inf_{λ, φ} L (λ, φ) > {cn}^{- 1}) ⩽ P (\inf_{λ, φ} L (λ, φ) > {cn}^{- 1} | E) P (E) + P (E^{c}) .$ Let $λ_{⋆}$ be the smallest value of the penalty parameter $λ$ such that no noise variable enters the selected variables, that is $\hat{β}_{k}^{λ} = 0$ for all $k > q$ ,(13) $λ_{⋆} ≔ \min_{λ ⩾ 0} {λ | \hat{β}_{k}^{λ} = 0, \forall k > q} .$ The loss $\inf_{λ, φ} L (λ, φ)$ is smaller than $L (λ_{⋆}, 0)$ . Note that, conditional on $E$ , the loss $L (λ_{⋆}, 0)$ is the loss of the regular OLS-estimator $\hat{β}^{⋆ 0}$ on the set $M_{⋆} = {1, \dots, q}$ of the q predictor variables with non-vanishing coefficients. Let $L^{⋆}$ be the loss of this OLS-estimator. It follows that $P (\inf_{λ, φ} L (λ, φ) > {cn}^{- 1}) ⩽ P (L^{⋆} > {cn}^{- 1} | E) P (E) + P (E^{c}) ⩽ P (L^{⋆} > {cn}^{- 1}) + P (E^{c}) .$ It follows from the proofs in Meinshausen and Bühlmann (2006) that there is a value of $λ$ such that the true model $M_{⋆}$ is selected with the Lasso estimator, so that $P (E^{c}) \to 0$ for $n \to \infty$ . By the known properties of the OLS-estimator, there exists some $c > 0$ for every $ɛ > 0$ , so that $\lim \sup_{n \to \infty} P (L^{⋆} > {cn}^{- 1}) < ɛ$ , which completes the proof. □

6.2. Some useful lemmas

6.2.1. Eigenvalues

Let $Σ (M)$ be the covariance matrix, restricted to the subset $M \subseteq {1, \dots, p}$ of variables. Let $Σ_{n} (M)$ be the corresponding empirical covariance matrix for n independent observations.

Lemma 8

Under Assumptions 2–4, there exist $0 < b_{\min} < b_{\max} < \infty$ , so that the maximal and minimal eigenvalues $λ_{\max} (M)$ and $λ_{\min} (M)$ of the empirical covariance matrices $Σ_{n} (M)$ are all bounded simultaneously for any $d > 0$ and all $M$ with $| M | = m_{n} ⩽ d \log n$ by $b_{\min}$ from below and $b_{\max}$ from above, with probability converging to 1 for $n \to \infty$ , $P (b_{\min} < λ_{\min} (M), λ_{\max} (M) < b_{\max}, \forall M : | M | ⩽ m_{n}) \to 1, n \to \infty .$

Proof

By Gershgorins theorem, all eigenvalues of the empirical covariance matrix $Σ_{n} (M)$ are in the set $Γ (M) ≔ ⋃_{a \in M} \{x : | x - (Σ_{n} (M))_{aa} | ⩽ \sum_{b \in M ⧹ a} | (Σ_{n} (M))_{ab} |\} .$ Let $Γ ≔ {1, \dots, p}$ be the set of all predictor variables. Taking the union over all sets with $| M | ⩽ m_{n}$ , $⋃_{M} Γ (M) \subseteq ⋃_{a \in {1, \dots, p}} \{x : | x - (Σ_{n})_{aa} | ⩽ \max_{Ξ \subseteq {1, \dots, p}, | Ξ | ⩽ m_{n} - 1} \sum_{b \in Ξ} | (Σ_{n})_{ab} |\} .$ Denoting the maximal difference between the covariance matrix and its empirical version by(14) $Δ = \max_{a, b} | (Σ_{n} - Σ)_{ab} |,$ it follows that $⋃_{M} Γ (M) \subseteq ⋃_{a \in {1, \dots, p}} \{x : | x - Σ_{aa} | ⩽ m_{n} Δ + \sum_{b \neq a} | Σ_{ab} |\} .$ Using the assumption that $Σ$ is diagonally dominant at value $ν < 1$ and $Σ_{aa} = 1$ , for all $a \in {1, \dots, p}$ , it follows that $⋃_{M} Γ (M) \subseteq ⋃_{a \in {1, \dots, p}} {x : 1 - ν - m_{n} Δ < x ⩽ 1 + ν + m_{n} Δ} .$ As $\log p_{n} \sim {cn}^{ξ}$ with $ξ < 1$ and $m_{n} ⩽ d \log n$ for some $d > 0$ , it is sufficient to show that there exist $g > 0$ for every $δ > 0$ so that for $n \to \infty$ ,(15) $P (Δ ⩾ δ / m_{n}) = O (p_{n}^{2} \exp (- gn / m_{n})) .$ Using Bernstein's inequality, there exists $g > 0$ so that for any $1 ⩽ a, b ⩽ p_{n}$ and for $n \to \infty$ , $P (|n^{- 1} \sum_{i = 1}^{n} (X_{i}^{a} X_{i}^{b}) - E (X^{a} X^{b})| > δ / m_{n}) = O (\exp (- gn / m_{n})) .$ With Bonferronis inequality, Eq. (15) follows, which completes the proof. □

6.2.2. Change in gradient

Let $V_{h}$ be the set of all diagonal $h \times h$ matrices V, where the diagonal elements are in ${- 1, 1}$ .

Lemma 9

It holds under Assumptions 2–4 that, for every $g > 0$ , with probability converging to 1 for $n \to \infty$ , simultaneously for all $M$ with $| M | ⩽ m_{n} = d \log n$ and $V \in V_{| M |}$ , $| Σ (M) Σ_{n} (M)^{- 1} V 1_{M} - V 1_{M} | < g,$ where the inequality is understood to be fulfilled if it is fulfilled componentwise.

Proof

First, $Σ (M) Σ_{n} (M)^{- 1} V 1_{M} = V 1_{M} + (Σ (M) - Σ_{n} (M)) Σ_{n} (M)^{- 1} V 1_{M} .$ Thus, simultaneously for all $M$ with $| M | ⩽ m_{n}$ , it holds componentwise that $| Σ (M) Σ_{n} (M)^{- 1} V 1_{M} - V 1_{M} | ⩽ m_{n} Δ \max_{M, a \in M} | (Σ_{n} (M)^{- 1} V 1_{M})_{a} |,$ where $Δ$ is defined as in (14). The last term $\max_{M, a \in M} | (Σ_{n} (M)^{- 1} V 1_{M})_{a} |$ is bounded by $m_{n} / λ_{\min}$ , where $λ_{\min}$ is the minimal eigenvalue of $Σ_{n} (M)$ over all subsets $M$ with $| M | ⩽ m_{n}$ . This minimal eigenvalue is bounded from below by $b_{\min} > 0$ with probability converging to 1 for $n \to \infty$ , according to Lemma 8. It remains to be shown that for any $δ > 0$ , $P (Δ > δ / m_{n}^{2}) \to 1$ for $n \to \infty$ . This follows analogously to (15), which completes the proof. □

6.2.3. Restricted positive cone condition

The positive cone condition of Efron et al. (2004) is fulfilled if, for all subsets $M \subseteq {1, \dots, p_{n}}$ and all $V \in V_{| M |}$ , $(V Σ_{n} (M) V)^{- 1} 1_{M} > 0,$ where the inequality holds componentwise. The restricted positive cone condition is fulfilled if the inequality holds for all subsets $M$ so that $| M | ⩽ m_{n}$ .

Lemma 10

Under Assumptions 2–4, the restricted positive cone condition is fulfilled for $m_{n} ⩽ d \log n$ with any $d > 0$ , with probability converging to 1 for $n \to \infty$ . Moreover, for any $0 < ε < 1 - ν$ , $P (\min_{M : | M | ⩽ m_{n}, V \in V_{| M |}} (V Σ_{n} (M) V)^{- 1} 1_{M} > ε) \to 1, n \to \infty .$

Proof

First, for any $M$ and $V \in V_{| M |}$ , $(V Σ_{n} (M) V)^{- 1} 1_{M} = (V Σ (M) V)^{- 1} (V Σ (M) Σ_{n} (M)^{- 1} V 1_{M}) .$ By Lemma 9, the components of $V Σ (M) Σ_{n} (M)^{- 1} V 1_{M}$ are, for every $δ > 0$ , simultaneously bounded for all $M$ with $| M | ⩽ m_{n}$ and $V \in V_{| M |}$ by $1 - δ$ from below and by $1 + δ$ from above, with probability converging to 1 for $n \to \infty$ . Thus it holds for every $a \in M$ and $V \in V_{| M |}$ , with probability converging to 1 for $n \to \infty$ , $((V Σ_{n} (M) V)^{- 1} 1_{M})_{a} ⩾ Σ (M)_{aa}^{- 1} (1 - δ) - \sum_{b \in M ⧹ a} | Σ (M)_{ab}^{- 1} | (1 + δ) = (1 - δ) (Σ (M)_{aa}^{- 1} - \frac{1 + δ}{1 - δ} \sum_{b \in M ⧹ a} | Σ (M)_{ab}^{- 1} |) ≕ g_{a} (δ) .$ The inverse covariance matrix $Σ^{- 1}$ is by assumption diagonally dominant at value $ν < 1$ , which is equivalent to $\sum_{b \in M ⧹ a} | Σ_{ab}^{- 1} | ⩽ ν Σ_{aa}^{- 1} .$ It is straightforward to show that in this case, for all $M \subseteq {1, \dots, p}$ , the inverse covariance matrices $Σ (M)^{- 1}$ are diagonally dominant at value $ν < 1$ as well. For $δ = 0$ , the continuous function $g_{a} (δ)$ is hence, for all components $a \in M$ , larger than or equal to $(1 - ν) (Σ_{aa} (M)^{- 1})$ . Note that $Σ_{aa} (M)^{- 1}$ is the inverse of the conditional variance $Var (X^{a} | {X^{b}, b \in M ⧹ a})$ , which is smaller than the unconditional variance $Var (X^{a})$ . Hence, as $Σ_{aa} = 1$ , it holds that $Σ_{aa} (M)^{- 1} > 1$ for all $a \in M$ and thus for all $a \in M$ , $\lim_{δ \to 0} g_{a} (δ) ⩾ 1 - ν .$ Choosing $δ$ sufficiently small, the continuous function $g_{a} (δ)$ is for all components $a \in M$ larger than $ε$ , as $ε < 1 - ν$ , which completes the proof. □

Lemma 11

Under Assumptions 2–4, for some $d > 0$ , it holds for any $ε > 1 + ν$ that $P (\max_{M : | M | ⩽ m_{n}, V \in V_{| M |}} (V Σ_{n} (M) V)^{- 1} 1_{M} < ε) \to 1, n \to \infty .$

Proof

The proof of Lemma 11 follows analogously to the proof of Lemma 10. □

6.2.4. Monotonicity of Lasso-solutions

Lemma 12

Under the restricted positive cone condition, the absolute value of the Lasso estimator $\hat{β}_{k}^{λ}$ is for all components $k = 1, \dots, p$ monotonously increasing for a decreasing value of $λ$ .

Proof

For any value of $λ$ , let $δ λ > 0$ be a small change of the penalty parameter $λ$ . Let $δ \hat{β}^{λ}$ be the corresponding change of the Lasso estimator, $δ \hat{β}^{λ} ≔ \hat{β}^{λ - δ λ} - \hat{β}^{λ} .$ It has to be shown that for any $λ > 0$ ,(16) $\hat{β}^{λ} \cdot δ \hat{β}^{λ} ⩾ 0 .$ For all components of $\hat{β}^{λ}$ equal to zero, the claim is automatically fulfilled. Let the set of non-zero components of $\hat{β}^{λ}$ be again denoted by $M_{λ} \subseteq {1, \dots, p}$ . Denote the restriction of $\hat{β}^{λ}$ and $δ \hat{β}^{λ}$ to the set $M$ by $\hat{β}^{λ} (M)$ and $δ \hat{β}^{λ} (M)$ , respectively. It follows e.g. from Efron et al. (2004) that the infinitesimal change $δ β (M)$ of the vector $\hat{β}^{λ} (M)$ is proportional to(17) $(Σ_{n} (M) V)^{- 1} 1_{M},$ where V is a diagonal $| M | \times | M |$ -matrix with diagonal elements $V_{kk}$ , $k \in M$ , identical to the signs of the correlations of $X_{i}^{k}$ , $i = 1, \dots, n$ with the residuals $Y_{i} - \sum_{a \in {1, \dots, p}} \hat{β}_{k}^{λ} X_{i}^{a}$ , $i = 1, \dots, n$ . As $\hat{β}^{λ}$ is a Lasso solution, $V_{kk}$ is identical to the sign of $\hat{β}_{k}^{λ}$ for all $k \in M$ . Therefore, componentwise, for all $λ > 0$ $sign (δ \hat{β}^{λ} (M) \cdot \hat{β}^{λ} (M)) = sign ((V Σ_{n} (M) V)^{- 1} 1_{M}) .$ If the restricted positive cone condition is fulfilled, all components on the r.h.s. are positive and so the same is true for the l.h.s., and (16) follows. The restricted positive cone condition is fulfilled with probability converging to 1 for $n \to \infty$ according to Lemma 10, which completes the proof. □

6.2.5. When do noise variables enter?

By assumption, the correct model is given by the first q predictor variables, $M_{⋆} = {1, \dots, q}$ . A noise variable is hence a variable with index larger than q. If any noise variable is part of the Lasso estimator, then, equivalently, there exists some $k > q$ so that $k \in M_{λ}$ .

Lemma 13

Let $λ_{n}$ , $n \in N$ , be a sequence with $λ_{n} = o (n^{(- 1 + ξ) / 2})$ for $n \to \infty$ . Then, under Assumptions 2–4 and independent predictor variables, $P (\exists k > q : k \in M_{λ_{n}}) \to 1, n \to \infty .$

Proof

Let $\hat{β}^{⋆ λ}$ be the Lasso estimator, which is constrained to be zero outside the set $M_{⋆} = {1, \dots, q}$ ,(18) $\hat{β}^{⋆ λ} = \arg \min_{β} n^{- 1} \sum_{i = 1}^{n} {(Y_{i} - \sum_{k \in M_{⋆}} β_{k} X_{i}^{k})}^{2} + λ ∥ β ∥_{1} .$ If $\hat{β}^{⋆ λ}$ is a valid Lasso solution to the unconstrained problem, as in Eq. (2), then there does not exist, by uniqueness of the solution, any $k > q$ so that $k \in M_{λ}$ . It suffices hence to show that $\hat{β}^{⋆ λ_{n}}$ cannot be the solution to (2), with probability converging to 1 for $n \to \infty$ . Using results in Osborne et al. (2000), the Lasso estimator $\hat{β}^{⋆ λ}$ is only a valid Lasso solution for the whole set of $p_{n}$ predictor, if the gradient $n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k}$ is smaller or equal to $λ$ for all $k > q$ , where, for $i = 1, \dots, n$ , $R_{i} = Y_{i} - \sum_{a \in M_{⋆}} \hat{β}_{k}^{⋆ λ} X_{i}^{a},$ are the residuals under the estimator $\hat{β}^{⋆ λ}$ . Thus(19) $P (\exists k > q : k \in M_{λ_{n}}) ⩾ P (\max_{k > q} n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} > λ_{n}) .$ Conditional on $(Y, X^{1}, \dots, X^{q})$ , it holds for every $k > q$ , that $n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} \sim N (0, n^{- 2} \sum_{i = 1}^{n} R_{i}^{2}) .$ The expected value of $n^{- 1} \sum_{i = 1}^{n} R_{i}^{2}$ , the averaged squared residuals, is larger than $σ^{2} (n - q) / n$ for all values of $λ$ and $P (n^{- 1} \sum_{i = 1}^{n} R_{i}^{2} > σ^{2} / 2) \to 1, n \to \infty .$ If $n^{- 1} \sum_{i = 1}^{n} R_{i}^{2} = σ^{2} / 2$ , then $n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} \sim N (0, σ^{2} / (2 n))$ . Thus, for some $c, d > 0$ , $P (n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} > λ_{n}) ⩾ d λ_{n}^{- 1} \exp (- cn λ_{n}^{2}),$ which holds for every $k > q$ , of which there are $p_{n} - q$ variables. The probability that the gradient $n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k}$ is smaller than $λ_{n}$ for all $p_{n} - q$ noise variables is hence bounded by $P (\max_{k > q} n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} ⩽ λ_{n}) ⩽ (1 - d λ_{n}^{- 1} \exp (- cn λ_{n}^{2}))^{p_{n} - q} ⩽ \exp (- (p_{n} - q) d λ_{n}^{- 1} \exp (- cn λ_{n}^{2})) .$ Let $λ_{n}$ be a sequence with $λ_{n} = o (n^{(- 1 + ξ) / 2})$ for $n \to \infty .$ Then $n λ_{n}^{2} = o (n^{ξ})$ , and as $\log p_{n} \sim {gn}^{ξ}$ , for some $g > 0$ , it follows that $P (\max_{k > q} n^{- 1} \sum_{i = 1}^{n} R_{i} X_{i}^{k} ⩽ λ_{n}) \to 0, n \to \infty,$ which, using (19), completes the proof. □

6.2.6. Error of estimators

The following lemma bounds from below the difference between the estimator under $λ ⩾ λ_{⋆}$ and the true parameter value.

Lemma 14

Assume $Σ = 1$ and Assumptions 2 and 3. For any $δ > 0$ , with probability converging to 1 for $n \to \infty$ , it holds for all $k ⩽ q$ that for $λ ⩾ λ_{⋆}$ , $| \hat{β}_{k}^{λ} - β_{k} | ⩾ (1 - δ) λ .$

Proof

First, $| \hat{β}_{k}^{λ} - β_{k} | ⩾ | \hat{β}_{k}^{λ} - \hat{β}_{k}^{⋆ 0} | - | \hat{β}_{k}^{⋆ 0} - β_{k} |,$ where $\hat{β}^{⋆ 0}$ is defined as in (18) as the Lasso estimator where all components of noise variables, for $k > q$ , are restricted to be zero. This estimator is the regular OLS estimator on the set $M = {1, \dots, q}$ of variables and it follows by standard results that for any series $c_{n}$ with $c_{n}^{- 1} = o_{p} (n^{- 1 / 2})$ , it holds that $P (| \hat{β}_{k}^{⋆ 0} - β_{k} | > c_{n}) \to 0$ for $n \to \infty$ . By Lemma 13, $λ_{⋆}^{- 1} = o_{p} (n^{- 1 / 2})$ . It suffices hence to show that, for any $δ > 0$ , for all $k ⩽ q$ and $λ ⩾ λ_{⋆}$ ,(20) $P (| \hat{β}_{k}^{λ} - \hat{β}_{k}^{⋆ 0} | > (1 - δ) λ) \to 1, n \to \infty .$ Note that for $λ ⩾ λ_{⋆}$ , $\hat{β}^{λ} = \hat{β}^{⋆ λ}$ by definition of $\hat{β}^{⋆ λ}$ in (18). Using (17), it holds for every $λ > 0$ that $| \hat{β}_{k}^{⋆ λ} - \hat{β}_{k}^{⋆ 0} | = |\int_{0}^{λ} (V Σ_{n} (M_{λ}) V)^{- 1} 1_{M_{λ}} d λ^{'}|,$ where $M_{λ} = {k ⩽ q : \hat{β}_{k}^{⋆ λ} \neq 0} \subseteq M_{⋆}$ . By Lemma 10 and $Σ = 1$ , it holds for every $δ > 0$ with probability converging to 1 for $n \to \infty$ that(21) $\min_{M : | M | ⩽ m_{n}, V} (V Σ_{n} (M) V)^{- 1} 1_{M} > (1 - δ) .$ As $q = | M_{⋆} | ⩽ m_{n}$ , it follows that with probability converging to 1 for $n \to \infty$ , $| \hat{β}_{k}^{⋆ λ} - \hat{β}_{k}^{⋆ 0} | ⩾ (1 - δ) λ,$ which shows, using $\hat{β}^{λ} = \hat{β}^{⋆ λ}$ for $λ ⩾ λ_{⋆}$ , that (20) holds true and thus completes the proof. □

6.2.7. Errors due to finite validation set

Let $L_{\tilde{n}} (λ, φ)$ be the empirical version of $L (λ, φ)$ for $\tilde{n}$ observations of $(Y, X)$ , which are independent of the observations used to construct the relaxed Lasso estimator.

Lemma 15

Let $\lim \inf_{n \to \infty} \tilde{n} / n \to 1 / K$ with $K ⩾ 2$ . Then, under Assumptions 2–4, $\sup_{λ \in Λ, φ \in [0, 1]} | L (λ, φ) - L_{\tilde{n}} (λ, φ) | = O_{p} (n^{- 1} \log^{2} n), n \to \infty .$

Proof

The restricted positive cone condition is satisfied with probability converging to 1 for $n \to \infty$ , according to Lemma 10. It hence suffices to show the claim under assumption of the restricted positive cone condition. Let, as before, $M_{1}, \dots, M_{m}$ be the set of all models attained with Lasso estimates and let $λ_{k}$ , $k = 1, \dots, m$ , (with $λ_{1} < \dots < λ_{m}$ ) be the largest value of the penalty parameter $λ$ so that $M_{k} = M_{λ}$ . Using Lemma 12 and the definition of the relaxed Lasso estimates, Eq. (4), any relaxed Lasso solution is in one of the sets $B_{1}, \dots, B_{m}$ , where for all $k \in {1, \dots, m}$ ,(22) $B_{k} = {β = φ \hat{β}^{λ_{k}, 0} + (1 - φ) \hat{β}^{λ_{k}, 1} | φ \in [0, 1]} .$ The estimates $\hat{β}^{λ_{k}, 1}$ are the Lasso estimates for penalty parameter $λ_{k}$ , and $\hat{β}^{λ_{k}, 0}$ the corresponding OLS-estimates. The loss under a choice of $λ, φ$ as penalty parameters is given by $L (λ, φ) = E {(Y - \sum_{k \in {1, \dots, p}} \hat{β}_{k}^{λ, φ} X^{k})}^{2} .$ For any $λ$ , set $δ \hat{β}^{λ} = (\hat{β}^{λ, 1} - \hat{β}^{λ, 0})$ . The loss $L (λ, φ)$ can then be written as(23) $L (λ, φ) = E (U_{λ}^{2}) + 2 φ E (U_{λ} V_{λ}) + φ^{2} E (V_{λ}^{2}),$ where $U_{λ} = Y - \sum_{k \in {1, \dots, p}} \hat{β}_{k}^{λ, 0} X^{k}$ , and $V_{λ} = \sum_{k \in {1, \dots, p}} δ \hat{β}_{k}^{λ} X^{k}$ . The loss $L (λ, φ)$ is hence, for a given $λ$ , a quadratic function in $φ$ . Both $U_{λ}$ and $V_{λ}$ are normal distributed random variables conditional on the sample on which $\hat{β}^{λ, φ}$ is estimated. There exists some $h > 0$ so that, for all $λ$ and $φ$ , $P (\max_{k} \hat{β}_{k}^{λ, φ} > h) \to 0$ for $n \to \infty$ . As the number of non-zero coefficients is bounded by $m_{n} ⩽ d \log n$ , it thus follows by Bernstein's inequality that there exists some $g > 0$ for every $ɛ > 0$ so that, $\lim \sup_{n \to \infty} P (| E (U_{λ}^{2}) - E_{\tilde{n}} (U_{λ}^{2}) | > g {\tilde{n}}^{- 1} \log n) < ɛ,$ where $E_{\tilde{n}} (U_{λ}^{2})$ is the empirical mean of $U_{λ}$ in the sample of $\tilde{n}$ observations in the validation set. For the second and third term in the loss (23) it follows analogously that there exists $g > 0$ for every $ɛ > 0$ so that $\lim \sup_{n \to \infty} P (| E (U_{λ} V_{λ}) - E_{\tilde{n}} (U_{λ} V_{λ}) | > g {\tilde{n}}^{- 1} \log n) < ɛ,$ $\lim \sup_{n \to \infty} P (| E (V_{λ}^{2}) - E_{\tilde{n}} (V_{λ}^{2}) | > g {\tilde{n}}^{- 1} \log n) < ɛ .$ Hence, using (23), there exists some $g > 0$ for every $ɛ > 0$ so that $\lim \sup_{n \to \infty} P (\sup_{φ \in [0, 1]} | L (λ, φ) - L_{\tilde{n}} (λ, φ) | > g {\tilde{n}}^{- 1} \log n) < ɛ .$ When extending the supremum over $φ \in Λ$ to a supremum over $λ > 0, φ \in [0, 1]$ , note that it is sufficient, due to (22), to consider values of $λ$ in the finite set ${λ_{1}, \dots, λ_{m}}$ . Using Bonferroni's inequality and $m ⩽ d \log n$ , it follows that there exists some $g > 0$ for every $ɛ > 0$ so that $\lim \sup_{n \to \infty} P (\sup_{λ, φ} | L (λ, φ) - L_{\tilde{n}} (λ, φ) | > g {\tilde{n}}^{- 1} \log^{2} n) < ɛ,$ which completes the proof as $\tilde{n} / n \to 1 / K > 0$ for $n \to \infty$ . □

6.3. Proof of Theorem 5

For independent predictor variables, the loss $L (λ)$ of the Lasso estimator under penalty parameter $λ$ is given by(24) $L (λ) = \sum_{k \in {1, \dots, p}} (\hat{β}_{k}^{λ} - β_{k})^{2} = \sum_{k ⩽ q} (\hat{β}_{k}^{λ} - β_{k})^{2} + \sum_{k > q} (\hat{β}_{k}^{λ})^{2},$ using that the variance of all components of X is identical to 1 and $β_{k} = 0$ for all $k > q$ . Let $λ_{⋆}$ be defined as in (13). Using Lemma 14, it follows that for all $ε > 0$ , with probability converging to 1 for $n \to \infty$ , for all $k ⩽ q$ and $λ ⩾ λ_{⋆}$ , $(\hat{β}_{k}^{λ} - β_{k})^{2} ⩾ (1 - ε)^{2} (λ - λ_{⋆})^{2} .$ Summing only over components with $k ⩽ q$ in (24), it follows that the loss is bounded from below for $λ ⩾ λ_{⋆}$ by(25) $\inf_{λ ⩾ λ_{⋆}} L (λ) ⩾ q (1 - ε)^{2} λ_{⋆}^{2} .$ Now the case $λ < λ_{⋆}$ is examined. The range of $λ$ is furthermore restricted to lie in the area $Λ$ , defined in (10). Denote in the following the difference between the Lasso estimators $\hat{β}^{λ}$ and $\hat{β}^{λ_{⋆}}$ by $δ^{λ} = \hat{β}^{λ} - \hat{β}^{λ_{⋆}}$ . Denote the difference between $\hat{β}^{λ_{⋆}}$ and the true parameter $β$ by $θ = \hat{β}^{λ_{⋆}} - β$ . Then $(\hat{β}_{k}^{λ} - β_{k})^{2} = θ_{k}^{2} - 2 θ_{k} δ_{k}^{λ} + (δ_{k}^{λ})^{2} .$ It follows by Lemma 14 that, with probability converging to 1 for $n \to \infty$ , for any $ε > 0$ , $| θ_{k} | > (1 - ε) λ_{⋆}$ . It holds by an analogous argument that $| θ_{k} | < (1 + ε) λ_{⋆}$ . Hence, for all $k ⩽ q$ , $(\hat{β}_{k}^{λ} - β_{k})^{2} ⩾ (1 - ε)^{2} λ_{⋆}^{2} - 2 (1 + ε) λ_{⋆} δ_{k}^{λ} + (δ_{k}^{λ})^{2} .$ By Lemma 11 and analogously to Lemma 14, it holds furthermore with probability converging to 1, that $(1 - ε) (λ_{0} - λ) ⩽ | δ_{k}^{λ} | ⩽ (1 + ε) (λ_{0} - λ)$ and hence, for all $k ⩽ q$ , $(\hat{β}_{k}^{λ} - β_{k})^{2} ⩾ (1 - ε)^{2} λ_{⋆}^{2} - 2 (1 + ε)^{2} λ_{⋆} (λ_{⋆} - λ) + (1 - ε)^{2} (λ_{⋆} - λ)^{2} .$ As $λ_{⋆}$ is the largest value of $λ$ such that $M_{λ} = M_{⋆}$ , a noise variable (with index $k > q$ ) enters the model $M_{λ}$ if $λ < λ_{⋆}$ . Using again Lemma 10, with probability converging to 1 for $n \to \infty$ , it holds for this component that for any $ε > 0$ ,(26) $(\hat{β}_{k}^{λ})^{2} ⩾ (1 - ε)^{2} (λ_{⋆} - λ)^{2} .$ It follows that with probability converging to 1 for $n \to \infty$ , $L (λ) ⩾ q (1 - ε)^{2} λ_{⋆}^{2} - 2 q (1 + ε)^{2} λ_{⋆} (λ_{⋆} - λ) + (q + (1 - ε)^{2}) (λ_{⋆} - λ)^{2} .$ Denote the infimum over $λ_{0} ⩽ λ ⩽ λ_{⋆}$ of the r.h.s. by $f (ε)$ , $f (ε) ≔ \inf_{λ_{0} ⩽ λ ⩽ λ_{⋆}} (q (1 - ε)^{2} λ_{⋆}^{2} - 2 q (1 + ε)^{2} λ_{⋆} (λ_{⋆} - λ) + (q + (1 - ε)^{2}) (λ_{⋆} - λ)^{2}) .$ Note that $f (ε)$ is a continuous function of $ε$ and $\lim_{ε \to 1} f (ε) = q / (q + 1) λ_{⋆}^{2} .$ Hence, as $ε$ can be chosen arbitrarily close to 1, it holds that, with probability converging to 1 for $n \to \infty$ , $\inf_{λ_{0} ⩽ λ ⩽ λ_{⋆}} L (λ) ⩾ \inf_{ε > 0} f (ε) ⩾ λ_{⋆}^{2} / 2 .$ By Lemma 13, $λ_{⋆}^{- 2} = O_{p} (n^{1 - ξ})$ and thus, using (25), for any $r > 1 - ξ$ , $P (\inf_{λ \in Λ} L (λ) > {cn}^{- r}) \to 1, n \to \infty,$ which completes the proof. □

6.4. Proof of Theorem 7

It holds for the loss under $\hat{λ}$ and $\hat{φ}$ for every $g > 0$ that $P (L (\hat{λ}, \hat{φ}) > {gn}^{- 1} \log^{2} n) ⩽ P (\inf_{λ \in Λ, φ \in [0, 1]} L (λ, φ) > \frac{1}{2} {gn}^{- 1} \log^{2} n) + 2 P (\sup_{λ \in Λ, φ \in [0, 1]} | L (λ, φ) - L_{cv} (λ, φ) | > \frac{1}{2} {gn}^{- 1} \log^{2} n) .$ It follows by Theorem 6 that the first term on the r.h.s. vanishes for $n \to \infty$ . The second term is by Bonferroni's inequality bounded from above by $K \max_{1 ⩽ S ⩽ K} P (\sup_{λ \in Λ, φ \in [0, 1]} | L (λ, φ) - L_{S, \tilde{n}} (λ, φ) | > \frac{1}{2} {gn}^{- 1} \log^{2} n) .$ Using Lemma 15, there exists thus for every $ɛ > 0$ some $g > 0$ so that $\lim \sup_{n \to \infty} P (L (\hat{λ}, \hat{φ}) > {gn}^{- 1} \log^{2} n) < ɛ,$ which completes the proof. □

References

Breiman, 1995
L. Breiman
Better subset regression using the nonnegative garrote
Technometrics, 37 (1995), pp. 373-384
View in Scopus Google Scholar
Efron et al., 2004
B. Efron, T. Hastie, I. Johnstone, R. Tibshirani
Least angle regression
Ann. Statist., 32 (2004), pp. 407-451
View in Scopus Google Scholar
Fan and Li, 2001
J. Fan, R. Li
Variable selection via penalized likelihood
J. Amer. Statist. Assoc., 96 (2001), pp. 1348-1360
View in Scopus Google Scholar
Fan and Peng, 2004
J. Fan, H. Peng
Nonconcave penalized likelihood with a diverging number of parameters
Ann. Statist., 32 (2004), pp. 928-961
View in Scopus Google Scholar
Frank and Friedman, 1993
I. Frank, J. Friedman
A statistical view of some chemometrics regression tools (with discussion)
Technometrics, 35 (1993), pp. 109-148
CrossRef Google Scholar
Huber, 1973
P. Huber
Robust regression: asymptotics, conjectures, and Monte Carlo
Ann. Statist., 1 (1973), pp. 799-821
Google Scholar
Knight and Fu, 2000
K. Knight, W. Fu
Asymptotics for lasso-type estimators
Ann. Statist., 28 (2000), pp. 1356-1378
View in Scopus Google Scholar
McCullagh and Nelder, 1989
P. McCullagh, J.A. Nelder
Generalized Linear Models
Chapman & Hall, London (1989)
Google Scholar
Meinshausen and Bühlmann, 2006
N. Meinshausen, P. Bühlmann
High dimensional graphs and variable selection with the lasso
Ann. Statist., 34 (2006), pp. 1436-1462
View in Scopus Google Scholar
Osborne et al., 2000
M. Osborne, B. Presnell, B. Turlach
On the lasso and its dual
J. Comput. Graph. Statist., 9 (2000), pp. 319-337
View in Scopus Google Scholar
Tibshirani, 1996
R. Tibshirani
Regression shrinkage and selection via the lasso
J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267-288
CrossRef Google Scholar
Tsybakov and van de Geer, 2005
A. Tsybakov, S. van de Geer
Square root penalty: adaptation to the margin in classification and in edge estimation
Ann. Statist., 33 (2005), pp. 1203-1224
View in Scopus Google Scholar
van de Geer and van Houwelingen, 2004
S. van de Geer, H. van Houwelingen
High dimensional data: $p ⪢ n$ in mathematical statistics and bio-medical applications
Bernoulli, 10 (2004), pp. 939-943
View in Scopus Google Scholar
Zhao and Yu, 2004
Zhao, P., Yu, B., 2004. Boosted lasso. Technical Report 678, University of California, Berkeley.
Google Scholar

Cited by (462)

Mathematical programming for simultaneous feature selection and outlier detection under l1 norm
2024, European Journal of Operational Research
Scenario selection with LASSO regression for the valuation of variable annuity portfolios
2024, Insurance: Mathematics and Economics
Personalized choice model for forecasting demand under pricing scenarios with observational data—The case of attended home delivery
2024, International Journal of Forecasting
Air pollution prediction and backcasting through a combination of mobile monitoring and historical on-road traffic emission inventories
2024, Science of the Total Environment
Dynamically engineered multi-modal feature learning for predictions of office building cooling loads
2024, Applied Energy
Variables selection using L<inf>0</inf> penalty
2024, Computational Statistics and Data Analysis
The determination of a tuning parameter by the generalized information criterion (GIC) is considered an important issue in variable selection. It is shown that the GIC and the penalized objective functions are equivalent, leading to a new penalized maximum likelihood method for high-dimensional generalized linear models in this article. Based on the technique of the well-known discrete optimization problem in theoretical computer science, a two-step algorithm for local solutions is proposed. The first step optimizes the penalized objective function under a given model size, where only a maximum likelihood algorithm is needed. The second step optimizes the penalized objective function under a candidate set of model sizes, where only the GIC is needed. As the tuning parameter can be fixed, the selection of the tuning parameter can be ignored in the proposed method. The theoretical study shows that the algorithm is polynomial and any resulting local solution is consistent. Thus, it is not necessary to use the global solution in practice. The numerical studies show that the proposed method outperforms its competitors in general.

View all citing articles on Scopus

View Abstract

[1] Breiman, 1995
L. Breiman
Better subset regression using the nonnegative garrote
Technometrics, 37 (1995), pp. 373-384
View in Scopus Google Scholar

[2] Efron et al., 2004
B. Efron, T. Hastie, I. Johnstone, R. Tibshirani
Least angle regression
Ann. Statist., 32 (2004), pp. 407-451
View in Scopus Google Scholar

[3] Fan and Li, 2001
J. Fan, R. Li
Variable selection via penalized likelihood
J. Amer. Statist. Assoc., 96 (2001), pp. 1348-1360
View in Scopus Google Scholar

[4] Fan and Peng, 2004
J. Fan, H. Peng
Nonconcave penalized likelihood with a diverging number of parameters
Ann. Statist., 32 (2004), pp. 928-961
View in Scopus Google Scholar

[5] Frank and Friedman, 1993
I. Frank, J. Friedman
A statistical view of some chemometrics regression tools (with discussion)
Technometrics, 35 (1993), pp. 109-148
CrossRef Google Scholar

[6] Huber, 1973
P. Huber
Robust regression: asymptotics, conjectures, and Monte Carlo
Ann. Statist., 1 (1973), pp. 799-821
Google Scholar

[7] Knight and Fu, 2000
K. Knight, W. Fu
Asymptotics for lasso-type estimators
Ann. Statist., 28 (2000), pp. 1356-1378
View in Scopus Google Scholar

[8] McCullagh and Nelder, 1989
P. McCullagh, J.A. Nelder
Generalized Linear Models
Chapman & Hall, London (1989)
Google Scholar

[9] Meinshausen and Bühlmann, 2006
N. Meinshausen, P. Bühlmann
High dimensional graphs and variable selection with the lasso
Ann. Statist., 34 (2006), pp. 1436-1462
View in Scopus Google Scholar

[10] Osborne et al., 2000
M. Osborne, B. Presnell, B. Turlach
On the lasso and its dual
J. Comput. Graph. Statist., 9 (2000), pp. 319-337
View in Scopus Google Scholar

[11] Tibshirani, 1996
R. Tibshirani
Regression shrinkage and selection via the lasso
J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267-288
CrossRef Google Scholar

[12] Tsybakov and van de Geer, 2005
A. Tsybakov, S. van de Geer
Square root penalty: adaptation to the margin in classification and in edge estimation
Ann. Statist., 33 (2005), pp. 1203-1224
View in Scopus Google Scholar

[13] van de Geer and van Houwelingen, 2004
S. van de Geer, H. van Houwelingen
High dimensional data: $p ⪢ n$ in mathematical statistics and bio-medical applications
Bernoulli, 10 (2004), pp. 939-943
View in Scopus Google Scholar

[14] Zhao and Yu, 2004
Zhao, P., Yu, B., 2004. Boosted lasso. Technical Report 678, University of California, Berkeley.
Google Scholar