# Sign Consistency of the Generalized Elastic Net Estimator

Wencan Zhu, Eric Houngla Adjakossa, Céline Lévy-Leduc, Nils Ternès

► To cite this version:

Wencan Zhu, Eric Houngla Adjakossa, Céline Lévy-Leduc, Nils Ternès. Sign Consistency of the Generalized Elastic Net Estimator. 2021. hal-03254462

HAL Id: hal-03254462

https://hal.science/hal-03254462

Preprint submitted on 8 Jun 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Sign Consistency of the Generalized Elastic Net Estimator

Wencan Zhu, Eric Adjakossa, Céline Lévy-Leduc, Nils Ternès

## Abstract

In this paper, we propose a novel variable selection approach in the framework of high-dimensional linear models where the columns of the design matrix are highly correlated. It consists in rewriting the initial high-dimensional linear model to remove the correlation between the columns of the design matrix and in applying a generalized Elastic Net criterion since it can be seen as an extension of the generalized Lasso. The properties of our approach called gEN (generalized Elastic Net) are investigated both from a theoretical and a numerical point of view. More precisely, we provide a new condition called GIC (Generalized Irrepresentable Condition) which generalizes the EIC (Elastic Net Irrepresentable Condition) of [1] under which we prove that our estimator can recover the positions of the null and non null entries of the coefficients when the sample size tends to infinity. We also assess the performance of our methodology using synthetic data and compare it with alternative approaches. Our numerical experiments show that our approach improves the variable selection performance in many cases.

**Key words:** Lasso; Model selection consistency; Irrepresentable Condition; Generalized Lasso; Elastic Net.

## 1 Introduction

Variable selection has become an important and actively used task for understanding or predicting an outcome of interest in many fields such as medicine [2, 3, 4, 5], social media [6, 7, 8], or finance [9, 10, 11]. Through decades, numerous variable selection methods have been developed such as subset selection [12] or regularization techniques [13].

Subset selection methods achieve sparsity by selecting the best subset of relevant variables using the Akaike information criterion [14] or the Bayesian information criterion [15] but are shown to be NP-hard and could be unstable in practice [16, 17].

The regularized variable selection techniques have become popular for their capability to overcome the above difficulties [18, 19, 20, 21]. Among them, the Lasso approach [18] is one of the most popular and can be defined as follows. Let y satisfy the following linear model

$$y = X\beta^* + \epsilon, \quad (1)$$
where $y = (y_1, \dots, y_n)' \in \mathbb{R}^n$ is the response variable, $'$ denoting the transposition, $X = (X_1, \dots, X_p)$ is the design matrix with $n$ rows of observations on $p$ covariates, $\boldsymbol{\beta}^* = (\beta_1^*, \dots, \beta_p^*)' \in \mathbb{R}^p$ is a sparse vector, namely contains a lot of null components, and $\boldsymbol{\epsilon}$ is a Gaussian vector with zero-mean and a covariance matrix equal to $\sigma^2 \mathbb{I}_n$, $\mathbb{I}_n$ denoting the identity matrix in $\mathbb{R}^n$. The Lasso approach estimates $\boldsymbol{\beta}^*$ with a sparsity enforcing constraint by minimizing the following penalized least-squares criterion:

$$L_{\lambda}^{\text{Lasso}}(\boldsymbol{\beta}) = \|y - X\boldsymbol{\beta}\|_{2}^{2} + \lambda \|\boldsymbol{\beta}\|_{1}, \qquad (2)$$

where $\|a\|_1 = \sum_{k=1}^{p} |a_k|$ denotes the $\ell_1$ norm of the vector $(a_1, \dots, a_p)'$, $\|b\|_2^2 = \sum_{k=1}^{n} b_k^2$ denotes the $\ell_2$ norm of the vector $(b_1, \dots, b_n)'$, and $\lambda$ is a positive constant corresponding to the regularization parameter. The Lasso popularity largely comes from the fact that the resulting estimator

$$\hat{\boldsymbol{\beta}}^{\text{Lasso}}(\lambda) = \underset{\boldsymbol{\beta} \in \mathbb{R}^p}{\operatorname{Argmin}} L_{\lambda}^{\text{Lasso}}(\boldsymbol{\beta})$$

is sparse (has only a few nonzero entries), and sparse models are often preferred for their interpretability [22]. Moreover, $\hat{\boldsymbol{\beta}}^{\text{Lasso}}(\lambda)$ can be proved to be sign consistent under some assumptions, namely there exists $\lambda$ such that

$$\lim_{n \to \infty} \mathbb{P} \left( \text{sign} \left( \hat{\boldsymbol{\beta}}^{\text{Lasso}}(\lambda) \right) = \text{sign}(\boldsymbol{\beta}^*) \right) = 1,$$

where $\text{sign}(x) = 1$ if $x > 0$, $-1$ if $x < 0$ and $0$ if $x = 0$. Before giving the conditions under which [22] prove the sign consistency of $\hat{\boldsymbol{\beta}}^{\text{Lasso}}$, we first introduce some notations. Without loss of generality, we shall assume as in [22] that the first $q$ components of $\boldsymbol{\beta}^*$ are non null (i.e. the components that are associated to the active variables, and denoted as $\boldsymbol{\beta}_1^*$) and the last $p-q$ components of $\boldsymbol{\beta}^*$ are null (i.e. the components that are associated to the non active variables, and denoted as $\boldsymbol{\beta}_2^*$). Moreover, we shall denote by $X_1$ (resp. $X_2$) the first $q$ (resp. the last $p-q$) columns of $X$. Hence, $C_n = n^{-1}X'X$, which is the empirical covariance matrix of the covariates, can be rewritten as follows:

$$C_n = \begin{bmatrix} C_{11}^n & C_{12}^n \\ C_{21}^n & C_{22}^n \end{bmatrix},$$

with $C_{11}^n = n^{-1}X_1'X_1$, $C_{12}^n = n^{-1}X_1'X_2$, $C_{21}^n = n^{-1}X_2'X_1$, $C_{22}^n = n^{-1}X_2'X_2$. It is proved by Zhao and Yu in [22] that $\hat{\boldsymbol{\beta}}^{\text{Lasso}}(\lambda)$ is sign consistent when the following Irrepresentable Condition (IC) is satisfied:

$$\left| (C_{21}^n (C_{11}^n)^{-1} \text{sign}(\boldsymbol{\beta}_1^*))_j \right| \le 1 - \alpha, \text{ for all } j, \qquad (3)$$

where $\alpha$ is a positive constant. In the case where $p \gg n$, Wainwright develops in [23] the necessary and sufficient conditions, for both deterministic and random designs, on $p, q$, and $n$ for which it is possible to recover the positions of the null and non null components of $\boldsymbol{\beta}^*$, namely its support, using the Lasso.

When there are high correlations between covariates, especially the active ones, the $C_{11}^n$ matrix may not be invertible, and the Lasso estimator fails to be sign consistent. To
circumvent this issue, Zou and Hastie [20] introduced the Elastic Net estimator defined by:

$$ \hat{\beta}^{EN}(\lambda, \eta) = \underset{\beta \in \mathbb{R}^p}{\operatorname{Argmin}} L_{\lambda, \eta}^{EN}(\beta), \qquad (4) $$

where

$$ L_{\lambda, \eta}^{EN}(\beta) = \|y - X\beta\|_2^2 + \lambda \|\beta\|_1 + \eta \|\beta\|_2 \quad \text{with } \lambda, \eta > 0. $$

Yuan and Lin prove in [24] that when the following Elastic Net Condition (EIC) is satisfied the Elastic Net estimator defined by (4) is sign consistent when p and q are fixed: there exist positive λ and η such that

