A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers

Introduction

High-dimensional statistics is concerned with models in which the ambient dimension of the problem ${p}$ may be of the same order as—or substantially larger than—the sample size ${n}$. On the one hand, its roots are quite old, dating back to work on random matrix theory and high-dimensional testing problems (e.g., [Gir95 , Mehta , Pas72 , Wig55 ]). On the other hand, the past decade has witnessed a tremendous surge of research activity. Rapid development of data collection technology is a major driving force: it allows for more observations to be collected (larger ${n}$) and also for more variables to be measured (larger ${p}$). Examples are ubiquitous throughout science: astronomical projects such as the Large Synoptic Survey Telescope (available at www.lsst.org) produce terabytes of data in a single evening; each sample is a high-resolution image, with several hundred megapixels, so that ${p}\gg 10^{8}$. Financial data is also of a high-dimensional nature, with hundreds or thousands of financial instruments being measured and tracked over time, often at very fine time intervals for use in high frequency trading. Advances in biotechnology now allow for measurements of thousands of genes or proteins, and lead to numerous statistical challenges (e.g., see the paper BicBroHuaLi09 and references therein). Various types of imaging technology, among them magnetic resonance imaging in medicine LusDonSanPau08 and hyper-spectral imaging in ecology Lan02 , also lead to high-dimensional data sets.

Within the framework of high-dimensional statistics, the goal is to obtain bounds on a given performance metric that hold with high probability for a finite sample size, and provide explicit control on the ambient dimension ${p}$, as well as other structural parameters such as the sparsity of a vector, degree of a graph or rank of matrix. Typically, such bounds show that the ambient dimension and structural parameters can grow as some function of the sample size ${n}$, while still having the statistical error decrease to zero. The choice of performance metric is application-dependent; some examples include prediction error, parameter estimation error and model selection error.

Our Contributions

As we have noted previously, almost all of these estimators can be seen as particular types of regularized $M$-estimators, with the choice of loss function, regularizer and statistical assumptions changing according to the model. This methodological similarity suggests an intriguing possibility: is there a common set of theoretical principles that underlies analysis of all these estimators? If so, it could be possible to gain a unified understanding of a large collection of techniques for high-dimensional estimation and afford some insight into the literature.

The main contribution of this paper is to provide an affirmative answer to this question. In particular, we isolate and highlight two key properties of a regularized $M$-estimator—namely, a decomposability property for the regularizer and a notion of restricted strong convexity that depends on the interaction between the regularizer and the loss function. For loss functions and regularizers satisfying these two conditions, we prove a general result (Theorem 1) about consistency and convergence rates for the associated estimators. This result provides a family of bounds indexed by subspaces, and each bound consists of the sum of approximation error and estimation error. This general result, when specialized to different statistical models, yields in a direct manner a large number of corollaries, some of them known and others novel. In concurrent work, a subset of the current authors has also used this framework to prove several results on low-rank matrix estimation using the nuclear norm NegWai09 , as well as minimax-optimal rates for noisy matrix completion NegWai10b and noisy matrix decomposition AgaNegWai11 . Finally, en route to establishing these corollaries, we also prove some new technical results that are of independent interest, including guarantees of restricted strong convexity for group-structured regularization (Proposition 1).

The remainder of this paper is organized as follows. We begin in Section 2 by formulating the class of regularized $M$-estimators that we consider, and then defining the notions of decomposability and restricted strong convexity. Section 3 is devoted to the statement of our main result (Theorem 1) and discussion of its consequences. Subsequent sections are devoted to corollaries of this main result for different statistical models, including sparse linear regression (Section 4) and estimators based on group-structured regularizers (Section 5). A number of technical results are presented within the appendices in the supplementary file Neg12supp .

Problem Formulation and Some Key Properties

In this section we begin with a precise formulation of the problem, and then develop some key properties of the regularizer and loss function.

2 Decomposability of ℛℛ{\mathcal{R}}

