Group lasso is a commonly used regularization method in statistical learning in which parameters are eliminated from the model according to predefined groups. However, when the groups overlap, optimizing the group lasso penalized objective can be time-consuming on large-scale problems because of the non-separability induced by the overlapping groups. This bottleneck has seriously limited the application of overlapping group lasso regularization in many modern problems, such as gene pathway selection and graphical model estimation. In this paper, we propose a separable penalty as an approximation of the overlapping group lasso penalty. Thanks to the separability, the computation of regularization based on our penalty is substantially faster than that of the overlapping group lasso, especially for large-scale and high-dimensional problems. We show that the penalty is the tightest separable relaxation of the overlapping group lasso norm within the family of $\ell_{q_1}/\ell_{q_2}$ norms. Moreover, we show that the estimator based on the proposed separable penalty is statistically equivalent to the one based on the overlapping group lasso penalty with respect to their error bounds and the rate-optimal performance under the squared loss. We demonstrate the faster computational time and statistical  equivalence of our method compared with the overlapping group lasso in simulation examples and a classification problem of cancer tumors based on gene expression and multiple gene pathways.

§ INTRODUCTION

Grouping patterns of variables are commonly observed in real-world applications. For example, in regression modeling, explanatory variables might belong to different groups with the expectation that the variables are highly correlated within the groups. In this context, variable selection or model regularization should also consider the grouping patterns, and one may prefer to either include the whole group of variable in the selection or completely rule out the group. Group lasso [Yuan and Lin, 2006] is one popular method designed for this group selection task via adding $\ell_1/\ell_2$ regularization, as a broader class for group selection. [Zhao et al., 2009, Levina et al., 2008, Meier et al., 2008, Yan and Bien, 2017, Bach, 2008, Ravikumar et al., 2009, Xiang et al., 2015, Loh, 2014, Campbell and Allen, 2017, Tank et al., 2017, Danaher et al., 2014, Basu et al., 2015, Austin et al., 2020, Yang and Peng, 2020].

While in the original motivation of group lasso assumes disjoint groups, overlapping groups also appear frequently in many applications such as tumor metastasis analysis  [Zhao et al., 2009, Jacob et al., 2009, Yuan et al., 2011, Chen et al., 2012] and structured model estimations [Cheng et al., 2017, Mohan et al., 2014, Yu and Bien, 2017, Tarzanagh and Michailidis, 2018]. In tumor metastasis analysis, scientists usually aim to select a small number of tumor-related genes. Biological theory indicates that genes do not function in isolation but rather that suites of genes act in concert to perform biological functions. Hence, the gene selection is more meaningful if co-functioning groups of genes are selected together [Ma and Kosorok, 2010]. In particular, pathway analysis renders mechanistic insight into the co-functioning pattern, which results in overlapping groups of genes. Applying group lasso with these overlapping groups is then a natural way to incorporate the prior group information into tumor metastasis analysis. For another example, graphical model estimation has been widely used to express conditional dependency structures among variables. Cheng et al., 2017 developed a mixed graphical model for high-dimensional data with both continuous and discrete variables. In their model, the groups are naturally predetermined by the parameter vector corresponding to each edge, and groups overlap because they represent edges sharing common nodes. In this scenario, the group lasso penalty provides a natural way for edge selection.

The original group lasso problem with non-overlapping groups can be solved efficiently [Qin et al., 2013, Yang and Zou, 2015, Friedman et al., 2010, Meier et al., 2008]. However, solving the overlapping group lasso problems, despite its convexity,  becomes nontrivial. This is because the non-separability between groups intrinsically increases the dimensionality of the problem compared with the non-overlapping situation, as revealed in the study of [Yan and Bien, 2017].  Proposed methods include the second-order cone program method SLasso [Jenatton et al., 2011], the ADMM-based methods  [Boyd et al., 2011, Deng et al., 2013], and their smoothed improvement, FoGLasso, introduced by [Yuan et al., 2011]. All these exact solvers of the problem involve expensive gradient evaluations when the overlapping becomes severe, limiting the applicability of the overlapping group lasso in many large-scale applications such as genomewide association studies (Section <ref>) or graphical model fitting problems [Cheng et al., 2017]. For instance, Cheng et al., 2017 showed that overlapping group lasso, though as a natural choice for the problem, is infeasible even for moderate-size graphs, and they used a fast lasso approach [Tibshirani, 1996] to solve the graph estimation problem without theory. As we introduce later, our proposed solution includes the method of Cheng et al., 2017 as a special case, but our method is more general and comes with theoretical guarantees.

In this paper, we propose a non-overlapping approximation penalty for the overlapping group lasso penalty. The approximation is formulated as a weighted non-overlapping group lasso penalty that respects the original overlapping patterns. The proposed penalty is shown to be the tightest separable relaxation of the original overlapping group lasso penalty with the family of $\ell_{q_1}/\ell_{q_2}$ norms. The non-overlapping nature of our penalty opens the door to eﬃcient computation. We show that our proposed estimator leads to an equivalent estimator of the original overlapping group lasso estimator in that our method allows the same or better order estimation errors and achieves a minimax rate when the original estimator is minimax. We demonstrate the value of our proposed method using simulation examples and a prediction task on a breast cancer gene data set.

The rest of the paper is structured as follows: we introduce the proposed approximation method in Section <ref> and prove that it is optimality as the tightest separable relaxation of the overlapping group lasso norm. We introduce our study of statistical estimation errors in Section <ref>. In Section <ref> and Section <ref>, we present several empirical evaluations on both simulation data and the real breast cancer gene expression data.

Section <ref> concludes the paper with further discussions.

§ STATISTICAL PROPERTIES

Using our proposed norm $\psi_{\Gcal}$ as an alternative to the original group lasso norm $\phi_G$ would result in a different optimization problem compared to (<ref>). However, as we shall justify in this section, the resulting estimator enjoys a similar theoretical estimation error. Our theoretical analysis will focus on (potentially high-dimensional) linear models, which is the setting of most previous group lasso theoretical analysis [Lounici et al., 2011, Huang and Zhang, 2010, Dedieu, 2019, Negahban et al., 2012]. Specifically, define the linear model as

\begin{equation}\label{eq:linear-model}
\end{equation}

where $Y \in \mathbb{R}^{n \times 1}$ is the response vector,  $X \in \mathbb{R}^{n \times p}$ is the data matrix,  and $\varepsilon \in \mathbb{R}^{n \times 1}$ is a random noise vector. The two estimators we want to study are the original overlapping group lasso estimator, defined as

\begin{equation}\label{eq:OGL-est}
\hat{\beta}^G = \argmin_{\beta \in \bR^p}~~\frac{1}{2n}\norm{Y-X\beta}_2^2 + \lambda_n  \phi_G(\beta)
\end{equation}

and the regularized estimator by our approximation norm, defined as

\begin{equation}\label{eq:Our-est}
\hat{\beta}^\Gcal = \argmin_{\beta \in \bR^p}~~\frac{1}{2n}\norm{Y-X\beta}_2^2 + \mathcal{\lambda}_n \psi_{\Gcal}(\beta).
\end{equation}

As a remark, our target is not to argue that (<ref>) is an approximate optimization problem of (<ref>). Instead, we will show that the two classes of estimators defined by (<ref>) and (<ref>) are statistically equivalent in their estimation errors when the $\lambda_n$ values are properly chosen, which may differ for the two estimators. Therefore, from the standpoint of statistical estimation, the class of estimators introduced by our method  (<ref>) is preferable because it gives a similar estimation accuracy with significantly better computational efficiency. Our theoretical results include two parts. In the first part, we show that under reasonable assumptions, the estimation error bound of (<ref>) is no larger than that of (<ref>). In the second part, we give the minimax error rate of overlapping sparse group regression problem and show that both  (<ref>) and (<ref>)  are minimax optimal under additional requirements of the group structures.

§.§ Estimation Error Bounds

The theoretical analysis involves more quantities about group structures. For a group index set $I \subseteq [m]$, we define $G_{I}$  as $\mathop{\bigcup}_{g\in I}G_g $. Additionally, we define $\mathbf{G_{I}}$ as a new group membership matrix corresponding to $G_{I}$.

Given a group structure $G$ and a group index set $I,$ we introduce two parameter spaces
$M(I)=\left\{\beta\in{\mathbb{R}^p}|\beta_j=0 \text{ for all } j \in (G_{I})^c\right\}$ and $M^{\perp}(I)=\left\{\beta\in \mathbb{R}^p |\beta_j=0 \text{ for all } j\in G_{I}\right\}.$ We further use $\beta_{M(I)}$ to denote the projection of $\beta$ onto $M(I).$ Additionally, we introduce the following definitions.

Given $\beta \in \bR^p$, the support set of $\beta$ is denoted as
$$\textit{supp}(\beta)=\{j\in [p]|\beta_j\neq 0\},$$

the group support set of $\beta$ is defined as

$$S(\beta) =\left\{g\in [m]|G_g \cap \textit{supp}(\beta)\neq
\varnothing\right\},$$

and the augmented group support set
is defined as
$$\overline{S(\beta)}=\{g \in [m]|G_g\cap
{G_{S(\beta)}\neq \varnothing}\}.$$

We use $s = |\textit{supp}(\beta)|$ to denote the number of non-zero elements, use $s_g = |S(\beta)|$ to denote the number of non-zero groups, and use  $\overline{s_g} = |\overline{S(\beta)}|$ to denote the number of groups in the augmented group support set.
For simplicity,  we also abbreviate $S(\beta)$ by $S$ and $\overline{S(\beta)}$ by $\overline{S}$.
We first introduce the distributional assumptions.

Under model (<ref>), we further assume

* (Sub-Gaussian noises) The coordinates of $\varepsilon$ are i.i.d zero mean sub-Gaussian random variable denote with parameter $\sigma$. That is, there exists $\sigma > 0$ such that

$$ E[e^{t\varepsilon}] \leqslant {e^{\frac{\sigma^2t^2}{2}}}, \hspace{0.3cm} \text{for all} \hspace{0.2cm} t \in \mathbb{R}.$$

* (Normal random design)   The rows of data matrix $X$ are i.i.d from  $N(0,\Theta)$,  where  $\frac{1}{c_1} \leqslant \gamma_{\min}(\Theta) \leqslant \gamma_{\max}(\Theta) \leqslant c_1$ for some constant $c_1>0$.

* (Pattern of group structure) The pre-defined group structure $G$ satisfies $d_{\max} \le c_2n$ for some constant $c_2>0$ and $\log{m}\ll n$.

Given $G$ and its induced $\Gcal$ according to our method, define $h_{\min}^{g} = \min\limits_{j \in G_g}h_j$, $d_{\max} = \max\limits_{g \in [m]}d_g$, and $\dcal_{\max} = \max\limits_{\gcal \in [\mcal]}\dcal_{\gcal}$.  Under Assumption <ref>, suppose $\hat{\beta}^G, \hat{\beta}^{\Gcal}$ are defined in (<ref>) and (<ref>). For $\delta \in (0,1)$ which is a scalar that might depend on $n$ and some constant $c_3 > 0$, we have the following results.

* Suppose $\beta^*$ satisfies the following group sparsity

\begin{equation}\label{eq:orig-sparsity}
\overline{s_g}(\beta^*) \lesssim
\frac{n}{\log m + d_{\max} }
\cdot
\frac{\min\limits_{g\in[m]}( w_g^2 h_{\min}^{g})}{\max\limits_{g\in \overline{S}} (w_g^2 h_{\max}^{g})}.
\end{equation}

When $\lambda_n =  \frac{c' \sigma }{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}\sqrt{\frac{d_{\max}}{n}+
\frac{\log{m}}{n}+\delta}$ for some constant $c'>0$, we have

\begin{equation}
\label{eq:ell2bound}
\left\|\hat{\beta}^{G}-\beta^{\ast}\right\|^2_2\lesssim\sigma^2\cdot\frac{\left(\sum\limits_{g\in\overline{S}}{w_g}^2\right)\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}
\cdot\left(\frac{d_{\max}{}}{n}+\frac{\log{m}}{n}+\delta\right).
\end{equation}

with probability at least $1-e^{-c_3n\delta}$ form constant $c_3>0$.

* Suppose $\beta^*$ satisfies the following group sparsity

\begin{equation}\label{eq:new-sparsity}
\overline{s_\gcal}(\beta^*) \lesssim
\frac{n}{\log \mcal + \dcal_{\max} }
\cdot
\frac{\min\limits_{\gcal\in[\mcal]}( \wcal_\gcal^2 )}{\max\limits_{\gcal\in S} (\wcal_\gcal^2)}.
\end{equation}

When $
\lambda_n =  \frac{c' \sigma }{\min\limits_{\gcal\in[\mcal]} \wcal_g^2}
\sqrt{\frac{\dcal_{\max}}{n}+
\frac{\log{\mcal}}{n}+\delta}$  for some constant $c'>0$, we have

\begin{equation}
\label{eq:parell2bound}
\left\|\hat{\beta}^{\mathcal{G}}-\beta^{\ast}\right\|_2^2 \lesssim\sigma^2\cdot\frac{\sum\limits_{\mathcal{g}\in \{F^{-1}(g)\}_{g \in S} }{\mathcal{w}_{\mathcal{g}}}^2}{\min\limits_{\mathcal{g}\in[\mathcal{m}]}\left(\wcal_\mathcal{g}^2 \right)}
\cdot\left(\frac{\mathcal{d}_{\max}{}}{n}+\frac{\log{\mathcal{m}}}{n}+\delta\right).
\end{equation}

with probability at least $1-e^{-c_4n\delta}$ form constant $c_4>0$.

The error bound (<ref>) includes the non-overlapping group lasso error bound as a special case. When the groups in $G$ are disjoint, the reduced form of (<ref>) matches the bounds studied in [Huang and Zhang, 2010, Negahban et al., 2012, Lounici et al., 2011, Wainwright, 2019]. The main difference is that in the overlapping situation, we have to include the measurement of overlapping degree and the sparsity requirement is extended to the augmented groups. Moreover, the group sparsity requirements in (<ref>) and (<ref>) are slightly different. However, in many common situations, they are essentially the same. For example, in the previous interlocking group example, they match each other. In this case, our requirement is that the cardinality of the augmented group support is much smaller than $\frac{n}{\log m + d_{\max}}$.

Moreover, we show the relation between the two bounds in (<ref>) and (<ref>) under a mild assumption under which both (<ref>) and (<ref>) match each other.

Suppose that $\max\limits_{g \in \overline{S}} |F^{-1}(g)| \leqslant c_3$ for some constant $c_3$. Furthermore, $d_{\max} \asymp \dcal_{\max}$, and $m \asymp \mcal$.

Under Assumption <ref>, we have

\begin{equation*}
\frac{\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{w}_{\mathcal{g}}}^2}{\min\limits_{\mathcal{g}\in[m]}\left(w_\mathcal{g}^2 \right)}
\cdot\left(\frac{\mathcal{d}_{\max}{}}{n}+\frac{\log{\mathcal{m}}}{n}+\delta\right) \lesssim \frac{\left(\sum\limits_{g\in\overline{S}}{w_g}^2\right)\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}
\cdot\left(\frac{d_{\max}{}}{n}+\frac{\log{m}}{n}+\delta\right).
\end{equation*}

This means that the error bound of $\hat{\beta}^{G}$ in (<ref>) is also an upper bound for the error of $\hat{\beta}^{\Gcal}$.

§.§ Lower Bound of Estimation Error

The previous section compares the  estimation error upper bounds of the two estimators. To make the result stronger, we study the minimax rate of the estimation error in the linear regression model with overlapping group sparsity. We will focus on the following class of group-wise sparse vectors.

\begin{equation}
\label{class}
\Omega(G,s_g) = \Bigg\{\beta : \sum\limits_{G_g \in G}\mathbbm{1}_{\{\norm{\beta_{G_g}}_2 \neq 0\} } \leqslant s_g\Bigg\}
\end{equation}

We need to further introduce additional constraints on the parameter space that are similar to the Assumptions in  [Cai et al., 2022].

Under model (<ref>), further assume

* X is a random design data matrix, and all rows of $X$ are i.i.d centered sub-gaussian distributed with covariance matrix $\Theta$. We further assume that $ \gamma_{\max }(\Theta)  \leqslant c_4$ for some constant $c_4$.

* The $m$ predefined groups of $G$ come with equal group size $d$, $m \ll p, d \ll \log(p).$

(Lower bound of estimation error)·
Under Assumption <ref>,  we have

\begin{equation}\label{eq:minimax}
\inf\limits_{\hat{\beta}}  \sup\limits_{\beta \in \Omega(G,s_g)} E\|\hat{\beta}-\beta\|_{2}^{2} \gtrsim \frac{\sigma^2\left(s_g(d +\log (\frac{m}{s_g}))\right)}{n}.
\end{equation}

Theorem <ref> and  Theorem <ref> together indicate that the two estimators achieve the minimax error rate, as formulated in the following corollary. Therefore, in this case, they are precisely statistically equivalent.

Under the conditions of Theorem <ref> and  Theorem <ref>, if $m \asymp \mathcal{m}$ and $h_{\max}(\mathbf{G_{\overline{S}}}) \asymp 1$, then both $\hat{\beta}^G$ and $\hat{\beta}^{\Gcal}$ achieves the minimax estimation rate specified in (<ref>).

§ SIMULATION

In this section, we use synthetic data to compare overlapping group lasso and our proposed group lasso approximation. As another reference for separable but loose approximation, we include the weighted lasso (<ref>). We use the SLEP package [Liu et al., 2009] in MATLAB for computation. Although the package may not be the most eﬃcient for implementing non-overlapping group lasso and lasso optimization, it is the most efficient one we know for overlapping group lasso [Yuan et al., 2011], and it provides the same implementation framework for all three methods, thus ensuring a fair comparison.

For each configuration of the data-generating model, we evaluate the performance in two aspects:

* Regularization path computing time. We first use a line search to find approximately the smallest $\lambda$ that selects no variables, denoted by $\lambda_{\max}$, and also the maximum $\lambda$ that selects the full model, denoted by $\lambda_{\min}$. Then we pick 100 values in log-scale in $[\lambda_{\min}, \lambda_{\max}]$. The full regularization path is computed on the 100 $\lambda$ values and the computing time of the regularization path is recorded as a performance metric. The computing time evaluation mimics the most practical situation where the whole regularization path is solved for tuning purposes.

* Estimation error: From the computed regularization path, we take the smallest relative estimation error, defined as $\norm{\hat{\beta}-\beta^{\ast}}_2/\norm{\beta^{\ast}}_2$, as the estimation error for the method. This is the measure of the ideally tuned performance.

In the settings, the group weight of the overlapping group lasso is set to be $w_g = \sqrt{d_g}$, as is usually used in practice. We generate 100 independent replicates for each configuration and report the average result.

§.§ Interlocking group structure