$$ \left| \left( C_{21}^n \left( C_{11}^n + \frac{\eta}{n} \mathbb{I}_q \right)^{-1} \left( \operatorname{sign}(\beta_1^*) + \frac{2\eta}{\lambda} \beta_1^* \right) \right)_j \right| \le 1 - \alpha, \quad \text{for all } j. \qquad (5) $$

Moreover, when p, q, and n go to infinity with $p \gg n$, Jia and Yu prove in [1] that the sign consistency of the Elastic Net estimator holds if additionally to Condition (5) n goes to infinity at a rate faster than $q \log(p - q)$.

In the case where the active and non active covariates are highly correlated, IC (3) and EIC (5) may be violated. To overcome this issue several approaches were proposed: the Standard Partial Covariance (SPAC) method [25] and preconditioning approaches among others. Xue and Qu [25] developed the so-called SPAC-Lasso which enjoys strong sign consistency in both finite-dimensional ($p < n$) and high-dimensional ($p \gg n$) settings. However, the authors mentioned that the SPAC-Lasso method only selects the active variables that are not highly correlated to the non active ones, which may be a weakness of this approach. The preconditioning approaches consist in transforming the given data X and y before applying the Lasso criterion. For example, [26] and [27] proposed to left-multiply X, y and thus $\epsilon$ in Model (1) by specific matrices to remove the correlations between the columns of X. A major drawback of the latter approach, called HOLP (High dimensional Ordinary Least squares Projection), is that the preconditioning step may increase the variance of the error term and thus may alter the variable selection performance.

Recently, [5] proposed another strategy under the following assumption:

(A1) X is assumed to be a random design matrix such that its rows $(x_i)_{1 \le i \le n}$ are i.i.d. zero-mean Gaussian random vectors having a covariance matrix equal to $\Sigma$.

More precisely, they propose to rewrite Model (1) in order to remove the correlation existing between the columns of X. Let $\Sigma^{-1/2} := UD^{-1/2}U^T$ where U and D are the matrices involved in the spectral decomposition of the symmetric matrix $\Sigma$ given by: $\Sigma = UDU^T$, then, denoting $\tilde{X} = X\Sigma^{-1/2}$, (1) can be rewritten as follows:

$$ y = \tilde{X}\tilde{\beta}^* + \epsilon, \qquad (6) $$

where $\tilde{\beta}^* = \Sigma^{1/2}\beta^* := UD^{1/2}U^T\beta^*$. With such a transformation, the covariance matrix of the n rows of $\tilde{X}$ is equal to identity and the columns of $\tilde{X}$ are thus uncorrelated. The advantage of such a transformation with respect to the preconditioning approach proposed by [27] is that the error term $\epsilon$ is not modified thus avoiding an increase of the noise which can
overwhelm the benefits of a well conditioned design matrix. Their approach then consists in minimizing the following criterion with respect to $\tilde{\beta}$:

$$ \|y - \tilde{X}\tilde{\beta}\|_2^2 + \lambda \|\Sigma^{-1/2}\tilde{\beta}\|_1, \qquad (7) $$

where $\tilde{X} = X\Sigma^{-1/2}$ in order to ensure a sparse estimation of $\beta^*$ thanks to the penalization by the $\ell_1$ norm. This criterion actually boils down to the Generalized Lasso proposed by [28]:

$$ L_{\lambda}^{genlasso}(\tilde{\beta}) = \|y - \tilde{X}\tilde{\beta}\|_2^2 + \lambda \|D\tilde{\beta}\|_1, \quad \text{with } \lambda > 0 \qquad (8) $$

and $D = \Sigma^{-1/2}$.

Since, as explained in [28], some problems may occur when the rank of the design matrix is not full, we will consider in this paper the following criterion:

$$ L_{\lambda, \eta}^{gEN}(\tilde{\beta}) = \|y - \tilde{X}\tilde{\beta}\|_2^2 + \lambda \|\Sigma^{-1/2}\tilde{\beta}\|_1 + \eta \|\tilde{\beta}\|_2^2, \quad \text{with } \lambda, \eta > 0. \qquad (9) $$

Since it consists in adding an $L_2$ penalty part to the Generalized Lasso as in the Elastic Net, we will call it generalized Elastic Net (gEN). We prove in Section 2 that under Assumption (A1) and the Generalized Irrepresentable Condition (GIC) (12) given below among others, $\tilde{\beta}$ is a sign-consistent estimator of $\beta^*$ where $\tilde{\beta}$ is defined by

$$ \tilde{\beta} = \Sigma^{-1/2}\tilde{\beta}, \qquad (10) $$

with

$$ \tilde{\beta} = \underset{\tilde{\beta}}{\operatorname{Argmin}} L_{\lambda, \eta}^{gEN}(\tilde{\beta}), \qquad (11) $$

$L_{\lambda, \eta}^{gEN}(\tilde{\beta})$ being defined in Equation (9). The Generalized Irrepresentable Condition (GIC) can be stated as follows: There exist $\lambda, \eta, \alpha, \delta_4 > 0$ such that for all $j$,

$$ \mathbb{P}\left(\left|\left((C_{21}^n + \frac{\eta}{n}\Sigma_{21})(C_{11}^n + \frac{\eta}{n}\Sigma_{11})^{-1}\left(\operatorname{sign}(\beta_1^*) + \frac{2\eta}{\lambda}\beta_1^*\right) - \frac{2\eta}{\lambda}\Sigma_{21}\beta_1^*\right)_j\right| \le 1 - \alpha\right) = 1 - o\left(e^{-n\delta_4}\right). \qquad (12) $$

Note that GIC coincides with EIC when $X$ is not random and $\Sigma = \mathbb{I}_p$. Moreover, GIC does not require $C_{11}^n$ to be invertible. Since EIC and IC are both particular cases of GIC, if the IC or EIC holds, then there exist $\lambda$ or $\eta$ such that the GIC holds.

The rest of the paper is organized as follows. Section 2 is devoted to the theoretical results of the paper. More precisely, we prove that under some mild conditions $\tilde{\beta}$ defined in (10) is a sign-consistent estimator of $\beta^*$. To support our theoretical results, some numerical experiments are presented in Section 3. The proofs of our theoretical results can be found in Section 5.

## 2 Theoretical results

The goal of this section is to establish the sign consistency of the Generalized Elastic Net estimator defined in (10). To prove this result, we shall use the following lemma.
**Lemma 2.1.** Let y satisfying Model (1) under Assumption (A1) and $\hat{\beta}$ be defined in (10). Then,

$$ \mathbb{P}(\mathrm{sign}(\hat{\beta}) = \mathrm{sign}(\beta^*) \ge \mathbb{P}(A_n \cap B_n), \quad (13) $$

where

$$ A_n := \left\{ \left| \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} W_n(1) \right| < \sqrt{n} \left| \left( \beta_1^* \right) - \frac{\lambda}{2n} \left| \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} \mathrm{sign}(\beta_1^*) \right| - \frac{\eta}{n} \left| \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} \Sigma_{11} \beta_1^* \right| \right\}, $$

$$ B_n := \left\{ \left| \mathcal{C}_{21}^{n,\Sigma} \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} W_n(1) - W_n(2) \right| \le \frac{\lambda}{2\sqrt{n}} - \frac{\lambda}{2\sqrt{n}} \left| \mathcal{C}_{21}^{n,\Sigma} \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} \left( \mathrm{sign}(\beta_1^*) + \frac{2\eta}{\lambda}\Sigma_{11}\beta_1^* \right) - \frac{2\eta}{\lambda}\Sigma_{21}\beta_1^* \right| \right\}, $$

and