is referred to as the perturbation subspace, representing deviations away from the model subspace ${\mathcal{M}}$. In the ideal case, we have $\overline{{\mathcal{M}}}{}^{\perp}={\mathcal{M}}^{\perp}$, but our definition allows for the possibility that $\overline{{\mathcal{M}}}$ is strictly larger than ${\mathcal{M}}$, so that $\overline{{\mathcal{M}}}{}^{\perp}$ is strictly smaller than ${{\mathcal{M}}^{\perp}}$. This generality is needed for treating the case of low-rank matrices and nuclear norm, as discussed in Example 3 to follow.

Given a pair of subspaces ${\mathcal{M}}\subseteq\overline{{\mathcal{M}}}$, a norm-based regularizer ${\mathcal{R}}$ is decomposable with respect to $({\mathcal{M}},\overline{{\mathcal{M}}}{}^{\perp})$ if

In order to build some intuition, let us consider the ideal case ${\mathcal{M}}=\overline{{\mathcal{M}}}$ for the time being, so that the decomposition (4) holds for all pairs $({\theta},{\gamma})\in{\mathcal{M}}\times{{\mathcal{M}}^{\perp}}$. For any given pair $({\theta},{\gamma})$ of this form, the vector ${\theta}+{\gamma}$ can be interpreted as a perturbation of the model vector ${\theta}$ away from the subspace ${\mathcal{M}}$, and it is desirable that the regularizer penalize such deviations as much as possible. By the triangle inequality for a norm, we always have ${{\mathcal{R}}({\theta}+{\gamma})}\leq{{\mathcal{R}}({\theta})}+{{\mathcal{R}}({\gamma})}$, so that the decomposability condition (4) holds if and only if the triangle inequality is tight for all pairs $({\theta},{\gamma})\in({\mathcal{M}},{{\mathcal{M}}^{\perp}})$. It is exactly in this setting that the regularizer penalizes deviations away from the model subspace ${\mathcal{M}}$ as much as possible.

with the projection $\Pi_{{{\mathcal{M}}^{\perp}}}$ defined in an analogous manner. To simplify notation, we frequently use the shorthand $u_{{\mathcal{M}}}={\Pi_{{\mathcal{M}}}(u)}$ and $u_{{\mathcal{M}}^{\perp}}=\Pi_{{{\mathcal{M}}^{\perp}}}(u)$.

Here our notation reflects the fact that ${\mathcal{M}}$ depends explicitly on the chosen subset ${S}$. By construction, we have $\Pi_{{\mathcal{M}}({S})}(\theta^{*})=\theta^{*}$ for any vector $\theta^{*}$ that is supported on ${S}$.

In this case, we may define $\overline{{\mathcal{M}}}({S})={\mathcal{M}}({S})$ and note that the orthogonal complement with respect to the Euclidean inner product is given by

In many applications sparsity arises in a more structured fashion, with groups of coefficients likely to be zero (or nonzero) simultaneously. In order to model this behavior, suppose that the index set $\{1,2,\ldots,{p}\}$ can be partitioned into a set of ${{N_{{\mathcal{G}}}}}$ disjoint groups, say, ${\mathcal{G}}=\{{G}_{1},{G}_{2},\ldots,{G}_{{N_{{\mathcal{G}}}}}\}$. With this setup, for a given vector ${\vec{{\alpha}}}=({\alpha}_{1},\ldots,{\alpha}_{{N_{{\mathcal{G}}}}})\in[1,\infty]^{{N_{{\mathcal{G}}}}}$, the associated $(1,{\vec{{\alpha}}})$-group norm takes the form

We now show that the norm ${\|\cdot\|_{{\mathcal{G}},{\vec{{\alpha}}}}}$ is again decomposable with respect to appropriately defined subspaces. Indeed, given any subset ${{S}_{{\mathcal{G}}}}\subseteq\{1,\ldots,{{N_{{\mathcal{G}}}}}\}$ of group indices, say, with cardinality ${{s}_{\mathcal{G}}}=|{{S}_{{\mathcal{G}}}}|$, we can define the subspace