In the first set of experiments, we evaluate the performances based on interlocking group structure of Figure <ref>. We set $m$ interlocked groups with $d$ variables in each group and  $0.2d$ variables in each intersection. For example, with $m = 5$ and $d = 10$, we have $G_1 = \{1,\cdots,10\}, G_2 = \{8, 9,\cdots,17\},\cdots,G_{10} = \{33, 34,\cdots,42\}.$

The data matrix $X$ is generated from a Gaussian distribution $N(0, \Theta)$, where $\Theta$ is specified with correlations matching the group structure. We first construct the following matrix $\tilde{\Theta}$

$$\tilde{\Theta}_{ij} =
\begin{cases}
1, &\text{if i = j,} \\
0, &\text{$\beta_i$ and $\beta_j$ are in different groups in $G$}\\
0.6, &\text{$\beta_i$ and $\beta_j$ are in the same  group in $\Gcal$}\\
0.36, &\text{$\beta_i$ and $\beta_j$ are in the same group in $G$ but different groups in $\Gcal$}
\end{cases}.$$

$\Theta$ is then taken to be the projection of $\tilde{\Theta}$ on the set of positive definite matrices with with minimum eigenvalue of 0.1.

We generate each coordinate of $\beta^{\ast}$ by first sampling from $N(10, 16)$,  assigning negative and positive signs randomly, and then randomly setting $\floor*{0.9m}$ groups to be zero. The response variable $Y$ is generated by  $Y = X\beta^{\ast} + \epsilon$, where $\epsilon \sim N(0,\sigma^2)$ and $\sigma^2$ is set to give the signal-to-noise ratio of $3$.

Figure <ref> shows the average computation time (sec.) with its 95% confidence interval (CI) in logarithmic scale and average estimation error with its 95% CI  under different configurations.
As expected, solving the proposed approximation method is much faster than solving the original overlapping group lasso problem by a factor of 20–150, and  lasso approximation is even faster than our group lasso approximation. As expected, increasing the sample size, number of variables or group size would increase the computational time. With these increase of problem scale, the computational advantage of method is more significant.

Under all configurations, the lasso approximation gives much larger estimation errors compared with the original overlapping group lasso solution. In contrast, our proposed method achieves very similar accuracy to that of the overlapping group lasso estimator. This empirically verifies our theoretical results.

In summary, the estimation from our proposed approximation gives similar statistical estimation performance to the original overlapping group lasso estimation while rendering significant improvement in computation. The weighted lasso is computationally eﬃcient but gives very poor estimation, thus it is not a competitive approximation of the original problems.

Performance vs. Sample size

Performance vs. Number of groups

Performance vs. Groups size

Regularization path computing time comparison and estimation error under different configurations.  (a) Varying sample size $n$ when fixing $m = 400$ and $d = 20$; (b) Varying number of groups $m$ when fixing $n = 800$ and $d = 20$ ;  (c) Varying group size $d$ when fixing $n = 800$ and $m = 200$ .

§.§ Group structures based on real-world gene pathways

In this set of experiments, we use real-world designs to evaluate the methods. Specifically, we use the gene canonical pathways from the Molecular Signatures Database [Subramanian et al., 2005] as the group structures. Each gene pathway is a collection of genes that share common biological features. Therefore, the sets of gene pathways can be used as gene group structures. Such group structures can provide helpful and interpretable ways to improve prediction performance in practice [Yuan et al., 2011, Jacob et al., 2009, Chen et al., 2012]. We use five major gene pathway sets as five different group structures in our evaluation, as summarized in Table <ref>.

Summary of the collections of gene pathways, including number of groups ($m$) , average group size ($\bar{d}$), average overlapping degree  ($\bar{h}$) and the number of genes after filtering (p) are also summarized in the table.

Pathways     Information     $m$    $\bar{d}$     $\bar{h}$     p

BioCarta is a database of gene interaction models. The database contains high-quality images of several cellular signaling and interaction pathways, and each diagram is fully hyperlinked to products and information pages about individual genes.     292    15.4
3.25    1129

PID     The Pathway Interaction Database (PID) is a freely available collection of curated and peer-reviewed pathways composed of human molecular signaling and regulatory events and key cellular processes [Schaefer et al., 2008]     196    38.51
3.28    2297

KEGG     The Kyoto Encyclopedia of Genes and Genomes (KEGG) is an integrated database resource for biological interpretation of genome sequences and other high-throughput data [Kanehisa et al., 2015].     186     58.48
2.58    4207

WIKI     WikiPathways captures the collective knowledge represented in biological pathways. By providing a database in a curated, machine readable way, omics data analysis and visualization is enabled. WikiPathways and other pathway databases are used to analyze experimental data by research groups in many fields [Slenter et al., 2017]     712     38.17
4.35    6242

Reactome     The Reactome Knowledgebase, an Elixir core resource, provides manually curated molecular details across a broad range of physiological and pathological biological processes in humans, including both hereditary and acquired disease processes [Gillespie et al., 2021].      1615    45.31
8.78    8331

The design matrix $X$ in this example is the gene expression data in [Van De Vijver et al., 2002] as our design matrix. The data can be founded in R package "breastCancerNKI" [Schroeder et al., 2021]. The design matrix contains 295 observations and 24481 genes. Given each gene pathway set, we filter all the genes that are undefined in the pathway sets.

The data-generating procedure for $\beta^*$ and $y$ remains almost the same as before, except that here we use a much sparser model because of the small sample size. Specifically, we randomly sample $0.05m$ active groups and set the coefficients in other groups to zero. We set the group weights in overlapping group lasso to be $\sqrt{d_g}$ and use the proposed weight modification for our approximation. Figure <ref> displays the computing time and estimation error results for the five pathway group structures. The high-level message remains the same as before: the overlapping group lasso is extremely slow in this problem. Both our proposed group lasso approximation and the lasso approximation could substantially reduce the computing time by a factor of 10–60. Meanwhile, our proposed group lasso approximation delivers very similar statistical estimation performance to the original overlapping group lasso estimator, whereas the lasso approximation fails to effectively leverage the group information, delivering worse estimation performance.

Estimation error v.s. group structure

Computing time (sec.) v.s group structure

Comparison of performances on different group structures.

§ APPLICATION TO  BREAST CANCER DATA

The gene expression data set we used in Section <ref> also contains additional attributes for the 295 observations. In particular, the observations have labeled the status of breast cancer tumors (79 metastatic and 216 non-metastatic). Previous studies [Yuan et al., 2011, Jacob et al., 2009, Chen et al., 2012] showed that some of the canonical gene pathways might provide helpful grouping information in predicting the tumor type from gene expression data. In this example, we want to examine the pathway sets in Table <ref>. Specifically, we use regularized logistic regression to build a prediction model, with the overlapping group lasso penalty, our proposed group lasso approximation, and the standard lasso penalty. In this case, the lasso penalty does not take the pathway information. Hence, comparing the performance of the overlapping group lasso and the lasso approximation would provide some empirical insights into whether a specific gene pathway set contains predictive grouping information for breast cancer tumor type. Please note this example is designed to demonstrate our approximation to the overlapping group lasso. We aim to examine, rather than to claim, the effectiveness of gene pathways.

Similar to the setting in [Lee and Xing, 2014], we randomly assign 200 samples to the training data and 95 samples to the testing data. All three methods are tuned by 5-fold cross-validation on the training data. We  calculate the area under the receiver operating characteristic (AUC) curve, a commonly used metric for classifying accuracy  [Hanley and McNeil, 1982], on the test data.  The total time for the entire cross-validation process is recorded as computation time. Again, the experiment is repeated 100 times independently. Table <ref> shows the average computing time and Table <ref> shows the average AUC.

Solving time (in sec) under different pathway databases

[30mm]Overlapping group lasso   [5mm]Lasso    [45mm]Proposed group lasso approximation

BioCarts    653.94   25.39   65.52
KEGG   1239.71   43.08   90.86
PID    2219.12    117.65     270.30
WikiPathways    4865.09   196.08   446.41
Reactome    10483.99   348.84   990.18

Predictive AUC results of the three methods under different pathway databases. The $*$ indicates that the AUC is significantly different from the AUC of the overlapping group lasso by a paired t-test.

[30mm]Overlapping group lasso   [5mm]Lasso    [45mm]Proposed group lasso approximation

BioCarts    0.7239     0.6993*   0.7247
KEGG   0.7071   0.6836*     0.7098
PID    0.7513   0.7138*     0.7382*
WikiPathways    0.6979   0.7261*   0.6838*
Reactome    0.6727   0.7288*    0.6911*

From these results, we can see that the pathway sets in BioCarts, KEGG and PID databases seem predictive, while the other two are not very helpful. The proposed approximation method results in similar predictive performance with the overlapping group lasso while the computation is much faster.

§ DISCUSSION

We have introduced a separable penalty as an approximation to the group lasso penalty when groups overlap. The penalty is designed by partitioning the original overlapping groups into disjoint subgroups and reweighing the new groups according to the original overlapping pattern. The penalty is the tightest separable relaxation of the overlapping group lasso among all $\ell_{q_1}/\ell_{q_2}$ norms. We have also shown that for linear problems, the proposed estimator is statistically equivalent to the original overlapping group lasso estimator. However, the proposed method is significantly faster in computation as compared to the original overlapping group lasso, rendering the proposed method applicable in large-scale problems.

Several interesting directions could be considered for future research. First, the theoretical study in this paper focuses on the estimator errors of the two estimators. Correct support recovery can be proved, assuming a proper group sparsity pattern. However, without assuming such a model, the output of the two estimators might not be perfectly aligned.  If a group-union zero pattern is still strictly required, certain post-processing of our estimator is needed. The in-depth study of this step would be of great practical interest. Second, when a group-union nonzero pattern is desirable, the latent overlapping group lasso [Jacob et al., 2009], as a popular choice, also suffers from a non-separability computational bottleneck. It would be valuable to investigate whether a similar approximation strategy could be designed to boost the computational performance in this scenario.

The work is supported in part by the NSF grant DMS-2015298 and the 3-Caveliers award from the University of Virginia.

[Austin et al., 2020]
E. Austin, W. Pan, and X. Shen.
A new semiparametric approach to finite mixture of regressions using
penalized regression via fusion.
Statistica Sinica, 300 (2):0 783, 2020.

[Bach, 2008]
F. R. Bach.
Consistency of the group lasso and multiple kernel learning.
Journal of Machine Learning Research, 90 (6), 2008.

[Basu et al., 2015]
S. Basu, A. Shojaie, and G. Michailidis.
Network granger causality with inherent grouping structure.
The Journal of Machine Learning Research, 160
(1):0 417–453, 2015.

[Beck and Teboulle, 2009]
A. Beck and M. Teboulle.
A fast iterative shrinkage-thresholding algorithm for linear inverse
SIAM journal on imaging sciences, 20 (1):0
183–202, 2009.

[Bertsekas, 1997]
D. P. Bertsekas.
Nonlinear programming.
Journal of the Operational Research Society, 480
(3):0 334–334, 1997.

[Bien, 2018]
J. Bien.
Graph-guided banding of the covariance matrix.
Journal of the American Statistical Association, 2018.

[Boyd et al., 2011]
S. Boyd, N. Parikh, E. Chu, B.Peleato, and J.Eckstein.
Distributed optimization and statistical learning via the alternating
direction method of multipliers.
Foundations and Trends in Machine learning, 3:0
1–122, 2011.

[Cai et al., 2022]
T. T. Cai, A. R. Zhang, and Y. Zhou.
Sparse group lasso: Optimal sample complexity, convergence rate, and
statistical inference.
IEEE Transactions on Information Theory, 2022.

[Campbell and Allen, 2017]
F. Campbell and G. I. Allen.
Within group variable selection through the exclusive lasso.
Electronic Journal of Statistics, 110 (2):0
4220–4257, 2017.

[Chen et al., 2012]
X. Chen, Q. Lin, S. Kim, J. G. Carbonell, and E. P. Xing.
Smoothing proximal gradient method for general structured sparse
The Annals of Applied Statistics, 60 (2):0
719–752, 2012.

[Cheng et al., 2017]
J. Cheng, T. Li, E. Levina, and J. Zhu.
High-dimensional mixed graphical models.
Journal of Computational and Graphical Statistics, 26, 2017.

[Danaher et al., 2014]
P. Danaher, P. Wang, and D. M. Witten.
The joint graphical lasso for inverse covariance estimation across
multiple classes.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 760 (2):0 373–397, 2014.

[Dedieu, 2019]
A. Dedieu.
An error bound for lasso and group lasso in high dimensions.
arXiv:1912.11398, 2019.

[Deng et al., 2013]
W. Deng, W. Yin, and Y. Zhang.
Group sparse optimization by alternating direction method.
Proceedings of the SPIE, 2013.

[Friedman et al., 2010]
J. H. Friedman, T. J. Hastie, and R. Tibshirani.
A note on the group lasso and a sparse group lasso.
arXiv: Statistics Theory, 2010.

[Gillespie et al., 2021]
M. Gillespie, B. Jassal, R. Stephan, M. Milacic, K. Rothfels, A. Senff-Ribeiro,
J. Griss, C. Sevilla, L. Matthews, C. Gong, C. Deng, T. Varusai,
E. Ragueneau, Y. Haider, B. May, V. Shamovsky, J. Weiser, T. Brunson,
N. Sanati, L. Beckman, X. Shao, A. Fabregat, K. Sidiropoulos, J. Murillo,
G. Viteri, J. Cook, S. Shorser, G. Bader, E. Demir, C. Sander, R. Haw, G. Wu,
L. Stein, H. Hermjakob, and P. D’Eustachio.
The reactome pathway knowledgebase 2022.
Nucleic Acids Research, 500 (D1):0 D687–D692,
11 2021.

[Graham et al., 1994]
R. L. Graham, D. E. Knuth, and O. Patashnik.
Concrete Mathematics: A Foundation for Computer Science.
Addison-Wesley, Reading, MA, second edition, 1994.
ISBN 0201558025 9780201558029 0201580438 9780201580433 0201142368

[Hanley and McNeil, 1982]
J. A. Hanley and B. J. McNeil.
The meaning and use of the area under a receiver operating
characteristic (roc) curve.
Radiology, 1430 (1):0 29–36, 1982.

[Huang and Zhang, 2010]
J. Huang and T. Zhang.
The benefit of group sparsity.
The Annals of Statistics, 380 (4):0
1978–2004, 2010.
ISSN 00905364, 21688966.
URL <http://www.jstor.org/stable/20744481>.

[Jacob et al., 2009]
L. Jacob, G. Obozinski, and J. Vert.
Group lasso with overlap and graph lasso.
Proceedings of the 26th Annual International Conference on
Machine Learning,ICML, 09:0 433–440, 2009.

[Jenatton et al., 2011]
R. Jenatton, J.-Y. Audibert, and F. Bach.
Structured variable selection with sparsity-inducing norms.
The Journal of Machine Learning Research, 12:0
2777–2824, 2011a.

[Jenatton et al., 2011]
R. Jenatton, J. Mairal, G. Obozinski, and F. Bach.
Proximal methods for hierarchical sparse coding.
The Journal of Machine Learning Research, 12:0
2297–2334, 2011b.

[Kanehisa et al., 2015]
M. Kanehisa, Y. Sato, M. Kawashima, M. Furumichi, and M. Tanabe.
KEGG as a reference resource for gene and protein annotation.
Nucleic Acids Research, 440 (D1):0 D457–D462,
10 2015.

[Lee and Xing, 2014]
S. Lee and E. Xing.
Screening rules for overlapping group lasso.
arXiv:1410.6880, 2014.

[Levina et al., 2008]
E. Levina, A. Rothman, and J. Zhu.
Sparse estimation of large covariance matrices via a nested lasso
The Annals of Applied Statistics, 20 (1):0
245–263, 2008.

[Liu et al., 2009]
J. Liu, S. Ji, and J. Ye.
SLEP: Sparse Learning with Efficient Projections.
Arizona State University, 2009.
URL <http://www.public.asu.edu/ jye02/Software/SLEP>.

[Loh, 2014]
P.-L. Loh.
High-dimensional statistics with systematically corrupted
University of California, Berkeley, 2014.

[Lounici et al., 2011]
K. Lounici, M. Pontil, S. V. D. Geer, and A. B. Tsybakov.
Oracle inequalities and optimal inference under group sparsity.
The Annals of Statistics, 39(4):0 2164–2204, 2011.

[Ma and Kosorok, 2010]
S. Ma and M. R. Kosorok.
Detection of gene pathways with predictive power for breast cancer
BMC bioinformatics, 110 (1):0 1–11, 2010.

[Meier et al., 2008]
L. Meier, S. Van De Geer, and P. Bühlmann.
The group lasso for logistic regression.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 700 (1):0 53–71, 2008.

[Mohan et al., 2014]
K. Mohan, P. London, M. Fazel, D. Witten, and S.-I. Lee.
Node-based learning of multiple gaussian graphical models.
The Journal of Machine Learning Research, 150
(1):0 445–488, 2014.

[Negahban et al., 2012]
S. N. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu.
A unified framework for high-dimensional analysis of $ m $-estimators
with decomposable regularizers.
Statistical science, 270 (4):0 538–557, 2012.

[Nesterov, 2013]
Y. Nesterov.
Gradient methods for minimizing composite functions.
Mathematical programming, 1400 (1):0 125–161,

[Qin et al., 2013]
Z. Qin, K.Scheinberg, and D. Goldfarb.
Efficient block-coordinate descent algorithms for the grouplasso.
Mathematical Programming Computation, 5(2), 2013.

[Ravikumar et al., 2009]
P. Ravikumar, J. Lafferty, H. Liu, and L. Wasserman.
Sparse additive models.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 710 (5):0 1009–1030, 2009.

[Schaefer et al., 2008]
C. Schaefer, K. Anthony, S. Krupa, J. Buchoff, M. Day, T. Hannay, and
K. Buetow.
Pid: The pathway interaction database.
Nature Precedings, 3, 08 2008.

[Schroeder et al., 2021]
M. Schroeder, B. Haibe-Kains, A. Culhane, C. Sotiriou, G. Bontempi, and
J. Quackenbush.
breastCancerNKI: Genexpression dataset published by van't Veer
et al. [2002] and van de Vijver et al. [2002] (NKI)., 2021.
URL <http://compbio.dfci.harvard.edu/>.
R package version 1.32.0.

[Slenter et al., 2017]
D. N. Slenter, M. Kutmon, K. Hanspers, A. Riutta, J. Windsor, N. Nunes,
J. Mélius, E. Cirillo, S. L. Coort, D. Digles, F. Ehrhart, P. Giesbertz,
M. Kalafati, M. Martens, R. Miller, K. Nishida, L. Rieswijk, A. Waagmeester,
L. M. T. Eijssen, C. T. Evelo, A. R. Pico, and E. L. Willighagen.
WikiPathways: a multifaceted pathway database bridging metabolomics
to other omics research.
Nucleic Acids Research, 460 (D1):0 D661–D667,
11 2017.
ISSN 0305-1048.

