Sparsistency of $\ell_1$-Regularized $M$-Estimators

I Introduction

Performing a general sparsistency analysis requires the identification of general properties of statistical models, and their corresponding $M$-estimators, that can be exploited to obtain strong performance guarantees. In this paper, we introduce the local structured smoothness condition (LSSC) condition (Definition III.1), which controls the smoothness of the objective function in a particular structured set. We illustrate how the LSSC enables us to address a broad set of sparsistency results in a unified fashion, including logistic regression, gamma regression, and graph selection. We explicitly check the LSSC for these statistical models, and as in previous works , we derive sample complexity bounds for the high-dimensional setting, where the ambient dimension and sparsity level are allowed to scale with the number of samples.

To the best of our knowledge, the first work to study the sparsistency of a broad class of models was that of for generalized linear models; however, the technical assumptions therein appear to be difficult to check for specific models, thus making their application difficult. Another related work is ; in Section VII, we compare the two, and discuss a key advantage of our approach.

II Problem Setup

where $L_{n}$ is some convex function, and $\tau_{n}>0$ is a regularization parameter.

There are of course many other examples; to name one other, we mention the graphical learning problem, where we want to learn a sparse concentration matrix of a vector-valued random variable. In this setting, we also arrive at the formulation (1), where $L_{n}$ is the negative log-likelihood of the data .

We focus on the sparsistency of $\hat{\beta}_{n}$; roughly speaking, an estimator $\hat{\beta}_{n}$ is sparsistent if it recovers the support of $\beta^{*}$ with high probability when the number of samples $n$ is large enough.

A sequence of estimators $\{\hat{\beta}_{n}\}_{n=1}^{\infty}$ is called sparsistent if

Let $X$ be a real-valued random variable. We denote the expectation and variance of $X$ by $\mathsf{E}\,X$ and $\mathsf{var}\,X$, respectively. The probability of an event $\mathcal{E}$ is denoted by $\mathsf{P}\,\mathcal{E}$.

The third order Fréchet derivative is defined as follows. We first define the 2-linear form (matrix) $D^{3}f(x)[u]:=\lim_{t\to 0}\frac{\nabla^{2}f(x+tu)-\nabla^{2}f(x)}{t}$. Then

When the arguments are the same, we simply have $D^{k}f(x)[u,\ldots,u]=\left.\frac{d^{k}\phi_{u}(t)}{dt^{k}}\right|_{t=0}$, where $\phi_{u}(t):=f(x+tu)$.

III Local Structured Smoothness Condition

The following definition provides the key property of convex functions that will be exploited in the subsequent sparsistency analysis.

The function $f$ satisfies the $(x^{*},\mathcal{N}_{x^{*}})$-LSSC with parameter $K\geq 0$ if and only if

As we will see in the next section, this equivalent characterization is useful when verifying the LSSC for a given $M$-estimator.

Since differentiation is a linear operator, the LSSC is preserved under linear combinations with positive coefficients, as is stated formally in the following lemma.

Let $f_{1}$ satisfy the $(x,\mathcal{N}_{1})$-LSSC with parameter $K_{1}$, and $f_{2}$ satisfy the $(x,\mathcal{N}_{2})$-LSSC with parameter $K_{2}$. Let $\alpha$ and $\beta$ be two positive real numbers. The function $f:=\alpha f_{1}+\beta f_{2}$ satisfies the $(x,\mathcal{N}_{x})$-LSSC with parameter $K$, where $\mathcal{N}_{x}:=\mathcal{N}_{1}\cap\mathcal{N}_{2}$, and $K:=\alpha K_{1}+\beta K_{2}$.

We conclude this section by briefly discussing the connection of the LSSC with other conditions. The following result, Proposition 9.1.1 of , will be useful here and throughout the paper.

This proposition shows that the condition in (2) without structural constraints on $u$ and $e_{j}$ is equivalent to the statement that

The preceding observations reveal that (3), or the equivalent formulation (4), is more restrictive than the LSSC. That is, (3) implies the LSSC, while the reverse is not true in general.