as well as its orthogonal complement with respect to the usual Euclidean inner product

With these definitions, for any pair of vectors ${\theta}\in{\mathcal{M}}({{S}_{{\mathcal{G}}}})$ and ${\gamma}\in\overline{{\mathcal{M}}}{}^{\perp}({{S}_{{\mathcal{G}}}})$, we have

thus verifying the decomposability condition.

In the preceding example, we exploited the fact that the groups were nonoverlapping in order to establish the decomposability property. Therefore, some modifications would be required in order to choose the subspaces appropriately for overlapping group regularizers proposed in past work Jac09 , JenMai10 .

In many settings, it is natural to consider estimating matrices that are low-rank; examples include principal component analysis, spectral clustering, collaborative filtering and matrix completion. With certain exceptions, it is computationally expensive to enforce a rank-constraint in a direct manner, so that a variety of researchers have studied the nuclear norm, also known as the trace norm, as a surrogate for a rank constraint. More precisely, the nuclear norm is given by

where $\{\sigma_{j}(\Theta)\}$ are the singular values of the matrix $\Theta$.

So as to simplify notation, we omit the indices $(U,V)$ when they are clear from context. Unlike the preceding examples, in this case, the set ${\mathcal{M}}$ is notHowever, as is required by our theory, we do have the inclusion ${\mathcal{M}}\subseteq\overline{{\mathcal{M}}}$. Indeed, given any $\Theta\in{\mathcal{M}}$ and $\Gamma\in\overline{{\mathcal{M}}}{}^{\perp}$, we have $\Theta^{T}\Gamma=0$ by definition, which implies that ${\langle\!\langle{\Theta},{\Gamma}\rangle\!\rangle}=\operatorname{trace}(\Theta^{T}\Gamma)=0$. Since $\Gamma\in\overline{{\mathcal{M}}}{}^{\perp}$ was arbitrary, we have shown that $\Theta$ is orthogonal to the space $\overline{{\mathcal{M}}}{}^{\perp}$, meaning that it must belong to $\overline{{\mathcal{M}}}$. equal to $\overline{{\mathcal{M}}}$.

Finally, we claim that the nuclear norm is decomposable with respect to the pair $({\mathcal{M}},\overline{{\mathcal{M}}}{}^{\perp})$. By construction, any pair of matrices $\Theta\in{\mathcal{M}}$ and $\Gamma\in\overline{{\mathcal{M}}}{}^{\perp}$ have orthogonal row and column spaces, which implies the required decomposability condition—namely, $|\!|\!|\Theta+\Gamma|\!|\!|_{{1}}=|\!|\!|\Theta|\!|\!|_{{1}}+|\!|\!|\Gamma|\!|\!|_{{1}}$.

3 A Key Consequence of Decomposability

This notion is best understood by working through some examples.

Dual of group norm

As special cases of this general duality relation, the block $(1,2)$ norm that underlies the usual group Lasso leads to a block $(\infty,2)$ norm as the dual, whereas the block $(1,\infty)$ norm leads to a block $(\infty,1)$ norm as the dual.

Dual of nuclear norm

The dual norm plays a key role in our general theory, in particular, by specifying a suitable choice of the regularization weight ${\lambda_{n}}$. We summarize in the following:

Suppose that ${\mathcal{L}}$ is a convex and differentiable function, and consider any optimal solution $\widehat{{\theta}}$ to the optimization problem (1) with a strictly positive regularization parameter satisfying

Then for any pair $({\mathcal{M}},\overline{{\mathcal{M}}}{}^{\perp})$ over which ${\mathcal{R}}$ is decomposable, the error ${\widehat{{\Delta}}}={\widehat{{\theta}}_{{\lambda_{n}}}}-{{\theta}^{*}}$ belongs to the set