[Subramanian et al., 2005]
A. Subramanian, P. Tamayo, V. K. Mootha, S. Mukherjee, B. L. Ebert, M. A.
Gillette, A. Paulovich, S. L. Pomeroy, T. R. Golub, E. S. Lander, et al.
Gene set enrichment analysis: a knowledge-based approach for
interpreting genome-wide expression profiles.
Proceedings of the National Academy of Sciences, 1020
(43):0 15545–15550, 2005.

[Tank et al., 2017]
A. Tank, E. B. Fox, and A. Shojaie.
An efficient admm algorithm for structural break detection in
multivariate time series.
arXiv preprint arXiv:1711.08392, 2017.

[Tarzanagh and Michailidis, 2018]
D. A. Tarzanagh and G. Michailidis.
Estimation of graphical models through structured norm minimization.
Journal of machine learning research, 180 (1), 2018.

[Tibshirani, 1996]
R. Tibshirani.
Regression shrinkage and selection via the lasso.
Journal of the Royal Statistical Society: Series B
(Methodological), 580 (1):0 267–288, 1996.

[Van De Vijver et al., 2002]
M. J. Van De Vijver, Y. D. He, L. J. Van't Veer, H. Dai, A. A. Hart, D. W.
Voskuil, G. J. Schreiber, J. L. Peterse, C. Roberts, M. J. Marton, et al.
A gene-expression signature as a predictor of survival in breast
New England Journal of Medicine, 3470 (25):0
1999–2009, 2002.

[Wainwright, 2019]
M. J. Wainwright.
High-dimensional statistics: A non-asymptotic viewpoint,
volume 48.
Cambridge University Press, 2019.

[Xiang et al., 2015]
S. Xiang, X. Shen, and J. Ye.
Efficient nonconvex sparse group feature selection via continuous and
discrete optimization.
Artificial Intelligence, 224:0 28–50, 2015.
ISSN 0004-3702.

[Yan and Bien, 2017]
X. Yan and J. Bien.
Hierarchical sparse modeling: A choice of two group lasso
Statistical Science, 320 (4):0 531–560, 2017.

[Yang and Peng, 2020]
J. Yang and J. Peng.
Estimating time-varying graphical models.
Journal of Computational and Graphical Statistics, 290
(1):0 191–202, 2020.

[Yang and Zou, 2015]
Y. Yang and H. Zou.
A fast unified algorithm for solving group-lasso penalize learning
Statistics and Computing, 250 (6):0
1129–1141, 2015.

[Yu and Bien, 2017]
G. Yu and J. Bien.
Learning local dependence in ordered data.
The Journal of Machine Learning Research, 180
(1):0 1354–1413, 2017.

[Yuan et al., 2011]
L. Yuan, J. Liu, and J. Ye.
Efficient methods for overlapping group lasso.
Advances in Neural Information Process Systems, pages
352–360, 2011.

[Yuan and Lin, 2006]
M. Yuan and Y. Lin.
Model selection and estimation in regression with grouped variables.
Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 680 (1):0 49–67, 2006.

[Zhao et al., 2009]
P. Zhao, G. Rocha, and B. Yu.
The composite absolute penalties family for grouped and hierarchical
variable selection.
Annals of Statistics, 37(6A):0 3468–3497, 2009.

§ NOTATION SUMMARY

Major notations used in this paper.

$[m]$     group index set $\{1,...,m\}$

$[n]$     sample index set  $ \{1,...,n\}$

$[p]$     parameter index set   $\{1,...,p\}$

$G_g$     index set  of $g^{th}$ group

$G_S$     collection of non-zero groups, $\mathop{\bigcup}_{g\in S(\beta)}G_g $

$G_{\overline{S}}$      $\mathop{\bigcup}_{g\in \overline{S(\beta)}}G_g $

$\beta_j$     the $j^{th}$ element of $\beta$

$\beta_{G_g}$     subvector of $\beta$ indexed by $G_g$

$\beta_{M(S)}$     projection of $\beta$ onto $M(S)$

$A_{,T}$     sub-matrix  consisting of the columns indexed by  T

$H$      a diagonal matrix, $diag(\frac{1}{h_1},\cdots,\frac{1}{h_p})$

$\mathbf{G}$      group structure matrix, $\mathbf{G}_{gj} = 1$ iff $\beta_j \in G_g$

$d_g$     group size,  $d_g = \sum_{j\in[p]}\mathbf{G}_{gj}$

$d_{\max}$      maximum group size, $d_{\max} = \max_{g \in [m]}d_g$

$h_j$     overlap degree, $h_j = \sum_{g \in [m]}\mathbf{G}_{gj}$

$h_{\max}^g$      maximum overlap degree in $G_g$, $h_{\max}^g= \max_{j \in G_g}h_j$

$h_{\min}^{g}$     minimum overlap degree in $G_g,$ $\min_{j \in G_g}h_j$

$h_{\max}$     maximum overlap degree, $h_{\max} = \max_{j \in [p]}h_j$

$\mathcal{h}_{\mathcal{g}}$    overlap degree of $\mathcal{G}_\mathcal{g},$ $h_{\text{\{}j|j \in \mathcal{G}_{\mathcal{g}}\text{\}}}$

$\sigma$       parameter in the sub-Gaussian distribution

$s_g$            number of non-zero groups  $|S|$

$\overline{s_g}$     number of groups in the argument group support set $|\overline{S}|$

$\kappa$      parameter controls convexity

$\phi(\beta)$       group lasso norm, $\sum\limits_{g \in [m]}w_g \left\|\beta_{G_g}\right\|_2,$

$\phi^{\ast}(\beta)$     dual norm of $\phi(\beta),$ $\max\limits_{g\in[m]}\frac{1}{w_g}\left\|(H\beta)_{G_g}\right\|_2$

$F(\mathcal{g}) \subseteq [m]$       overlapping groups which include the variables in $\mathcal{G}_\mathcal{g}$

$F^{-1}(g) \subseteq [\mathcal{m}]$        non-overlapping groups that were partitioned from $G_g$

$||\beta_{\{G,w\}}||_{q_1,q_2}$     $\ell_{q_1,q_2}$ norm, $ \left\{ \sum\limits_{g \in [m]} w_g\left( \sum\limits_{j \in G_g}|\beta_j|^{q_2}\right)^{\frac{q_1}{q_2}}\right\}^{\frac{1}{q_1}} $

$\textit{supp}(\beta)$     support set, $\{j\in\{1,\cdots,p\}|\beta_j\neq 0\}$

$S(\beta)$      group support set, $\left\{g\in \{1,\cdots,m\}|G_g \cap \textit{supp}(\beta)\neq
\varnothing\right\}$

$\overline{S(\beta)}$      $\{g=\{1,\cdots,m\}|G_g\cap
{G_{S(\beta)}\neq \varnothing}\}$

$M(S)$    $\left\{\beta\in{\mathbb{R}^p}|\beta_j=0 \text{ for all } j \in (G_{S})^c\right\}$

$M^{\perp}(S)$     $\left\{\beta\in \mathbb{R}^p |\beta_j=0 \text{ for all } j\in G_{S}\right\}$

§ ADDITIONAL THEORETICAL RESULTS

To begin with, we introduce our proposed upper bound for the dual norm of the overlapping group lasso.

The sharp upper bound for $\phi^{\ast}$ (the dual norm of overlapping group lasso penalty in  (<ref>)) is

\begin{equation}
\max\limits_{g\in[m]}\frac{1}{w_g}\left\|(H\beta)_{G_g}\right\|_2,
\end{equation}

where $H$ is a diagonal matrix with diagonals $(\frac{1}{h_1},\cdots,\frac{1}{h_p})$.

Developing the upper bound of dual norm of overlapping group lasso regularizer is an essential step  as the dual norm affects the choice of $\lambda_n$ and ultimately affects the results on the estimation error bound.

Under model (<ref>), we assume

* (Sub-Gaussian noises) The coordinates of $\varepsilon$ are i.i.d zero mean sub-Gaussian random variable denote with parameter $\sigma$, which means that there exist $\sigma > 0$ such that

$$ E[e^{t\varepsilon})] \leqslant \frac{e^{\sigma^2 t^2}}{2}, \hspace{0.2cm} \text{for all} \hspace{0.2cm} t \in \mathbb{R}.$$

* (Group normalization condition) $ \sqrt{\gamma_{\max}(\frac{{X_{G_g}}^TX_{G_g}}{n} })\leqslant c$ for some constant c.

* (Restricted strong convexity condition) For some $\kappa >0$,
$$\frac{\left\|X\left(\bar{\beta}-\beta^{\ast}\right)\right\|_2^2}{n}\geqslant \kappa\left\|\bar{\beta}-\beta^{\ast}\right\|_2^2, \hspace{0.2cm}  \text{for all}\hspace{0.2cm} \bar{\beta}\in\left\{\beta \mid \phi \left(\left(\beta-\beta^{\ast}\right)_{M^{\perp}(\overline{S})}\right) \leqslant 3\phi\left(\left(\beta-\beta^{\ast}\right)_{M(\overline{S})}\right)\right\}.$$

Remark: The assumption requires an upper bound for the quadratic form associated with each group. This type of assumption is commonly used for developing the upper estimation error bound for non-overlapping group lasso  [Lounici et al., 2011, Huang and Zhang, 2010, Dedieu, 2019, Negahban et al., 2012, Wainwright, 2019]. Additionally, the restricted curvature conditions that has been well discussed by Wainwright, 2019. The curvature $\kappa$ in Assumption <ref> is a parameter measure the convexity. Generally speaking, the restricted curvature conditions states the loss function is locally strongly convex in a neighborhood of ground truth, and thus guarantees that a small distance between the estimate and the true parameter implies the closeness in the loss function.  However, such a strong convexity condition cannot hold in the high-dimensional setting. So we focus on a restrictive set of the estimates. Restricted curvature conditions are milder that the group-based RIP conditions used in [Huang and Zhang, 2010, Dedieu, 2019] which require that all submatrices up to a certain size are close to isometries [Wainwright, 2019]. Based on Assumption <ref>, Theorem <ref> gives $\ell_2$ norm estimation upper error bound for overlapping group lasso.

Define $h_{\min}^{g} = \min\limits_{j \in G_g}h_j$, $d_{\max} = \max\limits_{g \in [m]}d_g$, and $\dcal_{\max} = \max\limits_{\gcal \in [\mcal]}\dcal_g$. Suppose Assumption <ref> holds, for any $\delta \in [0,1]$,

* with $\lambda_n =  \frac{8c \sigma}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}\sqrt{\frac{d_{\max}\log{5}}{n}+
\frac{\log{m}}{n}+\delta}$, the following  bound hold for $\hat{\beta}^G$ in (<ref>)

\begin{equation}
\label{eq:el2bound}
\left\|\hat{\beta}^{G}-\beta^{\ast}\right\|^2_2\lesssim\frac{ \sigma^2}{\kappa^2}\cdot\frac{\left(\sum\limits_{g\in\overline{S}}{w_g}^2\right)\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}
\cdot\left(\frac{d_{\max}{\log{5}}}{n}+\frac{\log{m}}{n}+\delta\right).
\end{equation}

with probability at least $1-e^{-2n\delta}$.

* with $
\lambda_n =  \frac{8c\sigma}{\min\limits_{g\in[m]} \wcal_g^2}\sqrt{\frac{\dcal_{\max}\log{5}}{n}+
\frac{\log{m}}{n}+\delta}$, the following  bound hold for $\hat{\beta}^{\Gcal}$ in (<ref>)

\begin{equation}
\label{xxq1}
\left\|\hat{\beta}^{\mathcal{G}}-\beta^{\ast}\right\|_2^2 \lesssim\frac{ \sigma^2}{\kappa^2}\cdot\frac{\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{w}_{\mathcal{g}}}^2}{\min\limits_{\mathcal{g}\in[\mathcal{m}]}\left(w_\mathcal{g}^2 \right)}
\cdot\left(\frac{\mathcal{d}_{\max}{\log{5}}}{n}+\frac{\log{\mathcal{m}}}{n}+\delta\right).
\end{equation}

Following the framework in [Negahban et al., 2012, Wainwright, 2019], we further study the applicability of  the restricted curvature conditions in terms of random design matrix.
Given a group structure $G$, Theorem <ref> is developed based on the assumption that the fixed design matrix X satisfies the restricted curvature condition.  In practice, it is difficult to verify that a given design matrix $X$ satisfies this condition. Indeed, developing methods to “certify” design matrices in this way is one line of on-going research [Wainwright, 2019]. However, it is possible to give high-probability results based on following assumptions.

Under Assumption <ref>, we have

* With probability at least $1 - e^{-c'n}$, $\max_{g\in [m]}\sqrt{ \gamma_{\max}(\frac{X_{G_g}^TX_{G_g}}{n}) } \leqslant c $ for some constants $c,c'>0$, as long as $\log m = o(n)$.

* The restricted strong convexity condition, which is

$$\frac{\left\|X\left(\bar{\beta}-\beta^{\ast}\right)\right\|_2^2}{n}\geqslant \kappa\left\|\bar{\beta}-\beta^{\ast}\right\|_2^2, \hspace{0.2cm}  \text{for all}\hspace{0.2cm} \bar{\beta}\in\left\{\beta \mid \phi \left(\left(\beta-\beta^{\ast}\right)_{M^{\perp}(\overline{S})}\right) \leqslant 3\phi\left(\left(\beta-\beta^{\ast}\right)_{M(\overline{S})}\right)\right\}.$$

hold with probability at least $1- \frac{e^{-\frac{n}{32}}}{1-e^{-\frac{n}{64}}}$ for some constant $\kappa > 0$.

§ PROOFS

§.§ Proof of Theorem <ref>

If there exists a norm $||\cdot_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2}$  such that  (<ref>) hold, then for any $\mathcal{g} \in [\mathcal{m}]$,  there exists a $\tilde{g} \in [|\tilde{G}|]$ such that $\mathcal{G}_{\mathcal{g}} \subseteq \tilde{G}_{\tilde{g}}$.

If there exists a norm $||\cdot_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2}$ such that (<ref>) hold, then for any $\tilde{g} \in [|\tilde{G}|]$,  there exists a $\mathcal{g} \in [\mathcal{m}]$ such that $\tilde{G}_{\tilde{g}} = \mathcal{G}_{\mathcal{g}}$.

Based on Lemma <ref> and Lemma <ref>, if there exists $||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2}$ which satisfies $\eqref{twocondi}$, then $\tilde{G} = \mathcal{G}$. Therefore, the difference in between $||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2}$ and our proposed norm could be only introduced by different weights or different values of either $q_1$ or $q_2$.

For any $\beta$ with non-zero elements only in $\mathcal{g}$-th group $\mathcal{G}_\mathcal{g}$,

\begin{equation}
\label{eq:equalnorm}
\sum\limits_{g\in [m]}w_g||\beta_{G_g}||_2 = \left( \sum_{g\in F(\mathcal{g}) }w_g\right)||\beta_{\mathcal{G}_\mathcal{g}}||_2 \leqslant  ||\beta_{\{\mathcal{G},\tilde{w}\}}||_{q_1,q_2} \leqslant \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2.
\end{equation}

It implies that $ (\tilde{w}_{\mathcal{g}}||\beta_{\mathcal{G}_{\mathcal{g}}}||_{q_2}^{q_1})^{\frac{1}{q_1}}= \mathcal{w}_{\mathcal{g}}||\beta_{\mathcal{G}_{\mathcal{g}}}||_2$. By setting one element in $\mathcal{G}_\mathcal{g}$ to 1, and other elements to 0, we have $\tilde{w}_{\mathcal{g}} = \mathcal{w}_{\mathcal{g}}$. Because this hold for any group in $\mathcal{G}$, $\tilde{w} = \mathcal{w}$.

From (<ref>), we have that $(\mathcal{w}_{\mathcal{g}}||\beta_{\mathcal{G}_{\mathcal{g}}}||_{q_2}^{q_1})^{\frac{1}{q_1}} = \mathcal{w}_{\mathcal{g}}||\beta_{\mathcal{G}_{\mathcal{g}}}||_2  $ for  any $\beta$ with non-zero elements only in $\mathcal{G}_{\mathcal{g}}$. It implies that $q_1 = 1,q_2 = 2$. Therefore, the existed norm $||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2} = \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2$, which does not meet the second condition in $\eqref{twocondi}$.

§.§.§ Proof of Lemma <ref>

Since  $\tilde{G} \in \mathbb{G},$ for an arbitrary $\mathcal{g} \in [\mathcal{m}]$, if $\mathcal{G}_\mathcal{g} \nsubseteq \tilde{G}_{\tilde{g}}$ for any $\tilde{g}$, then we can find the smallest set $T$, such that

$$\mathcal{G}_{\mathcal{g}} \subseteq \bigcup\limits_{\tilde{g} \in T}\tilde{G}_{\tilde{g}}.$$

Denote $T = \{t_1,t_2,\cdots,t_{|T|}\}$, choose $\beta_{j} \in (\mathcal{G}_{\mathcal{g}} \bigcap \tilde{G}_{t_1}) $ and  $\beta_{k} \in (\mathcal{G}_{\mathcal{g}} \bigcap \tilde{G}_{t_2}) $.  Since  $\beta_j$ and $\beta_k$ are both in $\mathcal{G}_{\mathcal{g}}$, if an original group contains $\beta_j$, then this original group also contains $\beta_k$. Consider $\beta$ where $\beta_j$ and $\beta_k$ are the only non-zero elements,  we have

\begin{equation*}
\label{fcondi}
\begin{aligned}
\sum\limits_{g\in [m]}w_g||\beta_{G_g}||_2 &= \left( \sum_{\{g|\beta_j \in G_g\} }w_g\right)\sqrt{\beta_j^2 + \beta_k^2}
\leqslant ||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2} \\&\leqslant \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2 =  \left( \sum_{\{g|\beta_j \in G_g\} }w_g\right)\sqrt{\beta_j^2 + \beta_k^2},
\end{aligned}
\end{equation*}

which is equivalent to

$$||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2} = \left(\tilde{w}_{t_1}(|\beta_j|)^{q_1} + \tilde{w}_{t_2}(|\beta_k|)^{q_1}\right)^{\frac{1}{q_1}}  = \left( \sum_{\{g|\beta_j \in G_g\} }w_g\right)\sqrt{\beta_j^2 + \beta_k^2},$$
for any  $0 \leqslant q_1,q_2 \leqslant \infty.$ However, by setting
\beta_j = \beta_k = 1, \beta_{\{[p]\backslash\{j,k\}\}} = 0 &  \text{if $(w_{t_1} + w_{t_2})^{\frac{1}{q_1}} \neq \sqrt{2}\left( \sum_{\{g|\beta_j \in G_g\} }w_g\right)$ } \\
\beta_j = 2, \beta_k = 1, \beta_{\{[p]\backslash\{j,k\}\}} = 0 &  \text{if $(w_{t_1}+ w_{t_2})^{\frac{1}{q_1}} = \sqrt{2}\left( \sum_{\{g|\beta_j \in G_g\} }w_g\right)$ }
\end{cases},$$
we have a contradiction. Therefore, we show that if there exists a norm $||\cdot_{\{\tilde{G},w\}}||_{q_1,q_2},$ then each group in $\tilde{G}$ is a union of groups in $\mathcal{G}$.