$$ \mathcal{C}_{11}^{n,\Sigma} = C_{11}^{n} + \frac{\eta}{n}\Sigma_{11}, \quad \mathcal{C}_{21}^{n,\Sigma} = C_{21}^{n} + \frac{\eta}{n}\Sigma_{21}, \quad W_n = \frac{1}{\sqrt{n}}X'\epsilon = \begin{bmatrix} W_n(1) \\ W_n(2) \end{bmatrix}, \quad (14) $$

with

$$ W_n(1) = \frac{1}{\sqrt{n}}X_1'\epsilon \quad \text{and} \quad W_n(2) = \frac{1}{\sqrt{n}}X_2'\epsilon. $$

The proof of Lemma 2.1 is given in Section 5.

The following theorem gives the conditions under which the sign consistency of the generalized Elastic Net estimator $\hat{\beta}$ defined in (10) holds.

**Theorem 2.2.** Assume that y satisfies Model (1) under Assumption (A1) with $p = p_n$ is such that $p_n \exp(n^{-\delta})$ tends to 0 as $n$ tends to infinity for all positive $\delta$. Assume also that there exist some positive constants $M_1, M_2, M_3$ and $\alpha$ satisfying

$$ M_1 < \frac{\beta_{\min}^2}{9\sigma^2} \quad \text{and} \quad \frac{\sqrt{2 + \sqrt{2\sqrt{M_3}\sigma}}}{\alpha} < \frac{\beta_{\min}}{3M_2\sqrt{q}}, \quad (15) $$

and that there exist $\lambda > 0$ and $\eta > 0$ such that (12) and

$$ \frac{\lambda}{n} < \frac{2\beta_{\min}}{3M_2\sqrt{q}}, \quad (16) $$

$$ \frac{\lambda}{n} \ge \frac{2\sqrt{2 + \sqrt{2\sqrt{M_3}\sigma}}}{\alpha}, \quad (17) $$

$$ \frac{\eta}{n} < \frac{1}{3M_2\lambda_{\max}(\Sigma_{11})} \times \frac{\beta_{\min}}{\|\beta_1^*\|_2}, \quad (18) $$

hold as $n$ tends to infinity, where $\beta_{\min} = \min_{1 \le j \le q} |(\beta_1^*)_j|$. Suppose also that there exist some positive constants $\delta_1, \delta_2, \delta_3$ such that, as $n \to \infty$,