4 Restricted Strong Convexity

We now turn to an important requirement of the loss function and its interaction with the statistical model. Recall that $\widehat{\Delta}={\widehat{{\theta}}_{{\lambda_{n}}}}-{{\theta}^{*}}$ is the difference between an optimal solution ${\widehat{{\theta}}_{{\lambda_{n}}}}$ and the true parameter, and consider the loss differenceTo simplify notation, we frequently write ${\mathcal{L}}({\theta})$ as shorthand for ${\mathcal{L}}({\theta};{Z_{1}^{n}})$ when the underlying data ${Z_{1}^{n}}$ is clear from context. ${\mathcal{L}}({\widehat{{\theta}}_{{\lambda_{n}}}})-{\mathcal{L}}({{\theta}^{*}})$. In the classical setting, under fairly mild conditions, one expects that the loss difference should converge to zero as the sample size ${n}$ increases. It is important to note, however, that such convergence on its own is not sufficient to guarantee that ${\widehat{{\theta}}_{{\lambda_{n}}}}$ and ${{\theta}^{*}}$ are close or, equivalently, that $\widehat{\Delta}$ is small. Rather, the closeness depends on the curvature of the loss function, as illustrated in Figure 2.

In a desirable setting [panel (a)], the loss function is sharply curved around its optimum ${\widehat{{\theta}}_{{\lambda_{n}}}}$, so that having a small loss difference $|{\mathcal{L}}({{\theta}^{*}})-{\mathcal{L}}({\widehat{{\theta}}_{{\lambda_{n}}}})|$ translates to a small error $\widehat{\Delta}={\widehat{{\theta}}_{{\lambda_{n}}}}-{{\theta}^{*}}$. Panel (b) illustrates a less desirable setting, in which the loss function is relatively flat, so that the loss difference can be small while the error $\widehat{\Delta}$ is relatively large.

The standard way to ensure that a function is “not too flat” is via the notion of strong convexity. Since ${\mathcal{L}}$ is differentiable by assumption, we may perform a first-order Taylor series expansion at ${{\theta}^{*}}$ and in some direction $\Delta$; the error in this Taylor series is given by

The loss function satisfies a restricted strong convexity (RSC) condition with curvature ${{\kappa}_{{\mathcal{L}}}}>0$ and tolerance function $\tau_{\mathcal{L}}$ if

We will see in the sequel that for many loss functions, it is possible to prove that with high probability the first-order Taylor series error satisfies a lower bound of the form

A bound of the form (24) implies a form of restricted strong convexity as long as ${{\mathcal{R}}({\Delta})}$ is not “too large” relative to $\|{\Delta}\|$. In order to formalize this notion, we define a quantity that relates the error norm and the regularizer:

This quantity reflects the degree of compatibility between the regularizer and the error norm over the subspace ${\mathcal{M}}$. In alternative terms, it is the Lipschitz constant of the regularizer with respect to the error norm, restricted to the subspace ${\mathcal{M}}$. As a simple example, if ${\mathcal{M}}$ is a ${s}$-dimensional coordinate subspace, with regularizer ${{\mathcal{R}}(u)}=\|u\|_{1}$ and error norm ${\|u\|}=\|u\|_{2}$, then we have ${\Psi({\mathcal{M}})}=\sqrt{{s}}$.

Therefore, whenever a bound of the form (24) holds and $\theta^{*}\in{\mathcal{M}}$, we are guaranteed that

Consequently, as long as the sample size is large enough that $16{\kappa_{2}}{\Psi^{2}(\overline{{\mathcal{M}}})}g({n},{p})<\frac{\kappa_{1}}{2}$, the restricted strong convexity condition will hold with ${{\kappa}_{{\mathcal{L}}}}=\frac{\kappa_{1}}{2}$ and $\tau_{\mathcal{L}}(\theta^{*})=0$. We make use of arguments of this flavor throughout this paper.

Bounds for General M𝑀M-Estimators