§.§.§ Proof of Lemma <ref>

Lemma <ref> implies that each group in $\tilde{G}$ is a union of groups in $\mathcal{G}$. Without loss of generality, suppose that for $\tilde{g} \in [|\tilde{G}|]$,  there exits $V \subseteq [\mathcal{m}]$, such that $\tilde{G}_{\tilde{g}} = \bigcup\limits_{\mathcal{g} \in V}\mathcal{G}_{\mathcal{g}}$ and $|V| > 1$.   Denote $V = \{v_1,\cdots,v_{|V|}\},$ then one of the following cases must happen

case 1: $\nexists a \in [m]$, s.t. $(\mathcal{G}_{\mathcal{v_1}} \bigcup \mathcal{G}_{\mathcal{v_2}}) \subseteq G_a$.

case 2: $\exists a \in [m]$, s.t.  $(\mathcal{G}_{\mathcal{v_1}} \bigcup \mathcal{G}_{\mathcal{v_2}}) \subseteq G_a$.

Under case 1, if only $\mathcal{G}_{\mathcal{v_1}}$ and  $\mathcal{G}_{\mathcal{v_2}}$ have non-zero values in $\beta$,  we have

\begin{equation}
\label{wcondi}
\begin{aligned}
\sum\limits_{g\in [m]}||\beta_{G_g}||_2 &= \left( \sum_{g\in F(\mathcal{v}_1) }w_g\right)||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_2 +\left( \sum_{g\in F(\mathcal{v}_2) }w_g\right)|| \beta_{\mathcal{G}_{\mathcal{v_2}}}||_2
\leqslant ||\beta_{\{\tilde{G},\tilde{w}\}}||_{q_1,q_2} \\&\leqslant \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2 =  \mathcal{w}_{\mathcal{v_1}}||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_2 +\mathcal{w}_{\mathcal{v_2}}||\beta_{\mathcal{G}_{\mathcal{v_2}}}||_2,
\end{aligned}
\end{equation}

which is equivalent to

$$\mathcal{w}_{\mathcal{v_1}}\sqrt{\beta_{\mathcal{G}_{\mathcal{v_1}}}^2} +\mathcal{w}_{\mathcal{v_2}}\sqrt{ \beta_{\mathcal{G}_{\mathcal{v_2}}}^2} = \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}}\left( \sum\limits_{j \in \tilde{G}_{\tilde{g}}}|\beta_j|^{q_2}\right)^{\frac{1}{q_2}} = \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}}\left( \sum\limits_{j \in \{\mathcal{G}_{\mathcal{v_1}}\bigcup\mathcal{G}_{\mathcal{v_2}}\}}|\beta_j|^{q_2}\right)^{\frac{1}{q_2}}

This equation does not hold by picking one specific $j \in \mathcal{G}_{\mathcal{v_1}}$, and another specific $k \in \mathcal{G}_{\mathcal{v_2}}$, and setting
\beta_j = \beta_k = 1,\beta_{\{[p]\backslash\{j,k\}\}} = 0 &  \text{if $\mathcal{w}_{\mathcal{v_1}} + \mathcal{w}_{\mathcal{v_2}} \neq  \tilde{w}_{\tilde{g}}^{\frac{1}{q_2}}\cdot 2^{\frac{1}{q_2}}$ } \\
\beta_j = 2, \beta_k = 1, \beta_{\{[p]\backslash\{j,k\}\}}=0 &  \text{if $\mathcal{w}_{\mathcal{v_1}} + \mathcal{w}_{\mathcal{v_2}} =  \tilde{w}_{\tilde{g}}^{\frac{1}{q_2}}\cdot 2^{\frac{1}{q_2}}$ }
\end{cases}.$$
Therefore, $|V| > 1$ cannot happen.

Under case 2,  suppose that $\beta$ only has one $1$ at an element in $ \mathcal{G}_{\mathcal{v_1}}$ and has $0$ elsewhere , we have
$$\sum\limits_{g\in [m]}w_g||\beta_{G_g}||_2 = \left( \sum_{g\in F(\mathcal{v}_1) }w_g\right) \leqslant  \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}} \leqslant \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2 = \mathcal{w}_{\mathcal{v_1}}, $$
that is $ \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}}  = \mathcal{w}_{\mathcal{v_1}}, \text{for all} \hspace{0.2cm} q_2$.

Suppose that $\beta$ only has one $1$ at an element in $ \mathcal{G}_{\mathcal{v_2}}$ and has $0$ elsewhere, we have
$$\sum\limits_{g\in [m]}w_g||\beta_{G_g}||_2 = \left( \sum_{g\in F(\mathcal{v}_2) }w_g\right) \leqslant  \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}} \leqslant \sum\limits_{\mathcal{g} \in [\mathcal{m}]}\mathcal{w}_\mathcal{g}||\beta_{\mathcal{G}_\mathcal{g}}||_2 = \mathcal{w}_{\mathcal{v_2}}, $$
that is $ \tilde{w}_{\tilde{g}}^{\frac{1}{q_1}}  = \mathcal{w}_{\mathcal{v_2}}, \text{for all} \hspace{0.2cm} q_2$.

Therefore, such $w$ does not exist if $\mathcal{w}_{\mathcal{v_1}} \neq \mathcal{w}_{\mathcal{v_2}}$. Suppose that $\mathcal{w}_{\mathcal{v_1}} =\mathcal{w}_{\mathcal{v_2}} =  w_{\tilde{g}}^{\frac{1}{q_1}}, $ then for any $\beta$ that has non-zero values only in $\mathcal{G}_{\mathcal{v_1}},$ we have $w_{\tilde{g}}^{\frac{1}{q_1}}||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_2 = (w_{\tilde{g}}||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_{q_2}^{q_1})^{\frac{1}{q_1}}.$ Therefore, if there is norm satisfies (<ref>), it must be a $\ell_1/\ell_2$ norm.

Because  $\mathcal{G}_{\mathcal{v_1}}$ and  $\mathcal{G}_{\mathcal{v_2}}$ are two different groups after-partition, if one original group contains variables in  $\mathcal{G}_{\mathcal{v_1}}$, then this group must contain all variables in $\mathcal{G}_{\mathcal{v_1}}$. Moreover, for one original group contains all variables in $\mathcal{G}_{\mathcal{v_1}}$, such group either containing none variable in  $\mathcal{G}_{\mathcal{v_2}}$ or containing all variables in $\mathcal{G}_{\mathcal{v_2}}$. Thus, we can define a partition A,B,C,D of $[m]$, where

g \in A &  \text{if $\mathcal{G}_{\mathcal{v_1}} \cup \mathcal{G}_{\mathcal{v_2}} \subseteq G_g$} \\
g \in B &  \text{if $\mathcal{G}_{\mathcal{v_1}} \subseteq G_g, \mathcal{G}_{\mathcal{v_2}} \cap  G_g = \phi$}\\
g \in C &  \text{if $\mathcal{G}_{\mathcal{v_2}} \subseteq G_g, \mathcal{G}_{\mathcal{v_1}} \cap  G_g = \phi$} \\
g \in D &  \text{if $\mathcal{G}_{\mathcal{v_1}} \cap  G_g = \phi, \mathcal{G}_{\mathcal{v_2}} \cap  G_g = \phi$}
\end{cases}.$$

Since  $\mathcal{G}_{\mathcal{v_1}}$ and  $\mathcal{G}_{\mathcal{v_2}}$ are two different groups after-partition, we know that $B \cap C \neq \phi$. Since $\mathcal{w}_{\mathcal{v_1}} = \sum\limits_{g \in A\cup B}w_g =\mathcal{w}_{\mathcal{v_2}} =  \sum\limits_{g \in A\cup C}w_g = w_{\tilde{g}}$, we know that both $B \neq \phi, C \neq \phi$ and $\sum\limits_{g \in  B}w_g = \sum\limits_{g \in C}w_g$. Suppose that $\beta$ has non-zero values only in $\mathcal{G}_{\mathcal{v_1}}$ and  $\mathcal{G}_{\mathcal{v_2}}$, we have

\begin{equation*}
\begin{aligned}
\sum\limits_{g\in [m]}w_g||\beta_{G_g}||_2 & =
\sum\limits_{g\in A}w_g||\beta_{\mathcal{G}_{\mathcal{v_1}}}\cup \beta_{\mathcal{G}_{\mathcal{v_2}}}||_2 + \sum\limits_{g\in B}w_g||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_2 +
\sum\limits_{g\in C}w_g|| \beta_{\mathcal{G}_{\mathcal{v_2}}}||_2\\
& =  \sum\limits_{g\in A}w_g||\beta_{\mathcal{G}_{\mathcal{v_1}}}\cup \beta_{\mathcal{G}_{\mathcal{v_2}}}||_2 +
(||\beta_{\mathcal{G}_{\mathcal{v_1}}}||_2 + ||\beta_{\mathcal{G}_{\mathcal{v_2}}}||_2)\sum\limits_{g\in B}w_g \\
&> \tilde{w}_{\tilde{g}}||\beta_{\mathcal{G}_{\mathcal{v_1}}}\cup \beta_{\mathcal{G}_{\mathcal{v_2}}}||_2 = ||\beta_{\{\tilde{G},\tilde{w}\}}||_{1,2},
\end{aligned}
\end{equation*}

which is a contradiction. Therefore, in both cases, we cannot have   $|V| > 1$ which means that there exists a $\mathcal{g} \in [\mathcal{m}]$ such that $\tilde{G}_{\tilde{g}} = \mathcal{G}_{\mathcal{g}}.$

§.§ Proof of Theorem <ref>

We first focus on the bound of $\hat{\beta}^G$. Given a group structure $G$ and a fixed design matrix $X$ satisfies  Assumption <ref>, by taking an appropriate $\lambda_n$,  Theorem <ref> implies that (<ref>) and (<ref>) hold with probability at least $1-e^{-2n\delta}$.

Under Assumption <ref>, Theorem <ref> implies that Assumption <ref> holds with probability at least $1-e^{-c_2n\delta^2}-\frac{e^{-\frac{n}{32}}}{1-e^{\frac{n}{64}}}$, for some positive constant $c_2$.

Taking account of both theorems together, we have Assumption <ref>, (<ref>) and (<ref>) hold with probability at least  $1-e^{-c_2n}- e^{-2n\delta}-\frac{e^{-\frac{n}{32}}}{1-e^{\frac{n}{64}}} \ge 1-e^{-c'n\delta}$ for some suitable constant $c'$.

The bound for $\hat{\beta}^{\Gcal}$ is directly available by noticing that it is a group lasso estimator with group $\Gcal$ and $\wcal$.

§.§ Proof of Corollary <ref>

Recall that

$$F(\mathcal{g}) = \{g: g\in [m], \Gcal_{\gcal} \subset G_g \} ~~~~\text{and}~~~~F^{-1}(g) = \{\gcal: \gcal\in [\mcal], \Gcal_{\gcal} \subset G_g\},

futher define

$$ F^{-1}(S) = \{\gcal \mid \gcal \in F^{-1}(g), g \in S\}.$$

By assuming $d \asymp \dcal$ and $m \asymp \mcal$, we have $\left(\frac{\mathcal{d}_{\max}{\log{5}}}{n}+\frac{\log{\mathcal{m}}}{n}+\delta\right) \asymp \left(\frac{d_{\max}{\log{5}}}{n}+\frac{\log{m}}{n}+\delta\right)$.

With the setting $ \mathcal{w}_\mathcal{g} =  \sum\limits_{g\in F(\mathcal{g}) }w_g$, by Cauchy–Schwartz inequality, we have

\mathcal{w}_\mathcal{g}^2 = \left(\sum\limits_{g\in F(\mathcal{g}) }w_g \right)^2
\leqslant \mathcal{h}_\mathcal{g}(\sum\limits_{g\in F(\mathcal{g})}w_g^2).

\begin{align*}
& \sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{w}_{\mathcal{g}}}^2
\leqslant \sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{h}_\mathcal{g}(\sum\limits_{g\in F(\mathcal{g})}w_g^2)}
\leqslant h_{\max}(\mathbf{G_{\overline{S}}})\left(\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\sum\limits_{g\in F(\mathcal{g})}w_g^2} \right).
\end{align*}

Now we want to show that  $\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\sum\limits_{g\in F(\mathcal{g})}w_g^2}  \leqslant \sum\limits_{g \in \overline{S}} k_g w_g^2$.  First, the $g$-th group is partitioned into $k_g$ non-overlapping groups. For any  $\gcal \in F^{-1}(g)$, if $\gcal \in F^{-1}(S)$, then one $w_g^2$ is added to the left-hand side. Therefore, no more than $k_g w_g^2$ would be added to $\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\sum\limits_{g\in F(\mathcal{g})}w_g^2}$ based on the $g$-th group. Since
$$\{g | g\in F(\mathcal{g}) \hspace{0.2cm}\text{and}\hspace{0.2cm} \mathcal{g}\in F^{-1}(S)\} = \overline{S},$$

we have

\begin{align*}
h_{\max}(\mathbf{G_{\overline{S}}})\left(\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\sum\limits_{g\in F(\mathcal{g})}w_g^2} \right)\leqslant h_{\max}(\mathbf{G_{\overline{S}}})\sum\limits_{g \in \overline{S}} k_g w_g^2\leqslant h_{\max}(\mathbf{G_{\overline{S}}})K\sum\limits_{g \in \overline{S}} w_g^2
\end{align*}

where $K = \max\limits_{g \in \overline{S}}k_g$. On the other hand, we have

\begin{align*}
{\min\limits_{\mathcal{g}\in[m]}\left(\mathcal{w}_\mathcal{g}^2 \right)} &	= \min\limits_{\mathcal{g}\in[\mathcal{m}]} \left(\sum\limits_{g\in F(\mathcal{g}) }w_g \right)^2\geqslant \min\limits_{\mathcal{g}\in[\mathcal{m}]} \left(\sum\limits_{g\in F(\mathcal{g}) }\min\limits_{g\in[m]}\{w_g\} \right)^2 \\
& \geqslant \min\limits_{\mathcal{g}\in[\mathcal{m}]} \left(h_{\min}^{g}\min\limits_{g\in[m]}\{w_g\} \right)^2 = \left(h_{\min}^{g}\min\limits_{g\in[m]}\{w_g\} \right)^2
\geqslant \min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right).
\end{align*}

$$ \frac{\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{w}_{\mathcal{g}}}^2}{\min\limits_{\mathcal{g}\in[\mathcal{m}]}\left(w_\mathcal{g}^2 \right)} \leqslant \frac{K\left(\sum\limits_{g\in\overline{S}}{w_g}^2\right)\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}.$$

\frac{\sum\limits_{\mathcal{g}\in F^{-1}(S) }{\mathcal{w}_{\mathcal{g}}}^2}{\min\limits_{\mathcal{g}\in[\mathcal{m}]}\left(w_\mathcal{g}^2 \right)}
\cdot\left(\frac{\mathcal{d}_{\max}{\log{5}}}{n}+\frac{\log{\mathcal{m}}}{n}+\delta\right) \lesssim\frac{\left(\sum\limits_{g\in\overline{S}}{w_g}^2\right)\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}
\cdot\left(\frac{d_{\max}{\log{5}}}{n}+\frac{\log{m}}{n}+\delta\right).

§.§ Proof of Proposition <ref>

Let $H_{G_g}$ be the sub-matrix of $H$ consisting of the columns indexed by $G_g$. Let  $u_{G_g}$, $v_{G_g}$ be the sub-vectors of $u,v$ indexed by $G_g$ respectively. Given two vectors $u, v \in \mathbb{R}^p$, we have

\begin{equation*}
\begin{aligned}
\phi^{\ast}(v) & =\sup\limits_{\phi(u)\leqslant 1}\left\{u^Tv\right\}
=\sup\limits_{\phi(u)\leqslant 1}\left\{u_1v_1+u_2v_2+\cdots+u_pv_p\right\}\\
&  =\sup\limits_{\phi(u)\leqslant 1}\left\{ \frac{v_1}{h_1}\cdot{h_1}\cdot{u_1} + \cdots+ \frac{v_p}{h_p}\cdot{h_p}\cdot{u_p}    \right\}\\
& =\sup\limits_{\phi(u)\leqslant 1}\left\{  \sum\limits_{g=1}^{m} \left(H_{G_g}v_{G_g}\right)^T u_{G_g}   \right\}
=\sup\limits_{\phi(u)\leqslant 1}\left\{  \sum\limits_{g=1}^{m} \frac{\left((Hv)_{G_g}\right)}{w_g}\cdot w_g \cdot u_{G_g}   \right\}\\
&\leqslant \sup\limits_{\phi(u)\leqslant 1}\left\{  \sum\limits_{g=1}^{m} \frac{\left\|(Hv)_{G_g}\right\|_2}{w_g} \cdot \left\|w_g{u_{G_g}}\right\|_2 \right\}
\leqslant \left( \max\limits_{g\in[m]}\frac{1}{w_g}\cdot\left\|(Hv)_{G_g}\right\|_2\right)\cdot\phi(u)\\
& \leqslant \max\limits_{g\in[m]}\frac{1}{w_g}\cdot\left\|(Hv)_{G_g}\right\|_2,
\end{aligned}
\end{equation*}

where the first inequality is achieved by using Cauchy's inequality.

Let $g_0 =  \argmax\limits_{g\in[m]}{\frac{1}{w_g}\left\|\left(Hv\right)_{G_g}\right\|_2}$, and suppose that $h^{g_0}_{\max} = 1$. Define $u\in \mathbb{R}^p$ as

\begin{equation*}
0\hspace{0.2cm}\textit{for}\hspace{0.2cm} j\notin G_{g_0}\\
\frac{1}{w_{g_0}}\cdot \frac{v_j}{{h_j}^2}\cdot\frac{1}{\left\|\left(Hv\right)_{G_{g_0}}\right\|_2}\hspace{0.2cm}\textit{for}\hspace{0.2cm} j\in G_{g_0},
\end{array}\right.
\end{equation*}

then we have

\begin{equation*}
\begin{aligned}
\phi\left(u\right)  &=\sum\limits_{g=1}^m{w_g}\left\|u_{G_g}\right\|_2
&  =\frac{1}{\left\|\left(Hv\right)_{G_{g_0}}\right\|_2}\sqrt{\sum\limits_{j\in{G_{g_0}}}\frac{{v_j}^2}{{h_j}^2}}= 1,
\end{aligned}
\end{equation*}

where the last inequality holds due to the fact that $h_j = 1$ for any $j \in G_{g_0}$, and we also have