IV Examples

In this section, we provide some examples of functions that satisfy the LSSC.

Combining this with Proposition III.3, we have for each standard basis vector $e_{j}$ that

where $\lambda_{\max}$ is the maximum restricted eigenvalue of $D^{2}f(\beta^{*})$ defined as

and $d_{\max}$ denotes the maximum diagonal entry of $\nabla^{2}f(\beta^{*})$. Therefore, $f$ satisfies the $(\beta^{*},\mathcal{N}_{\beta^{*}})$-LSSC with parameter $K:=2(1+\kappa^{-1})^{3}\lambda_{\max}d_{\max}^{1/2}$, where

Note that the previous definitions (in particular, Definition III.1), should be interpreted here as being taken with respect to the vectorizations of the relevant matrices.

It is already known that $f$ is standard self-concordant ; that is,

Fix a positive constant $\kappa$, and suppose that we choose $\Delta$ such that $\left\|\Delta\right\|_{F}\leq(1+\kappa)^{-1}\rho_{\min}$, where $\rho_{\min}$ denotes the smallest eigenvalue of $\Theta^{*}$. Since $\left\|\Delta\right\|_{2}\leq\left\|\Delta\right\|_{F}$, it follows that $\left\|\Delta\right\|_{2}\leq(1+\kappa)^{-1}\rho_{\min}$, and, by Weyl’s theorem ,

Combining the preceding observations, it follows that $f$ satisfies the $(\Theta^{*},\mathcal{N}_{\Theta^{*}})$-LSSC with parameter $K:=2\kappa^{-3}(1+\kappa)^{3}\rho_{\min}^{-3}$, where

V Deterministic Sufficient Conditions

We are now in a position to state the main result of this paper, whose proof can be found in the appendix.

where here and subsequently we assume that the $\arg\min$ is uniquely achieved.

(Positive definite restricted Hessian) The restricted Hessian at $\beta^{*}$ satisfies $\left[\nabla^{2}L_{n}(\beta^{*})\right]_{\mathcal{S},\mathcal{S}}\geq\lambda_{\min}I$ for some $\lambda_{\min}>0$.

(Irrepresentablility condition) For some $\alpha\in(0,1]$, it holds that

(Beta-min condition) The smallest non-zero entry of $\beta$ satisfies

The regularization parameter $\tau_{n}$ satisfies

The gradient of $L_{n}$ at $\beta^{*}$ satisfies

The relation $\mathcal{B}_{r_{n}}\subseteq\mathcal{N}_{\beta^{*}}$ holds, where

As mentioned previously, the first condition is the key assumption permitting us to perform a general analysis. The second, third, and forth assumptions are analogous to those appearing in the literature for sparse linear regression. We refer to for a systematic discussion of these conditions.Equation (8) is sometimes called the incoherence condition .

The remaining conditions determine the interplay between $\tau_{n}$ , $n$, $p$, and $s$. Whether the relation $\mathcal{B}_{r_{n}}\subseteq\mathcal{N}_{\beta^{*}}$ holds depends on the specific $\mathcal{N}_{\beta^{*}}$ that one can derive for the given loss function $L_{n}$. Whether the upper bound on $\left\|\nabla L_{n}(\beta^{*})\right\|_{\infty}$ holds depends on the concentration of measure behavior of $\nabla L_{n}(\beta^{*})$, which usually concentrates around . In the next section, we will give concrete examples for the high-dimensional setting, where $p$ and $s$ scale with $n$.

VI Applications

In this section, we provide several applications of Theorem V.1, presenting concrete bounds on the sample complexity in each case. We defer the full proofs of the results in this section to the appendix. However, in each case, we present here the most important step of the proof, namely, verifying the LSSC.

Note that instead of the classical setting where only the sample size $n$ increases, we consider the high-dimensional setting, where the ambient dimension $p$ and the sparsity level $s$ are allowed to grow with $n$ .