$$ \mathbb{P}(\lambda_{\max}(H_A H_A') \le M_1) = 1 - o(e^{-n\delta_1}), \quad (19) $$
$$ \mathbb{P} \left( \lambda_{\max} \left( \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} \right) \leq M_2 \right) = 1 - o \left( e^{-n^{\delta_2}} \right), \qquad (20) $$

$$ \mathbb{P} \left( \lambda_{\max} (H_B H_B') \leq M_3 \right) = 1 - o \left( e^{-n^{\delta_3}} \right), \qquad (21) $$

where $\lambda_{\max}(A)$ denotes the largest eigenvalue of A,

$$ H_A = \frac{1}{\sqrt{n}} \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} X'_1 \quad \text{and} \quad H_B = \frac{1}{\sqrt{n}} \left( \mathcal{C}_{21}^{n,\Sigma} \left( \mathcal{C}_{11}^{n,\Sigma} \right)^{-1} X'_1 - X'_2 \right), $$

$\mathcal{C}_{11}^{n,\Sigma}$ and $\mathcal{C}_{21}^{n,\Sigma}$ being defined in (14) and $X_1$ (resp. $X_2$) denoting the first $q$ (resp. the last $p-q$) columns of $X$. Then,

$$ \mathbb{P} \left( \mathrm{sign} \left( \hat{\beta} \right) = \mathrm{sign} \left( \beta^* \right) \right) \to 1, \text{ as } n \to \infty, $$

where $\hat{\beta}$ is defined in (10).

Note that Conditions (16) and (17) are consistent thanks to (15).

The proof of Theorem 2.2 is given in Section 5 and a discussion on the assumptions of Theorem 2.2 is provided in Section 3.

# 3 Numerical experiments

The goal of this section is to discuss the assumptions and illustrate the results of Theorem 2.2. For this, we generated datasets from Model (1) where the matrix $\Sigma$ appearing in (A1) is defined by

$$ \Sigma = \begin{bmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma'_{12} & \Sigma_{22} \end{bmatrix}. \qquad (22) $$

In (22), $\Sigma_{11}$ is the correlation matrix of the active variables having its off-diagonal entries equal to $\alpha_1$, $\Sigma_{22}$ is the correlation matrix of the non active variables having its off-diagonal entries equal to $\alpha_3$ and $\Sigma_{12}$ is the correlation matrix between the active and the non active variables with entries equal to $\alpha_2$. In the numerical experiments, $(\alpha_1, \alpha_2, \alpha_3) = (0.3, 0.5, 0.7)$. Moreover, $\beta^*$ appearing in Model (1) has $q$ non zero components which are equal to $b$ and $\sigma = 1$. The number of predictors $p$ is equal to 200, 400, or 600 and the sample size $n$ takes the same values for each value of $p$.

## 3.1 Discussion on the assumptions of Theorem 2.2

We first show that GIC defined in (12) can be satisfied even when EIC and IC, defined in (5) and (3) respectively, are not fulfilled. For this, we computed for different values of $\lambda$ and $\eta$
the following values:

$$
\begin{align}
\text{IC} &= \max_j \left( \left| (C_{21}^n (C_{11}^n)^{-1} (\text{sign}(\boldsymbol{\beta}_1^\star))_j) \right| \right) \nonumber \\
\text{EIC} &= \min_{\lambda, \eta} \max_j \left( \left| \left( C_{21}^n (C_{11}^n + \frac{\eta}{n} \mathbb{I}_q)^{-1} (\text{sign}(\boldsymbol{\beta}_1^\star) + \frac{2\eta}{\lambda} \boldsymbol{\beta}_1^\star) \right)_j \right| \right) \nonumber \\
\text{GIC} &= \min_{\lambda, \eta} \max_j \left( \left| \left( (C_{21}^n + \frac{\eta}{n} \Sigma_{21}) (C_{11}^n + \frac{\eta}{n} \Sigma_{11})^{-1} \left( \text{sign}(\boldsymbol{\beta}_1^\star) + \frac{2\eta}{\lambda} \boldsymbol{\beta}_1^\star \right) - \frac{2\eta}{\lambda} \Sigma_{21} \boldsymbol{\beta}_1^\star \right)_j \right| \right) \tag{23}
\end{align}
$$

and Figure 1 displays the boxplots of these criteria obtained from 100 replications. We can
see from these figures that in all the considered cases GIC is satisfied (i.e. all values are
smaller than 1) whereas EIC and IC are not. The values of p and n do not seem to have a big
impact on EIC and IC. However, contrary to p, n seems to have an influence on GIC which
increases with n when b = 1 and decreases when n increases when b = 10.

Figures 2 and 3 show the behavior of $\lambda_{\max} (H_A H'_A)$, $\lambda_{\max} ((C_{11}^{n,\Sigma})^{-1})$ and $\lambda_{\max} (H_B H'_B)$ appearing in (19), (20) and (21) with respect to $\eta$ for different values of $n$, $p$ and for $q = 5$ or $10$. These plots thus provide lower bounds for $M_1$, $M_2$ and $M_3$ appearing in the previous equations. Observe that (18) can be rewritten as:

$$
\eta M_2 < \frac{n}{3\lambda_{\max}(\Sigma_{11})} \times \frac{\beta_{\min}}{\|\boldsymbol{\beta}_1^*\|_2}. \quad (24)
$$

Based on the plots at the bottom right of Figures 2 and 3, we can see that there exist $\eta$'s
satisfying Condition 24 and thus (18) and that the interval in which the adapted $\eta$'s lie is
larger when $q = 5$ than when $q = 10$.

Based on the average of $M_1$ previously obtained, the left part of (15) is always satisfied as soon as $b > \sqrt{18}$. Based on the average of $M_2$ and $M_3$ previously obtained, the average of left-hand side and of the right-hand side of the right part of Equation (15) are displayed in Figures 4 and 5. We can see from these figures that it is only satisfied for large values of $b$. Moreover, it is more often satisfied when $q = 5$ than for $q = 10$.

We will show in the next section that even if the cases where all the conditions of the
theorem are not fulfilled our method is robust enough to outperform the Elastic Net defined
in (4) even in these cases.

3.2 Comparison with other methods

To assess the performance of our approach (gEN) in terms of sign-consistency with respect to other methods and to illustrate the results of Theorem 2.2, we computed the True Positive Rate (TPR), namely the proportion of active variables selected, and the False Positive Rate (FPR), namely the proportion of non active variables selected, of the Elastic Net and gEN estimators defined in (4) and (10), respectively.

Figures 6 and 8 display the empirical mean of the largest difference between the True Positive Rate and False Positive Rate over the replications. It is obtained by selecting for each replication the value of $\lambda$ and $\eta$ achieving the largest difference between the TPR and FPR and by averaging these differences. They also display the corresponding TPR and FPR
<figure><img src="image_1.png" /><figcaption>Figure 1: Boxplot of values defined in (23) and obtained from 100 replications.</figcaption></figure>
<figure><img src="image_2.png" /><figcaption>Figure 2: Top left: Average of $\lambda_{\max}(H_A H'_A)$ in (19) as a function of $\eta$. Top right: Average of $\lambda_{\max}((C_{11}^{n,\Sigma})^{-1})$ in (20) as a function of $\eta$. Bottom left: Average of $\lambda_{\max}(H_B H'_B)$ in (21) as a function of $\eta$. Bottom right: Average of the left (resp. right) part of (24) in plain (resp. dashed) line. The averages are obtained from 10 replications. Here $q = 5$.</figcaption></figure>

for gEN and Elastic Net for different values of $n$ and $p$. We can see from these figures that the gEN and the Elastic Net estimators have a TPR equal to 1 but that the FPR of gEN is smaller than Elastic Net. We can see from these figures that the difference between the performance of gEN and Elastic Net is larger for high signal-to-noise ratios ($b = 10$). It has to be noticed that when TPR=1 for our approach it also means that the signs of the non null $\beta_i^*$ are also properly retrieved.

# 4 Discussion

In this paper, we proposed a novel variable selection approach called gEN (generalized Elastic Net) in the framework of linear models where the columns of the design matrix are highly correlated and thus when the standard Lasso criterion usually fails. We proved that under mild conditions, among which the GIC, which is valid when other standard conditions like EIC or IC are not fulfilled, our method provides a sign-consistent estimator of $\beta^*$. For a more thorough discussion regarding the application of our approach in practical
<figure><img src="image_3.png" /><figcaption>Figure 3: Top left: Average of $\lambda_{\max}(H_A H'_A)$ in (19) as a function of $\eta$. Top right: Average of $\lambda_{\max}((\mathcal{C}_{11}^{n,\Sigma})^{-1})$ in (20) as a function of $\eta$. Bottom left: Average of $\lambda_{\max}(H_B H'_B)$ in (21) as a function of $\eta$. Bottom right: Average of the left (resp. right) part of (24) in plain (resp. dashed) line. The averages are obtained from 10 replications. Here $q = 10$.</figcaption></figure>

situations, we refer the reader to [5].

# 5 Proofs

## 5.1 Proof of Lemma 2.1

Note that (9) given by:

$$L^{gEN}(\tilde{\beta}) = \|y - \tilde{X}\tilde{\beta}\|_2^2 + \lambda \|\Sigma^{-1/2}\tilde{\beta}\|_1 + \eta \|\tilde{\beta}\|_2^2$$

can be rewritten as

$$L^{gEN}(\tilde{\beta}) = \|y^* - \tilde{X}^*\tilde{\beta}\|_2^2 + \lambda \|\Sigma^{-1/2}\tilde{\beta}\|_1,$$

where

$$y^* = \begin{pmatrix} y \\ 0 \end{pmatrix}, \quad \tilde{X}^* = \begin{pmatrix} \tilde{X} \\ \sqrt{\eta} \mathbb{I}_p \end{pmatrix}.$$
<figure><img src="image_4.png" /><figcaption>Figure 4: Average of the left-hand (resp. right-hand) side of the second part of (15) in red (resp. blue) for $q = 5$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 5: Average of the left-hand (resp. right-hand) side of the second part of (15) in red (resp. blue) for $q = 10$.</figcaption></figure>

Then, $\tilde{\beta}$ satisfies

$$ \tilde{\mathbf{X}}^* (\mathbf{y}^* - \tilde{\mathbf{X}}^* \tilde{\beta}) = \frac{\lambda}{2} (\Sigma^{-1/2})' z, \quad (25) $$

where $A'$ denotes the transpose of the matrix $A$, and

$$ \begin{cases} z_j = \text{sign} \left( (\Sigma^{-1/2} \tilde{\beta})_j \right), & \text{if } (\Sigma^{-1/2} \tilde{\beta})_j \neq 0 \\ z_j \in [-1, 1], & \text{if } (\Sigma^{-1/2} \tilde{\beta})_j = 0 \end{cases} $$
<figure><img src="image_6.png" /><figcaption>Figure 6: Average of max(TPR-FPR) and the corresponding TPR and FPR for gEN (in red) and Elastic Net (in blue) with *p* = 200.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 7: Average of max(TPR-FPR) and the corresponding TPR and FPR for gEN (in red) and Elastic Net (in blue) with *p* = 400.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 8: Average of max(TPR-FPR) and the corresponding TPR and FPR for gEN (in red) and Elastic Net (in blue) with $p = 600$.</figcaption></figure>
Equation (25) can be rewritten as:

$$X'y - (X'X + \eta\Sigma)\hat{\beta} = \frac{\lambda}{2}z$$

which leads to

$$X'X(\beta^* - \hat{\beta}) + X'\epsilon - \eta\Sigma\hat{\beta} = \frac{\lambda}{2}z,$$

by using that $y = X\beta^* + \epsilon$. By using the following notations: $\hat{u} = \hat{\beta} - \beta^*$,

$$C_n = \frac{1}{n}X'X \text{ and } W_n = \frac{1}{\sqrt{n}}X'\epsilon,$$

Equation (25) becomes

$$(C_n + \frac{\eta}{n}\Sigma) \sqrt{n}\hat{u} + \frac{\eta}{\sqrt{n}}\Sigma\beta^* - W_n = -\frac{\lambda}{2\sqrt{n}}z. \quad (26)$$

With the following notations:

$$C_n = \begin{pmatrix} C_{11}^n & C_{12}^n \\ C_{21}^n & C_{22}^n \end{pmatrix}, \Sigma = \begin{pmatrix} \Sigma_{11} & \Sigma_{12} \\ \Sigma_{21} & \Sigma_{22} \end{pmatrix}, \hat{u} = \begin{pmatrix} \hat{u}_1 \\ \hat{u}_2 \end{pmatrix}, W_n = \begin{pmatrix} W_n(1) \\ W_n(2) \end{pmatrix}, \beta^* = \begin{pmatrix} \beta_1^* \\ \mathbf{0} \end{pmatrix},$$

the first components of Equation (26) are:

$$(C_{11}^n + \frac{\eta}{n}\Sigma_{11}) \sqrt{n}\hat{u}_1 + (C_{12}^n + \frac{\eta}{n}\Sigma_{12}) \sqrt{n}\hat{u}_2 + \frac{\eta}{\sqrt{n}}\Sigma_{11}\beta_1^* - W_n(1) = -\frac{\lambda}{2\sqrt{n}}\mathrm{sign}(\beta_1^*). \quad (27)$$

If $\hat{u} = \begin{pmatrix} \hat{u}_1 \\ 0 \end{pmatrix}$, it can be seen as a solution of the generalized Elastic Net criterion where, by Equation (27), $\hat{u}_1$ is defined by:

$$\sqrt{n}\hat{u}_1 = (\mathscr{C}_{11}^{n,\Sigma})^{-1} W_n(1) - \frac{\eta}{\sqrt{n}} (\mathscr{C}_{11}^{n,\Sigma})^{-1} \Sigma_{11} \beta_1^* - \frac{\lambda}{2\sqrt{n}} (\mathscr{C}_{11}^{n,\Sigma})^{-1} \mathrm{sign}(\beta_1^*), \quad (28)$$

where we used (14).

Note that the event $A_n$ can be rewritten as follows:

$$\sqrt{n}\left(-|\boldsymbol{\beta}_1^*| + \frac{\lambda}{2n}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \mathrm{sign}(\boldsymbol{\beta}_1^*)\right| + \frac{\eta}{n}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right|\right) < \left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} W_n(1) < \sqrt{n}\left(|\boldsymbol{\beta}_1^*| - \frac{\lambda}{2n}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \mathrm{sign}(\boldsymbol{\beta}_1^*)\right| - \frac{\eta}{n}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right|\right)$$

which implies

$$\sqrt{n}\left(-|\boldsymbol{\beta}_1^*| + \frac{\lambda}{2n}\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \mathrm{sign}(\boldsymbol{\beta}_1^*) + \frac{\eta}{n}\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right) < \left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} W_n(1) < \sqrt{n}\left(|\boldsymbol{\beta}_1^*| + \frac{\lambda}{2n}\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \mathrm{sign}(\boldsymbol{\beta}_1^*) + \frac{\eta}{n}\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right),$$
using that $-|x| \le x \le |x|$, $\forall x \in \mathbb{R}$. Then, by using (28), we get that $\sqrt{n}|\hat{u}_1| < \sqrt{n}|\boldsymbol{\beta}_1^*|$ and thus $|\hat{u}_1| < |\boldsymbol{\beta}_1^*|$. Notice that $|\hat{u}_1| < |\boldsymbol{\beta}_1^*|$ implies that $\hat{\boldsymbol{\beta}}_1 \ne 0$ and that $\text{sign}(\hat{\boldsymbol{\beta}}_1) = \text{sign}(\boldsymbol{\beta}_1^*)$. Moreover, since $\hat{u}_2 = 0$, we get that $\text{sign}(\hat{\boldsymbol{\beta}}) = \text{sign}(\boldsymbol{\beta}^*)$.