\begin{equation*}
\begin{aligned}
u^Tv &=\frac{1}{{w_{g_0}}}\frac{1}{\left\|\left(Hv\right)_{G_{g_0}}\right\|_2}\cdot\sum\limits_{j\in{G_{g_0}}}\frac{{v_j}^2}{{h_j}^2}
&=\frac{1}{{w_{g_0}}} \left\|\left(Hv\right)_{G_{g_0}}\right\|_2
\end{aligned}
\end{equation*}

Therefore, this is a sharp bound.

§.§ Proof of Theorem <ref>

By default, we take $S = S(\beta^*)$ and $\overline{S} = \overline{S}(\beta^*)$ in all settings. From the optimality of $\hat{\beta}^G$, we have

\begin{equation*}
\begin{aligned}
0 \ge &\quad \hspace{0.1cm}\frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2 - \frac{1}{n}\left\|Y-X\beta^{\ast}\right\|_2^2 +\lambda_n\left(\phi(\hat{\beta})-\phi(\beta^{\ast})\right)
\\&=\frac{1}{n}\left(Y^TY-2Y^TX\hat{\beta}+\hat{\beta}^TX^TX\hat{\beta}-Y^TY+2Y^TX{\beta^{\ast}}-\beta^{\ast{T}}X^TX\beta^\ast\right)+\lambda_n\left(\phi(\hat{\beta})-\phi\left(\beta^{\ast}\right)\right)\\
&=\left\langle\bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle +\frac{\left\|X\left(\hat{\beta}-\beta^{\ast}\right)\right\|_2}{n}+\lambda_n\left(\phi(\hat{\beta})-\phi(\beta^{\ast})\right)\\
&\geqslant\left\langle \bigtriangledown\frac{\left\|Y-X\beta^\ast\right\|_2^2}{n}, \left(\hat{\beta}-\beta^{\ast}\right)\right\rangle
+\kappa{\left\|\left( \hat{\beta}-\beta^\ast\right) \right\|_2^2}
&\geqslant-\left| \left\langle \bigtriangledown\frac{\left\|Y-X\beta^\ast\right\|_2^2}{n}, \left(\hat{\beta}-\beta^{\ast}\right)\right\rangle \right|+
\kappa{\left\|\left( \hat{\beta}-\beta^\ast\right) \right\|_2^2}
\end{aligned}
\end{equation*}

where the penultimate step is valid due to the assumption on restrictive strong convexity.

By applying Holder's inequality with the regularizer $\phi$ and its dual norm $\phi^{\ast}$, we have

\begin{equation}
\label{b}
\left|\left\langle \bigtriangledown\frac{\left\|Y-X{\beta^{\ast}}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle  \right|\leqslant \phi^{\ast}\left(\bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n}\right)
\phi\left(\hat{\beta}-\beta^{\ast}\right).
\end{equation}

Next, we have

\begin{equation*}
\begin{aligned}
\phi(\beta_{M^{\perp}(S)}^{\ast})
& \hspace{0.8cm} = \phi(\beta_{M(S)}^{\ast})+\phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)-
\phi(\beta_{M^{\perp}(S)}^{\ast})
\end{aligned}
\end{equation*}

The inequality hold by applying the triangle inequality on $\phi(\hat{\beta})$, and the last step hold by applying Lemma <ref>. Consequently, we have

\begin{equation}
\begin{aligned}
\phi(\hat{\beta})-\phi\left(\beta^{\ast}\right)&\geqslant \phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)-
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)
-2\phi(\beta_{M^{\perp}(S)}^{\ast}) \\
&= \phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)-
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right),
\end{aligned}
\label{c}
\end{equation}

where $\phi\left(\beta_{M^{\perp}(S)}^{\ast}\right)=0$ as $\beta_{M^{\perp}\left(S\right)}^{\ast}$ is a zero vector.

Based on equation(<ref>) and equation(<ref>), we have

\begin{equation*}
\begin{aligned}
&\quad \frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2-\frac{1}{n}\left\|Y-X{\beta^{\ast}}\right\|_2^2+\lambda_n\left(\phi(\hat{\beta})-\phi(\beta^{\ast})\right)
\\&\geqslant-\left| \left\langle \bigtriangledown\frac{\left\|Y-X\beta^\ast\right\|_2^2}{n}, \left(\hat{\beta}-\beta^{\ast}\right)\right\rangle \right|+
\kappa{\left\|\left( \hat{\beta}-\beta^\ast\right) \right\|_2^2}
\\&\geqslant \kappa{\left\|\left( \hat{\beta}-\beta^\ast\right) \right\|_2^2}
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)\right)-\left| \left\langle \bigtriangledown\frac{\left\|Y-X\beta^\ast\right\|_2^2}{n}, \left(\hat{\beta}-\beta^{\ast}\right)\right\rangle \right|
\\&\geqslant \kappa{\left\|\left( \hat{\beta}-\beta^\ast\right) \right\|_2^2}
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)\right)- \phi^{\ast} \left(\bigtriangledown\frac{\left\|Y-X{\beta^{\ast}} \right\|_2^2}{n}\right) \phi\left(\hat{\beta}-\beta^{\ast}\right)
\\&\geqslant \kappa\left\|\left(\hat{\beta}-\beta^{\ast}\right) \right\|_2^2
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)\right)
\end{aligned}
\end{equation*}

where the last step is valid because Lemma <ref> implies that we can guarantee $\lambda_n\geqslant 2\phi^{\ast} \left(\bigtriangledown\frac{\left\|Y-X{\beta^{\ast}} \right\|_2^2}{n}\right)$ with high probability by taking appropriate $\lambda_n$. Moreover, Lemma <ref> implies that
$$\hat{\beta}\in\left\{\beta\in{\mathbb{R}^p} \mid \phi \left(\left(\beta-\beta^{\ast}\right)_{M^{\perp}(\overline{S})}\right) \leqslant 3\phi\left(\left(\beta-\beta^{\ast}\right)_{M(\overline{S})}\right)\right\}.$$

By the triangle inequality, we have

$$\phi(\hat{\beta}-\beta^{\ast})=\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}+(\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)\leqslant \phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)+\phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right),$$

and hence we have

\begin{equation*}
\begin{aligned}
&\quad \frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2-\frac{1}{n}\left\|Y-X{\beta^{\ast}}\right\|_2^2+\lambda_n\left(\phi(\hat{\beta})-\phi(\beta^{\ast})\right)
\\&\geqslant \kappa\left\|\left(\hat{\beta}-\beta^{\ast}\right) \right\|_2^2
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)\right)
\\&\geqslant \kappa\left\|\left(\hat{\beta}-\beta^{\ast}\right) \right\|_2^2
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)\right)\\
&\quad~~~~~~~~~~ \quad -\frac{\lambda_n}{2}\left(\phi\left((\hat{\beta}-\beta^{\ast})_{M(S)}\right)+\phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)\right)\\
&\geqslant \kappa\left\|\hat{\beta}-\beta^{\ast}\right\|_2^2
&\geqslant \kappa\left\|\hat{\beta}-\beta^{\ast}\right\|_2^2
\end{aligned}
\end{equation*}

By definition, we have $\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)=\sum\limits_{g\in\overline{S}}{w_g}\left\|\left(\hat{\beta}-\beta^{\ast}\right)_{G_g}\right\|_2,$ and by Cauchy-Schwartz inequality, we have

\begin{equation*}
\begin{aligned}
\sum\limits_{g\in\overline{S}}{w_g}\left\|\left(\hat{\beta}-\beta^{\ast}\right)_{G_g}\right\|_2
&\leqslant \sqrt{\sum\limits_{g\in\overline{S}}{w_g}^2}\cdot\sqrt{h_{\max}(\mathbf{G_{\overline{S}}})\cdot\max\limits_{g\in\overline{S}}\left\|\left(\hat{\beta}-\beta^{\ast}\right)_{G_g}\right\|^2_2}\\
&\leqslant \sqrt{\sum\limits_{g\in\overline{S}}{w_g}^2}\cdot\sqrt{h_{\max}(\mathbf{G_{\overline{S}}})\cdot\left\|\left(\hat{\beta}-\beta^{\ast}\right)\right\|^2_2} \\
&= \sqrt{\sum\limits_{g\in\overline{S}}{w_g}^2}\cdot\sqrt{h_{\max}(\mathbf{G_{\overline{S}}})}\left\|\left(\hat{\beta}-\beta^{\ast}\right)\right\|_2.
\end{aligned}
\end{equation*}

On the other hand, since
$\kappa\left\|\hat{\beta}-\beta^{\ast}\right\|_2^2-\frac{3\lambda_n}{2}\sqrt{\sum\limits_{g\in\overline{S}}{w_g}^2}\cdot\sqrt{h_{\max}(\mathbf{G_{\overline{S}}})}\left\|\left(\hat{\beta}-\beta^{\ast}\right)\right\|_2\leqslant 0$, we have

\begin{equation*}
\begin{aligned}
\left\|\hat{\beta}-\beta^{\ast}\right\|_2^2&\leqslant
\frac{9\lambda_n^2}{4\kappa^2}\sum\limits_{g\in\overline{S}}{{w_g}^2}\cdot h_{\max}(\mathbf{G_{\overline{S}}})\\
&\leqslant\frac{9}{4\kappa^2}\cdot\frac{64{ c^2 \sigma^2} \sum \limits_{g\in\overline{S}}{w_g}^2\cdot h_{\max}(\overline{S})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}\cdot\left(\frac{d_{\max}{\log{5}}}{n}+\frac{\log{m}}{n}+\delta\right)\\
&\leqslant \frac{144c^2 \sigma^2}{\kappa^2}\cdot\frac{\sum\limits_{g\in\overline{S}}{w_g}^2\cdot h_{\max}(\mathbf{G_{\overline{S}}})}{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}
\cdot\left(\frac{d_{\max}{\log{5}}}{n}+\frac{\log{m}}{n}+\delta\right)
\end{aligned}
\end{equation*}

§.§ Lemmas for the proof of Theorem <ref>

In these lemmas, we abbreviate $\hat{\beta}^{G}$ by $\hat{\beta}$.

Under the Assumption <ref> and (<ref>), taking

\lambda_n =  \frac{8c \sigma}{\sqrt{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}}
\sqrt{\frac{d_{\max}\log{5}}{n}+
\frac{\log{m}}{n}+\delta} \hspace{0.5cm}\textit{for some $\delta \in [0,1]$,}
\end{array}$$

then $P \left(\lambda_n \geqslant 2 \phi^{*}(\frac{X^{\top} \varepsilon}{n})\right) \geqslant 1-e^{-2 n \delta}. $

Let $V_{i\cdot g}= - \varepsilon_i \left(\frac{X_{ig_1}}{h_{g_1}w_g},\frac{X_{ig_2}}{h_{g_2}w_g},\dots,\frac{X_{ig_{d_g}}}{h_{g_{d_g}}w_g}\right) \in \mathbb{R}^{d_g}$.
According to the variational form of $\ell_2$ norm, we have $\frac{1}{n}\left\|\sum_{i=1}^{n} V_{i \cdot g}\right\|_{2}=\underset{u\in S^{d_{g-1}}}{\operatorname{sup}} \left\langle u, \frac{1}{n} \sum_{i=1}^{n} V_{i \cdot g} \right\rangle$, where  $S^{d_{g}-1}$ is the Euclidean sphere $\operatorname{in} \mathbb{R}^{d_g}$. Also, for any vector $u \in S^{d_{g-1}}$ and $t \in \mathbb{R}$, we have

\begin{equation*}
\begin{aligned}
\frac{1}{n} \log E\left(e^{t\left\langle  u, \sum\limits_{i=1}^{n} V_{i\cdot g} \right\rangle }  \right)&
= \frac{1}{n} \log E\left(e^{t  \sum\limits_{j=1}^{d_{g}} u_{j } \sum\limits_{i=1}^nV_{i\cdot g_j}  }  \right)
= \frac{1}{n} \log E\left(e^{t  \sum\limits_{i=1}^{n} \left( \sum\limits_{j=1}^{d_{g}} u_{j } V_{i\cdot g_j}\right)   }  \right)\\
&=\frac{1}{n}\log E \left( e^{-t  \sum\limits_{i=1}^n\left( \sum\limits_{g=1}^{d_g} \frac{u_j X_{ig_j} \varepsilon_{i}}{h_{g_j}  w_g} \right) } \right)
=\frac{1}{n}\log E \left( e^{-t  \sum\limits_{i=1}^n \varepsilon_{i} \left( \sum\limits_{j=1}^{d_g} \frac{u_j X_{ig_j} }{h_{g_j}  w_g} \right) } \right).
\end{aligned}
\end{equation*}

Since $\left\{\epsilon_{i}\right\}_{i=1}^{n} $ are i.i.d zero mean sub-Gaussian random variables with parameter $\sigma$, let $u = (u_1, \cdots,u_{d_g})^T \in \mathbb{R}^{d_g \times 1}$, $X_{i,g} = (X_{ig_1},\cdots X_{ig_{d_g}})^T \in \mathbb{R}^{d_g \times 1}$, then we have

\begin{aligned}\frac{1}{n}\log E \left( e^{-t  \sum\limits_{i=1}^n \varepsilon_{i} \left( \sum\limits_{j=1}^{d_g} \frac{u_j x_{ig_j} }{h_{g_j} w_g} \right) } \right)& =\frac{1}{n}\log E\left(e^{-t\varepsilon_{1}\left( \sum\limits_{j=1}^{d_g} \frac{u_j X_{1g_j} }{h_{g_j}  w_g} \right)}\right)+\cdots+\frac{1}{n}\log E\left(e^{-t \varepsilon_{n} \left( \sum\limits_{j=1}^{d_g} \frac{u_j X_{ng_j} }{h_{g_j} w_g} \right)}\right) \\ & \leqslant \frac{t^2 \sigma^2}{2n} \left(\sum\limits_{i=1}^{n} \left(\sum\limits_{j=1}^{d_g} \frac{u_j X_{ig_j}}{ w_g h_{g_j}}\right)^2\right)
\leqslant  \frac{t^2 \sigma^2}{2n} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( \sum\limits_{i=1}^{n} \left(\sum\limits_{j=1}^{d_g} u_j X_{ig_j}\right)^2\right)\\
&= \frac{t^2 \sigma^2}{2n} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( \sum\limits_{i=1}^{n} \langle u,\ X_{i,g} \rangle^2\right) = \frac{t^2 \sigma^2}{2n} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( \sum\limits_{i=1}^{n}( u^TX_{i,g}X^T_{i,g}u)\right)\\
&= \frac{t^2 \sigma^2}{2} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( u^T\left(\frac{1}{n}\sum\limits_{i=1}^{n}X_{i,g}X^T_{i,g}\right)u\right)\\
&= \frac{t^2 \sigma^2}{2} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( u^T\frac{X^T_{G_g}X_{G_g}}{n}u\right)\\
&\leqslant \frac{t^2 \sigma^2}{2} \frac{1}{w_g^2 \left(h_{\min}^{g}\right)^2} \left( \gamma_{\max}(\frac{X^T_{G_g}X_{G_g}}{n})\right)\\
\end{aligned}

By Assumption <ref>, we have
$ \gamma_{\max}(\frac{X^T_{G_g}X_{G_g}}{n}) \leqslant c^2$. Combining this with the previous proof, we have
$\frac{1}{n} \log E\left(e^{t\left\langle u, \sum\limits_{i=1}^{n} V_{i\cdot g}\right\rangle }\right) \leqslant \frac{c^2 t^2 \sigma^2}{2 w_g^2 \left(h_{\min}^{g}\right)}$. Therefore, the random variable $\left\langle u, \sum\limits_{i=1}^{n} V_{i\cdot g}\right\rangle$ is the sub-Gaussian with the parameter at most $\sqrt{\frac{ c^2 \sigma^2}{w_g^2 \left(h_{\min}^{g}\right)}}$, and by properties of sub-Gaussian variables, we have

\begin{equation*}
\log P\left(\left\langle u, \sum\limits_{i=1}^{n} V_{i\cdot g}\right\rangle \geqslant \frac{\lambda_n}{4}\right) \leqslant -\frac{\lambda_n^2 w_g^2 h_{\min}^{g} }{32 C^2 \sigma^2}.
\end{equation*}

We can find a $\frac{1}{2}$ covering of $S^{d_g-1}$ in Euclidean norm:$\{u^1,u^2,\dots,u^N\}$ with $N \leq 5^{d_g}$, recall that
$\frac{1}{n} \left\|\sum_{i=1}^{n}V_{i\cdot g} \right\|_2
\underset{u\in S^{d_{g-1}}}{\operatorname{sup}}
\left\langle u , \sum\limits_{i=1}^{n} V_{i\cdot g}\right\rangle,
$ so that for any   $u\in S^{d_{g-1}}$, we can find a $u^{q(u)} \in \left\{u^1, \ldots, u^N\right\}$, such that $\left\|u^{q(u)}-u\right\|_2\leqslant\frac{1}{2}$, and

\begin{equation*}
\begin{aligned}
\frac{1}{n}
\underset{u\in S^{d_{g-1}}}{\operatorname{sup}}
\left\langle u ,  \sum\limits_{i=1}^{n}V_{i\cdot g}\right\rangle &=\frac{1}{n} \underset{u\in S^{d_{g-1}}}{\operatorname{sup}}
\left(\left\langle u-u^{q(u)},\sum_{i=1}^{n} V_{i\cdot g}\right\rangle +\left\langle u^{q(u)}, \sum_{i=1}^{n}V_{i\cdot g} \right\rangle \right)\\
& \leqslant \frac{1}{n} \underset{u\in S^{d_{g-1}}}{\operatorname{sup}} \left\langle u-u^{q(u)},\sum_{i=1}^{n} V_{i\cdot g}  \right\rangle + \frac{1}{n} \max\limits_{q\in[N]} \left\langle u^q,  V_{i\cdot g} \right\rangle
\end{aligned}
\end{equation*}

By Cauchy inequality,
$\frac{1}{n} \underset{u\in S^{d_{g-1}}}{\operatorname{sup}}
\left\langle u-u^{q(u)},\sum\limits_{i=1}^{n} V_{i\cdot g} \right\rangle
\leqslant \frac{\left\|  u-u^{q(u)} \right\|_2}{n}  \left\| \sum\limits_{i=1}^{n}V_{i\cdot g} \right\|_2
\leqslant \frac{1}{2n} \left\| \sum\limits_{i=1}^{n}V_{i\cdot g} \right\|_2,
$ hence we have $\frac{1}{n} \left\| \sum\limits_{i=1}^{n}V_{i\cdot g} \right\|_2 \leqslant  \frac{1}{2n} \left\| \sum\limits_{i=1}^{n}V_{i\cdot g} \right\|_2 + \frac{1}{n} \max\limits_{q\in[N]}
\left\langle u^q \sum\limits_{i=1}^{n} V_{i\cdot g} \right\rangle,$
which indicates that $ \frac{1}{n}\left\|\sum\limits_{i=1}^{n} V_{i\cdot g}\right\|_2 \leqslant 2\max\limits_{q\in[N]} \left\langle u^q, \frac{1}{n} \sum\limits_{i=1}^{n} V_{i\cdot g}\right\rangle.$ Consequently,