We first consider the linear regression model with additive sub-Gaussian noise. This setting trivially fits into our theoretical framework.

A zero-mean real-valued random variable $Z$ is sub-Gaussian with parameter $c>0$ if

By the union bound and the standard concentration inequality for sub-Gaussian random variables ,

Observe that this recovers the scaling law given in for the linear regression model.

VI-B Logistic Regression

The random variables $Y_{1},\ldots,Y_{n}$ are assumed to be independent.

In , a scaling law of the form $s\ll\frac{\sqrt{n}}{(\log n)^{2}}$ is given, but the result is restricted to the case that $p$ grows polynomially with $n$. The result in yields the scaling $s^{2}(\log p)\overline{\nu_{n}}^{2}\ll n$, where $\overline{\nu}_{n}:=\max\left\{\left\|x_{i}\right\|_{2}\right\}$. It should be noted that $\overline{\nu}_{n}$ is generally significantly larger than $\nu_{n}$ and $\gamma_{n}$; for example, for i.i.d. Gaussian vectors, these scale on average as $O(\sqrt{p})$, $O(\sqrt{s})$ and $O(1)$, respectively. Our result recovers the same dependence of $n$ on $s$ and $p$ as that in , but removes the dependence on $\overline{\nu}_{n}$. Of course, we do not restrict $p$ to grow polynomially with $n$.

VI-C Gamma Regression

for some $\mu_{n}>0$, so $\theta_{i}$ is always well-defined. Moreover, the random variables $Y_{1},\ldots,Y_{n}$ are assumed to be independent.

Note that $\theta_{i}$ only enters the log-likelihood via constant terms not containing $\beta$; these have been omitted, as they do not affect the estimation.

Fix $\kappa>0$. By Example IV.2, $L_{n}$ satisfies the $(\beta^{*},\mathcal{N}_{\beta^{*}})$-LSSC with parameter $K=2(1+\kappa^{-1})^{3}\mu_{n}^{-3}\nu_{n}^{2}\gamma_{n}$, and

To the best of our knowledge, this is the first sparsistency result for gamma regression.

VI-D Graphical Model Learning

We assume that each $\left(\Sigma_{i,i}\right)^{-1/2}X_{i,i}$ is sub-Gaussian with parameter $c>0$, and that $\Sigma_{i,i}$ is bounded above by a constant $\kappa_{\Sigma^{*}}$, for all $i\in\{1,\ldots,p\}$. Let $\rho_{\min}$ denote the smallest eigenvalue of $\Theta^{*}$.

where $\hat{\Sigma}_{n}:=\frac{1}{n}\sum_{i=1}^{n}X_{i}X_{i}^{T}$ is the sample covariance matrix.

Fix $\kappa>0$. By Example IV.3, we know that $L_{n}$ satisfies the $(\Theta^{*},\mathcal{N}_{\Theta^{*}})$-LSSC with parameter $2\kappa^{-3}(1+\kappa)^{3}\rho_{\min}^{-3}$, where

where $\rho_{\min}$ denotes the smallest eigenvalue of $\Theta^{*}$.

Corollary VI.4 is for graphical learning on general sparse networks, as we only put a constraint on $s$. Several previous works have instead imposed structural constraints on the maximum degree of each node; e.g. see . Since this model requires additional structural assumptions beyond sparsity alone, it is outside the scope of our theoretical framework.

VII Discussion

Our work bears some resemblance to the independent work of . The smoothness condition therein is in fact the non-structured condition in (4). From the discussion in Section III, we see that our condition is less restrictive. As a consequence, both analyses lead to scaling laws of the form $n\gg K^{2}s^{2}\log p$ for generalized linear models, but the corresponding definitions of $K$ differ significantly. Eliminating the dependence of $K$ on $p$ requires additional non-trivial extensions of the framework in , whereas in our framework the desired independence is immediate (e.g. see the logistic and gamma regression examples).