Let us recall our running assumptions on the structure of the convex program (1). {longlist}[(G2)]

The regularizer ${\mathcal{R}}$ is a norm and is decomposable with respect to the subspace pair $({\mathcal{M}},\overline{{\mathcal{M}}}{}^{\perp})$, where ${\mathcal{M}}\subseteq\overline{{\mathcal{M}}}$.

The loss function ${\mathcal{L}}$ is convex and differentiable, and satisfies restricted strong convexity with curvature ${{\kappa}_{{\mathcal{L}}}}$ and tolerance $\tau_{\mathcal{L}}$. The reader should also recall the definition (25) of the subspace compatibility constant. With this notation, we can now state the main result of this paper:

Under conditions (G1) and (G2), consider the problem (1) based on a strictly positive regularization constant ${\lambda_{n}}\geq 2{{\mathcal{R}}^{*}(\nabla{\mathcal{L}}({{\theta}^{*}}))}$. Then any optimal solution ${\widehat{{\theta}}_{{\lambda_{n}}}}$ to the convex program (1) satisfies the bound

Let us consider in more detail some different features of this result.

It should be noted that Theorem 1 is actually a deterministic statement about the set of optimizers of the convex program (1) for a fixed choice of ${\lambda_{n}}$. Although the program is convex, it need not be strictly convex, so that the global optimum might be attained at more than one point ${\widehat{{\theta}}_{{\lambda_{n}}}}$. The stated bound holds for any of these optima. Probabilistic analysis is required when Theorem 1 is applied to particular statistical models, and we need to verify that the regularizer satisfies the condition

and that the loss satisfies the RSC condition. A challenge here is that since ${{\theta}^{*}}$ is unknown, it is usually impossible to compute the right-hand side of the condition (28). Instead, when we derive consequences of Theorem 1 for different statistical models, we use concentration inequalities in order to provide bounds that hold with high probability over the data.

As the dimension of the subspace ${\mathcal{M}}$ increases (so that the dimension of ${\mathcal{M}}^{\perp}$ decreases), the approximation error tends to zero. But since ${\mathcal{M}}\subseteq\overline{{\mathcal{M}}}$, the estimation error is increasing at the same time. Thus, in the usual way, optimal rates are obtained by choosing ${\mathcal{M}}$ and $\overline{{\mathcal{M}}}$ so as to balance these two contributions to the error. We illustrate such choices for various specific models to follow.

As will be clarified in the sequel, many high-dimensional statistical models have an unidentifiable component, and the tolerance term $\tau_{\mathcal{L}}$ reflects the degree of this nonidentifiability.

Focusing first on the bound (30a), it consists of three terms, each of which has a natural interpretation. First, it is inversely proportional to the RSC constant ${{\kappa}_{{\mathcal{L}}}}$, so that higher curvature guarantees lower error, as is to be expected. The error bound grows proportionally with the subspace compatibility constant ${\Psi(\overline{{\mathcal{M}}})}$, which measures the compatibility between the regularizer ${\mathcal{R}}$ and error norm ${\|\cdot\|}$ over the subspace $\overline{{\mathcal{M}}}$ (see Definition 3). This term increases with the size of subspace $\overline{{\mathcal{M}}}$, which contains the model subspace ${\mathcal{M}}$. Third, the bound also scales linearly with the regularization parameter ${\lambda_{n}}$, which must be strictly positive and satisfy the lower bound (28). The bound (30b) on the error measured in the regularizer norm is similar, except that it scales quadratically with the subspace compatibility constant. As the proof clarifies, this additional dependence arises since the regularizer over the subspace $\overline{{\mathcal{M}}}$ is larger than the norm ${\|\cdot\|}$ by a factor of at most ${\Psi(\overline{{\mathcal{M}}})}$ (see Definition 3).

Obtaining concrete rates using Corollary 1 requires some work in order to verify the conditions of Theorem 1 and to provide control on the three quantities in the bounds (30a) and (30b), as illustrated in the examples to follow.