\begin{align*}
P\left(\frac{1}{n} \left\|\sum\limits_{i=1}^{n}V_{i\cdot g}\right\|_2\geqslant \frac{\lambda_n}{2}\right) &  \leqslant  P \left( \max\limits_{q\in[N]}\left\langle u^q, \frac{1}{n} \sum\limits_{i=1}^{n}V_{i\cdot g} \right\rangle \geqslant \frac{\lambda_n}{4}\right)\leqslant  P \left(\bigcup\limits_{q=1}^{N} \left\langle u^q, \frac{1}{n} \sum\limits_{i=1}^{n}V_{i\cdot g} \right\rangle \geqslant \frac{\lambda_n}{4}\right)\\ &\leqslant  \sum_{q=1}^{N}P \left( \left\langle u^q, \frac{1}{n} \sum\limits_{i=1}^{n}V_{i\cdot g} \right\rangle \geqslant \frac{\lambda_n}{4}\right)
\leqslant  N  \exp \left(- \frac{n \lambda_n^2 {w_g}^2 h_{\min}^{g}}{32 C^2 \sigma^2} \right)\\
&\leqslant \exp \left(- \frac{n \lambda_n^2 {w_g}^2 h_{\min}^{g}}{32 c^2 \sigma^2} + d_g \log{5}\right),
\end{align*}

and by setting $\lambda_n =  \frac{8c \sigma}{\sqrt{\min\limits_{g\in[m]}\left(w_g^2 h_{\min}^{g}\right)}}
\sqrt{\frac{d_{\max}\log{5}}{n}+
\frac{\log{m}}{n}+\delta}$, we have

\begin{equation*}
\begin{aligned}
P\left(\max\limits_{g \in [m]} \frac{1}{n} \left\| \sum\limits_{i=1}^{n} V_{i\cdot g}\right\|_2 \geqslant \frac{\lambda_n}{2}  \right) &\leqslant P \left( \bigcup\limits_{g=1}^{m}\frac{1}{n}  \left\|\sum_i^n V_{i\cdot g} \right\|_2 \geqslant \frac{\lambda_n}{2} \right)\leqslant \sum_{g=1}^m P \left(\frac{1}{n} \left\| \sum \limits_{i=1}^{n} V_{i\cdot g}\right\|_2 \geqslant \frac{\lambda_n}{2} \right) \\
&\leqslant \exp \left( - \frac{n \lambda_n^2}{32 c^2 \sigma^2}\cdot \min\limits_{g \in\{1, \cdots, m\}}\{ {w_g}^2 h_{\min}^{g}\} + d_{\max} \log{5} + \log{m}\right) \\
&\leqslant \operatorname{exp}\{-2 n \delta \},
\end{aligned}
\end{equation*}

which equivalent to $ P\left(\lambda_n \geqslant 2\max\limits_{g \in [m]} \frac{1}{n} \left\| \sum\limits_{i=1}^{n} V_{i\cdot g}\right\|_2  \right) \geqslant 1-\operatorname{exp}\{-2 n \delta \}$.  From Proposition <ref>, we have

\begin{equation*}
\begin{aligned}
\phi^{*}\left(\frac{X^{\top} \varepsilon}{n}\right)&\leqslant\max \limits_{g \in [m]} \frac{1}{w_g}\left\|\left(\frac{HX^{\top} \varepsilon}{n}\right)_{G_{g}}\right\|_{2}
=\max \limits_{g \in [m]} \frac{1}{w_g}\left\|\frac{1}{n}\sum\limits_{i=1}^n-\varepsilon_i\left(\frac{X_{ig_1}}{h_{g_1}},\cdots,\frac{X_{ig_{d_g}}}{h_{g_{d_g}}}\right)\right\|_{2}\\
&=\max \limits_{g \in [m]}\left\|\frac{1}{n} \sum\limits_{i=1}^n V_{i\cdot g} \right\|_2.
\end{aligned}
\end{equation*}

Therefore,  $P \left(\lambda_n \geqslant 2 \phi^{*}(\frac{X^{\top} \varepsilon}{n})\right) \geqslant 1-e^{-2 n \delta}. $

The group lasso regularizer (<ref>) is decomposable with respect to the pair $\left\{M\left(S\right), M^{\perp}(\overline{S})\right\}$. That is, $
\phi(a+b)=\phi(a)+\phi(b), \hspace{0.2cm} \text{for all} \hspace{0.2cm} a\in M\left(S\right) \hspace{0.1cm}\textit{and} \hspace{0.2cm}  \text{for all} \hspace{0.2cm} b\in M^{\perp}(\overline{S})$.

\begin{align*}
\phi\left(a+b\right)	&=\sum\limits_{g=1}^m{w_g}\left\|\left(a+b\right)_{G_g}\right\|_2
=\sum\limits_{g\in M(\overline{S})}{w_g}\left\|\left(a+b\right)_{G_g}\right\|_2+\sum\limits_{g\notin M(\overline{S})}{w_g}\left\|\left(a+b\right)_{G_g}\right\|_2\\
&=\sum\limits_{g\in M(\overline{S})}{w_g}\left\|a_{G_g}\right\|_2+\sum\limits_{g\in M^{\perp}(\overline{S})}{w_g}\left\|b_{G_g}\right\|_2 =\sum\limits_{g\in M(S)}{w_g}\left\|a_{G_g}\right\|_2+\sum\limits_{g\in M^{\perp}(\overline{S})}{w_g}\left\|b_{G_g}\right\|_2\\
\end{align*}

If $\lambda_n\geqslant 2 \phi^{\ast}\left(\frac{X^T\varepsilon}{n}\right)$, then  $\phi\left((\hat{\beta}-\beta^*)_{M^\perp(\overline{S})}\right)\leqslant3\phi\left((\hat{\beta}-\beta^*)_{M(\overline{S})}\right)$.

From equation (<ref>), we have

\begin{equation}
\phi(\hat{\beta})-\phi\left(\beta^{\ast}\right)\geqslant  \phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)-
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right),
\end{equation}

On the other hand, by the convexity of the cost function, we have

\begin{align*}
\frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2
\geqslant\left\langle \bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle
\geqslant-\left\langle \bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle.
\end{align*}

By applying Holder's inequality with the regularizer $\phi$ and its dual norm $\phi^{\ast}$, we have

$$\left|\left\langle \bigtriangledown\frac{\left\|Y-X{\beta^{\ast}}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle  \right|\leqslant \phi^{\ast}\left(\bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n}\right)
\phi\left(\hat{\beta}-\beta^{\ast}\right).

\begin{align*}
\frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2
-\frac{1}{n}\left\|Y-X{\beta^{\ast}}\right\|_2^2 &
\geqslant-\left\langle \bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n},\left(\hat{\beta}-\beta^{\ast}\right)\right\rangle
\geqslant-\phi^{\ast}\left(\bigtriangledown\frac{\left\|Y-X{\beta^\ast}\right\|_2^2}{n}\right)
\phi\left(\hat{\beta}-\beta^{\ast}\right)\\
&\geqslant-\frac{\lambda_n}{2} \phi\left(\hat{\beta}-\beta^{\ast}\right) \geqslant-\frac{\lambda_n}{2}
\left(\phi(\hat{\beta}-\beta^{\ast})_{M(\overline{S})} + \phi(\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right),
\end{align*}

\begin{equation*}
\begin{aligned} 0 & =\frac{1}{n}\left\|Y-X\hat{\beta}\right\|_2^2-\frac{1}{n}\left\|Y-X\beta^{\ast}\right\|_2^2+\lambda_n\left(\phi(\hat{\beta})-\phi(\beta^{\ast})\right) \\
& \geq \lambda_n\left(\phi\left((\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right)-
\phi\left((\hat{\beta}-\beta^{\ast})_{M(\overline{S})}\right)
-2\phi(\beta_{M^{\perp}(S)}^{\ast})\right) -\frac{\lambda_n}{2}
\left(\phi(\hat{\beta}-\beta^{\ast})_{M(\overline{S})} + \phi(\hat{\beta}-\beta^{\ast})_{M^{\perp}(\overline{S})}\right) \\ &
\end{equation*}

from which the claim follows.

§.§ Proof of Theorem <ref>

(Theorem 6.5 in [Wainwright, 2019])

Let $|||.|||_2$ be the spectral norm of a matrix . There are universal constants $c_2, c_3,c_4,c_5$ such that, for any matrix $A \in \mathbb{R}^{n \times p} $, if all rows are drawn i.i.d from $N(0,\Theta)$, then the sample covariance matrix $\hat{\Theta}$ satisfies the bound

\begin{equation*}
E\left(e^{t|||\hat{\Theta}-\Theta|||_2}\right) \leqslant e^{c_3\frac{t^2\theta^2}{n} + 4p} \hspace{0.3cm} \text{for all} \hspace{0.2cm} |t| <
\frac{n}{64e^2|||\Theta|||_2},
\end{equation*}

and hence for all $\delta \in [0,1]$

\begin{equation}
\label{eq:expspctral}
P\left(\frac{|||\hat{\Theta}-\Theta|||_2}{|||\Theta|||_2} \leqslant c_5(\sqrt{\frac{p}{n}}+\frac{p}{n}) + \delta \right) > 1 - c_4e^{-c_2n\delta^2}
\end{equation}

Under Assumption <ref>, and use $\rho (\Theta)$ to denote the maximum diagonal of a covariance matrix $\Theta$. For any vector $\beta \in \mathbb{R}^p$ and a given group structure with $m$ groups, we have

\begin{equation}
\label{eq:lemrsc}
\frac{\left\|X\beta\right\|_2}{\sqrt{n}}
\geq \frac{1}{4} \left\|\Theta^{\frac{1}{2}}\beta\right\|_2
-  8\rho(\Theta) \left( \max\limits_{g\in [m]} \frac{1}{w_g \sqrt{h_{\min}^{g}}}\right)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}} \phi(\beta),
\end{equation}

with probability at least $1- \frac{e^{-\frac{n}{32}}}{1-e^{-\frac{n}{64}}}.$

By Lemma <ref>, we have

$$ P\left(\frac{|||\frac{X_{G_g}^TX_{G_g}}{n} - \Theta_{G_g,G_g}|||_2}{|||\Theta|_{G_g,G_g}||_2} \leqslant c_5(\sqrt{\frac{d_g}{n}}+\frac{d_g}{n}) + \delta \right) >1 - c_4e^{-c_2n\delta^2}$$

By triangle inequality, since $X_{G_g}^TX_{G_g}$ is a positive semi-definite, we have

\begin{equation*}
\begin{aligned}
\gamma_{\max}(\frac{X_{G_g}^TX_{G_g}}{n}) & = |||\frac{X_{G_g}^TX_{G_g}}{n}|||_2 = |||\frac{X_{G_g}^TX_{G_g}}{n} - \Theta_{G_g,G_g}|||_2 + |||\Theta_{G_g,G_g}|||_2\\
&\leqslant (1+c_5(\sqrt{\frac{d_g}{n}}+\frac{d_g}{n}) + \delta) |||\Theta_{G_g,G_g}|||_2,
\end{aligned}
\end{equation*}

with probability at least $1 - c_4e^{-c_2n\delta^2}$. Because $|||\Theta_{G_g,G_g}|||_2 \le |||\Theta|||_2 \leqslant c_1$ for some constant $c_1$ and $d_g \leqslant n$, we have $ \gamma_{\max}(\frac{X_{G_g}^TX_{G_g}}{n})  \leqslant c + \delta$ for some constant $c$, with probability at least $1 - e^{-c_2n\delta^2}$. Taking the union probability for all $m$ groups, we have

$$\max_{g\in [m]}\gamma_{\max}(\frac{X_{G_g}^TX_{G_g}}{n}) \le c+\delta$$

with probability at least $1-\exp( -c'2n\delta^2)$ for some constant $c'>0$ as long as

$$\log m \ll n\delta^2.$$

For simplicity, we take $\delta$ as a constant as the result.

First note that we must have $\rho(\Theta) \le \gamma_{\max}(\Theta) \le c_1$ by Assumption <ref>. By applying Minkowski  inequality, we have

\begin{align*}
&\phi(\beta) =  \sum\limits_{g=1}^{m} w_g \left\|\beta_{G_g}\right\|_2
\leqslant  \sqrt{m} \sqrt{\sum\limits_{g=1}^{m} w_g^2 \left\|\beta_{G_g}\right\|^2_2}
\leqslant  \sqrt{m} \sqrt{ \max\limits_{g\in[m]}  w_g^2 h_{\max}^{g} \left\| \beta \right\|^2_2 }
\end{align*}

Let $\beta=\beta^{\ast}-\bar{\beta}$, we now want to prove that
$\phi \left( \beta_{M^\perp(\bar{S})}\right) \leqslant 3 \phi \left( \beta_{M(\bar{S})}  \right)$ implies $\frac{\left\| X \beta \right\|_2^2}{n} \geqslant \frac{\gamma_{\min}}{64} \left\| \beta \right\|_2^2.$

Since $\phi \left( \beta_{M^\perp(\bar{S})}\right) \leqslant 3 \phi \left( \beta_{M(\bar{S})}  \right)$, combining with triangle inequality, we have

\begin{align*}
\phi(\beta) & =  \phi \left( \beta_{M(\bar{S})}\right) + \phi \left( \beta_{M^\perp(\bar{S})} \right) \leqslant 4 \phi \left( \beta_{M(\bar{S})} \right)
\leqslant 4 \sqrt{\overline{s_g}} \sqrt{ \max\limits_{g\in\bar{S}}  w_g^2 h_{\max}^{g}} \left\| \beta_{M(\bar{S})} \right\|_2 \\
& \leqslant 4 \sqrt{\overline{s_g}} \sqrt{ \max\limits_{g\in\bar{S}} w_g^2 h_{\max}^{g}} \left\| \beta \right\|_2
\end{align*}

From Lemma <ref>, we have

\begin{equation*}
\begin{split}
\frac{\left\|X\beta\right\|_2}{\sqrt{n}}
\geqslant & \frac{1}{4} \left\| \Theta^{\frac{1}{2}} \beta \right\|_2 -8\rho(\Theta)\max\limits_{g\in[m]} \frac{1}{w_g \sqrt{h_{\min}^{g}}}
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}} \phi(\beta)\\
\geqslant & \frac{1}{4\sqrt{c_1}} \left\| \beta \right\|_2 - 32\rho(\Theta)\max\limits_{g\in[m]} \frac{1}{w_g \sqrt{h_{\min}^{g}}}
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}} \sqrt{\overline{s_g}} \sqrt{ \max\limits_{g\in\bar{S}} w_g^2 h_{\max}^{g}} \left\| \beta \right\|_2 \\
\geqslant &  \frac{1}{64\sqrt{c_1}} \left\| \beta \right\|_2,
\end{split}
\end{equation*}

where the last step is valid due to Assumption <ref>.

§.§ Lemmas for the proof of Theorem <ref>

To begin with, for a vector $\beta \in \mathbb{R}^p$ with a fixed group structure, we define the set  $S^{p-1}(\Theta)= \left\{ \beta \in \mathbb{R}^p \middle| \left\|\Theta^{\frac{1}{2}}\beta\right\|_2 =1\right\}$, the function
g(t) = 4\rho(\Theta)\max\limits_{g\in[m]} \frac{1}{w_g \sqrt{h_{\min}^{g}}}
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}} \cdot t

and the event

\mathcal{E}\left( S^{p-1}(\Theta)\right) = \left\{ X\in \mathbb{R}^{n\times p} \middle| \inf\limits_{\beta\in S^{p-1} (\Theta)} \frac{ \left\| X \beta \right\|_2 }{ \sqrt{n}}+2 g (\phi(\beta)) \leqslant \frac{1}{4}  \right\}.

where $\phi(.)$ is the overlapping group lasso regularizer. In addition, given $0 \leqslant r_\ell \leqslant r_u$, we define the set
$$\mathbb{K} \left( r_\ell, r_u \right) = \left\{ \beta \in S^{p-1} (\Theta) \middle| g \left( \phi(\beta)\right) \in \left[r_\ell, r_u \right] \right\},$$
and the event:

\mathcal{A} \left(r_{\ell}, r_{u}\right)=
\left\{ X \in \mathbb{R}^{n \times p} \middle|\inf\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{\left\| X \beta  \right\|_2}{\sqrt{n}} \leqslant \frac{1}{2} - r_u\right\}.

Based on lemma <ref>.1 and lemma <ref>.2, we have

$$P\left( X \in \mathcal{E} \right) \leqslant P \left( \mathcal{A} (0, \upsilon)\right) + \sum\limits_{\ell=1}^{\infty} P \left(\mathcal{A} ( 2^{\ell-1} \upsilon, 2^{\ell} \upsilon)\right) \leqslant e^{-\frac{n}{32} }  \left\{ \sum\limits_{t=0}^{\infty} e^{ -\frac{n}{8} 2^{2\ell} \upsilon^2} \right\}.$$

Since $\upsilon=\frac{1}{4}$ and $2^{2\ell} \geqslant 2\ell$, we have $P \left( X \in \mathcal{E}  \right) \leqslant e^{-\frac{n}{32}} \sum\limits_{\ell=0}^{\infty} e^{-\frac{n}{8} 2^{2\ell} \upsilon^2} \leqslant e^{-\frac{n}{32}} \sum\limits_{\ell=0}^{\infty} e^{-n \frac{\ell}{4} \upsilon^2} \leqslant \frac{e^{-\frac{n}{32}}}{1- e^{-\frac{n}{64}}}$.

We just get upper bound of $P\left(X\in \mathcal{E}\right)$. We next show that the bound in (<ref>) always hold on the complementary set $\mathcal{E} ^c.$

If $ X\notin \mathcal{E}$, based on the definition of $\mathcal{E}$, we have
\inf\limits_{\beta \in S^{p-1} (\Theta)} \frac{\left|X\beta\right\|_2}{\sqrt{n}} \geqslant \frac{1}{4} - 2 g \left(\phi(\beta)\right).
$  That is $\forall \beta \in S^{p-1} (\Theta)$.
$\frac{\left\|X\beta\right\|_2}{\sqrt{n}} \geqslant \frac{1}{4} - 2 g \left( \phi (\beta)\right)$.
Therefore, for any $\beta'\in \{\beta'\in \mathbb{R} | \frac{\beta'}{\left\|\Theta^{\frac{1}{2}}\beta'\right\|_2} \in S^{p-1} (\Theta)\}$, we have