The derivation of estimation error bounds such as (7) (as opposed to full sparsistency) usually only requires some kind of local restricted strong convexity (RSC) condition on $L_{n}$. It is interesting to note that in this paper, it suffices for sparsistency to assume only the LSSC and the positive definiteness of the restricted Hessian at the true parameter. It would be interesting to derive connections between the LSSC and such local RSC conditions, which in turn may shed light on whether the LSSC is necessary to derive sparsistency results, or whether a weaker condition may suffice.

The framework presented here considers general sparse parameters. It is of great theoretical and practical importance to sharpen this framework for structured sparse parameters, e.g., group sparsity, and graphical model learning for networks with bounded degrees.

Appendix A Auxiliary Result for the Non-Structured Case

In this section, we prove the following claim made in Section 3. Note that, in contrast to the main definition of the LSSC, the vectors here are not necessarily structured.

$D^{2}f(x)$ is locally Lipschitz continuous with respect to $x^{*}$; that is,

Suppose that (13) holds. By Proposition 3.3, it suffices to prove that

We therefore have (14) since $\left\|H\right\|_{2}\leq K\left\|\delta\right\|_{2}$ by (13).

Conversely, suppose that (14) holds. We have the following Taylor expansion :

where $x_{t}:=x^{*}+t\delta$. We also have from (14) and the definition of the spectral norm that $\left\|D^{3}f(x^{*}+\delta)[\delta]\right\|_{2}\leq K\left\|u\right\|_{2}$, and hence

Appendix B Proof of Theorem 5.1

The proof is based on the optimality conditions on $\hat{\beta}$ for the original problem, and those on $\check{\beta}$ for the restricted problem. We first observe that $\check{\beta}_{n}$ exists, since the function $x\mapsto\left\|x\right\|_{1}$ is coercive. We have assumed uniqueness in the theorem statement, thus ensuring the validity of (2).

The following lemma is proved via an extension of the techniques of .

We have $\hat{\beta}_{n}=\check{\beta}_{n}$ if

We now combine Lemma B.1 with the assumptions of Theorem 5.1 to obtain the following.

Applying a Taylor expansion at $\beta^{*}$, and noting that both $\beta^{*}$ and $\check{\beta}_{n}$ are supported on $\mathcal{S}$, we obtain

where the remainder term is given by $\epsilon_{n}=\int_{0}^{1}(1-t)D^{3}L_{n}(\beta_{t})[\check{\beta}-\beta^{*},\check{\beta}-\beta^{*}]$dt with $\beta_{t}:=\beta^{*}+t(\check{\beta}-\beta^{*})$ (see Section 4.5 of ), and thus satisfies

Recall the optimality condition for $\check{\beta}$ in (16). Again using a Taylor expansion, we can write this condition as

Recall that $\left[\nabla^{2}L_{n}(\beta^{*})\right]_{\mathcal{S},\mathcal{S}}$ is invertible by the second assumption of Theorem 5.1. Solving for $\left(\check{\beta}_{n}-\beta^{*}\right)_{\mathcal{S}}$ in (20) and substituting the solution into (18), we obtain

The first requirement $\left\|\nabla L_{n}(\beta^{*})\right\|_{\infty}\leq(\alpha/4)\tau_{n}$ is simply assumption 6 of Theorem 5.1, so it remains to determine a sufficient condition for $\left\|\epsilon_{n}\right\|_{\infty}\leq(\alpha/4)\tau_{n}$. Since $L_{n}$ satisfies the $(\beta^{*},\mathcal{N}_{\beta^{*}})$-LSSC with parameter $K$, we have from (19) that

provided that $\check{\beta}\in\mathcal{N}_{\beta^{*}}$ (since $\mathcal{N}_{\beta^{*}}$ is convex by assumption, this implies $\beta_{t}\in\mathcal{N}_{\beta^{*}}$). Thus, to have $\left\|\epsilon_{n}\right\|_{\infty}\leq\frac{\alpha}{4}\tau_{n}$, it suffices that

and $\check{\beta}\in\mathcal{N}_{\beta^{*}}$. ∎