Convergence Rates for Sparse Regression

for some choice ${\lambda_{n}}>0$ of regularization parameter. Note that this Lasso estimator is a particular case of the general $M$-estimator (1), based on the loss function and regularization pair ${\mathcal{L}}({\theta};{Z_{1}^{n}})=\frac{1}{2{n}}\|y-X\theta\|_{2}^{2}$ and ${{\mathcal{R}}(\theta)}=\sum_{j=1}^{p}|\theta_{j}|=\|\theta\|_{1}$. We now show how Theorem 1 can be specialized to obtain bounds on the error ${\widehat{{\theta}}_{{\lambda_{n}}}}-{{\theta}^{*}}$ for the Lasso estimate.

For the least squares loss function that underlies the Lasso, the first-order Taylor series expansion from Definition 2 is exact, so that

Thus, in this special case, the Taylor series error is independent of $\theta^{*}$, a fact which allows for substantial theoretical simplification. More precisely, in order to establish restricted strong convexity, it suffices to establish a lower bound on $\|{X}{\Delta}\|_{2}^{2}/{n}$ that holds uniformly for an appropriately restricted subset of ${p}$-dimensional vectors ${\Delta}$.

2 Lasso Estimates with Exact Sparsity

Here we have set the upper bound to one in order to simplify notation. This particular choice entails no loss of generality, since we can always rescale the linear model appropriately (including the observation noise variance) so that it holds.

For instance, this condition holds when the noise vector $w$ has i.i.d. $N(0,1)$ entries or consists of independent bounded random variables. Under these conditions, we recover as a corollary of Theorem 1 the following result:

Consider an ${s}$-sparse instance of the linear regression model (31) such that ${X}$ satisfies the RE condition (34) and the column normalization condition (38). Given the Lasso program (32) with regularization parameter ${\lambda_{n}}=4\sigma\sqrt{\frac{\log{p}}{{n}}}$, then with probability at least $1-{c}_{1}\exp(-{c}_{2}{n}{\lambda_{n}}^{2})$, any optimal solution ${\widehat{{\theta}}_{{\lambda_{n}}}}$ satisfies the bounds

3 Lasso Estimates with Weakly Sparse Models

with probability at least $1-{c}_{1}\exp(-{c}_{2}{n}{\lambda_{n}}^{2})$.

Now recall the subspaces ${\mathcal{M}}({{S}_{\eta}})$ and ${{\mathcal{M}}^{\perp}}({{S}_{\eta}})$ previously defined in equations (6) and (1) of Example 1, where we set ${S}={{S}_{\eta}}$. The following lemma, proved in the supplement Neg12supp , provides sufficient conditions for restricted strong convexity with respect to these subspace pairs:

Consequently, we may apply Theorem 1 with ${{\kappa}_{{\mathcal{L}}}}=\kappa_{1}/4$ and $\tau_{\mathcal{L}}^{2}(\theta^{*})=8\kappa_{2}\frac{\log{p}}{{n}}\|\theta^{*}_{{S}_{\eta}^{c}}\|_{1}^{2}$ to conclude that

where we have used the fact that ${\Psi^{2}({{S}_{\eta}})}=|{{S}_{\eta}}|$, as noted in the proof of Corollary 2.

Setting ${\eta}={\lambda_{n}}/\kappa_{1}$ and then substituting the bounds (46) and (4.3) into the bound (4.3) yields

For any fixed noise variance, our choice of regularization parameter ensures that the ratio $\frac{(\log{p})/{n}}{{\lambda_{n}}/\kappa_{1}}$ is of order one, so that the claim follows.

4 Extensions to Generalized Linear Models