The last components of (26) satisfy:

$$ (C_{21}^n + \frac{\eta}{n}\Sigma_{21}) \sqrt{n}\hat{u}_1 + (C_{22}^n + \frac{\eta}{n}\Sigma_{22}) \sqrt{n}\hat{u}_2 + \frac{\eta}{\sqrt{n}}\Sigma_{21}\boldsymbol{\beta}_1^* - W_n(2) = -\frac{\lambda}{2\sqrt{n}}z_2, $$

where by (25), $|z_2| \le 1$. Hence,

$$ \left| (C_{21}^n + \frac{\eta}{n}\Sigma_{21}) \sqrt{n}\hat{u}_1 + \frac{\eta}{\sqrt{n}}\Sigma_{21}\boldsymbol{\beta}_1^* - W_n(2) \right| \le \frac{\lambda}{2\sqrt{n}}, $$

which can be rewritten as follows by using (28):

$$ \left| \mathscr{C}_{21} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \left( W_n(1) - \frac{\eta}{\sqrt{n}} \Sigma_{11} \boldsymbol{\beta}_1^* - \frac{\lambda}{2\sqrt{n}} \text{sign}(\boldsymbol{\beta}_1^*) \right) + \frac{\eta}{\sqrt{n}} \Sigma_{21} \boldsymbol{\beta}_1^* - W_n(2) \right| \le \frac{\lambda}{2\sqrt{n}}. \quad (29) $$

When the event $B_n$ is satisfied:

$$ \begin{aligned} & -\frac{\lambda}{2\sqrt{n}} + \frac{\lambda}{2\sqrt{n}} \left| \mathscr{C}_{21}^{n, \Sigma} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \left( \text{sign}(\boldsymbol{\beta}_1^*) - \frac{2\eta}{\lambda}\Sigma_{11}\boldsymbol{\beta}_1^* \right) - \frac{2\eta}{\lambda}\Sigma_{21}\boldsymbol{\beta}_1^* \right| \\ & \le \mathscr{C}_{21}^{n, \Sigma} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} W_n(1) - W_n(2) \\ & \le \frac{\lambda}{2\sqrt{n}} - \frac{\lambda}{2\sqrt{n}} \left| \mathscr{C}_{21}^{n, \Sigma} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \left( \text{sign}(\boldsymbol{\beta}_1^*) + \frac{2\eta}{\lambda}\Sigma_{11}\boldsymbol{\beta}_1^* \right) - \frac{2\eta}{\lambda}\Sigma_{21}\boldsymbol{\beta}_1^* \right|. \end{aligned} \quad (30) $$

By using that $-|x| \le x \le |x|$ for all $x$ in $\mathbb{R}$, we get that it implies that

$$ \left| \mathscr{C}_{21}^{n, \Sigma} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} W_n(1) - W_n(2) - \frac{\lambda}{2\sqrt{n}} \mathscr{C}_{21}^{n, \Sigma} \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \left( \text{sign}(\boldsymbol{\beta}_1^*) + \frac{2\eta}{\lambda}\Sigma_{11}\boldsymbol{\beta}_1^* \right) + \frac{\eta}{\sqrt{n}}\Sigma_{21}\boldsymbol{\beta}_1^* \right| \le \frac{\lambda}{2\sqrt{n}}, $$

which corresponds to (29). Thus, if $A_n$ and $B_n$ are satisfied, we get that $\text{sign}(\hat{\boldsymbol{\beta}}) = \text{sign}(\boldsymbol{\beta})$, which concludes the proof.

## 5.2 Proof of Theorem 2.2

By Lemma 2.1,

$$ \mathbb{P} \left( \text{sign} \left( \hat{\boldsymbol{\beta}} \right) = \text{sign} \left( \boldsymbol{\beta}^* \right) \right) \ge \mathbb{P} \left( A_n \cap B_n \right) \ge 1 - \mathbb{P} \left( A_n^c \right) - \mathbb{P} \left( B_n^c \right), $$

where $A_n^c$ and $B_n^c$ denote the complementary of $A_n$ and $B_n$, respectively. Thus, to prove the theorem it is enough to prove that $\mathbb{P}(A_n^c) \to 0$ and $\mathbb{P}(B_n^c) \to 0$ as $n \to \infty$.

Recall that

$$ A_n := \left\{ \left| \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} W_n(1) \right| < \sqrt{n} \left| \boldsymbol{\beta}_1^* - \frac{\lambda}{2n} \left| \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \text{sign}(\boldsymbol{\beta}_1^*) \right| - \frac{\eta}{n} \left| \left( \mathscr{C}_{11}^{n, \Sigma} \right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^* \right| \right\}. $$
Let $\zeta$ and $\tau$ be defined by