To bound the distance $\left\|\check{\beta}-\beta^{*}\right\|_{2}$, we adopt an approach from . We begin with an auxiliary lemma.

We use a proof by contradiction. Suppose that $z\notin\mathcal{B}$. We first note that there exists some $t^{*}\in(0,1)$ such that $b+t^{*}(z-b)\in\partial\mathcal{B}$; if such a $t^{*}$ did not exist, then we would have $z_{t}:=b+t(z-b)\to z$ as $t\to 1$, which is impossible since $z\notin\mathcal{B}$ and $\mathcal{B}$ is closed.

which is a contradiction since $g>0$ on $\partial\mathcal{B}$. ∎

The following lemma presents the desired bound on $\left\|\check{\beta}_{n}-\beta^{*}\right\|_{2}$; note that this can be interpreted as the estimation error in the $n>p$ setting, considering $\beta^{*}_{\mathcal{S}}$ as the parameter to be estimated.

Under assumptions 1, 2, 6 and 7 of Theorem 5.1, if

then $\check{\beta}_{n}\in\mathcal{B}_{r_{n}}$.

We proceed by deriving a lower bound on $g(\delta)$. We define $\phi(t):=(L_{n}\circ Z)(\beta_{\mathcal{S}}^{*}+t\delta)$, and write the following Taylor expansion:

where the first step is by Hölder’s inequality and the identity $\|z\|_{2}\leq\sqrt{s}\|z\|_{1}$, and the second step uses assumption 6 of Theorem 5.1. To bound the term $\phi^{\prime\prime}(0)$, we use the second assumption of Theorem 5.1 to write

Hence, and combining the preceding bounds, we have $g(\delta)\geq f\left(\left\|\delta\right\|_{2}\right)$, where

holds, then we can bound the coefficient to $x^{3}$ in terms of that of $x^{2}$ to obtain

By a direct calculation, this lower bound has roots at and $r_{n}$ (see (21)), and hence $f(r_{n})>0$ provided that $x=r_{n}$ satisfies (24). By a direct substitution, this condition can be ensured by requiring that

Recalling that $g(\delta)\geq f\left(\left\|\delta\right\|_{2}\right)$, we have proved that $g$ satisfies the conditions of Lemma B.3 with $z=\delta^{*}$, $b=0$, and $\mathcal{B}=(\mathcal{B}_{r_{n}})_{\mathcal{S}}$, and we thus have $\delta^{*}\in(\mathcal{B}_{r_{n}})_{\mathcal{S}}$, or equivalently $\check{\beta}_{n}\in\mathcal{B}_{r_{n}}$.

We now combine the preceding lemmas to obtain Theorem 5.1. We require $r_{n}\leq R_{n}$ so the assumption that $\left\|\check{\beta}-\beta^{*}\right\|_{\infty}\leq R_{n}$ in Lemma B.2 is satisfied. From the definitions in (17) and (21), this is equivalent to requiring

which is true by assumption 5 of the theorem. This assumption also implies that (22) holds, since $\frac{\alpha}{4(\alpha+4)}\leq\frac{3}{2}$ for any $\alpha\geq 0$. Finally, by the conclusion of Lemma B.4, we have successful sign pattern recovery if $\beta_{\min}\geq r_{n}$, thus recovering assumption 4 of the theorem.

Appendix C Proofs of the Results in Section 6

By a direct differentiation, we obtain for $j\in\{1,\ldots,p\}$ that

where $\varepsilon_{i}=n^{-1}\left(Y_{i}-\mathsf{E}\,Y_{i}\right)$.

Fix $j\in\{1,\ldots,p\}$, and let $X_{i}:=n^{-1}(x_{i})_{j}Y_{i}$. As $X_{1},\ldots,X_{n}$ are bounded, they can be characterized using Hoeffding’s inequality .

Let $X_{1},\ldots,X_{n}$ be independent random variables such that $X_{i}$ takes its value in $[a_{i},b_{i}]$ almost surely for all $i\in\{1,\ldots,n\}$. Then