\begin{align*}
\geqslant \frac{1}{4} - 2g \left( \phi \left( \frac{ \beta' }{ \left\| \Theta^{\frac{1}{2}}\beta' \right\|_2} \right) \right) \\
\geqslant
\frac{1}{4} \left\|\Theta^{\frac{1}{2}}\beta'\right\|_2
- 2g \left( \phi (\beta')\right),\\
\end{align*}

By substituting the definition of $g(\phi(\beta))$, we finish the proof.

Lemma <ref>.1 For $\upsilon=\frac{1}{4}$, we have
\mathcal{E}\subseteq
\mathcal{A} (0, \upsilon) \cup
\left(\bigcup_{\ell=1}^{\infty} \mathcal{A} \left( 2^{\ell-1}\upsilon,2^{\ell}\upsilon\right)\right).

Lemma <ref>.2  For any pair $\left(r_\ell, r_u \right)$, where $0\leqslant r_\ell \leqslant r_u$, we have $P\left(\mathcal{A} \left(r_\ell, r_u \right) \right) \leqslant {e^{-\frac{n}{32}} e^{-\frac{n}{8} r_u^2}}.$

By definition, $\mathbb{K}(0,\upsilon) \cup \left(\bigcup_{\ell=1}^{\infty} \mathbb{K} \left( 2^{\ell-1}\upsilon, 2^{\ell}\upsilon\right)\right)$ is a cover of  $S^{p-1} (\Theta)$. Therefore, for any $\beta$, it either belongs to $\mathbb{K}(0,\upsilon)$ or $\mathbb{K} \left( 2^{\ell-1} \upsilon, 2^{\ell} \upsilon \right)$.

Case 1 If $\beta \in \mathbb{K}(0,\upsilon)$, by definition, we have $ g \left( \phi(\beta)\right) \in \left[0, \upsilon \right]$ and

\begin{equation*}
\frac{ \left\| X \beta \right\|_2 }{ \sqrt{n} }
\leqslant \frac{1}{4} - 2 g \left(\phi(\beta)\right)
\leqslant \frac{1}{4} = \frac{1}{2} - \upsilon.\\
\end{equation*}

Therefore, the event $\mathcal{A} (0,\upsilon)$ must happen in this case.

Case 2: If $ \beta \notin \mathbb{K} (0,\upsilon) $, we must have $ \beta \in \mathbb{K} \left( 2^{\ell-1} \upsilon, 2^{\ell} \upsilon \right) $ for some $\ell=1,2,\cdots$, and moreover

\begin{equation*}
\frac{ \left\| X \beta \right\|_2 }{ \sqrt{n} }
\leqslant \frac{1}{4} - 2 g \left(\phi(\beta)\right)
\leqslant \frac{1}{4} - 2 \cdot \left( 2^{\ell-1}\upsilon \right)
\leqslant \frac{1}{2} - \left(2 \cdot 2^{\ell-1}\right) \upsilon
\leqslant \frac{1}{2} - 2^{\ell} \upsilon.\\
\end{equation*}

So that the event $\mathcal{A} \left( 2^{\ell-1}\upsilon, 2^{\ell}\upsilon \right)$ must happen. Therefore, $\mathcal{E}\subseteq \mathcal{A}(0,\upsilon) \cup \left(\bigcup\limits_{\ell=1}^{\infty} \mathcal{A} \left( 2^{\ell-1}\upsilon,2^{\ell}\upsilon\right)\right). $

To prove Lemma <ref>.2, we define and bound the random variable $T \left(r_\ell, r_u \right) = - \inf\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{\left\| X \beta\right\|_2}{\sqrt{n}}$.
Let $S^{n-1}$ be a unit ball on $\mathbb{R}^n$, by the variational representation of the $\ell_2$-norm, we have

\begin{equation*}
\begin{split}
T \left(r_\ell, r_u \right)
= & - \inf\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{\left\| X \beta\right\|_2}{\sqrt{n}}
= - \inf\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \sup\limits_{u \in S^{n-1}}
\frac{ \left\langle u, X \beta \right\rangle }{\sqrt{n}}
= \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \inf\limits_{u \in S^{n-1}}
\frac{ \left\langle u, X \beta \right\rangle }{\sqrt{n}}.\\
\end{split}
\end{equation*}

Let $ X = W \Theta^{\frac{1}{2}}$, where $W \in \mathbb{R}^{n\times p}$ is a standard Gaussian matrix, and define the transformed vector $v = \Theta^{\frac{1}{2}} \beta$, then

\begin{equation*}
T \left(r_\ell, r_u \right)= \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \inf\limits_{u \in S^{n-1}}
\frac{ \left\langle u, X \beta \right\rangle }{\sqrt{n}}
= \sup\limits_{v \in \bar{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}
\inf\limits_{u \in S^{n-1}}
\frac{ \left\langle u, Wv \right\rangle }{\sqrt{n}},
\end{equation*}

where $\bar{\mathbb{K}} \left( r_{\ell}, r_{u} \right) = \left\{ v \in \mathbb{R}^p \middle| \left\|v\right\|_2=1, g \left(\phi( \Theta^{-\frac{1}{2}} v) \right) \in \left[r_\ell, r_u \right] \right\}$.

Define $Z_{u,v} = \frac{ \left\langle u, Wv \right\rangle }{\sqrt{n}}$, since $(u, v)$ range over a subset of $S^{n-1} \times S^{p-1}$, each variable $Z_{u,v}$ is zero-mean Gaussian with variance $n^{-1}$. We compare the Gaussian process $Z_{u,v}$ to the zero-mean Gaussian process $Y_{u,v}$ which defined as:

\begin{equation*}
\frac{ \left\langle \zeta, u \right\rangle }{\sqrt{n}}
+ \frac{ \left\langle \xi, v \right\rangle }{\sqrt{n}}
~~~~~~~~\text{where }
\zeta \in \mathbb{R}^n , \xi \in \mathbb{R}^p,\text{have i.i.d $N(0,1)$ entries.}
\end{equation*}

Next, we show that the $Y_{u,v}$ and $Z_{u,v}$ defined above satisfies conditions in Gordon's inequality. By definition, we have

\begin{equation}\label{d}
\begin{aligned}
E \left(Z_{u,v} - Z_{u',v'} \right)^2 &= E \left( \frac{\left\langle u, Wv\right\rangle}{\sqrt{n}} - \frac{\left\langle u', Wv'\right\rangle}{\sqrt{n}} \right)^2
=\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^p \left( u_i v_j - u'_i v'_j \right)^2 \\&
=\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^p \left( u_i v_j - u'_i v_j + u'_i v_j - u'_i v'_j \right)^2 \\&
=\frac{1}{n} \left( \left\|v\right\|_2^2 \left \| u-u'\right\|_2^2 + \left\|u'\right\|_2^2 \left \|   v-v'\right\|_2^2 + 2\left( \left\|v\right\|_2^2 - \left\langle v, v' \right\rangle\right)\left( \left\langle u, u' \right\rangle - \left\|u\right\|_2^2 \right) \right),
\end{aligned}
\end{equation}

On one hand, since $\left\|v\right\|_2^2 \leqslant 1$, $\left\|u'\right\|_2^2 \leqslant 1$, $(7) \leqslant \frac{1}{n} \left( \left\|u-u'\right\|_2^2 + \left\|v-v'\right\|_2^2\right)$.

One the other hand, we have

\begin{equation}
\label{e}
\begin{aligned}
E\left(Y_{u,v} - Y_{u',v'} \right)^2 &= E \left( \frac{\left\langle \zeta, u - u' \right \rangle}{\sqrt{n}} + \frac{\left\langle \xi, v - v' \right \rangle}{\sqrt{n}} \right)^2 \\&
= \frac{1}{n} \left(\sum_{i = 1}^n\sum_{j = 1}^p (u - u')^2 + \sum_{i = 1}^n\sum_{j = 1}^p (v - v')^2 \right)
= \frac{1}{n} \left( \left\|u-u'\right\|_2^2 + \left\|v-v'\right\|_2^2\right).
\end{aligned}
\end{equation}

Taking  equation (<ref>) and (<ref>) together, we have
$$E \left(Z_{u,v} - Z_{u',v'} \right)^2 \leqslant \frac{1}{n} \left( \left\|u-u'\right\|_2^2 + \left\|v-v'\right\|_2^2\right) = E \left(Y_{u,v} - Y_{u',v'} \right)^2.$$

If $V=V^{\prime}, \text { then } n E\left(\left(Z_{u, v}-Z_{u^{\prime}, v^{\prime}}\right)^{2}\right)=\left\|u-u^{\prime}\right\|_{2}=n E\left(\left(Y_{u, v}-Y_{u^{\prime}, v^{\prime}}\right)^{2}\right).$

By applying Gordon's inequality, we have
$$E\left( \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \inf\limits_{u \in S^{n-1}} Z_{u,v}\right) \leqslant E\left( \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \inf\limits_{u \in S^{n-1}} Y_{u,v}\right).$$

\begin{equation*}
\begin{split}
E \left( T \left( r_{\ell}, r_{u} \right) \right)
E \left( \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \inf\limits_{u \in S^{n-1}} \frac{ \left\langle u, Wv \right\rangle }{\sqrt{n}} \right)
\leqslant
E \left( \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)} \inf\limits_{u \in S^{n-1}} \left( \frac{ \left\langle \xi, v \right\rangle }{\sqrt{n}} + \frac{ \left\langle \zeta, u \right\rangle }{\sqrt{n}} \right)\right)
\\
& =
E \left( \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{ \left\langle \Sigma^{\frac{1}{2}}\xi, \beta \right\rangle }{\sqrt{n}} \right)
- E \left( \frac{ \left\| \zeta \right\|_2 }{\sqrt{n}} \right)
\end{split}
\end{equation*}

Next, we bound these two terms. For the second term, we have $E \left( \frac{ \left\| \zeta \right\|_2 }{\sqrt{n}} \right) = E \left( \sqrt{\frac{\xi_1^2 + \ldots + \xi_n^2}{n}} \right) \geqslant E \left( \frac{|\xi_1| + \ldots + |\xi_n|}{n} \right)= \sqrt{\frac{2}{\pi}}$.  For the first term,  we have
$E \left( \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{ \left\langle \Theta^{\frac{1}{2}}\xi, \beta \right\rangle }{\sqrt{n}} \right) \leqslant
E \left( \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{\phi(\beta) \phi^{\ast}(\Theta^{\frac{1}{2}}\xi) }{\sqrt{n}} \right)$, where $\phi^{\ast}(\Theta^{\frac{1}{2}}\xi)$ is the the dual norm defined before. Since $ \beta \in \mathbb{K} \left( r_{\ell}, r_{u} \right) $, $ g \left( \phi (\beta) \right) \leqslant r_u$, by the definition of $g(t)$, we have

\begin{equation}
\label{f}
\phi(\beta) \leqslant \frac{r_u}{ \left(4\rho(\Theta)\max\limits_{g\in[m]} \frac{1}{w_g \sqrt{h_{\min}^{g}}}
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}.
\end{equation}

Let $\eta_{G_g} = (\Theta^{\frac{1}{2}}\xi)_{G_g} $, to bound $E \left( \max\limits_{g} \left\|(\Theta^{\frac{1}{2}}\xi)_{G_g}\right\|_2 \right) = E \left( \max\limits_{g} \left\|\eta_{G_g}\right\|_2 \right) $. Since $\Theta^{\frac{1}{2}} \xi \sim N(0,\Theta)$, by the properties of normal distribution, its corresponding marginal distribution of $j-\text{th}$ variable $(\Theta^{\frac{1}{2}} \xi)_{j}$ also follows zero mean normal distribution with covariance matrix $\Theta_{jj}$, which is the $j-\text{th}$ diagonal elements of $\Theta$. Therefore, any subset of $\Theta^{\frac{1}{2}} \xi$ is a zero-mean sub-Gaussian random sequence with parameters at most $\rho(\Theta)$. By equation (<ref>) and Lemma <ref>.2.3, we have

\begin{align*}
E \left( \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{ \phi (\beta) \phi^{\ast}  \Theta^{\frac{1}{2}} \xi }{\sqrt{n}}\right)
&\leqslant E \left( \sup\limits_{\beta \in \mathbb{K} \left(r_{\ell}, r_{u}\right)} \frac{r_u}{ \left(4\rho(\Theta)\left(\max\limits_{g\in[m]} \frac{1}{w_g h_{\min}^{g}}\right)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}  \frac{\phi^{\ast} \left(\Theta^{\frac{1}{2}} \xi\right)}{ \sqrt{n} } \right)\\
&= \frac{r_u}{ \left(4\rho(\Theta)\left(\max\limits_{g\in[m]} \frac{1}{ w_g h_{\min}^{g}}\right)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}
E \left(  \frac{\phi^{\ast} \left(\Theta^{\frac{1}{2}} \xi \right)}{ \sqrt{n} }\right)\\
&\leqslant \frac{r_u}{ \left(4\rho(\Theta)\left(\max\limits_{g\in[m]} \frac{1}{w_g h_{\min}^{g}}\right)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}
E \left( \max\limits_{g\in[m]} \frac{1}{\sqrt{n} w_g} \left\|H \left(\Theta^{\frac{1}{2}} \xi\right)_{G_g}\right\|_2\right)\\
&\leqslant\frac{r_u}{ \left(4\rho(\Theta)\left(\max\limits_{g\in[m]} \frac{1}{w_g h_{\min}^{g}}\right)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}
E \left( \max\limits_{g\in[m]} \frac{1}{\sqrt{n} w_g h_{\min}^{g}} \left\| \left(\Theta^{\frac{1}{2}} \xi\right)_{G_g}\right\|_2\right)\\
&\leqslant\frac{r_u}{ \left(4\rho(\Theta)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}
E\left(\left\| \max\limits_{g\in[m]} \left(\Theta^{\frac{1}{2}} \xi\right)_{G_g}\right\|_2\right)\\
& \leqslant\frac{r_u}{ \left(4\rho(\Theta)
\sqrt{\frac{2  (\log m + d_{\max} \log 5)}{n}}\right)}
\left( 2\rho(\Theta) \sqrt{ \left(\log m + d_{\max} \log 5\right) 2 \sigma^2}\right)\leqslant \frac{r_u}{2}
\end{align*}

Therefore, $E\left[T\left(r_{\ell},r_u\right)\right] \leqslant -\sqrt{\frac{2}{\pi}} + \frac{r_u}{2}$. Next we want to bound  $P \left( T \left( r_{\ell}, r_u \right) \geqslant - \frac{1}{2} +  r_u \right)$ based on the bound of this expectation. To apply Lemma <ref>.2.4, we first show that, the $f=T(r_l,r_u)$, a function of the random variable $W$ is a $\frac{1}{\sqrt{n}}$-Lipschitz function and without making confusion, we denote the corresponding function as $T(W)$. For any standard Gaussian matrix $W_1$ and $W_2$, we have

\begin{align*}
\left| T(W_1) - T(W_2) \right| & = \left| \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \inf\limits_{u \in S^{n-1}} \frac{\left\langle u,W_1 v \right\rangle }{\sqrt{n}} - \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \inf\limits_{u \in S^{n-1}} \frac{\left\langle u, W_2 v\right\rangle }{\sqrt{n}} \right| \\
& =  \left| \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \left(-\frac{\left\|W_1v\right\|_2 }{\sqrt{n}}\right) - \sup\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}  \left(-\frac{\left\|W_2v\right\|_2 }{\sqrt{n}}\right) \right| \\
& =  \left|  \left(-\inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_1v\right\|_2 }{\sqrt{n}}\right) -  \left(-\inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_2v\right\|_2 }{\sqrt{n}}\right) \right| \\
& =  \left|  \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_2v\right\|_2 }{\sqrt{n}} - \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_1v\right\|_2 }{\sqrt{n}} \right|.
\end{align*}

Suppose that  $\frac{\left\|W_1v_1\right\|_2 }{\sqrt{n}} = \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_1v\right\|_2 }{\sqrt{n}}$ and
$\frac{\left\|W_2v_2\right\|_2 }{\sqrt{n}} = \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_2v\right\|_2 }{\sqrt{n}}$.

Case 1 If $\left\|W_1v_1\right\|_2 > \left\|W_2v_2\right\|_2$, then we have

\begin{align*}
\left| T(W_1) - T(W_2) \right| & =  \left|  \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_2v\right\|_2 }{\sqrt{n}} - \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_1v\right\|_2 }{\sqrt{n}} \right|\\
& =  \frac{\left\|W_1v_1\right\|_2 - \left\|W_2v_2\right\|_2}{\sqrt{n}} \leqslant
\frac{\left\|W_1v_2\right\|_2 - \left\|W_2v_2\right\|_2}{\sqrt{n}}\\
&\leqslant \frac{\left\|(W_1-W_2)v_2\right\|_2}{\sqrt{n}} \leqslant \frac{\left\|W_1 - W_2\right\|_F}{\sqrt{n}}\\.
\end{align*}

Case 2 If $\left\|W_1v_1\right\|_2 \leqslant \left\|W_2v_2\right\|_2$, then we have

\begin{align*}
\left| T(W_1) - T(W_2) \right| & =  \left|  \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_2v\right\|_2 }{\sqrt{n}} - \inf\limits_{v \in \tilde{\mathbb{K}} \left(r_{\ell}, r_{u}\right)}\frac{\left\|W_1v\right\|_2 }{\sqrt{n}} \right|\\
& =  \frac{\left\|W_2v_2\right\|_2 - \left\|W_1v_1\right\|_2}{\sqrt{n}} \leqslant
\frac{\left\|W_2v_1\right\|_2 - \left\|W_1v_1\right\|_2}{\sqrt{n}}\\
&\leqslant \frac{\left\|(W_1-W_2)v_1\right\|_2}{\sqrt{n}} \leqslant \frac{\left\|W_1 - W_2\right\|_F}{\sqrt{n}}\\.
\end{align*}

where $\left\|.\right\|_F$ represent the Frobenious norm of a matrix. Thus under the Euclidean norm, $T(W)$ is a $\frac{1}{\sqrt{n}}$-Lipschitz function. Therefore, by lemma <ref>.2.3, we have

\begin{equation*}
P(T(r_l,r_u)- E(T(r_l,r_u)) \geqslant t) \leqslant e^{-nt^2/2}, \forall t\geqslant 0
\end{equation*}

Set t = $\sqrt{\frac{2}{\pi}} - \frac{1}{2}+\frac{r_u}{2} \geqslant \frac{1}{4} + \frac{r_u}{2}$,
we have, $E(T(r_l, r_u)) + t \leqslant -\frac{1}{2} + r_u$ and $P \left[ T \left( r_{\ell}, r_u \right) \geqslant - \frac{1}{2} +  r_u \right] \leqslant e^{-\frac{n}{32}} e^{-\frac{n}{8} r_u^2},$ which is actually the Lemma <ref>.2