$$ \zeta = (\mathscr{C}_{11}^{n,\Sigma})^{-1} W_n(1) \text{ and } \tau = \sqrt{n} \left( |\boldsymbol{\beta}_1^\star| - \frac{\lambda}{2n} \left| (\mathscr{C}_{11}^{n,\Sigma})^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star) \right| - \frac{\eta}{n} \left| (\mathscr{C}_{11}^{n,\Sigma})^{-1} \Sigma_{11} \boldsymbol{\beta}_1^\star \right| \right). $$

Then,

$$ \mathbb{P}(A_n) = \mathbb{P}(\forall j, |\zeta_j| < \tau_j). $$

Thus,

$$ \mathbb{P}(A_n^c) = \mathbb{P}(\exists j, |\zeta_j| \ge \tau_j) \le \sum_{j=1}^q \mathbb{P}(|\zeta_j| \ge \tau_j). $$

Note that

$$
\begin{align}
\mathbb{P}(|\zeta_j| \ge \tau_j) &= \mathbb{P}\left(|\zeta_j| \ge \sqrt{n}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star)\right)_j\right| - \frac{\lambda}{2n}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^\star\right)_j\right| - \frac{\eta}{n}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^\star\right)_j\right|\right) \right) \nonumber \\
&= \mathbb{P}\left(|\zeta_j| + \frac{\lambda}{2\sqrt{n}}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star)\right)_j\right| + \frac{\eta}{\sqrt{n}}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^\star\right)_j\right| \ge \sqrt{n}\left|\left(\boldsymbol{\beta}_1^\star\right)_j\right|\right) \nonumber \\
&\le \mathbb{P}\left(|\zeta_j| \ge \sqrt{n}\frac{|\boldsymbol{\beta}_1^\star|}{3}\right) + \mathbb{P}\left(\frac{\lambda}{2\sqrt{n}}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star)\right)_j\right| \ge \sqrt{n}\frac{|\boldsymbol{\beta}_1^\star|}{3}\right) \nonumber \\
&\quad + \mathbb{P}\left(\frac{\eta}{\sqrt{n}}\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^\star\right)_j\right| \ge \sqrt{n}\frac{|\boldsymbol{\beta}_1^\star|}{3}\right). \tag{31}
\end{align}
$$

Observe that

$$ \zeta = (\mathscr{C}_{11}^{n,\Sigma})^{-1} W_n(1) = \frac{1}{\sqrt{n}} \left( C_{11}^n + \frac{\eta}{n} \Sigma_{11} \right)^{-1} \mathbf{X}'_1 \epsilon = H_A \epsilon, $$

where

$$ H_A = \frac{1}{\sqrt{n}} \left( C_{11}^n + \frac{\eta}{n} \Sigma_{11} \right)^{-1} \mathbf{X}'_1, $$

$\mathbf{X}_1$ denoting the columns of the design matrix $\mathbf{X}$ associated to the $q$ active covariates. Thus, for all $j$ in $\{1, \dots, q\}$,

$$ \zeta_j = \sum_{k=1}^{n} (H_A)_{jk} \epsilon_k. $$

By using the Cauchy-Schwarz inequality,

