We consider the problem of model selection and estimation in sparse high dimensional linear regression models with strongly correlated variables. First, we study the theoretical properties of the dual Lasso solution, and we show that joint consideration of the Lasso primal and its dual solutions are useful for selecting correlated active variables. Second, we argue that correlation among active predictors is not problematic, and we derive a new weaker condition on the design matrix, called Pseudo Irrepresentable Condition (PIC). Third, we present a new variable selection procedure, Dual Lasso Selector, and we show that PIC is a necessary and sufficient condition for consistent variable selection for the proposed method. Finally, by combining the dual Lasso selector further with the Ridge estimation even better prediction performance is achieved. We call the combination, DLSelect+Ridge. We illustrate the DLSelect+Ridge method and compare it with popular existing methods in terms of variable selection and prediction accuracy by considering a real dataset.
( ) ( ) group of strongly correlated variables even if many or all of these variables are important. In the presence of correlated predictors, the concept of clustering or grouping correlated predictors and then pursuing group-wise model fitting was proposed (see [ ] and [ ]). When the dimension is very high or in case of overlapping clusters, finding an appropriate group structure remains as difficult as the original problem. An alternative approach is simultaneous clustering and model fitting that involves combination of two different penalties. For example, Elastic-Net [ ] is a combination of two regularization techniques, the ℓ2 regularization provides grouping effects and ℓ1 regularization produces sparse models. Therefore, Elastic-Net selects or drops highly correlated variables together that depends on the amount of ℓ1 and ℓ2 regularization.
The influence of correlations on Lasso prediction has been studied in [ ] and [ ], and it is shown that Lasso prediction works well in presence of any degree of correlations with an appropriate amount of regularization. However, studies show that correlations are problematic for parameter estimation and variable selection. It has been proven that the design matrix must satisfy the following two conditions for the Lasso to perform exact variable selection: irrepresentability condition (IC) [ ] and beta-min condition [ ]. Having highly correlated variables implies that the design matrix violates IC, and the Lasso solution is not stable. When active covariates are highly correlated, the Lasso solution is not unique and Lasso randomly selects one or a few variables from a correlated group. However, even in case of highly correlated variables the corresponding dual Lasso solution is always unique. The dual of the Lasso problem as given in equation ( ), as shown in [ ] is given by
1 sup 2 ‖Y‖22 − ‖ − Y‖22
subject to | | ≤ for = 1, ..., , ( ) where is the dual vector. The intuitions drawn from the articles [ ] and [ ] further motivate us to consider the Lasso optimal and its dual optimal solution together, that yields in selecting correlated active predictors.
Exploiting the fact about uniqueness of the dual Lasso solution, we propose a new variable selection procedure; the Dual Lasso Selector (DLS). For a given Lasso estimator ^(), we can compute the corresponding dual Lasso solution by the following relationship between the Lasso solution and its dual (see [ ] for the derivation): ^() = Y − X^(). ( ) Basically, the DLS active set (to be defined later), corresponds to the predictors that satisfy dual Lasso feasible boundary conditions (we discuss it in details in a later section). We argue that correlation among active predictors is not problematic, and we define a new weaker condition on the design matrix that allows for correlation among active predictors, called Pseudo Irrepresentable Condition (PIC). We show that the PIC is a necessary and sufficient condition for the proposed dual Lasso selector to select the true active set (under the assumption of beta-min condition) with a high probability. Moreover, we use the ℓ2 penalty (the Ridge regression, [ ]) which is known to perform best in case of correlated variables, to estimate the coefficients of the predictors selected by the dual Lasso selector. We call the combination of the two, DLSelect+Ridge. The DLSelect+Ridge resembles the Ridge post Lasso, but it is conceptually different and behaves differently from the Lasso followed by the Ridge, especially in the presence of highly correlated variables. Moreover, DLSelect+Ridge sounds like Elastic-net, since both are combinations of ℓ1 and ℓ2 penalties but Elastic-net is a combination of the Ridge Regression followed by the Lasso. In addition, Elastic-Net needs to cross-validate on a two-dimensional surface (2) to select its optimal regularization parameters, whereas DLSelect+Ridge needs to cross validate twice on one-dimensional surface (), where k is the length of the search space for a regularization parameter.
We have organized the rest of the paper in the following manner. We start with background in Section . In Section , we present Dual Lasso Selector, we define PIC and discuss variable selection consistency under this assumption on the design matrix and we illustrate the proposed method on a real set. We shall provide some concluding remarks in Section .
In this section, we state notations and assumptions, used throughout the paper. We consider usual sparse high-dimensional linear regression model as given in equation ( ) with ≫ . For the design matrix X ∈ R×, we represent rows by ∈ R, = 1, ..., , and columns by ∈ R, = 1, ..., . We assume that the design matrix X× is fixed, the data is centred and the predictors are standardized, so that ∑︀ =1( ) = 0 and 1 X X = 1 for =1 Y = 0, ∑︀ all = 1, ..., . We denote by = { ∈ {1, ..., } : ̸= 0}, the true active set and cardinality of the set . We assume that the true coefficient vector is sparse, that is ≪ . We denote X as the restriction of X to columns in , and is the vector restricted to the support , with zero outside the support . Without loss of generality we can assume that the first variables are the active variables, and we partition the covariance matrix, = 1 X X, for the active and the redundant variables as follows.
= [︂ 11 12 ]︂
21 22 Similarly, the coefficient vector can be partitioned as (1 2) . The ℓ1-norm and ℓ2-norm (square) are defined as ‖‖1 = ∑︀ =1 2 =1 | | and ‖‖22 = ∑︀ respectively. The sub-gradient ‖‖1 and sign function () are defined as follows.
‖‖1 = ⎧⎨ 1 if > 0
[−1, 1] if = 0 , () = ⎩ −1 if < 0 ⎨⎧ 01 iiff => 00 ⎩ −1 if < 0 ( ) ( )
In this section, we present the dual Lasso selector, a variable selection method for sparse high-dimensional regression models with correlated variables. First, we state the basic properties of the Lasso and its dual, which have already been derived and studied by various authors, see [ ] and [ ] for more details. . Uniqueness of the Lasso-fit: There may not be a unique solution for the Lasso problem because for the criterion as given in equation ( ) is not strictly convex in . But the least square loss is strictly convex in X, hence there is always a unique fitted value X^. . Uniqueness of the dual vector: The dual problem is strictly convex in , therefore the dual optimal ^ is unique. Another argument for the uniqueness of ^ is that it is a function of X^ as given in equation ( ), which itself is unique. The fact that the DLS can achieve consistent variable selection for situations (with correlated active predictors) when the Lasso is unstable for estimation of the true active set is related to the uniqueness of the dual Lasso solution. . Uniqueness of the Sub-gradient: Sub-gradient of ℓ1 norm of any Lasso solution ^ is unique because it is a function of X^. More specifically, suppose that ^ and ˜ are two Lasso solutions for a fixed value, then they must have the same signs (^) = (˜). It is not possible that ^ > 0 and ^ < 0 for some .
Let ^ denote the support set or active set of the Lasso estimator ^ which is given as () = { ∈ {1, ..., } : (^) ̸= 0}. Similarly, we define the ^ active set of the dual Lasso vector that corresponds to the active constraints of the dual optimization problem, ^() = { ∈ {1, ..., } : | | = }. Now, we state the following lemmas that will be used later for our mathematical derivations.
Lemma . The active set selected by the Lasso ^() is always contained in the active set selected by the dual Lasso ^(), that is ^() ⊆ (). ^ Proof. The proof is rather easy. From KKT conditions (see [ ]), we have | | < =⇒ ^ = 0 ( ) The proof lies in the implication in the above equation ( ).
It is known that IC (assuming beta-min conditions holds throughout the paper) is a necessary and sufficient condition for the Lasso to select the true model (see [ ]).
Lemma . Under the assumption of IC on the design matrix, the active set selected by the Lasso ^() is equal to the active set selected by the dual Lasso (), that is ^() = ^(). ^ For proof of the above lemma lies in the uniqueness of the Lasso solution under IC assumption [ ]. Suppose that we partition the covariance matrix as given in equation ( ), then IC is said to be met for the set with a constant > 0, if the following holds:
‖121−11(1)‖∞ ≤ 1 − .
The IC may fail to hold due to violation of any one (or both) of the following two conditions: . When 11 is almost not invertible, and thus there is strong correlation among variables of the true active set, . The active predictors are correlated with the noise features.
When there is strong correlation among variables of the active set, then 11 is (almost) not invertible and the IC does not hold, and the Lasso fails to do variable selection. In the following, we argue that the dual Lasso can still perform variable selection consistently even when 11 not invertible under the assumption of a milder condition on the design matrix, called Pseudo Irrepresentable Condition. The Pseudo Irrepresentable Condition is defined as follows.
Definition (Pseudo Irrepresentable Condition (PIC)). We partition the covariance matrix as given in equation (5). Then the PIC is said to be met for the set with a constant > 0, if the following holds: | (1)| ≤ 1 − , for all ∈ , [︂ − 1 0 ]︂ where G is a generalized inverse of the form , and equation (9) holds for 0 0 each ∈ , where is defined as := { : () = (11) = , ⊆ }.
The following lemma gives a sufficient condition for the dual Lasso for support recovery. This lemma is similar in spirit to Lemma defined in [ ]. Here, we do not assume that 11 is invertible.
Lemma (Primal-dual Condition for Variable Selection). Suppose that we can find a primal-dual pair (^, ^) that satisfies the following conditions: ( ) ( ) ( ) ( ) ( ) ( ) X (Y − X^) + ^ = 0, where ^ = (^) ^ = Y − X^, ^ = 0 for all ∈ , |^ | < 1 for all ∈ .
Then ^ is the unique optimal solution to the dual Lasso and ^ recovers the true active set.
Proof. We have shown that the dual Lasso optimal ^ is always unique, and it remains to show that ^ recovers the true active set . Under the assumption as given in equation ( ), we can derive that | ^| < for all ∈ . Therefore ^ = . Theorem . Under the assumption of PIC on the design matrix X, the active set selected by the dual Lasso ^, is the same as the true active set with a high probability, that is, ^ = .
The proof of the above theorem is similar to the proof of Theorem . in [ ], if inverse of the matrix 11 is replaced with its generalized inverse . We note that PIC may hold even when 11 is not invertible, which implies that PIC is weaker than IC. It is illustrated with the following examples.
Let = {1, 2, 3, 4} be the active set, and let the covariance matrix = [︃ 1 0 0 0 ]︃ XX of the design matrix X is given as = 000 010 100 001 . Here, the active 1 variables are uncorrelated and the noise variable is equally correlated with all active covariates. First of all, it is easy to check that only for || ≤ 12 , is positive semi definite, and for || < 14 , satisfies the IC. Now, we augment this matrix with two additional columns, one copy of the first and one copy of the second active variables, and we rearrange the columns such that we get ⎡ 1 1 0 0 0 0 ⎤ 1 1 0 0 0 0 0 0 1 1 0 0 covariance matrix, 1 = ⎢ 0 0 1 1 0 0 ⎥. Suppose that the set of active variables ⎣ 0 0 0 0 1 0 ⎦ 0 0 0 0 0 1 1 is = {1, 2, 3, 4, 5, 6} and we assume that || < 14 . We partition 1 as given in equation ( ), and it is clear that the corresponding sub-matrix 11 is not invertible and IC does not hold, hence the Lasso may not perform variable selection. The rank of the matrix 11 is . Let us consider any (4 × 4) sub matrix of the matrix 11 such that its rank is four ( ⊂ , () = 4, Here = {{1, 3, 5, 6}, {1, 4, 5, 6}, {2, 3, 5, 6}, {2, 4, 5, 6}}). Further, we consider the [︂ − 1 0 ]︂ generalized inverse of 11 as 1+1 = 0 0 , where ∈ is invertible. With the above inverse 1+1 PIC holds for the design matrix X, and the dual Lasso will select the true active set with a high probability and will set zero to the coefficient of the noise features. Now, we combine the dual Lasso selection with the Ridge estimation. Mainly, we consider the ℓ2 penalty (Ridge penalty) which is known to perform best in case of correlated variables, to estimate the coefficients of the predictors selected by the dual Lasso. We develop an algorithm called DLSelect+Ridge, which is a two stage procedure, the dual selection followed by the Ridge Regression.
If model selection works perfectly (under strong assumptions, i.e. IC), then the post-model selection estimators are the oracle estimators with well behaved properties (see [ ]). It has been already proven that the Lasso+OLS [ ] estimator performs at least as good as Lasso in terms of the rate of convergence, and it has a smaller bias than the Lasso. Further Lasso+mLS (Lasso+ modified OLS) or Lasso+Ridge estimator have been also proven to be asymptotically unbiased under the IC, see [ ]. Under the IC the Lasso solution is unique and Algorithm
: DLSelect+Ridge Input: dataset (Y, X) Output: ^:= the set of selected variables, ^ := the estimated coefficient vector Steps: . Perform Lasso on the data (Y, X). Denote the Lasso estimator as ^. . Compute the dual optimal as ^ = Y − X^, and denote the dual Lasso active set as ^ ^ . Compute the reduced design matrix as X = { : ∈ }. . Perform Ridge regression based on the data (Y, X) and obtain the ridge estimator for ∈ . Set the remaining coefficients to zero.
return (^, ^) the DLSelect+Ridge is the same as the Lasso+Ridge and the same argument holds for the DLSelect+Ridge. In the following section, we empirically compare the performance of DLSelect+Ridge with other methods. The dataset of riboflavin consists of = 71 observations of = 4088 predictors (gene expressions) and univariate response, riboflavin production rate (log-transformed), see [ ] for details on riboflavin dataset. Since the ground truth is not available, we consider Riboflavin data for the design matrix X with synthetic parameters and simulated Gaussian errors ∼ N(0, 2). We fix the size of the active set to = 20 and = 1, and for the true active set select ten predictors which are highly correlated with the response and another ten variables which are most correlated with those selected variables. The true coefficient vector is: = {︂ 01 iiff ̸∈∈ . Then we compute the response using equation ( ). We compute Mean Squared Error (MSE) and True Positive Rate (TPR) as performance measures, which are defined as follows: = 1 ∑︀=1( − ^)2 and = |^ ⋂︀ |/||, where ^′ are estimated responses and ^ is the estimated active set. The performance measures (the median MSE with standard deviation for runs, and the median TPR) are reported in Table . From Table , we conclude that DLSelect+Ridge performs better than others in terms of prediction performance, and DLSelect+Ridge is as good as Elastic-Net in terms of variable selection.
The main achievements of this work are summarized as follows: we argued that the correlation among active predictors is not problematic, as long as PIC is satisfied by the design matrix. In particular, we showed that the dual Lasso performs consistent variable selection under the assumption of PIC. Exploiting this result we proposed DLSelect+Ridge method. We compared DLSelect+Ridge with the popular existing methods by considering a real dataset. The numerical studies show that the proposed method is very competitive in terms of variable selection and prediction accuracy.