Lemma <ref>.2.1  (Gordon's Inequality)
Let $\left\{Z_{u, v}\right\}_{u \in U, v \in V}$ and $\left\{Y_{u, v}\right\}_{u \in U, v \in V}$ be zero-mean Gaussian process indexed by a non-empty index set $I=U \times V$. If

1. $E\left(\left(Z_{u, v}-Z_{u^{\prime} v^{\prime}}\right)^{2}\right) \leq E\left(\left(Y_{u, v}-Y_{u^{\prime},v^{\prime}}\right)^{2}\right) \text { for all pairs }(u, v) \operatorname{and}\left(u^{\prime}\, v^{\prime}\right) \in I$

2. $E\left(\left(Z_{u, v}-Z_{u^{\prime} v}\right)^{2}\right)=E\left(\left(Y_{u, v}-Y_{u^{\prime},v}\right)^{2}\right),$

then we have $E(\max\limits_{v \in V} \min\limits_{u \in U} Z_{u,v}) \leq E(\max\limits_{v \in V} \min\limits_{u \in U} Y_{u,v}).$

Lemma <ref>.2.2 Suppose that $\alpha = (\alpha_{1},...,\alpha_{d}),$ where each $\alpha_{i}, i \in [d]$   is a zero-mean sub-Gaussian random variable with parameter at most $\sigma^2$, then for any $t\in \mathbb{R}$, we have  $E \left( \exp\left(t\left\|\alpha\right\|_2\right) \right) \leqslant 5^d \exp \left(2 t^2 \sigma^2\right).$

Lemma <ref>.2.3 Suppose that $\alpha = (\alpha_{1},...,\alpha_{d}),$ where each $\alpha_{i}, i \in [d]$   is a zero-mean sub-Gaussian random variable with parameter at most $\sigma^2$, and for a given group structure $G$, let $\left\|\alpha_{G_g} \right\| $ be the corresponding group norm, $m$ be the number of groups and $d_{max}$ be the maximum group size, then

\begin{equation*}
E\left(\max\limits_{g} \left\|\alpha_{G_g} \right\| \right) \leqslant 2 \sqrt{2 \sigma^2 \left( \log m +d_{max} \log 5\right)}\\
\end{equation*}

Lemma <ref>.2.4 (Theorem 2.26 in [Wainwright, 2019]): Let $x = \left(x_1, \cdots, x_n\right)$ be a vector of i.i.d standard Gaussian variable, and $ f: \mathbb{R}^n \to \mathbb{R} $ be a $L$-Lipschitz, with respect to the Euclidean norm, then $f(x)-E f(x)$ is sub-Gaussian with parameter at most $L$, and hence $ P\left( \left(f(x) - {E}\left[f(x)\right)\right) \geqslant t \right] \leqslant e^{-\frac{t^2}{2L^2}}$, $\forall t\geqslant 0$.

§.§.§ Proof of Lemma <ref>.2.2

We can find a $\frac{1}{2}$ - cover  of $S^{d-1}$, and for any $u\in S^{d-1}$ in the Euclidean norm with cardinally at most $N \leqslant 5^d$, say there exists $u^{q(u)} \in \left\{u^1, \ldots, u^N\right\}$, such that $\left\|u^{q(u)}-u\right\|_2\leqslant\frac{1}{2}$.

By the variational representation of the $\ell_2$ norm, we have $\left\|\alpha\right\|_2  = \max\limits_{u \in S^{d-1}} \left\langle u,\alpha\right\rangle \leqslant \max\limits_{q(u)\in [N]} \left\langle u^{q(u)},\alpha \right\rangle + \frac{1}{2} \left\|\alpha\right\|_2 $. Therefore, $\left\|\alpha\right\|_2 \leqslant 2 \max\limits_{q(u)\in [N]} \left\langle u^{q(u)},\alpha \right\rangle$.  Consequently,

\begin{align*}
E\left(\exp\left(t\left\|\alpha\right\|_2 \right)\right)  &\leqslant E \left(\exp \left(2 t \max\limits_{q\in [N]} \left\langle u^{q},\alpha \right\rangle \right)\right)
= E \left(\max\limits_{q\in [N]}\exp \left(2 t  \left\langle u^{q},\alpha \right\rangle \right)\right) \\
& \leqslant  \sum\limits_{q=1}^{N} E \left( \exp \left( 2 t \left\langle u^{q}, \alpha \right\rangle \right)\right) \leqslant 5^d \exp \left( \frac{ 4 t^2 \sigma^2 }{ 2 } \right)
\leqslant 5^d \exp \left(2 t^2 \sigma^2\right).  \\
\end{align*}

§.§.§ Proof of Lemma <ref>.2.3

For any $t > 0$, by Jensen's inequality, we have $\exp\left(t E \left( \max\limits_{g} \left\| \alpha_{G_g} \right\| \right)\right) \leqslant E \left( \exp \left( t \max\limits_{g} \left\| \alpha_{G_g} \right\|_2 \right)\right) $

$ = E \left( \max\limits_{j} \exp \left( t \left\| \alpha_{G_g} \right\|_2 \right) \right)  \leqslant \sum\limits_{j=1}^{m} E \left( \exp \left( t \left\|\alpha_{G_g}\right\|_2\right)\right) \leqslant \sum\limits_{j=1}^{m} 5^{d_g} \exp \left( 2 t^2 \sigma^2 \right) \leqslant m \cdot 5^{d_{\max}} \cdot \exp(2 t^2 \sigma^2) $.

By taking $\log$ at both sides, we have
$  tE \left( \max\limits_{g} \left\| \alpha_{G_g}\right\| \right) \leqslant \log m + d_{\max} \log 5 + 2 t^2 \sigma^2$. That is $E \left( \max\limits_{g} \left\| \alpha_{G_g}\right\| \right) \leqslant \frac{ \log m + d_{\max} \log 5 + 2t^2 \sigma^2 }{ t }$.

Let $ t = \sqrt{\frac{ \log m + d_{\max} \log 5 }{ 2 \sigma^2}} $, we have $  E \left( \max\limits_{g} \left\| \alpha_{G_g}\right\| \right) \leqslant 2 \sqrt{ \left(\log m + d_{\max} \log 5\right) 2 \sigma^2}$.

§.§ Proof of Theorem <ref>

Given $m,s_g \in \mathbb{R}$, define the set
A=\left\{a \in\{0,1\}^{m} \mid \sum_{j=1}^{m} a_{j} \leq s_{g}\right\},
then the $\sqrt{\frac{s_g}{2}}$-packing number of set $A \geqslant
\frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - \hspace{0.2cm}2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}}
$, and $\log \left( \frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - \hspace{0.2cm}2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}} \right) \asymp s_g \log (\frac{m}{s_g}).$

The $\sqrt{\frac{2ds_g}{5}}$-packing number of  $\Omega(G,s_g) \gtrsim \frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - 2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}} \cdot (\sqrt{2})^{ds_g},$ and
$$\log \left( \frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - 2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}} \cdot (\sqrt{2})^{ds_g} \right) \asymp s_g(d + \log (\frac{m}{s_g})).$$

First, take $N$ points $\omega^{(1)}, \cdots, \omega^{(N)}$  from $\Omega(G,s_g)$ such that $\left\|\omega^{(i)}-\omega^{(j)}\right\|>\sqrt{\frac{2ds_g}{5}}$ for all distinct $i,j$. Clearly we have $\left\|\omega^{(i)}-\omega^{(j)}\right\| \leq \sqrt{4s_g d}$.

Now denote $\beta^{(i)}=r \omega^{(i)}$,  we have

\frac{2ks_gr^2}{5} \leq\left\|\beta^{(i)}-\beta^{(j)}\right\|_{2}^{2} \leq 4 s_g d r^{2}.

Next, denote $y^{(i)}=X \beta^{(i)}+\varepsilon$ for $1 \leqslant i \leqslant N$, we consider the Kullback-Leibler divergence between different distribution pairs:

D_{K L}\left((y^{(i)}, X),(y^{(j)}, X)\right)=E_{(y^{(j)}, X)}\left[\log \left(\frac{p\left(y^{(i)}, X\right)}{p\left(y^{(j)}, X\right)}\right)\right] \text {, }

Where $p\left(y^{(i)}, X\right)$ is the probability density of $\left(y^{(i) }, X\right).$ Conditioning on $X$, we have

$$E_{(y^{(j)},X)}\left[\log\left(\frac{p\left(y^{(i)}, X\right)}{p\left(y^{(j)}, X\right)}\right) \mid X\right]=\frac{\|X(\beta^{(i)}-\beta^{(j)}) \|_2^2}{2\sigma ^2}$$

Thus for $1 \leq i \neq j \leq N,$

\begin{aligned}
&D_{K L}\left(\left(y^{(i)}, X\right),\left(y^{(j)}, X\right)\right)=E_{X} \frac{\left\|X\left(\beta^{(i)}-\beta^{(j)}\right)\right\|_{2}^{2}}{2 \sigma ^{2}}=\frac{\left.n (\beta^{(i)}-\beta^{(j)}\right)^{\top} \Sigma \left(\beta^{(i)}-\beta^{(j)}\right)}{2 \sigma ^{2}} \\
&\leq \frac{3c_3\left\|\beta^{(i)}-\beta^{(j)}\right\|_{2}^{2}}{2 \sigma ^{2}} \leq \frac{2c_3 n d r^{2} s_g}{\sigma ^{2}}
\end{aligned}

From Lemma <ref>, we have  $\log N \asymp s_g\left(d+\log \frac{m}{s_g}\right)$, by setting $\frac{\frac{n d r^{2} s_g}{\sigma^{2}}+\log 2}{\log N} = \frac{1}{2},$ we have
r \gtrsim \sqrt{\frac{\left(d +\log \frac{m}{s_g}\right) \sigma^{2}}   {3n d}}.

By generalized Fano's Lemma, we have $\inf\limits_{\hat{\beta}}\sup\limits_{\beta} E\|\hat{\beta}-\beta\|_{2} \geqslant \sqrt{\frac{2r^2ks_g}{5}}\left(1-\frac{\frac{1 n d r^{2} s_g}{\sigma^{2}}+\log 2}{\log N}\right)$, consequently

\inf  \sup E\|\hat{\beta}-\beta\|_{2}^{2} \geq \left(\inf\sup E\|\hat{\beta}-\beta\|_{2}\right)^{2} \gtrsim \frac{\sigma^2\left(s_g(d +\log (\frac{m}{s_g}))\right)}{n},

§.§.§ Proof of Lemma <ref>

Notice that the cardinality of $A$ is $\left(\begin{array}{l}m \\ s_{g}\end{array}\right)$. Denote the hamming distance between any two points $x, y \in A$ by

h(a, b)=|\left\{j: a_{j} \neq b_{j}\right\}|.

Then for a fixed point a $\in A$,

$$|\left\{b \in A, h(a, b) \leq \frac{s_{g}}{2}\right\} = \left(\begin{array}{c}
m \\
\lfloor\frac{s_g}{2} \rfloor
\end{array}\right)\cdot 2^{	\lfloor\frac{s_g}{2} \rfloor}|.$$

In fact, all elements $b \in A$ with $ h(a, b) \leq \frac{s_{g}}{2}$ can be obtained as follows. First, take any subset $J \subset [m]$ of cardinality  $\left\lfloor\frac{s_g}{2}\right\rfloor$, then set $a_j = b_j$ for $j \notin J$ and choose $b_j \in \{0,1\}$ for $j \in J$.

Now let $A_{s}$ be any subset of $A$ with cardinality at most
T=\frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - 2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}},
then we have

$$|\left\{b \in A \mid \text{there exist}\hspace{0.2cm} a \in A_{s}\right. \text{with} \left.h(a, b) \leq \frac{s_{g}}{2}\right\} \leq (|A_s|) \cdot \left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}| <  |A|.$$

It implies that one can find an element $b \in  A \hspace{0.2cm} \text{with}\hspace{0.2cm}  h(a, b) > \frac{s_g}{2} \hspace{0.2cm} \text{for all}\hspace{0.2cm}  a \in A_s$.  Therefore one can construct a subset $A_s$  with $|A_s| \geq T$ and the property $h(a, b) > \frac{s_g}{2}$ for any two distinct elements $a, b \in A_s$.

On the other hand, $h(a, b)>\frac{s_{g}}{2}$ implies  $\|a-b\|>\sqrt{\frac{s_g}{2}}$. Therefore, there exists at least $T$ points in $A$ such that the distance between any two points is greater than $\sqrt{\frac{s_g}{2}}$.

Moreover, since
\frac{\left(\begin{array}{c}
m \\
\end{array}\right)}{\left(\begin{array}{c}
m \\
\end{array}\right)}=\frac{\left\lfloor\frac{s_g}{2}\right\rfloor!\left(m-\lfloor\frac{s_g}{2}\rfloor\right)!}{s_g !(m-s_g) !}=\frac{\left(m-s_{g}+1\right) \cdots m-\left\lfloor\frac{s_{g}}{2}\right\rfloor}{\left(\left\lfloor\frac{s_g}{2}\right\rfloor+1\right) \cdots s_{g}}=\prod_{j=1}^{\lceil\frac{s_g}{2}\rceil} \frac{m-s _g+j}{\left\lfloor\frac{s_g}{2}\right\rfloor+j}
$, we have
\left(\frac{\left. m-\lfloor\frac{s_g}{2}\right\rfloor}{2 s _g}\right)^{\left\lfloor \frac{s_g}{2}\right\rfloor} \left.\leqslant \frac{\left(\begin{array}{c}
m \\
\end{array}\right)}{\left(\begin{array}{c}
m \\
\left\lfloor\frac{s_g}{2}\right\rfloor
\end{array}\right) 2^{\frac{s_g}{2}}} \leqslant\left(\frac{m-s_g+1}{\lceil s_g \rceil}\right)^{\lceil \frac{s_g}{2}  \rceil}\right.,$$

and therefore we can find $C_1, C_2,$ such that $
C_{1} s_g \log (\frac{m}{s_g}) \leqslant \log T \leqslant {C_2s_g \log (\frac{m}{s_g}})$, so that
$$\log \left( \frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - \hspace{0.2cm}2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}} \right) \asymp s_g \log (\frac{m}{s_g}).$$

§.§.§ Proof of Lemma <ref>

Given a group support $a \in A$,  define $k_{a} = |\left\{i \mid i \in \left(\bigcup\limits_{\{g \mid a_g = 0\}} G_g \right)^{C}   \right\}|$, and the set

$$\Omega^{(a)} =\left \{\omega \in \mathbb{R}^p \mid \omega_i =0 \text{ if } i \in \bigcup\limits_{\{g \mid a_g=0\}}G_g, \omega_i \in \{-1,1\} \text{ if }   i \in \left(\bigcup\limits_{\{g \mid a_g = 0\}} G_g \right)^{C} \right \}$$

Notice that $ \Omega^{(a)} \subseteq  \Omega(G,s_g)$, and  $|\Omega^{(a)}| = 2^{k_a}$. Also denote the hamming distance between $x, y \in \Omega^{(a)}$ by

h(x, y)=|\left\{j: x_{j} \neq y_{j}\right\}|.

then for any fixed $x \in \Omega_G^{(a)}$,

$$\left|\{y \in \Omega^{(a)}, h(x, y) \leq \frac{k_a}{10}\}\right| =\sum\limits_{j = 0}^{\lfloor\frac{k_a}{10} \rfloor}\left(\begin{array}{c}
k_a  \\
\end{array}\right)$$

Let $\Omega_{s}^{(a)}$ be any subset of $\Omega^{(a)}$ with cardinality at most
N^{(a)}=\frac{2^{k_a} - 2}{\sum\limits_{j = 0}^{\lfloor\frac{k_a}{10} \rfloor}\left(\begin{array}{c}
k_a  \\
\end{array}\right)}
$,  then

$\left|\{y \in \Omega^{(a)} \mid \text{there exist} \hspace{0.2cm} x \in \Omega_{s}^{(a)} \text{ with } h(x, y) \leq  \frac{k_a}{10}  \}\right|$ $\leq \left(|\Omega_{s}^{(a)}|\right) \sum\limits_{j = 0}^{\lfloor\frac{k_a}{10} \rfloor}\left(\begin{array}{c}
k_a  \\
\end{array}\right)< |\Omega^{(a)}|.$

On the other hand, $ h(x,y) > \frac{k_a}{10}$ implies  $\|x-y\|  \geq \sqrt{\frac{2k_a}{5}}$. Therefore, there exists at least $N^{(a)}$ points in $\Omega^{(a)}$ such that the distance between any two points is greater than $\sqrt{\frac{2k_a}{5}}.$

As stated in Chapter 9 in [Graham et al., 1994],

\sum\limits_{j \leq \lfloor\frac{k_a}{10} \rfloor}\left(\begin{array}{c}
k_a  \\
\end{array}\right) < \frac{9}{8}\left(\begin{array}{c}
k_a  \\
\lfloor\frac{k_a}{10} \rfloor
\end{array}\right) \leq \frac{9}{8}(10e)^{\frac{k_a}{10}} \leq \frac{9}{8}2^{\frac{k_a}{2}},
we have $N^{(a)}=\frac{2^{k_a} - 2}{\sum\limits_{j \leq \lfloor\frac{k_a}{10} \rfloor}\left(\begin{array}{c}
k_a  \\
\end{array}\right)} >  \frac{8}{9}2^{\frac{k_a}{2}} \gtrsim (\sqrt{2})^{k_a}.$

Notice that $k_a$ depends on the predefined groups and the group support $a$, the range is $0 \leq k_a \leq s_gd$. Since Lemma <ref> aims to find a lower bound for all possible overlapping patterns, we need to consider the upper bound of $k_a$.

On the other hand, based on Lemma <ref>,  we can find at least $T$ points in $A$ such that the distance between any two points is greater than $\sqrt{\frac{s_g}{2}}$. For $\{a_1,\cdots,a_T\}$ group supports, if there is a group structure such that we could find at least $\frac{8}{9}(\sqrt{2})^{s_gd}$ on each group support, and the distance between every pair of these points is greater than $\sqrt{\frac{2s_gd}{5}}$, then Lemma <ref> is proved.

Considering $m$ non-overlapping groups, $k_a = s_gd$ for each group support $a$. In addition,  given any two group support $a, b $ with $\|a - b\|>\sqrt{\frac{s_{g}}{2}},\|x-y\|>\sqrt{\frac{ds_g}{2}}>\sqrt{\frac{2ds_g}{5}}$ for any $x \in \Omega^{(a)}$ and $y \in \Omega^{(b)}$. Thus, considering all possible overlapping pattern, we can find at least $  \frac{\left(\begin{array}{l}m \\ s_{g}\end{array}\right) - 2}{\left(\begin{array}{c}
m \\
\end{array}\right) \cdot 2^{\frac{s_{g}}{2}}} \cdot \frac{8}{9}(\sqrt{2})^{ds_g}$ point in  $\Omega(G,s_g)$, such that the distance between every pair of points is greater than  $\sqrt{\frac{2ds_g}{5}}$.