$$
\begin{align*}
|\zeta_j| &= \left| \sum_{k=1}^{n} (H_A)_{jk} \epsilon_k \right| \\
&\le \left( \sum_{k=1}^{n} (H_A)_{jk}^2 \right)^{1/2} \left( \sum_{k=1}^{n} \epsilon_k^2 \right)^{1/2} \\
&= \sqrt{(H_A H'_A)_{jj}} \times \|\epsilon\|_2 \\
&\le \sqrt{\lambda_{\max} (H_A H'_A)} \times \|\epsilon\|_2.
\end{align*}
$$
Hence, the first term in the r.h.s. of (31) satisfies the following inequalities:

$$ 
\begin{aligned}
\mathbb{P}\left(\left|\zeta_j\right| \ge \sqrt{n}\frac{|(\boldsymbol{\beta}_1^\star)_j|}{3}\right) &\le \mathbb{P}\left(\sqrt{\lambda_{\max}(H_A H'_A)} \times \|\boldsymbol{\epsilon}\|_2 \ge \sqrt{n}\frac{|(\boldsymbol{\beta}_1^\star)_j|}{3}\right) \\
&\le \mathbb{P}\left(\lambda_{\max}(H_A H'_A) \times \|\boldsymbol{\epsilon}\|_2^2 \ge n\frac{(\boldsymbol{\beta}_1^\star)_j^2}{9}\right).
\end{aligned}
\quad (32) $$

Since by (19), there exist $M_1 > 0$ and $\delta_1 > 0$ such that

$$ \mathbb{P}(\lambda_{\max}(H_A H'_A) \le M_1) = 1 - o(e^{-n^{\delta_1}}), \text{ as } n \to \infty, $$

we have:

$$ 
\begin{aligned}
\mathbb{P}\left(\lambda_{\max}(H_A H'_A) \times \|\boldsymbol{\epsilon}\|_2^2 \ge n \frac{(\boldsymbol{\beta}_1^\star)_j^2}{9}\right) &\le \mathbb{P}\left(\|\boldsymbol{\epsilon}\|_2^2 \ge n \frac{(\boldsymbol{\beta}_1^\star)_j^2}{9M_1}\right) + \mathbb{P}(\lambda_{\max}(H_A H'_A) > M_1) \\
&\le \mathbb{P}\left(\frac{\|\boldsymbol{\epsilon}\|_2^2}{\sigma^2} \ge \frac{n\boldsymbol{\beta}_{\min}^2}{9M_1\sigma^2}\right) + o(e^{-n^{\delta_1}}).
\end{aligned}
$$

Using that $\frac{\|\boldsymbol{\epsilon}\|_2^2}{\sigma^2} \sim \chi^2(n)$, we get, by Lemma 1 of [29], that

$$ \mathbb{P}\left(\lambda_{\max}(H_A H'_A) \times \|\boldsymbol{\epsilon}\|_2^2 \ge n \frac{(\boldsymbol{\beta}_1^\star)_j^2}{9}\right) \le \exp\left(-\frac{t}{2} + \frac{1}{2}\sqrt{n(2t-n)}\right) + o\left(e^{-n^{\delta_1}}\right), \quad (33) $$

since $t = \frac{n\boldsymbol{\beta}_{\min}^2}{9M_1\sigma^2} > \frac{n}{2}$ using that $\frac{2\boldsymbol{\beta}_{\min}^2}{9\sigma^2} > M_1$ by (15).

By putting together Equations (32) and (33) we get

$$ \mathbb{P}\left(\left|\zeta_j\right| > \sqrt{n}\frac{|(\boldsymbol{\beta}_1^\star)_j|}{3}\right) \le \exp\left(-\frac{t}{2} + \frac{1}{2}\sqrt{n(2t-n)}\right) + o\left(e^{-n^{\delta_1}}\right), \quad (34) $$

with $t = \frac{n\boldsymbol{\beta}_{\min}^2}{9M_1\sigma^2} > \frac{n}{2}$.

Let us now derive an upper bound for the second term in the r.h.s. of (31):

$$ \mathbb{P}\left(\frac{\lambda}{2\sqrt{n}}\left|\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star)\right|\right|_j \ge \sqrt{n}\frac{|(\boldsymbol{\beta}_1^\star)_j|}{3}\right). $$

By using the Cauchy-Schwarz inequality, we get that:

$$ 
\begin{aligned}
\left|\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^\star)\right|\right|_j &= \left|\sum_{k=1}^q \left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right|_{jk} \left(\operatorname{sign}(\boldsymbol{\beta}_1^\star)\right)_k\right| \\
&\le \sqrt{\sum_{k=1}^q \left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right|_{jk}^2} \times \|\operatorname{sign}(\boldsymbol{\beta}_1^\star)\|_2 \\
&\le \sqrt{\left(\mathscr{C}_{11}^{n,\Sigma}\right)_{jj}^{-2}} \times \sqrt{q} \\
&\le \lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \times \sqrt{q}.
\end{aligned}
$$
Then,

$$
\begin{align*}
& \mathbb{P}\left(\frac{\lambda}{2\sqrt{n}}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \operatorname{sign}(\boldsymbol{\beta}_1^*)\right| \ge \sqrt{n}\frac{|(\boldsymbol{\beta}_1^*)_j|}{3}\right) \\
\le {} & \mathbb{P}\left(\frac{\lambda}{2}\sqrt{\frac{q}{n}}\lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \ge \sqrt{n}\frac{|(\boldsymbol{\beta}_1^*)_j|}{3}\right) \\
\le {} & \mathbb{P}\left(\lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \ge \frac{2n}{3\lambda\sqrt{q}}|(\boldsymbol{\beta}_1^*)_j|\right) \\
\le {} & \mathbb{P}\left(\lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \ge \frac{2n}{3\lambda\sqrt{q}}\boldsymbol{\beta}_{\min}\right) = o\left(e^{-n^{\delta_2}}\right), \quad \text{as } n \to \infty, \tag{35}
\end{align*}
$$

since $\frac{2n}{3\lambda\sqrt{q}}\boldsymbol{\beta}_{\min} > M_2$ by (16). Let us now derive an upper bound for the third term in the
r.h.s. of (31):

$$
\mathbb{P}\left(\frac{\eta}{\sqrt{n}}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\Sigma_{11}\boldsymbol{\beta}_1^*\right| > \sqrt{n}\frac{|(\boldsymbol{\beta}_1^*)_j|}{3}\right).
$$

We have

$$
\begin{align*}
\left|\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right)_j\right| &= \left|\sum_{k=1}^q \left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11}\right)_{jk} (\boldsymbol{\beta}_1^*)_k\right| \\
&\le \sqrt{\sum_{k=1}^q \left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11}\right)_{jk}^2} \times \|\boldsymbol{\beta}_1^*\|_2 \\
&\le \sqrt{\lambda_{\max} \left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11}^2 \left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right)} \times \|\boldsymbol{\beta}_1^*\|_2 \\
&\le \lambda_{\max} \left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \lambda_{\max}(\Sigma_{11}) \times \|\boldsymbol{\beta}_1^*\|_2.
\end{align*}
$$

Thus,

$$
\begin{align*}
& \mathbb{P}\left(\frac{\eta}{\sqrt{n}}\left|\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \Sigma_{11} \boldsymbol{\beta}_1^*\right| \ge \sqrt{n} \frac{|(\boldsymbol{\beta}_1^*)_j|}{3}\right) \\
\le {} & \mathbb{P}\left(\frac{\eta}{\sqrt{n}} \lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \lambda_{\max}(\Sigma_{11}) \|\boldsymbol{\beta}_1^*\|_2 \ge \sqrt{n} \frac{|(\boldsymbol{\beta}_1^*)_j|}{3}\right) \\
\le {} & \mathbb{P}\left(\lambda_{\max}\left(\left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1}\right) \ge \frac{n\boldsymbol{\beta}_{\min}}{3\eta \|\boldsymbol{\beta}_1^*\|_2 \lambda_{\max}(\Sigma_{11})}\right) = o\left(e^{-n^{\delta_2}}\right), \quad \text{as } n \to \infty, \tag{36}
\end{align*}
$$

$$
\text{since } \frac{n\boldsymbol{\beta}_{\min}}{3\eta \|\boldsymbol{\beta}_1^*\|_2 \lambda_{\max}(\Sigma_{11})} > M_2 \text{ by (18).}
$$

By putting together Equations (34), (35) and (36), we get:

$$
\mathbb{P}(A_n^c) \le q \exp \left[ -\frac{n}{2} (\kappa - \sqrt{2\kappa - 1}) \right] + q \times o(e^{-n^{\delta_1}}) + 2q \times o(e^{-n^{\delta_2}}), \quad (37)
$$

with $\kappa = \frac{\beta_{\min}^2}{9M_1\sigma^2}$. Note that $\kappa - \sqrt{2\kappa - 1} > 0$ since $\kappa = \frac{\beta_{\min}^2}{9M_1\sigma^2} > 1$ by (15). Equation (37)
then implies that

$$
\mathbb{P}(A_n^c) \to 0 \text{ as } n \to \infty.
$$
Let us now prove that $\mathbb{P}(B_n^c) \to 0$ as $n \to \infty$.

Recall that

$$B_n := \left\{ \left| \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} W_n(1) - W_n(2) \right| \le \frac{\lambda}{2\sqrt{n}} - \frac{\lambda}{2\sqrt{n}} \left| \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} \left( \mathrm{sign}(\boldsymbol{\beta}_1^\star) + \frac{2\eta}{\lambda} \Sigma_{11} \boldsymbol{\beta}_1^\star \right) - \frac{2\eta}{\lambda} \Sigma_{21} \boldsymbol{\beta}_1^\star \right| \right\}.$$

Let

$$\psi = \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} W_n(1) - W_n(2) = \frac{1}{\sqrt{n}} \left( \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} \mathbf{X}'_1 - \mathbf{X}'_2 \right) \epsilon :=: H_B \epsilon$$

and

$$\mu = \frac{\lambda}{2\sqrt{n}} - \frac{\lambda}{2\sqrt{n}} \left| \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} \left( \mathrm{sign}(\boldsymbol{\beta}_1^\star) + \frac{2\eta}{\lambda} \Sigma_{11} \boldsymbol{\beta}_1^\star \right) - \frac{2\eta}{\lambda} \Sigma_{21} \boldsymbol{\beta}_1^\star \right|.$$

Then,

$$\mathbb{P}(B_n^c) = \mathbb{P}(\exists j, |\psi_j| > \mu_j) \le \sum_{j=q+1}^p \mathbb{P}(|\psi_j| > \mu_j).$$

By using the Cauchy-Schwarz inequality, we get that:

$$|\psi_j| = \left| \sum_{k=1}^{n} (H_B)_{jk} \epsilon_k \right| \le \left( \sum_{k=1}^{n} (H_B)_{jk}^2 \right)^{1/2} \times \|\epsilon\|_2 = \sqrt{(H_B H'_B)_{jj}} \times \|\epsilon\|_2 \le \sqrt{\lambda_{\max}(H_B H'_B)} \times \|\epsilon\|_2, \quad (38)$$

where

$$H_B H'_B = \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} C_{11}^{n} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} \mathscr{C}_{12}^{n,\Sigma} - \mathscr{C}_{21}^{n,\Sigma} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} C_{12}^{n} - C_{21}^{n} \left( \mathscr{C}_{11}^{n,\Sigma} \right)^{-1} \mathscr{C}_{12}^{n,\Sigma} + C_{22}^{n}.$$

By (21), there exist $M_3 > 0$ and $\delta_3 > 0$ such that