In our case, we can set $(b_{i}-a_{i})^{2}=n^{-2}(x_{i})_{j}^{2}$, since $Y_{i}\in\{0,1\}$. Since $\sum_{i=1}^{n}|(x_{i})_{j}|^{2}\leq n$ for all $k$ by assumption, we obtain

Thus, by Hoeffding’s inequality and the union bound, we obtain

C-B Proof of Corollary 6.3

where $\Gamma$ denotes the gamma function.

To study the concentration of measure behavior of $\nabla L_{n}(\beta^{*})$, we use the following result .

Let $X_{1},\ldots,X_{n}$ be independent real random variables. Suppose that there exist $v>0$ and $c>0$ such that $\sum_{i=1}^{n}\mathsf{E}\,X_{i}^{2}\leq v$, and

We proceed by evaluating the required moments for our setting. By a direct differentiation, we obtain

for $j\in\{1,\ldots,p\}$, where $\varepsilon_{i}:=n^{-1}\left(Y_{i}-\mathsf{E}\,Y_{i}\right)$.

Fix $j\in\{1,\ldots,p\}$, and let $X_{i}:=n^{-1}(x_{i})_{j}Y_{i}$. We have

Recall that $\theta_{i}=k^{-1}\left\langle x_{i},\beta^{*}\right\rangle^{-1}$. Using the first displayed equation in Section 7.3, we have

where we have applied the assumption $\sum_{i=1}^{n}(x_{i})_{j}^{2}\leq n$. Using the identity $\Gamma(k+2)=k(k+1)\Gamma(k)$, we obtain

As for the moments of higher orders, we have

With the upper bound (28) on $\theta_{i}$, we have

Using the identity $\left\|z\right\|_{q}\leq\left\|z\right\|_{2}$ for $q\geq 2$, and the assumption $\sum_{i=1}^{n}(x_{i})_{j}^{2}\leq n$, we obtain

For $k\in(0,1]$, we have $\frac{\Gamma(k+q)}{\Gamma(q)}\leq q!$, and hence by a direct substitution it suffices to choose

For $k\in(1,\infty)$, we have by induction on $q$ that $\frac{\Gamma(k+q)}{\Gamma(q)}\leq q!k^{q}$. Thus, for $k\in(1,\infty)$, it suffices that

Thus, applying Bernstein’s inequality and the union bound, we obtain

Since $L_{n}$ is self-concordant and $\left[D^{2}L_{n}(\beta^{*})\right]_{\mathcal{S},\mathcal{S}}$ is positive definite by assumption, the composition $L_{n}\circ Z$ with the padding operator $Z$ is strictly convex and thus $\check{\beta}_{n}$ uniquely exists. Therefore, we can apply Theorem 5.1. The scaling laws on $\tau_{n}$ and $(p,n,s)$ follow via the same argument to that in the proof of Corollary 6.2. Note that the final condition of Theorem 5.1 also imposes conditions on $(p,n,s)$, but for this term even the weaker condition $s^{2}(\log p)\nu_{n}^{2}\ll n$ suffices.

Appendix D Proof of Corollary 6.4

We apply the following lemma from to study the concentration behavior of $\nabla L_{n}(\Theta^{*})$.

Let $\Sigma$ and $\hat{\Sigma}_{n}$ be defined as in Section 6.4. We have

for all $t\in(0,8\kappa_{\Sigma^{*}}(1+c)^{2})$.

provided that $\tau_{n}\to 0$, and that $n$ is large enough so that the upper bound on $t$ in the lemma is satisfied.

Since $L_{n}$ is self-concordant and $\left[D^{2}L_{n}(\Theta^{*})\right]_{\mathcal{S},\mathcal{S}}$ is positive definite by assumption, the composition $L_{n}\circ Z$ with the padding operator $Z$ is strictly convex and thus $\check{\Theta}_{n}$ uniquely exists. Therefore, we can apply Theorem 5.1. The scaling laws on $\tau_{n}$ and $(p,n,s)$ follow via the same arguments as the preceding examples.

References