Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
61,034 characters · 18 sections · 61 citation commands
Generalized Information Criteria for Structured Sparse Models
I this paper we derive a family of Generalized Information Criteria tailored for structured sparse models and show its statistical properties such as finite sample selection bounds and path-consistency. Sparsity is usually related to high dimensional models, but one can also think about it in low dimension settings. In fact, model selection is frequently related to selecting a sparse model in some sense: some of the variables, or groups of variables, are not included or we estimate the number of factors on a factor regression model. What we learn from high-dimensional statistics literature is that the sparsity pattern is often connected to regularizing norms, such as $L_1$ for variable selection in linear regressions, $L_{2,1}$ for selecting groups of variables and the nuclear norm for shrinking eigenvalues of a low rank matrix. These three examples illustrate how sparsity can be structured in a sense that we have deterministic information about the model that is embeded in the collection of models we are choosing from.
Model selection in high dimensions poses a challenge as the number of candidate models is very large. In these cases one indeed uses structured sparse norms to help estimating models, and controls the sparsity using a regularization parameter, i.e., indexes the candidate models along a path. We call path consistency the property that there exists a regularization parameter that indeed corresponds to teh target model. We show how to construct this sequence and that is indeed contains the target model. As we combine both cases we indeed can use the GIC to select the regularization parameter in high dimensions, meaning that our results are valid in a broad sense.
We study both asymptotic and non-asymptotic properties of generalized information criteria when the model has a structured sparsity pattern. The method contemplates situations where the ambient dimension of the problem $p$ is larger, in order, than the sample size $n$. In such cases, we will select the regularization parameter of a regularized $m$-estimation problem. This class of problems is the concern of high-dimensional statistics and frequently arises in economics and finance, as well as astronomy and biology, among other areas.
Estimating high-dimensional sparse models is infeasible unless one imposes low-dimensional constraints on the model space. The most popular example is variable selection within a linear regression problem where only a small number (${s\ll p}$) of variables are relevant. In this case, sparsity is unstructured as any variable can individually enter or not the model. In structured sparsity there is a natural structure to the problem. For instance, in a group sparse regression, we select variables in groups, whereas in low rank matrix estimation individual elements are not necessarily sparse, even if its singular values are. These examples illustrate what we call structured sparsity.
We estimate model parameters by minimizing some empirical loss function that incorporates a structured sparsity penalty. As such, we are within the regularized $m$-estimation framework. Our goal is to select an adequate model subspace from a large collection of candidate models, satisfying sparsity constraints.
For a comprehensive exposition of the area of high dimensional statistics, including methods, algorithms and theory, see the books buhlmann2011statistics,tibshirani2015statistical and, for the non-asymptotic perspective adopted in the paper, see wainwright2019High.
The Akaike Information Criterion (AIC) AkaikeAIC, cross-validation stone1974,cravenwhaba1978, and Schwarz Bayesian Information Criterion (BIC) schwarz1978 are traditional model selection methods. However, they are not consistent in selecting large model spaces bromanspeed2002,casellaetal2009,wangetal2009,zhangetal2010,shetran2019. Several methods have been proposed to address this limitation in high-dimensional settings.
For instance, chenchen2008,chenchen2012 argue that BIC's uniform prior on candidate models causes over-selection and propose the Extended BIC (EBIC), which uses an alternative prior distribution on model subspaces for variable selection. wangetal2009 suggest adding a penalty term to BIC to account for candidate model inflation, which leads to the Generalized Information Criterion (GIC). Some authors propose alternative methods, such as gaosong2010's gaosong2010 Composite Likelihood BIC, zhangshen2010's zhangshen2010 Corrected Risk Inflation Criterion, and shetran2019's shetran2019 new cross-validation scheme for sparse reduced rank regression that achieves optimal rate.
kimjeon2016 extend previous results beyond the quadratic loss or negative log-likelihood and demonstrate that GIC consistently selects the correct model for a broad range of loss functions.
In practice, it is often impossible to enumerate all candidate model subspaces in high-dimensional settings. Regularized $m$-estimators construct a path of candidate models indexed by a tuning parameter or regularization parameter, which may depend on the model space's complexity and sample size. These include LASSO or basis pursuit tibshirani1996,chenetal2001, SCAD fan2001variable, adaptive LASSO zou2006, group LASSO yuanlin2006, graphical LASSO for graphs and inverse covariances nMpB2006,yuanlin2007,friedmanetal2008, among others.
Numerous studies propose consistent model selection criteria for the regularization parameter. A method is path-consistent if the solution path indexed by the regularization parameter contains the true model, and the selection criteria are consistent. Most often, the proposed criteria use either the quadratic loss or Kullback-Leibler loss (negative log-likelihood function) with LASSO, adaptive LASSO, or SCAD regularization functions. chenchen2008,chenchen2012 use the EBIC within a regularized maximum likelihood framework with SCAD and LASSO penalties. wangetal2007,wangetal2009 show that their GIC consistently selects the correct model using the quadratic loss and LASSO or SCAD penalties.zhangshen2010 propose the high-dimensional BIC (HBIC) for selecting the regularization parameter in sparse regression problems with quadratic loss and SCAD penalty.
Other studies focus on specific families of models. For example, nicai2018 study selecting the tuning parameter in a penalized Cox proportional hazard model with SCAD penalty, foygeldrton2010 derive an EBIC for Gaussian graphical models, and leeetal2014 derive an EBIC for penalized quantile regression. kimjeon2016 consider a broader class of loss functions called quadratically supported risk and show path-consistency of their GIC for the LASSO and SCAD under a penalized least squares framework.
Current high-dimensional model selection methods do not take into account the sparsity pattern of the problem. In this paper we develop a formulation of the Generalized Information Criterion that accommodates the sparsity pattern, develop its non-asymptotic selection bound, and demonstrate its consistency and path-consistency for recovering the sparsity pattern. We apply our approach to group sparse GLM estimation and low rank matrix estimation, which have been studied in the literature, and connect our assumptions to those used to establish oracle bounds.
As motivation, consider three matrices with distinct sparsity constraints: (1) low rank, (2) element-wise sparsity, and (3) group row sparsity. In (1) the entries of the matrix may not be sparse in the traditional element-wise way, whereas in (2) the matrix may be full rank. Similarly, in group row sparsity (3) we shrink entire rows of the matrix while in element-wise sparsity (1) individual elements will be null within the same row. Information about the sparsity pattern is included in our estimation problem through an appropriate regularization norm. Even though the same loss used in all problems, the regularizing penalties are quite different. In (1) we use the nuclear norm, in (2) the element-wise $L_1$ norm, and in (3) the $L_1/L_2$ row norm, often used in group-LASSO.
In this paper we address the following questions: (a) how should one incorporate the sparsity pattern in the model selection criterion? (b) can this information criterion be used to to select the regularization parameter $\lambda$? (c) what are the finite sample and asymptotic behaviors of the method?
sNpRmWbY2012 introduce a unified framework for establishing properties of regularized $m$-estimators in high-dimensions. The authors identify two key properties that guide convergence rates: restricted strong convexity and decomposability. The restricted strong convexity depends on the interaction of the regularizer with the loss function. The decomposability property of the regularizer requires the regularizing norm to be additive in a pair of of orthogonal subspaces. Authors derive sharp bounds on the error norm under these two key properties and other rate restrictions.\footnote{Traditionally $L_2$ for vectors and Frobenius norm for matrices.} Results within this framework are restricted to regularization functions that are norms, such as the LASSO, Group LASSO, low lank recovery, among other, and does not include the SCAD and Elastic Net penalties.
Our formulation of the Generalized Information Criterion accounts for the sparsity pattern in the model. We define a penalty that depends on a subspace compatibility constant and some decreasing sequence that is related to the regularization norm used to capture the sparsity. We demonstrate that our proposed GIC is model selection consistent and also path-consistent for selecting the regularization parameter $\lambda$. Our conditions are connected to those in kimjeon2016 and sNpRmWbY2012, and are readily satisfied by many loss functions and penalties in the high-dimensional statistics literature wainwright2019High.
To illustrate the generality of our approach, consider a regularized generalized linear regression setting with LASSO or group LASSO penalty. In the former case, the penalty on the GIC is proportional to $\frac{\log p}{n}s$, where $s$ is the number of non-zero variables in the model, while in the latter case, the penalty function is proportional to $(\frac{m}{n} + \frac{\log g}{n})s_g$, where $s_g$ is the number of selected groups and $m$ the group size. The penalty function in the GIC for group LASSO takes into account the number and size of the groups and is smaller than that for LASSO.
Let $\|u\| = \langle u,u\rangle^{1/2}$ be the norm induced by the inner product $\langle\cdot,\cdot\rangle$ in the Euclidean space $\Omega$. Given a subspace $\mathcal{M}\subseteq\Omega$ and a point $u\in\Omega$, $u_\mathcal{M} = \Pi_\mathcal{M}(u) = \operatorname*{\mathsf{arg\,min}}_{v\in\mathcal{M}}\|u-v\|$ is the projection of $u$ onto $\mathcal{M}$. Denote the orthogonal complement of $\mathcal{M}$ on ${\mathbb{R}}^p$ as $\mathcal{M}^\perp :=\{u\in\Omega|\langle u,v\rangle = 0, \forall v\in\mathcal{M}\}$. Given some norm $\Phi$ on $\Omega$, its associated dual norm is $\Phi^*(u) = \sup_{\{v:\Phi(v)\le 1\}}\langle u,v\rangle$. For two sets $A,B\subset \Omega$, we define the operation $A+B:=\{u+v|(u,v)\in A\times B\}$. Finally, $\mathfrak{M}$ collects model subspaces.
Let ${\bf Z}^n = \{Z_i\}_{i=1}^n$ be a sequence of observations taking values on an Euclidean space $\mathcal{Z}$ and drawn from some distribution $\mathbb{P}$. We are interested in learning a $p$-dimensional parameter vector $\theta^*\in\Omega$, where, typically, $\Omega = {\mathbb{R}}^p$. Given a convex loss function $\mathcal{L}: \Omega \times \mathcal{Z}^{n} \to {\mathbb{R}}$, we aim to estimate the unique minimizer of the population risk \[ \theta^* = \operatorname*{\mathsf{arg\,min}}_{\theta \in \Omega} \mathbb{E}[\mathcal{L}(\theta;{\bf Z}^n)]. \] The dependence of $\mathcal{L}$ on ${\bf Z}^n$ is omitted whenever it is clear from the context.
In high-dimensional statistics we often impose restrictions on the parameter space. In other words, the parameter of interest $\theta^*$ does not reside in a $p$-dimensional space, but rather in a smaller subspace of $\Omega$ denoted $\mathcal{M}_*$, meaning that $\theta^* = \theta^*_{\mathcal{M}_*}$. This subspace incorporates the low dimensional constraints imposed to the problem. If $\mathcal{M}_*$ was known beforehand, we could estimate $\widehat{\theta}(\mathcal{M}_*) \in \operatorname*{\mathsf{arg\,min}}_{\theta\in\mathcal{M}^*}\mathcal{L}(\theta)$ and our problem would be solved. Unfortunately, $\mathcal{M}_*$ has to be estimated from a very large collection of candidate subspaces.
In order to construct the GIC penalty that incorporate sparsity constraints we use the notion of decomposable norms and subspace compatibility constant from sNpRmWbY2012.
For sake of simplicity, we denote $\bar{\mathcal{M}}$ as the smallest subspace containing $\mathcal{M}$ such that decomposability holds, but results are still valid even if $\bar{\mathcal{M}}$ is not the smallest possible.
The norm $\Phi$ is decomposable with respect to a pair of subspaces $(\mathcal{M},\bar{\mathcal{M}}^\perp)$ if it satisfies the decomposability property. sNpRmWbY2012 and wainwright2019High show that many commonly used norms, such as the $L_1$ (LASSO), the group LASSO ($L_2/L_2$), the nuclear norm for matrices, and overlapping group norms are decomposable with respect to $(\mathcal{M},\bar{\mathcal{M}}^\perp)$ selected in a way to take into consideration distinct types of low dimensional restrictions.
The subspace compatibility constant, or subspace Lipschitz constant, ties up the error norm, the decomposable norm, and the restricted subspace. It can be interpreted as a scaling constant necessary to fit every unitary vector in $\mathcal{M}$ to a scaled unit ball in the $\Phi$-norm.
The Subspace Compatibility Constant is connected to fundamental units of the model subspace $\mathcal{M}$ and corresponds to the scaling factor required to translate the size of any vector in $\mathcal{M}$ from $\Phi$-norm to the $\|\cdot\|$-norm. Larger, more complex models subspaces require larger constants. We use the square of this quantity as a measure of model complexity, which reduces to known cases in many settings, such as the LASSO sNpRmWbY2012.
Recall that we aim to estimate $\mathcal{M}_*$, the low-dimensional subspace in which the population parameter $\theta^*$ takes values. Define the set $\mathfrak{M}$ as the collection of all (paired) model subspaces $(\mathcal{M},\bar{\mathcal{M}}^\perp)$ with respect to which $\Phi$ is decomposable. We emphasize that we take $\mathcal{M}\subseteq\bar{\mathcal{M}}$ to be the smallest possible, hence selecting $\mathcal{M}$ is equivalent to selecting the pair $(\mathcal{M},\bar{\mathcal{M}}^\perp)$.
The size of $\mathfrak{M}$ can be very large, prompting us to restrict the search space to a smaller collection chenchen2012, kimetal2012, kimjeon2016. Suppose the subspace compatibility constant $\Psi(\mathcal{M}_*)\leq\psi_n$, for some $\psi_n>0$, and denote the restricted collection of model subspaces $\mathfrak{M}_{\psi_n^2} = \{\mathcal{M}\in \mathfrak{M} \mid \Psi^2(\mathcal{M}) \leq \psi_n^2\}$. This set collects all models that are not too large. It is equivalent to restricting the number of active regressors in a linear regression problem.
For all model subspaces $\mathcal{M}\in \mathfrak{M}_{\psi_n^2}$, let
denote the estimated parameter restricted to the model subspace $\mathcal{M}$. Given a non-increasing sequence of positive numbers $a_n$ (that may depend on the dimension of $\mathcal{M}$) we select the model subspace $\widehat{\mathcal{M}}_{a_n}$ minimizing $GIC_{a_n}(\mathcal{M})$ on $\mathfrak{M}$. More precisely
where $\Psi^2(\mathcal{M})$ is the compatibility constant between $\Phi$ and the error norm evaluated at $\mathcal{M}$. We denote $GIC_{a_n}(\mathcal{M}) = \mathcal{L}(\hat{\theta}(\mathcal{M})) + a_n\Psi^2(\mathcal{M})$.
We work with a specific class of Restricted Strongly Convex (RSC) functions, treated in raskutti2010restricted, in the case of vectors, in raskutti2011minimax and negahban2011estimation in the case of matrices, and, more generally in wainwright2019High. This class is similar to the quadratic supported risk class employed in kimjeon2016 and is a particular case of the RSC class defined in sNpRmWbY2012.
In high dimensions it is nearly impossible for strong convexity to hold for all error vectors $\Delta$. The RSC property imposes a milder restriction on the first-order Taylor expansion error's form, by adding the tolerance term $\tau_n^2\Phi(\Delta)^2$.
In many settings it is not computationally feasible to enumerate all candidate models in $\mathfrak{M}$. Instead, we can use a regularized $m$-estimation with the sparsity inducing norm:
were $\lambda>0$ is the regularization parameter and $\Phi:\Omega\rightarrow{\mathbb{R}}_+$ is a norm. Popular regularization methods, such as the LASSO, group LASSO, low rank regularization, and others fall within this framework.
sNpRmWbY2012 study this class os problems, where the norm $\Phi$ is decomposable with respect to a pair of subspaces $(\mathcal{M},\bar{\mathcal{M}}^\perp)$, and the convex loss function $\mathcal{L}$ is in the RSC class.\footnote{sNpRmWbY2012 work with a more flexible specification of RSC, but point out that “...for many loss functions it is possible to prove that with high probability...” our RSC specification holds with $\eta_n = 1$.} We adapt their main result to our setting, where we impose strong sparsity and use a distinct RSC.
Instead of enumerating all possible models, we construct a sequence of model subspaces indexed by the regularization parameter $\lambda$. For each $\lambda > 0$ define
for $\xi_n$ chosen adequately. This collection of model subspaces arises naturally in sparse estimation. Suppose the sequence $\mathfrak{M}_\lambda = \{\mathcal{M}_\lambda | \lambda>0\}$ contains the true model $\mathcal{M}_*$ . We use the GIC to estimate \[ \widehat{\mathcal{M}} = \operatorname*{\mathsf{arg\,min}}_{\mathcal{M}\in\mathfrak{M}_\lambda} GIC_{a_n}(\mathcal{M}), \] which is equivalent to selecting $\widehat\lambda$ that satisfy \[ \widehat{\lambda} = \operatorname*{\mathsf{arg\,min}}_{\lambda>0}GIC_{a_n}(\mathcal{M}_\lambda) \] and setting $\widehat{\mathcal{M}} = \mathcal{M}_{\widehat\lambda}$.
We introduce the main assumptions used in this paper, further illustrated in Section (ref).
This condition requires that the sparsity inducing norm $\Phi$ can adequately identify the true model subspace from a collection containing it. Furthermore, the true model subspace cannot be too large.
These condition are traditionally satisfied in a “high probability set”. wainwright2019High and sNpRmWbY2012 illustrate this condition in a series of examples, with distinct losses and penalty functions. Taking the sample size to infinity, yields a bound with probability converging to one. Also, under stronger conditions, this assumption is satisfied with probability one.
Assumption (A4) is a generalization of the well known “beta-min condition” in the sparse regularization literature. It states that we require a separation between the zero and non-zero parameters in the sparse model, that naturally decreases as the sample size increases. This condition is required for model selection consistency and sign-consistency of the LASSO and other sparse regularized $m$-estimators buhlmann2011statistics.
This section provides a deterministic statement about selecting the true model by minimizing the $GIC_{a_n}(\mathcal{M})$ statistic over a collection $\mathfrak{M}_{\psi_n^2}$. In practice, however, Assumptions (A2) and (A3) depend on stochastic quantities and hold only probabilistically, i.e., are only true in a in a set of high probability. Hence, if assumptions are satisfied in probability or with probability one, one has an asymptotic statement about model selection consistency.
This first result shows that, under a set of assumptions, the solution $\widehat{\mathcal{M}}_{a_n}$ to the $GIC_{a_n}$ problem is the true model. Nevertheless, these conditions involve random quantities and must be shown to be satisfied ´´in a set of high probability”, yielding a finite sample probability bound on selecting the true model. If these conditions hold asymptotically, in probability of with probability one, we have consistency.
In the next definition we use a small abuse of notation. Let $\mathcal{M}_*$ and $\{\mathcal{M}_n\}$ denote a fixed subspace and a sequence of subspaces of $\Omega$, respectively. Suppose $\mathcal{M}_n:=\mathcal{M}({\bf Z}^n)$, we say $\mathcal{M}_n\rightarrow \mathcal{M}_*$ in probability if $\mathbb{P}(\mathcal{M}_n\Delta\mathcal{M}_*)\rightarrow 0$ and $\mathcal{M}_n\rightarrow \mathcal{M}_*$ with probability one if $\Pr(\lim_n \mathcal{M}_n\Delta\mathcal{M}_*) = 0$.
Next Theorem shows that the $GIC_{a_n}$ selects the true model and is model selection consistent. Showing the selected model is the true model is equivalent to showing $GIC_{a_n}(\mathcal{M}^*) < GIC_{a_n}(\mathcal{M})$ for all $\mathcal{M}\in\mathfrak{M}_{\psi_n^2}\setminus\{\mathcal{M}_*\}$. Naturally, if $\widehat{\mathcal{M}}_{a_n}$ minimizes the $GIC_{a_n}(\cdot)$ over $\mathfrak{M}_{\psi_n^2}$ it has to be equal to $\mathcal{M}_*$.
In large dimensions it is usually computationally infeasible to enumerate and estimate all possible model subspaces satisfying $\Psi^2(\mathcal{M})\le\psi_n^2$ and estimate their GICs. Penalized $m$-estimators, discussed in Section (ref), are a convenient way of constructing a collection of model subspaces indexed by some regularization parameter $\lambda$. We show that under appropriate choice of $\lambda$, we can recover the true model subspace.
Recall we estimate $\widehat{\theta}_\lambda$ solving the convex minimization program (ref): \[ \widehat{\theta}(\lambda)\in\operatorname*{\mathsf{arg\,min}}_{\theta\in\Omega}\left\{\mathcal{L}(\theta)+\lambda\Phi({\theta})\right\},~~\lambda>0. \] Let $\{\widehat{\theta}(\lambda)\}_{\lambda>0}$ denote a sequence of parameter estimates indexed by $\lambda$. For each $\lambda$, we obtain the model subspace \[ \mathcal{M}_\lambda = \operatorname*{\mathsf{arg\,max}}_{\mathcal{M} \in \mathfrak{M}} \left\{\|\widehat{\theta}(\lambda)_\mathcal{M}\| \Big\vert \min_{\mathcal{S}\in\mathfrak{M}:~\mathcal{S}\subseteq\mathcal{M}}\|\widehat{\theta}(\lambda)_{\mathcal{S}} \| \ge \xi_n\right\}, \] for some $\xi_n$ satisfying regularity conditions, and collect them in $\mathfrak{M}_\lambda = \{\mathcal{M}_\lambda|\lambda>0\}$. The model subspace $\mathcal{M}_\lambda$ is interpreted as the largest model subspace $\mathcal{M}$ such that the error norm of the projection of $\widehat{\theta}_\lambda$ onto every model subspace $\mathcal{S}\subseteq\mathcal{M}$ is larger than a threshold $\xi_n$. A simpler truncation was used in kimjeon2016 for the particular cases of LASSO and SCAD. Here we adopt a more general definition adequate to the structured regularization problem.
Next theorem is a deterministic result showing that $\mathcal{M}_\lambda = \mathcal{M}^*$ for some $\lambda$, under regularity conditions. As in the model selection case, these conditions involve random quantities and can only be satisfied with certain probability or asymptotically. We need a stronger beta-min condition involving the regularization parameter $\lambda$ and the complement of the paired model subspace $\bar\mathcal{M}_*$. In practice, this bound is larger than (A4), meaning that (A4') implies (A4) if $\lambda>\kappa\sqrt{a_n}$.
We show that the sequence $\mathfrak{M}_\lambda$ is pathconsistent.
The most natural way of selecting the sparsity inducing norm $\Phi$ is to construct a penalized $m$-estimation problem that aims to recover the desired sparsity pattern. We illustrate the method in two examples. These examples are adapted from the literature in high dimensional statistics, in particular chapters 9 and 10 of wainwright2019High.
This example is adapted from wainwright2019High. Let ${\bf Z}^n = \{z_i' = (x_i', y_i): i=1,...,n\}$ denote a sequence of random variables where, conditionally on $x_i$, the dependent variables $y_i$ are drawn independently from: \[ f(y|x) \propto \exp\left\{\frac{y\langle x,\theta^*\rangle - b(\langle x,\theta^*\rangle)}{c(\sigma)}\right\}, \] where $g$ has a bounded second derivative $\|b''\|_\infty \le B^2$. The covariates $x_i\in{\mathbb{R}}^p$ are independent and identically distributed zero-mean sub-Gaussian random variables. Furthermore, let $\mathbf{X}_g\in{\mathbb{R}}^{n\times|g|}$ denote the sub-matrix of the covariates indexed by $g$. The covariates satisfy the group normalization condition $\max_{g\in\mathcal{G}}{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \mathbf{X}_g \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_F/\sqrt{n}\le C$, where ${\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \cdot \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_F$ is the Frobenius norm.
The group lasso penalty, or $l_1/l_2$-vector norm, is a natural way of modelling group sparsity. Let $\mathcal{G} = \{g_1, ..., g_G\}$ denote a partition of $\{1,...,p\}$ where groups $g_i$ have size at most $m$ and write $\theta_{g_i} = \{\theta_j:j\in g_i\}$. Let $u\in\Omega:={\mathbb{R}}^p$, the $l_1/l_2$-norm is \[ \Phi(u) =\sum_{g\in\mathcal{G}}\|\theta_g\|_2\mbox{ with conjugate norm } \Phi^*(u) = \max_{g\in\mathcal{G}}\|\theta_g\|_2. \] For any $S\subseteq\mathcal{G}$, the space of parameters ${\mathbb{R}}^{p}$ can be decomposed into \[ \mathcal{M}:=\mathcal{M}(S) = \{\theta\in{\mathbb{R}}^p|\theta_{g} = 0\mbox{ for all } g\notin S\}, \] and $\bar{\mathcal{M}}^\perp = \mathcal{M}^\perp(S) :=\mathcal{M}(\mathcal{G}\setminus S)$. It follows that $\Phi$ is decomposable with respect to $(\mathcal{M}(S),\mathcal{M}^{\perp}(S))$ for any $S\subseteq\mathcal{G}$.
The subspace compatibility constant is \[ \Psi(\mathcal{M}(S)) = \sup_{\theta\in \mathcal{M}(S)\setminus\{0\}}\frac{\sum_{g\in\mathcal{G}}\|\theta_g\|_2}{\|\theta\|_2} = \sqrt{|S|}, \] where $|S|$ is the cardinality of $S$.
Under assumptions above, it follows from Theorem 9.16 and Example 9.17 in wainwright2019High that RSC condition is satisfied with radius $\eta_n=1$, curvature $\kappa<\infty$ and tolerance $\tau_n^2 = c_1 \left(\frac{m}{n} + \frac{\log G}{n}\right)^2$. Precisely, \[ \mathcal{L}(\theta^* + \Delta) - \mathcal{L}(\theta^*) - \langle \nabla\mathcal{L}(\theta),\Delta\rangle \ge \kappa \|\Delta\|^2_2 - c_1 \left(\frac{m}{n} + \frac{\log G}{n}\right)^2\Phi^2(\Delta) \] for all $\|\Delta\|\le 1$, with probability at least $1-c_2e^{c_3n}$. The constants $c_1,c_2,c_3,\kappa$ depend on the GLM, the population vector $\theta^*$, $\alpha$ and $\beta$, but are independent of $n$. As $n\rightarrow\infty$ this bound holds with probability converging to one.
As in the proof of wainwright2019High, it follows from the union bound and standard sub-Gaussian tail bounds that \[ \Pr\left(2\max_{g\in\mathcal{G}}\|(\nabla\mathcal{L}(\theta^*))_g\|_2 \le \kappa \sqrt{a_n}\right)\ge 1-2e^{-n\delta^2}, \] where \[ a_n\ge \frac{32B^2C^2}{\kappa^2}\left(\frac{m}{n}\log 5 + \frac{\log G}{n} + \delta^2\right) = O \left(\frac{m}{n} + \frac{\log G}{n}\right), \] for adequate choice of $\delta$. Note that if $\log G\rightarrow\infty$ as $n\rightarrow\infty$, the choice $\delta^2 = (\log 5-1)\log(G)/n$ ensures $1-2e^{-n\delta^2}\rightarrow 1$, meaning that (A3) holds with probability converging to one. On the other hand, if $G$ is fixed, we might choose $\delta^2 = O(\log(n)/n)$ which yields $a_n\propto (m+\log G)\log(n)/n$.
Finally, let $\mathcal{M}_* := \mathcal{M}(S_*)$ denote the true model subspace, with support $S_*\subseteq\mathcal{G}$. Assumption (A4) is equivalent to \[ \min_{g\in S_*} \|\theta^*_g\|_2 \ge \frac{2}{\kappa}\sqrt{|S_*|a_n}. \]
In order to apply Theorem (ref), we also require that \[ \psi_n^2\le \frac{\kappa}{8c_1}\frac{n}{m + log G} \wedge \frac{\kappa}{4 a_n}. \] This condition is satisfied if $a_n\psi_n^2\rightarrow 0$. In this case, Theorem (ref) ensures the GIC is model selection consistent. The method is also pathconsistent if we take $\lambda = \kappa\sqrt{a_n}$, $\xi_n \propto \sqrt{a_n|S_*|}$ and construct \[ \mathcal{M}_\lambda:=\operatorname*{\mathsf{arg\,max}}_{S\subseteq\mathcal{G}}\left\{\|\hat\theta(\lambda)_{S}\|_2 \Big\vert \,\forall\,g\in S,~\|\hat\theta(\lambda)_{g}\|_2 > \xi_n\right\}. \]
In this example we estimate a low rank matrix regression parameter. It follows developments in wainwright2019High.
Let ${\bf Z}^n = \{(X_i, y_i)\}_{i=1}^n$ be a random sample, where $X_i \in {\mathbb{R}}^{p_1 \times p_2}$ is a matrix of covariates and $y_i \in {\mathbb{R}}$ is a response variable. We assume the simplest model, in which every observation pair $(X_i,y_i)$ are linked via the equation:
where $\langle A,B\rangle = \operatorname*{trace}(A'B)$ is the trace inner product, $w_i$ is a noise variable drawn independently from a zero-mean Normal distribution with variance $\sigma^2$, and $\Theta^* \in {\mathbb{R}}^{p_1 \times p_2}$ is a matrix of coefficients with rank $r^*<<\min(p_1,p_2)$.
We represent this model more compactly. Define the observation operator $\mathfrak{X}: {\mathbb{R}}^{p_1 \times p_2} \to {\mathbb{R}}^n$, with elements $[\mathfrak{X}(\Theta^*)]_i := \langle X_i, \Theta^* \rangle$. We write
where $y \in {\mathbb{R}}^n$ and $w \in {\mathbb{R}}^n$ are the vectors formed by stacking the response and noise variables, respectively. We are interested in estimating the matrix of coefficients $\Theta^*$ using least squares, i.e.: \[ \mathcal{L}(\Theta) := \frac{1}{2n}\|y - \mathfrak{X}(\Theta)\|_2^2, \] where $\|\cdot\|_2$ is the Euclidean norm in ${\mathbb{R}}^n$.
Take $\Theta^* \in {\mathbb{R}}^{p_1\times p_2}$ and assume the matrix $\Theta^*$ has a rank $r_*$ lower than $\min(p_1,p_2)$. For any $\Theta \in {\mathbb{R}}^{p_1\times p_2}$, denote by $\text{row}(\Theta) \subseteq {\mathbb{R}}^{p_2}$ and $\text{col}(\Theta) \subseteq {\mathbb{R}}^{p_2}$ the row and column spaces of $\Theta$, respectively. Let $\mathbb{U}$ and $\mathbb{V}$ be a pair of $r$-dimensional subspaces of ${\mathbb{R}}^{p_1}$ and ${\mathbb{R}}^{p_2}$, respectively. We define the subspaces \[ \mathcal{M}(\mathbb{U},\mathbb{V}) =\{\Theta \in {\mathbb{R}}^{p_1\times p_2} \mid \text{row}(\Theta) \subseteq \mathbb{V}, \text{col}(\Theta) \subseteq \mathbb{U}\}, \] and \[ \bar{\mathcal{M}}^\perp(\mathbb{U},\mathbb{V}) = \{\Theta \in {\mathbb{R}}^{p_1\times p_2} \mid \text{row}(\Theta) \subseteq \mathbb{V}^\perp, \text{col}(\Theta) \subseteq \mathbb{U}^\perp\}. \] Notice that, in this case, $\bar{\mathcal{M}}^\perp \subseteq \mathcal{M}^\perp$, and the sets are generally not equal c.f. recht2010guaranteed. For a fixed pair $(\mathbb{U},\mathbb{V})$, we set $\mathcal{M} := \mathcal{M}(\mathbb{U},\mathbb{V})$ and $\bar{\mathcal{M}}^{\perp} := \bar{\mathcal{M}}^\perp(\mathbb{U},\mathbb{V})$. We denote the collection of model subspaces \[ \mathfrak{M} = \{(\mathcal{M}(\mathbb{U},\mathbb{V}),\bar{\mathcal{M}}^\perp(\mathbb{U},\mathbb{V})) \mid \mathbb{U} \subseteq {\mathbb{R}}^{p_1}, \mathbb{V} \subseteq {\mathbb{R}}^{p_1} : \text{dim}(\mathbb{U}) = \text{dim}(\mathbb{V}) \leq p_1\wedge p_2\}, \] with pairs $(\mathcal{M}(\mathbb{U},\mathbb{V}),\bar{\mathcal{M}}^\perp(\mathbb{U},\mathbb{V}))$.
The nuclear norm $\|\cdot\|_\sigma$ is defined as \[ \|\Theta\|_\sigma = \sum_{i=1}^{p_1\wedge p_2}\sigma_i(\Theta)\mbox{ with conjugate norm } {\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \Theta \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_2 = \max_{i\le p_1\wedge p_2}\sigma_i, \] where $\sigma_i$ is the $i$-th largest singular value of $\Theta$. The conjugate norm is also known as $l_2$-operator norm. For any pair, $(A,B) \in (\mathcal{M},\bar{\mathcal{M}}^\perp)$, $A'B = 0$ and $AB' = 0$. recht2010guaranteed shows that, under these conditions, the Nuclear norm is additive: $\|A+B\|_\sigma = \|A\|_\sigma + \|B|_\sigma$. Therefore, the nuclear norm is decomposable with respect to any pair of subspaces in $\mathfrak{M}$.
Suppose $\Theta \in \mathcal{M}(\mathbb{U},\mathbb{V})$ has $\text{dim}(\text{col}(\Theta)) = \text{dim}(\text{row}(\Theta)) \leq r$, it follows from the Cauchy-Schwartz inequality
with equality holding when $\Theta = USV'$, where $S = \operatorname*{diag}(1,\dots,1,0,\dots,0)$ with $r$ entries one and $p-r$ entries zero, and $U \in {\mathbb{R}}^{p_1 \times p}, V \in {\mathbb{R}}^{p_2 \times p}$ are orthonormal matrices, with the first $r$ columns of both matrices spanning $\mathbb{U}$ and $\mathbb{V}$, respectively. Therefore we conclude that, \[\Psi(\mathcal{M}(U,V)) = \sqrt{r}.\]
wainwright2019High[Chapter 10] shows that,for some constants $\kappa/2<1<c_0$, the proposed loss function satisfies \[ \mathcal{L}(\Delta + \Theta^*) - \mathcal{L}(\Theta^*) -\langle \nabla\mathcal{L}(\Theta^*) , \Delta \rangle \geq \frac{\kappa}{2}{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \Delta \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_F^2 - c_0\frac{p_1+p_2}{n}{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \Delta \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_\sigma^2, \] for all $\Delta \in {\mathbb{R}}^{p_1 \times p_2}$. In other words, the squared loss satisfy the RSC with curvature $\kappa/2$, tolerance $\tau_n = c_0 (p_1+p_2)/n$ and radius $\eta_n\in {\mathbb{R}}$. This bound holds with probability at least $1-({1-e^{\frac{n}{32}}})^{-1}$ in the case where the matrix regressors $X_i$ are independent and identically distributed with entries drawn independently from a standard Gaussian distribution. This artificial example can be directly generalized to encompass entries with Gaussian dependence.
Following same arguments in wainwright2019High[Corollary 10.10], under the assumptions above,
where \[ a_n \ge \frac{32\sigma^2}{\kappa^2}\left(\frac{p_1+p_2}{n}log 9 + \delta^2\right) = O\left(\frac{p_1+p_2}{n}\right), \] for adequate choice of $\delta^2$. Note that if $p_1+p_2\rightarrow\infty$ as $n\rightarrow\infty$ the choice $\delta^2 = (\log 9 -1)(p_1+p_2)/n$ ensures $1- e^{-n/8}-2^{-n\delta^2}\rightarrow 1$, meaning that Assumption (A3) is satisfied with probability converging to one. On the other hand, if $p_1+p_2$ is fixed, we might choose $\delta^2 \propto (p_1+p_2)\log(n)/n$.
Finally, let $\sigma_1^*\ge\cdots\ge\sigma_{r_*}^*>\sigma_{r_*+1}^*= 0 =\cdots = 0$ denote the population singular values of $\Theta^*$. Assumption (A4) is satisfied if \[ \sigma_{r_*}^*\ge \frac{2}{\kappa}\sqrt{a_n r_*}. \]
In order to apply Theorem (ref), we also require that \[ \psi_n^2\le \frac{\kappa}{8c_0}\frac{n}{p_1+ p_2} \wedge \frac{\kappa}{4 a_n}. \] This condition is satisfied if $a_n\psi_n^2\rightarrow 0$. In this case, Theorem (ref) ensures the GIC is model selection consistent. In this case, Assumption (A4) and (A4') differ. However, the rank of $\bar{\mathcal{M}}_*$ and $\mathcal{M}_*$ is the same, hence $\Psi(\bar{\mathcal{M}}_*) = \Psi(\mathcal{M}_*)$. The method is pathconsistent if we take $\lambda = \kappa\sqrt{a_n}$, $\xi_n \propto \sqrt{a_nr_*}$ and construct \[ \mathcal{M}_\lambda:=\operatorname*{\mathsf{arg\,max}}_{\mathcal{M}\in\mathfrak{M}}\left\{{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \hat\Theta(\lambda)_{\mathcal{M}} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_F \Big\vert \,\forall\,\mathcal{S}\subseteq\mathcal{M} ,~{\left\vert\kern-0.25ex\left\vert\kern-0.25ex\left\vert \hat\Theta(\lambda)_\mathcal{S} \right\vert\kern-0.25ex\right\vert\kern-0.25ex\right\vert}_F > \xi_n\right\}. \]
In this section we prove Theorem (ref) and Theorem (ref).