$$\mathbb{P} (\lambda_{\max} (H_B H'_B) \le M_3) = 1 - o (e^{-n \delta_3}), \text{ as } n \to \infty.$$

By the GIC condition (12), there exist $\alpha > 0$ and $\delta_4 > 0$ such that for all $j$,

$$\mathbb{P}\left(\left|\mathscr{C}_{21}^{n,\Sigma} \left(\mathscr{C}_{11}^{n,\Sigma}\right)^{-1} \left(\mathrm{sign}(\boldsymbol{\beta}_1^\star) + \frac{2\eta}{\lambda}\Sigma_{11}\boldsymbol{\beta}_1^\star\right) - \frac{2\eta}{\lambda}\Sigma_{21}\boldsymbol{\beta}_1^\star\right| \le 1 - \alpha\right) = 1 - o\left(e^{-n\delta_4}\right).$$
Thus, we get that:

$$
\begin{align*}
\mathbb{P}(B_n^c) &\le \sum_{j=q+1}^p \mathbb{P}(|\psi_j| > \mu_j) \\
&\le \sum_{j=q+1}^p \mathbb{P}(|\psi_j| > \frac{\lambda\alpha}{2\sqrt{n}}) + (p-q)\mathcal{o}(e^{-n\delta_4}) \\
&\le \sum_{j=q+1}^p \mathbb{P}\left(\sqrt{\lambda_{\max}(H_B H'_B)} \times \|\boldsymbol{\epsilon}\|_2 > \frac{\lambda\alpha}{2\sqrt{n}}\right) + (p-q)\mathcal{o}(e^{-n\delta_4}), \text{ using Equation (38)} \\
&\le \sum_{j=q+1}^p \mathbb{P}\left(\lambda_{\max}(H_B H'_B) \times \|\boldsymbol{\epsilon}\|_2^2 > \frac{\lambda^2\alpha^2}{4n}\right) + (p-q)\mathcal{o}(e^{-n\delta_4}) \\
&\le \sum_{j=q+1}^p \mathbb{P}\left(\frac{\|\boldsymbol{\epsilon}\|_2^2}{\sigma^2} > \frac{\lambda^2\alpha^2}{4nM_3\sigma^2}\right) + (p-q)\mathcal{o}(e^{-n\delta_3}) + (p-q)\mathcal{o}(e^{-n\delta_4}) \\
&\le (p-q)\exp\left(-\frac{s}{2} + \frac{1}{2}\sqrt{n(2s-n)}\right) + (p-q)\mathcal{o}(e^{-n\delta_3}) + (p-q)\mathcal{o}(e^{-n\delta_4}) \\
&\le (p-q)\exp\left(-\frac{n}{2}\left(\frac{s}{n} - \sqrt{2\frac{s}{n}-1}\right)\right) + (p-q)\mathcal{o}(e^{-n\delta_3}) + (p-q)\mathcal{o}(e^{-n\delta_4}) \\
&\le (p-q)\exp\left(-\frac{n}{2}\right) + (p-q)\mathcal{o}(e^{-n\delta_3}) + (p-q)\mathcal{o}(e^{-n\delta_4}) \tag{39}
\end{align*}
$$

with $\frac{s}{n} = \frac{\lambda^2 \alpha^2}{4n^2 M_3 \sigma^2}$ since $\frac{\lambda^2 \alpha^2}{4n^2 M_3 \sigma^2} \ge 2 + \sqrt{2}$ by (17). Finally, Equation (39) implies that

$\mathbb{P}(B_n^c) \to 0, \text{ as } n \to \infty,$

which concludes the proof.

## References

[1] Jinzhu Jia and B. Yu. On model selection consistency of the elastic net when $p \gg n$. *Statistica Sinica*, 20, 04 2010.

[2] Wenbin Lu, Hao Zhang, and Donglin Zeng. Variable selection for optimal treatment decision. *Statistical methods in medical research*, 22, 11 2011.

[3] Lacey Gunter, Ji Zhu, and Susan Murphy. Variable selection for qualitative interactions in personalized medicine while controlling the family-wise error rate. *Journal of biopharmaceutical statistics*, 21(6):1063–1078, 2011.

[4] Xuemin Gu, Guosheng Yin, and J Jack Lee. Bayesian two-step lasso strategy for biomarker selection in personalized medicine development for time-to-event endpoints. *Contemporary clinical trials*, 36(2):642–650, 2013.
[5] Wencan Zhu, Céline Lévy-Leduc, and Nils Ternès. A variable selection approach for highly correlated predictors in high-dimensional genomic data. *Bioinformatics*, 2021. doi: 10.1093/bioinformatics/btab114. Epub ahead of print. PMID: 33617644.

[6] Zeynep Tufekci. Big questions for social media big data: Representativeness, validity and other methodological pitfalls. *Proceedings of the 8th International Conference on Weblogs and Social Media, ICWSM 2014*, 03 2014.

[7] Huijie Lin, Jia Jia, Liqiang Nie, Guangyao Shen, and Tat-Seng Chua. What does social media say about your stress?. In *IJCAI*, pages 3775–3781, 2016.

[8] Theodore S Tomeny, Christopher J Vargo, and Sherine El-Toukhy. Geographic and demographic correlates of autism-related anti-vaccine beliefs on twitter, 2009-15. *Social science & medicine*, 191:168–175, 2017.

[9] Georgios Sermpinis, Serafeim Tsoukas, and Ping Zhang. Modelling market implied ratings using lasso variable selection techniques. *Journal of Empirical Finance*, 48:19–35, 2018.

[10] Alessandra Amendola, Francesco Giordano, Maria Parrella, and Marialuisa Restaino. Variable selection in high-dimensional regression: A nonparametric procedure for business failure prediction. *Applied Stochastic Models in Business and Industry*, 33, 02 2017.

[11] Bartosz Uniejewski, Grzegorz Marcjasz, and Rafał Weron. Understanding intraday electricity markets: Variable selection and very short-term price forecasting using lasso. *International Journal of Forecasting*, 35(4):1533–1547, 2019.

[12] Norman R Draper and Harry Smith. *Applied regression analysis*, volume 326. John Wiley & Sons, 1998.

[13] Peter J Bickel, Bo Li, Alexandre B Tsybakov, Sara A van de Geer, Bin Yu, Teófilo Valdés, Carlos Rivero, Jianqing Fan, and Aad van der Vaart. Regularization in statistics. *Test*, 15(2):271–344, 2006.

[14] Hirotogu Akaike. Information theory and an extension of the maximum likelihood principle. In *Selected papers of hirotugu akaike*, pages 199–213. Springer, 1998.

[15] Gideon Schwarz et al. Estimating the dimension of a model. *Annals of statistics*, 6(2):461–464, 1978.

[16] William J Welch. Algorithmic complexity: three np-hard problems in computational statistics. *Journal of Statistical Computation and Simulation*, 15(1):17–25, 1982.

[17] Leo Breiman et al. Heuristics of instability and stabilization in model selection. *Annals of Statistics*, 24(6):2350–2383, 1996.

[18] Robert Tibshirani. Regression shrinkage and selection via the lasso. *Journal of the Royal Statistical Society: Series B (Methodological)*, 58:267–288, 01 1996.
[19] Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton, 05 2015.

[20] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society Series B, 67:768–768, 02 2005.

[21] Tong Tong Wu, Yi Fang Chen, Trevor Hastie, Eric Sobel, and Kenneth Lange. Genome-wide association analysis by lasso penalized logistic regression. Bioinformatics, 25(6):714–721, 01 2009.

[22] Peng Zhao and B. Yu. On model selection consistency of lasso. Journal of Machine Learning Research, 7:2541–2563, 12 2006.

[23] Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using l1-constrained quadratic programming (lasso). IEEE transactions on information theory, 55(5):2183–2202, 2009.

[24] Ming Yuan and Yi Lin. On the nonnegative garrote estimator. Journal of the Royal Statistical Society Series B, 69:143–161, 04 2007.

[25] Fei Xue and Annie Qu. Variable selection for highly correlated predictors. arXiv preprint arXiv:1709.04840, 2017.

[26] Jinzhu Jia and Karl Rohe. Preconditioning the lasso for sign consistency. Electron. J. Statist., 9(1):1150–1172, 2015.

[27] Xiangyu Wang and Chenlei Leng. High dimensional ordinary least squares projection for screening variables. J. R. Stat. Soc. Ser. B (Stat. Methodol.), 78(3):589–611, 2016.

[28] Ryan J. Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. Ann. Statist., 39(3):1335–1371, 06 2011.

[29] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302–1338, 2000.