In order to extend the error bounds from the previous section, a key ingredient is to establish that this GLM-based loss function satisfies a form of restricted strong convexity. Along these lines, Negahban et al. Neg09 proved the following result: suppose that the covariate vectors $x_{i}$ are zero-mean with covariance matrix $\Sigma\succ 0$ and are drawn i.i.d. from a distribution with sub-Gaussian tails [see equation (39)]. Then there are constants $\kappa_{1},\kappa_{2}$ such that the first-order Taylor series error for the GLM-based loss (4.4) satisfies the lower bound

As discussed following Definition 2, this type of lower bound implies that ${\mathcal{L}}$ satisfies a form of RSC, as long as the sample size scales as ${n}=\Omega({s}\log{p})$, where ${s}$ is the target sparsity. Consequently, this lower bound (51) allows us to recover analogous bounds on the error $\|{\widehat{\theta}}_{{\lambda_{n}}}-\theta^{*}\|_{2}$ of the GLM-based estimator (4.4).

Convergence Rates for Group-Structured Norms

Given a collection ${\mathcal{G}}=\{{G}_{1},\ldots,{G}_{{N_{{\mathcal{G}}}}}\}$ of groups, recall from Example 2 in Section 2.2 the definition of the group norm ${\|\cdot\|_{{\mathcal{G}},{\vec{{\alpha}}}}}$. In full generality, this group norm is based on a weight vector ${\vec{{\alpha}}}=({\alpha}_{1},\ldots,{\alpha}_{{N_{{\mathcal{G}}}}})\in[2,\infty]^{{{N_{{\mathcal{G}}}}}}$, one for each group. For simplicity, here we consider the case when ${\alpha}_{t}={\alpha}$ for all $t=1,2,\ldots,{{N_{{\mathcal{G}}}}}$, and we use ${\|\cdot\|_{{\mathcal{G}},{\alpha}}}$ to denote the associated group norm. As a natural extension of the Lasso, we consider the block Lasso estimator

where ${\lambda_{n}}>0$ is a user-defined regularization parameter. Different choices of the parameter ${\alpha}$ yield different estimators, and in this section we consider the range ${\alpha}\in[2,\infty]$. This range covers the two most commonly applied choices, ${\alpha}=2$, often referred to as the group Lasso, as well as the choice ${\alpha}=+\infty$.

As a parallel to our analysis of ordinary sparse regression, our first step is to provide a condition sufficient to guarantee restricted strong convexity for the group-sparse setting. More specifically, we state the natural extension of condition (37) to the block-sparse setting and prove that it holds with high probability for the class of $\Sigma$-Gaussian random designs. Recall from Theorem 1 that the dual norm of the regularizer plays a central role. As discussed previously, for the block-$(1,{{\alpha}})$-regularizer, the associated dual norm is a block-$(\infty,{{{\alpha}^{\ast}}})$ norm, where $({\alpha},{{{\alpha}^{\ast}}})$ are conjugate exponents satisfying $\frac{1}{{\alpha}}+\frac{1}{{{{\alpha}^{\ast}}}}=1$.

Let us consider a more general setting, say, with ${\alpha}=2$ and ${{N_{{\mathcal{G}}}}}$ groups each of size ${m}$, so that ${p}={{N_{{\mathcal{G}}}}}{m}$. For this choice of groups and norm, we have

2 Convergence Rates

Note that this is a natural generalization of the column normalization condition (38), to which it reduces when we have ${{N_{{\mathcal{G}}}}}={p}$ groups, each of size one. As before, we may assume without loss of generality, rescaling ${X}$ and the noise as necessary, that condition (56) holds with constant one. Finally, we define the maximum group size ${m}=\max_{t=1,\ldots,{{N_{{\mathcal{G}}}}}}|{G}_{t}|$. With this notation, we have the following novel result:

Suppose that the noise $w$ is sub-Gaussian (39), and the design matrix ${X}$ satisfies condition (53) and the block normalization condition (56). If we solve the group Lasso with

then with probability at least $1-2/{{N_{{\mathcal{G}}}}}^{2}$, for any group subset ${{S}_{{\mathcal{G}}}}\subseteq\{1,2,\ldots,{{N_{{\mathcal{G}}}}}\}$ with cardinality$|{{S}_{{\mathcal{G}}}}|={{s}_{\mathcal{G}}}$, any optimal solution ${\widehat{{\theta}}_{{\lambda_{n}}}}$ satisfies

Since the result applies to any ${\alpha}\in[2,\infty]$, we can observe how the choices of different group-sparse norms affect the convergence rates. So as to simplify this discussion, let us assume that the groups are all of equal size ${m}$, so that ${p}={m}{{N_{{\mathcal{G}}}}}$ is the ambient dimension of the problem.

Case ${\alpha}=2$: The case ${\alpha}=2$ corresponds to the block $(1,2)$ norm, and the resulting estimator is frequently referred to as the group Lasso. For this case, we can set the regularization parameter as ${\lambda_{n}}=2\sigma\{\sqrt{\frac{{m}}{{n}}}+\sqrt{\frac{\log{{N_{{\mathcal{G}}}}}}{{n}}}\}$. If we assume, moreover, that $\theta^{*}$ is exactly group-sparse, say, supported on a group subset ${{S}_{{\mathcal{G}}}}\subseteq\{1,2,\ldots,{{N_{{\mathcal{G}}}}}\}$ of cardinality ${{s}_{\mathcal{G}}}$, then the bound (58) takes the form

Similar bounds were derived in independent work by Lounici et al. Lou09 and Huang and Zhang HuaZha09 for this special case of exact block sparsity. The analysis here shows how the different terms arise, in particular, via the noise magnitude measured in the dual norm of the block regularizer.

In this case, if we optimize the choice of ${S}$ in the bound (58) so as to trade off the estimation and approximation errors, then we obtain

which is a novel result. This result is a generalization of our earlier Corollary 3, to which it reduces when we have ${{N_{{\mathcal{G}}}}}={p}$ groups each of size ${m}=1$.

We provide the proof of Corollary 4 in the supplementary appendix Neg12supp . It is based on verifying the conditions of Theorem 1: more precisely, we use Proposition 1 in order to establish RSC, and we provide a lemma that shows that the regularization choice (57) is valid in the context of Theorem 1.

Discussion

In this paper we have presented a unified framework for deriving error bounds and convergence rates for a class of regularized $M$-estimators. The theory is high-dimensional and nonasymptotic in nature, meaning that it yields explicit bounds that hold with high probability for finite sample sizes and reveals the dependence on dimension and other structural parameters of the model. Two properties of the $M$-estimator play a central role in our framework. We isolated the notion of a regularizer being decomposable with respect to a pair of subspaces and showed how it constrains the error vector—meaning the difference between any solution and the nominal parameter—to lie within a very specific set. This fact is significant, because it allows for a fruitful notion of restricted strong convexity to be developed for the loss function. Since the usual form of strong convexity cannot hold under high-dimensional scaling, this interaction between the decomposable regularizer and the loss function is essential.

Acknowledgments

All authors were partially supported by NSFGrants DMS-06-05165 and DMS-09-07632. B. Yu acknowledges additional support from NSF Grant SES-0835531 (CDI); M. J. Wainwright and S. N. Negahban acknowledge additional support from the NSF Grant CDI-0941742 and AFOSR Grant09NL184; and P. Ravikumar acknowledges additional support from NSF Grant IIS-101842. We thank a number of people, including Arash Amini, Francis Bach, Peter Buhlmann, Garvesh Raskutti, Alexandre Tsybakov, Sara van de Geer and Tong Zhang for helpful discussions.

Supplementary material for “A unified framework for high-dimensional analysis of $\bolds{M}$-estimators with decomposable regularizers” \slink[doi]10.1214/12-STS400SUPP \sdatatype.pdf \sfilenamests400_supp.pdf \sdescriptionDue to space constraints, the proofs and technical details have been given in the supplementary document by Negahban et al. Neg12supp .

References