A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

Sahand N. NegahbanPradeep RavikumarMartin J. WainwrightBin Yu

article2009NeurIPS1,483 citations

Establishes a unified theoretical framework for deriving consistency and optimal convergence rates for high-dimensional regularized M-estimators by characterizing regularizer decomposability and restricted strong convexity of loss functions.

Listen

Modern data collection across genomics, finance, imaging, and astronomy regularly produces datasets where the number of measured features far exceeds the number of available observations. In such high-dimensional regimes, classical statistical methods fail because models become mathematically nonidentifiable without enforcing structural constraints. To extract reliable insights, practitioners rely on regularized optimization estimators that penalize complexity, using techniques such as sparsity constraints, group structures, or low-rank matrix assumptions. While many separate theoretical analyses have emerged for individual algorithms, the lack of a common foundational theory has made it difficult to compare methods systematically and establish universal performance guarantees.

The article establishes a single, unified mathematical framework for analyzing the statistical consistency and convergence rates of regularized convex estimators in high-dimensional settings. It demonstrates that estimation error bounds for a wide variety of problem formulations follow from two core properties: decomposability of the regularizer and restricted strong convexity of the loss function.

The authors conducted a high-level theoretical and statistical analysis based on nonasymptotic convex optimization. Rather than relying on classical large-sample approximations where the parameter dimension is fixed, the framework accommodates settings where both the dimension and sample size grow toward infinity. The credibility of the framework is supported by deriving deterministic error bounds and pairing them with probabilistic concentration inequalities under standard sub-Gaussian noise and correlated random design models.

The article yields several critical findings. First, when a regularization penalty satisfies a decomposability property across subspace pairs, any estimation error vector is mathematically constrained to lie within a very small, structured set. Second, global strong convexity of the loss function is unnecessary; estimators achieve fast convergence as long as restricted strong convexity holds over this specific error set. Third, the resulting master theorem produces explicit, finite-sample error bounds that neatly decompose into estimation error and approximation error across sparse vectors, group-structured norms, and low-rank matrices. Fourth, applying this framework to sparse linear regression and group-sparse estimators recovers optimal convergence rates, demonstrating that sample size requirements scale with the intrinsic structural dimension—such as the number of active variables or groups—multiplied by logarithmic factors of the ambient dimension, rather than scaling with the ambient dimension itself.

These findings provide clear practical implications for high-dimensional modeling, risk management, and computational efficiency. Practitioners can now deploy regularized estimators with rigorous statistical guarantees on accuracy even when data features severely outnumber observations. The framework confirms that choosing penalties tailored to the true underlying structure—such as group-structured penalties when features naturally cluster—substantially reduces estimation error and sample size requirements compared to generic penalties. Furthermore, it ensures that these convex methods avoid overfitting and deliver predictable performance in high-stakes domains.

Decision-makers and analytics teams should adopt decomposable regularizers aligned with their domain structures, such as standard absolute-value penalties for sparse features, group penalties for clustered variables, and nuclear norms for low-rank matrix data. When configuring algorithms, teams should set regularization tuning parameters proportionally to the dual norm of the loss gradient, scaling with the noise level and logarithmic factor of the feature count to ensure optimal estimation. If the true data-generating process does not strictly adhere to simple sparsity, teams should evaluate weakly sparse formulations to properly account for approximation error trade-offs.

The analysis assumes convex, differentiable loss functions and covariates with reasonably well-behaved, sub-Gaussian tails, meaning performance could degrade under heavy-tailed distributions or severe model misspecification. However, within these standard operating assumptions, there is high confidence in the theoretical optimality and robustness of the resulting convergence guarantees.

Massachusetts Institute of Technology University of California Berkeley University of Texas at Austin inference optimization optimization problems decomposable regularizers low-rank matrix estimation sparse regression

arXiv: 1010.2731

Paper: Regression Shrinkage and Selection Via the Lasso, Robert Tibshirani (1996). It introduces the foundational Lasso regularizer for sparse regression, providing the basic regularized M-estimation paradigm that this paper generalizes to decomposable regularizers and high-dimensional settings.
Paper: On Model Selection Consistency of Lasso, Peng Zhao et al. (2006). It analyzes the irrepresentable condition and consistency guarantees of L1 regularization in high dimensions, establishing classical recovery bounds that the unified framework recovers and generalizes.
Paper: Feature selection, L1 vs. L2 regularization, and rotational invariance, Andrew Y. Ng (2004). It establishes early sample-complexity and geometric properties of L1 versus L2 penalties in high dimensions, motivating the theoretical analysis of structured regularizers.
Paper: Convex multi-task feature learning, Andreas Argyriou et al. (2008). It develops block-norm and group-regularized convex estimation for multi-task learning, serving as a primary structured regularizer unified under the decomposability framework.
Paper: Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Peter L. Bartlett et al. (2002). It provides the empirical process and Rademacher complexity machinery used to analyze statistical risk and restricted curvature under high-dimensional scaling.

Paper: Spectral Regularization Algorithms for Learning Large Incomplete Matrices, Rahul Mazumder et al. (2010). It develops practical spectral regularization algorithms for matrix completion under nuclear norm penalties, directly implementing the structured matrix M-estimators analyzed theoretically in the unified framework.
Paper: Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, Martin Jaggi (2013). It presents projection-free Frank-Wolfe optimization tailored for sparse and low-rank regularized convex problems, offering scalable solvers for the high-dimensional estimators characterized in this work.
Paper: Robust Recovery of Subspace Structures by Low-Rank Representation, Guangcan Liu et al. (2010). It applies decomposable low-rank and sparse matrix regularizers to the robust subspace recovery problem, extending the theoretical estimation principles to corrupted multi-subspace data.
Paper: Tensor Completion for Estimating Missing Values in Visual Data, Ji Liu et al. (2009). It extends convex low-rank trace-norm regularization from matrices to higher-order tensors for missing value estimation in visual data.

Cover for A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

Abstract

High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n → 0, a line of recent work has studied models with various types of low-dimensional structure, including sparse vectors, sparse and structured matrices, low-rank matrices and combinations thereof. In such settings, a general approach to estimation is to solve a regularized optimization problem, which combines a loss function measuring how well the model fits the data with some regularization function that encourages the assumed structure. This paper provides a unified framework for establishing consistency and convergence rates for such regularized M-estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive some existing results, and also to obtain a number of new results on consistency and convergence rates, in both ℓ2-error and related norms. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure corresponding regularized M-estimators have fast convergence rates and which are optimal in many well-studied cases.

Topics

inference optimization optimization problems regularization maximum likelihood estimator

Keywords

decomposable regularizers low-rank matrix estimation sparse regression nuclear norm minimization matrix completion robust PCA covariance matrix estimation high-dimensional linear regression group-structured regularizers noisy matrix decomposition

1 Introduction
2 Problem Formulation and Some Key Properties
2.1 A Family of MM-Estimators
2.2 Decomposability of ℛ{\mathcal{R}}
2.3 A Key Consequence of Decomposability
2.4 Restricted Strong Convexity
3 Bounds for General MM-Estimators
4 Convergence Rates for Sparse Regression
4.1 Restricted Eigenvalues for Sparse Linear Regression
4.2 Lasso Estimates with Exact Sparsity
4.3 Lasso Estimates with Weakly Sparse Models
4.4 Extensions to Generalized Linear Models
5 Convergence Rates for Group-Structured Norms
5.1 Restricted Strong Convexity for Group Sparsity
5.2 Convergence Rates
6 Discussion
References

Knowls

Knowl 1 — Master Error Bound for Regularized M-Estimators with Decomposable Norms
theoretical result
Consider the regularized $M$ -estimator

$\widehat{\theta}_{\lambda_n} \in \arg\min_{\theta \in \mathbb{R}^p} \left\{ \mathcal{L}(\theta; Z_1^n) + \lambda_n \mathcal{R}(\theta) \right\}$

where $\mathcal{L}: \mathbb{R}^p \times \mathcal{Z}^n \to \mathbb{R}$ is a convex, differentiable empirical loss function over $n$ observations $Z_1^n = \{Z_1, \dots, Z_n\}$ , $\mathcal{R}: \mathbb{R}^p \to \mathbb{R}_+$ is a norm regularizer, $\lambda_n > 0$ is a regularization parameter, and $\theta^* \in \arg\min_{\theta \in \mathbb{R}^p} \mathbb{E}[\mathcal{L}(\theta; Z_1^n)]$ is a minimizer of the population risk.

Let $\|\cdot\|$ be an error norm induced by an inner product $\langle \cdot, \cdot \rangle$ on $\mathbb{R}^p$ , and let $\mathcal{R}^*(v) := \sup_{\mathcal{R}(u) \le 1} \langle u, v \rangle$ denote the dual norm of $\mathcal{R}$ . Suppose the following conditions hold:
1. Decomposability: The regularizer $\mathcal{R}$ is decomposable with respect to a pair of subspaces $\mathcal{M} \subseteq \overline{\mathcal{M}} \subseteq \mathbb{R}^p$ , meaning $\mathcal{R}(\theta + \gamma) = \mathcal{R}(\theta) + \mathcal{R}(\gamma)$ for all $\theta \in \mathcal{M}$ and $\gamma \in \overline{\mathcal{M}}^\perp$ , where $\overline{\mathcal{M}}^\perp := \{v \in \mathbb{R}^p \mid \langle u, v \rangle = 0 \; \forall u \in \overline{\mathcal{M}}\}$ .
2. Restricted Strong Convexity (RSC): The first-order Taylor series error $\delta\mathcal{L}(\Delta, \theta^*) := \mathcal{L}(\theta^* + \Delta; Z_1^n) - \mathcal{L}(\theta^*; Z_1^n) - \langle \nabla \mathcal{L}(\theta^*; Z_1^n), \Delta \rangle$ satisfies
$\delta\mathcal{L}(\Delta, \theta^*) \ge \kappa_L \|\Delta\|^2 - \tau_L^2(\theta^*)$

for all $\Delta \in \mathbb{C}(\mathcal{M}, \overline{\mathcal{M}}^\perp; \theta^*) := \{\Delta \in \mathbb{R}^p \mid \mathcal{R}(\Delta_{\overline{\mathcal{M}}^\perp}) \le 3\mathcal{R}(\Delta_{\overline{\mathcal{M}}}) + 4\mathcal{R}(\theta^*_{\mathcal{M}^\perp})\}$ , where $\kappa_L > 0$ is the curvature, $\tau_L(\theta^*)$ is a tolerance function, and $u_S$ denotes the orthogonal projection of $u$ onto subspace $S$ . 3. Regularization Scale: The regularization parameter satisfies $\lambda_n \ge 2\mathcal{R}^*(\nabla \mathcal{L}(\theta^*; Z_1^n))$ .

Then, any optimal solution $\widehat{\theta}_{\lambda_n}$ satisfies the deterministic upper bound

$\|\widehat{\theta}_{\lambda_n} - \theta^*\|^2 \le 9 \frac{\lambda_n^2}{\kappa_L^2} \Psi^2(\overline{\mathcal{M}}) + \frac{\lambda_n}{\kappa_L} \left[ 2\tau_L^2(\theta^*) + 4\mathcal{R}(\theta^*_{\mathcal{M}^\perp}) \right]$

where $\Psi(\overline{\mathcal{M}}) := \sup_{u \in \overline{\mathcal{M}} \setminus \{0\}} \frac{\mathcal{R}(u)}{\|u\|}$ is the subspace compatibility constant.
Knowl 2 — Error Bounds Under Exact Model Subspace Membership
theoretical result
Consider the regularized $M$ -estimation problem

$\widehat{\theta}_{\lambda_n} \in \arg\min_{\theta \in \mathbb{R}^p} \left\{ \mathcal{L}(\theta; Z_1^n) + \lambda_n \mathcal{R}(\theta) \right\}$

under an induced error norm $\|\cdot\|$ and dual regularizer norm $\mathcal{R}^*$ . Suppose that the true parameter satisfies exact subspace inclusion $\theta^* \in \mathcal{M}$ , the regularizer $\mathcal{R}$ is decomposable over $(\mathcal{M}, \overline{\mathcal{M}}^\perp)$ with $\mathcal{M} \subseteq \overline{\mathcal{M}}$ , the regularization penalty satisfies $\lambda_n \ge 2\mathcal{R}^*(\nabla \mathcal{L}(\theta^*))$ , and the loss $\mathcal{L}$ satisfies restricted strong convexity over the cone $\mathbb{C}(\mathcal{M}, \overline{\mathcal{M}}^\perp; \theta^*) = \{\Delta \in \mathbb{R}^p \mid \mathcal{R}(\Delta_{\overline{\mathcal{M}}^\perp}) \le 3\mathcal{R}(\Delta_{\overline{\mathcal{M}}})\}$ with curvature $\kappa_L > 0$ and zero tolerance $\tau_L(\theta^*) = 0$ .

Then, any optimal solution $\widehat{\theta}_{\lambda_n}$ satisfies the bounds in the error norm and regularizer norm:

$\|\widehat{\theta}_{\lambda_n} - \theta^*\| \le \frac{9\lambda_n}{2\kappa_L} \Psi(\overline{\mathcal{M}})$

$\mathcal{R}(\widehat{\theta}_{\lambda_n} - \theta^*) \le \frac{12\lambda_n}{\kappa_L} \Psi^2(\overline{\mathcal{M}})$

where $\Psi(\overline{\mathcal{M}}) := \sup_{u \in \overline{\mathcal{M}} \setminus \{0\}} \frac{\mathcal{R}(u)}{\|u\|}$ is the subspace compatibility constant.
Knowl 3 — Decomposability of Regularization Norms
definition
Given a pair of subspaces $\mathcal{M} \subseteq \overline{\mathcal{M}} \subseteq \mathbb{R}^p$ , a norm regularizer $\mathcal{R}: \mathbb{R}^p \to \mathbb{R}_+$ is defined to be decomposable with respect to the pair $(\mathcal{M}, \overline{\mathcal{M}}^\perp)$ if

$\mathcal{R}(\theta + \gamma) = \mathcal{R}(\theta) + \mathcal{R}(\gamma) \quad \text{for all } \theta \in \mathcal{M} \text{ and } \gamma \in \overline{\mathcal{M}}^\perp$

where $\overline{\mathcal{M}}^\perp := \{v \in \mathbb{R}^p \mid \langle u, v \rangle = 0 \; \forall u \in \overline{\mathcal{M}}\}$ is the orthogonal complement of $\overline{\mathcal{M}}$ with respect to the inner product $\langle \cdot, \cdot \rangle$ .

Examples of decomposable regularizers include:
1. $\ell_1$ -norm for sparse vectors: For a support subset $S \subseteq \{1, \dots, p\}$ of size $s$ , let $\mathcal{M}(S) = \overline{\mathcal{M}}(S) = \{\theta \in \mathbb{R}^p \mid \theta_j = 0 \; \forall j \notin S\}$ . Then $\mathcal{R}(\theta) = \|\theta\|_1$ satisfies $\|\theta + \gamma\|_1 = \|\theta\|_1 + \|\gamma\|_1$ for all $\theta \in \mathcal{M}(S), \gamma \in \mathcal{M}^\perp(S)$ .
2. Group $(1, \alpha)$ -norms: For a partition $\mathcal{G} = \{G_1, \dots, G_{N_G}\}$ of $\{1, \dots, p\}$ and $\alpha \in [1, \infty]^{N_G}$ , the norm $\|\theta\|_{\mathcal{G}, \alpha} = \sum_{t=1}^{N_G} \|\theta_{G_t}\|_{\alpha_t}$ is decomposable with respect to the subspace of vectors supported on a group subset $S_G$ and its orthogonal complement.
3. Nuclear norm for low-rank matrices: For matrices $\Theta \in \mathbb{R}^{p_1 \times p_2}$ and $r$ -dimensional left and right singular subspaces $U \subseteq \mathbb{R}^{p_1}, V \subseteq \mathbb{R}^{p_2}$ , the nuclear norm $\|\Theta\|_{\mathrm{nuc}} = \sum_{j} \sigma_j(\Theta)$ is decomposable with respect to $\mathcal{M}(U, V) = \{\Theta \mid \mathrm{row}(\Theta) \subseteq V, \mathrm{col}(\Theta) \subseteq U\}$ and $\overline{\mathcal{M}}^\perp(U, V) = \{\Theta \mid \mathrm{row}(\Theta) \subseteq V^\perp, \mathrm{col}(\Theta) \subseteq U^\perp\}$ , where $\overline{\mathcal{M}}(U, V) = \{\Theta \mid \mathrm{row}(\Theta) \subseteq V \text{ or } \mathrm{col}(\Theta) \subseteq U\}$ .
Knowl 4 — Restricted Strong Convexity (RSC)
definition
Let $\mathcal{L}: \mathbb{R}^p \times \mathcal{Z}^n \to \mathbb{R}$ be a convex and differentiable loss function, and let $\delta\mathcal{L}(\Delta, \theta^*) := \mathcal{L}(\theta^* + \Delta) - \mathcal{L}(\theta^*) - \langle \nabla \mathcal{L}(\theta^*), \Delta \rangle$ denote the remainder of the first-order Taylor expansion around $\theta^*$ .

The loss function $\mathcal{L}$ satisfies the restricted strong convexity (RSC) condition with respect to an error norm $\|\cdot\|$ , positive curvature constant $\kappa_L > 0$ , and tolerance function $\tau_L(\theta^*)$ if

$\delta\mathcal{L}(\Delta, \theta^*) \ge \kappa_L \|\Delta\|^2 - \tau_L^2(\theta^*)$

for all perturbation vectors $\Delta$ in the set

$\mathbb{C}(\mathcal{M}, \overline{\mathcal{M}}^\perp; \theta^*) := \left\{ \Delta \in \mathbb{R}^p \mid \mathcal{R}(\Delta_{\overline{\mathcal{M}}^\perp}) \le 3\mathcal{R}(\Delta_{\overline{\mathcal{M}}}) + 4\mathcal{R}(\theta^*_{\mathcal{M}^\perp}) \right\}$

where $\mathcal{M} \subseteq \overline{\mathcal{M}}$ are subspaces associated with the decomposability of the regularizer $\mathcal{R}$ .
Knowl 5 — Error Confinement Under Dual Regularization Scaling
theoretical result
Let $\mathcal{L}: \mathbb{R}^p \to \mathbb{R}$ be a convex and differentiable loss function, and let $\mathcal{R}: \mathbb{R}^p \to \mathbb{R}_+$ be a norm regularizer that is decomposable with respect to a subspace pair $(\mathcal{M}, \overline{\mathcal{M}}^\perp)$ with $\mathcal{M} \subseteq \overline{\mathcal{M}}$ . Consider any optimal solution $\widehat{\theta}_{\lambda_n}$ to the regularized convex program

$\widehat{\theta}_{\lambda_n} \in \arg\min_{\theta \in \mathbb{R}^p} \left\{ \mathcal{L}(\theta) + \lambda_n \mathcal{R}(\theta) \right\}$

If the regularization penalty satisfies

$\lambda_n \ge 2\mathcal{R}^*(\nabla \mathcal{L}(\theta^*))$

where $\mathcal{R}^*(v) := \sup_{\mathcal{R}(u) \le 1} \langle u, v \rangle$ is the dual norm of $\mathcal{R}$ , then the estimation error vector $\Delta := \widehat{\theta}_{\lambda_n} - \theta^*$ is guaranteed to belong to the set

$\mathbb{C}(\mathcal{M}, \overline{\mathcal{M}}^\perp; \theta^*) := \left\{ \Delta \in \mathbb{R}^p \mid \mathcal{R}(\Delta_{\overline{\mathcal{M}}^\perp}) \le 3\mathcal{R}(\Delta_{\overline{\mathcal{M}}}) + 4\mathcal{R}(\theta^*_{\mathcal{M}^\perp}) \right\}$

where $\Delta_S$ denotes the orthogonal projection of $\Delta$ onto the subspace $S$ .
Knowl 6 — Subspace Compatibility Constant
definition
For any subspace $\mathcal{M} \subseteq \mathbb{R}^p$ , regularizer norm $\mathcal{R}: \mathbb{R}^p \to \mathbb{R}_+$ , and error norm $\|\cdot\|$ on $\mathbb{R}^p$ , the subspace compatibility constant $\Psi(\mathcal{M})$ is defined as

$\Psi(\mathcal{M}) := \sup_{u \in \mathcal{M} \setminus \{0\}} \frac{\mathcal{R}(u)}{\|u\|}$

This constant corresponds to the Lipschitz constant of the regularizer $\mathcal{R}$ with respect to the error norm $\|\cdot\|$ restricted to the subspace $\mathcal{M}$ . For example, when $\mathcal{R}(u) = \|u\|_1$ , $\|u\| = \|u\|_2$ , and $\mathcal{M}$ is an $s$ -dimensional coordinate subspace of $\mathbb{R}^p$ , the compatibility constant evaluates to $\Psi(\mathcal{M}) = \sqrt{s}$ .
Knowl 7 — Lasso Convergence Rates for Exactly Sparse Linear Regression
theoretical result
Consider the linear regression model $y = X\theta^* + w$ , where $y \in \mathbb{R}^n$ , $X \in \mathbb{R}^{n \times p}$ , and $\theta^* \in \mathbb{R}^p$ is supported on a subset $S \subseteq \{1, \dots, p\}$ of cardinality $|S| = s$ . Assume that:
1. The design matrix $X$ is column-normalized: $\frac{\|X_j\|_2}{\sqrt{n}} \le 1$ for all $j = 1, \dots, p$ .
2. The design matrix $X$ satisfies the restricted eigenvalue (RE) condition:
$\frac{\|X\theta\|_2^2}{n} \ge \kappa_L \|\theta\|_2^2 \quad \text{for all } \theta \in \left\{ \Delta \in \mathbb{R}^p \mid \|\Delta_{S^c}\|_1 \le 3\|\Delta_S\|_1 \right\}$

with $\kappa_L > 0$ . 3. The noise vector $w \in \mathbb{R}^n$ has zero mean and sub-Gaussian tails with parameter $\sigma > 0$ , such that $\mathbb{P}(|\langle v, w \rangle| \ge t) \le 2\exp\left(-\frac{t^2}{2\sigma^2}\right)$ for all unit vectors $\|v\|_2 = 1$ .

Setting the Lasso regularization parameter to $\lambda_n = 4\sigma \sqrt{\frac{\log p}{n}}$ , any optimal solution $\widehat{\theta}_{\lambda_n} \in \arg\min_{\theta \in \mathbb{R}^p} \left\{ \frac{1}{2n}\|y - X\theta\|_2^2 + \lambda_n \|\theta\|_1 \right\}$ satisfies

$\|\widehat{\theta}_{\lambda_n} - \theta^*\|_2^2 \le \frac{64\sigma^2}{\kappa_L^2} \frac{s \log p}{n}$

$\|\widehat{\theta}_{\lambda_n} - \theta^*\|_1 \le \frac{24\sigma}{\kappa_L} s \sqrt{\frac{\log p}{n}}$

with probability at least $1 - c_1 \exp(-c_2 n \lambda_n^2)$ for universal positive constants $(c_1, c_2)$ .
Knowl 8 — Lasso Convergence Rates for Weakly Sparse ($\ell_q$-Ball) Linear Models
theoretical result
Consider the linear regression model $y = X\theta^* + w$ with sub-Gaussian noise $w$ of parameter $\sigma$ , column-normalized design matrix $X$ ( $\frac{\|X_j\|_2}{\sqrt{n}} \le 1$ ), and $\theta^*$ belonging to the $\ell_q$ -ball of radius $R_q$ for $q \in [0, 1]$ :

$\mathbb{B}_q(R_q) := \left\{ \theta \in \mathbb{R}^p \;\middle|\; \sum_{i=1}^p |\theta_i|^q \le R_q \right\}$

Suppose the design matrix satisfies the restricted eigenvalue condition $\frac{\|X\theta\|_2^2}{n} \ge \kappa_1 \|\theta\|_2^2 - \kappa_2 \frac{\log p}{n} \|\theta\|_1^2$ for all $\theta \in \mathbb{R}^p$ with positive constants $\kappa_1, \kappa_2$ , and the radius satisfies $R_q \left(\frac{\log p}{n}\right)^{1/2 - q/4} \le 1$ .

Solving the Lasso with regularization parameter $\lambda_n = 4\sigma \sqrt{\frac{\log p}{n}}$ yields an estimator $\widehat{\theta}_{\lambda_n}$ satisfying

$\|\widehat{\theta}_{\lambda_n} - \theta^*\|_2^2 \le c_0 R_q \left( \frac{\sigma^2}{\kappa_1^2} \frac{\log p}{n} \right)^{1 - q/2}$

with probability at least $1 - c_1 \exp(-c_2 n \lambda_n^2)$ for universal positive constants $(c_0, c_1, c_2)$ . These rates match the minimax-optimal rate for estimation over $\ell_q$ -balls.
Knowl 9 — Restricted Strong Convexity for Correlated Gaussian Designs and GLMs
theoretical result
Let $X \in \mathbb{R}^{n \times p}$ be a random design matrix drawn from the $\Sigma$ -Gaussian ensemble, where each row $x_i \sim \mathcal{N}(0, \Sigma)$ is independently sampled with positive definite covariance $\Sigma \succ 0$ .
1. Linear Regression (Least Squares Loss): There exist strictly positive constants $(\kappa_1, \kappa_2)$ depending only on $\Sigma$ such that
$\frac{\|X\theta\|_2^2}{n} \ge \kappa_1 \|\theta\|_2^2 - \kappa_2 \frac{\log p}{n} \|\theta\|_1^2 \quad \text{for all } \theta \in \mathbb{R}^p$

with probability at least $1 - c_1 \exp(-c_2 n)$ . Consequently, the restricted eigenvalue property $\frac{\|X\theta\|_2^2}{n} \ge \frac{\kappa_1}{2} \|\theta\|_2^2$ holds on the cone $\{\theta \in \mathbb{R}^p \mid \|\theta_{S^c}\|_1 \le 3\|\theta_S\|_1\}$ whenever $n > 64(\kappa_2 / \kappa_1) s \log p$ .
1. Generalized Linear Models (GLM Loss): For GLM negative log-likelihood loss functions with link function $\Phi$ and i.i.d. zero-mean sub-Gaussian covariates $x_i$ with covariance $\Sigma \succ 0$ , the first-order Taylor series remainder satisfies
$\delta\mathcal{L}(\Delta, \theta^*) \ge \kappa_1 \|\Delta\|_2^2 - \kappa_2 \frac{\log p}{n} \|\Delta\|_1^2 \quad \text{for all } \|\Delta\|_2 \le 1$

with high probability, establishing restricted strong convexity for sample sizes scaling as $n = \Omega(s \log p)$ .
Knowl 10 — Convergence Rates for Group Lasso and Block-Structured Regularizers
theoretical result
Let the index set $\{1, \dots, p\}$ be partitioned into $N_G$ groups $\mathcal{G} = \{G_1, \dots, G_{N_G}\}$ , each of maximum size $m = \max_t |G_t|$ . Consider the $(1, \alpha)$ -group regularized estimator with $\alpha \in [2, \infty]$ :

$\widehat{\theta}_{\lambda_n} \in \arg\min_{\theta \in \mathbb{R}^p} \left\{ \frac{1}{n}\|y - X\theta\|_2^2 + \lambda_n \|\theta\|_{\mathcal{G}, \alpha} \right\}, \quad \|\theta\|_{\mathcal{G}, \alpha} := \sum_{t=1}^{N_G} \|\theta_{G_t}\|_\alpha$

Assume the noise $w \in \mathbb{R}^n$ is sub-Gaussian with parameter $\sigma$ , the design matrix $X$ satisfies the block normalization condition $\frac{\|X_{G_t}\|_{\alpha \to 2}}{\sqrt{n}} \le 1$ for all $t$ (where $\|X_G\|_{\alpha \to 2} := \max_{\|\theta\|_\alpha = 1} \|X_G \theta\|_2$ ), and $X$ satisfies the block restricted strong convexity condition:

$\frac{\|X\Delta\|_2^2}{n} \ge \kappa_1 \|\Delta\|_2^2 - \kappa_2 \rho_{\mathcal{G}}^2(\alpha^*) \|\Delta\|_{\mathcal{G}, \alpha}^2$

where $\frac{1}{\alpha} + \frac{1}{\alpha^*} = 1$ and $\rho_{\mathcal{G}}(\alpha^*) := \mathbb{E}\left[\max_{t=1, \dots, N_G} \frac{\|\varepsilon_{G_t}\|_{\alpha^*}}{\sqrt{n}}\right]$ for $\varepsilon \sim \mathcal{N}(0, I_{p \times p})$ .

If the regularization parameter is chosen as $\lambda_n \ge 2\sigma \left( \frac{m^{1 - 1/\alpha}}{\sqrt{n}} + \sqrt{\frac{\log N_G}{n}} \right)$ , then with probability at least $1 - 2/N_G^2$ , for any group support subset $S_G \subseteq \{1, \dots, N_G\}$ of size $s_G = |S_G|$ ,

$\|\widehat{\theta}_{\lambda_n} - \theta^*\|_2^2 \le \frac{4\lambda_n^2}{\kappa_L^2} s_G + \frac{4\lambda_n}{\kappa_L} \sum_{t \notin S_G} \|\theta^*_{G_t}\|_\alpha$

For exactly group-sparse vectors with equal group size $m$ and $\alpha = 2$ (Group Lasso), this yields the rate $\|\widehat{\theta}_{\lambda_n} - \theta^*\|_2^2 = \mathcal{O}\left( \frac{s_G m}{n} + \frac{s_G \log N_G}{n} \right)$ .

Coverage note — Omitted detailed derivations, auxiliary lemmas, and supplementary proofs from [49], as well as extended matrix completion/decomposition results referenced from companion papers [1, 51, 52].

References

1.AGARWAL, A., NEGAHBAN, S. and WAINWRIGHT, M. J. (2011). Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions. Ann. Statist. 40 1171–1197.
2.BACH, F. (2010). Self-concordant analysis for logistic regression. Electron. J. Stat. 4 384–414. MR2645490
3.BACH, F. R. (2008). Consistency of the group lasso and multiple kernel learning. J. Mach. Learn. Res. 9 1179–1225. MR2417268
4.BACH, F. R. (2008). Consistency of trace norm minimization. J. Mach. Learn. Res. 9 1019–1048. MR2417263
5.BARANIUK, R. G., CEVHER, V., DUARTE, M. F. and HEGDE, C. (2008). Model-based compressive sensing. Technical report, Rice Univ. Available at arXiv:0808.3572.
6.BICKEL, P. J., BROWN, J. B., HUANG, H. and LI, Q. (2009). An overview of recent developments in genomics and associated statistical methods. Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 367 4313–4337. MR2546390
7.BICKEL, P. J. and LEVINA, E. (2008). Covariance regularization by thresholding. Ann. Statist. 36 2577–2604. MR2485008
8.BICKEL, P. J., RITOV, Y. and TSYBAKOV, A. B. (2009). Simultaneous analysis of lasso and Dantzig selector. Ann. Statist. 37 1705–1732. MR2533469
9.BUNEA, F. (2008). Honest variable selection in linear and logistic regression models via l1 and l1 + l2 penalization. Electron. J. Stat. 2 1153–1194. MR2461898
10.BUNEA, F., SHE, Y. and WEGKAMP, M. (2010). Adaptive rank penalized estimators in multivariate regression. Technical report, Florida State. Available at arXiv:1004.2995.
11.BUNEA, F., TSYBAKOV, A. and WEGKAMP, M. (2007). Sparsity oracle inequalities for the Lasso. Electron. J. Stat. 1 169–194. MR2312149
12.BUNEA, F., TSYBAKOV, A. B. and WEGKAMP, M. H. (2007). Aggregation for Gaussian regression. Ann. Statist. 35 1674–1697. MR2351101
13.CAI, T. and ZHOU, H. (2010). Optimal rates of convergence for sparse covariance matrix estimation. Technical report, Wharton School of Business, Univ. Pennsylvania. Available at http://www-stat.wharton.upenn.edu/~tcai/paper/html/Sparse-Covariance-Matrix.html.
14.CANDES, E. and TAO, T. (2007). The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. 35 2313–2351. MR2382644
15.CANDÈS, E. J. and RECHT, B. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. 9 717–772. MR2565240
16.CANDES, E. J. and TAO, T. (2005). Decoding by linear programming. IEEE Trans. Inform. Theory 51 4203–4215. MR2243152
17.CANDES, E. J., X. LI, Y. M. and WRIGHT, J. (2010). Stable principal component pursuit. In IEEE International Symposium on Information Theory, Austin, TX.
18.CHANDRASEKARAN, V., SANGHAVI, S., PARRILO, P. A. and WILLSKY, A. S. (2011). Rank-sparsity incoherence for matrix decomposition. SIAM J. Optimiz. 21 572–596.
19.CHEN, S. S., DONOHO, D. L. and SAUNDERS, M. A. (1998). Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20 33–61. MR1639094
20.DONOHO, D. L. (2006). Compressed sensing. IEEE Trans. Inform. Theory 52 1289–1306. MR2241189
21.DONOHO, D. L. and TANNER, J. (2005). Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. USA 102 9452–9457 (electronic). MR2168716
22.EL KAROUI, N. (2008). Operator norm consistent estimation of large-dimensional sparse covariance matrices. Ann. Statist. 36 2717–2756. MR2485011
23.FAZEL, M. (2002). Matrix rank minimization with applications. Ph.D. thesis, Stanford. Available at http://faculty.washington.edu/mfazel/thesis-final.pdf.
24.GIRKO, V. L. (1995). Statistical Analysis of Observations of Increasing Dimension. Theory and Decision Library. Series B: Mathematical and Statistical Methods 28. Kluwer Academic, Dordrecht. Translated from the Russian. MR1473719
25.GREENSHTEIN, E. and RITOV, Y. (2004). Persistence in high-dimensional linear predictor selection and the virtue of overparametrization. Bernoulli 10 971–988. MR2108039
26.HSU, D., KAKADE, S. M. and ZHANG, T. (2011). Robust matrix decomposition with sparse corruptions. IEEE Trans. Inform. Theory 57 7221–7234.
27.HUANG, J. and ZHANG, T. (2010). The benefit of group sparsity. Ann. Statist. 38 1978–2004. MR2676881
28.JACOB, L., OBOZINSKI, G. and VERT, J. P. (2009). Group Lasso with overlap and graph Lasso. In International Conference on Machine Learning (ICML) 433–440, Haifa, Israel.
29.JENATTON, R., MAIRAL, J., OBOZINSKI, G. and BACH, F. (2011). Proximal methods for hierarchical sparse coding. J. Mach. Learn. Res. 12 2297–2334.
30.KAKADE, S. M., SHAMIR, O., SRIDHARAN, K. and TEWARI, A. (2010). Learning exponential families in high-dimensions: Strong convexity and sparsity. In AISTATS, Sardinia, Italy.
31.KESHAVAN, R. H., MONTANARI, A. and OH, S. (2010). Matrix completion from noisy entries. J. Mach. Learn. Res. 11 2057–2078.
32.KIM, Y., KIM, J. and KIM, Y. (2006). Blockwise sparse regression. Statist. Sinica 16 375–390. MR2267240
33.KOLTCHINSKII, V. and YUAN, M. (2008). Sparse recovery in large ensembles of kernel machines. In Proceedings of COLT, Helsinki, Finland.
34.KOLTCHINSKII, V. and YUAN, M. (2010). Sparsity in multiple kernel learning. Ann. Statist. 38 3660–3695. MR2766864
35.LAM, C. and FAN, J. (2009). Sparsistency and rates of convergence in large covariance matrix estimation. Ann. Statist. 37 4254–4278. MR2572459
36.LANDGREBE, D. (2008). Hyperspectral image data analsysis as a high-dimensional signal processing problem. IEEE Signal Processing Magazine 19 17–28.
37.LEE, K. and BRESLER, Y. (2009). Guaranteed minimum rank approximation from linear observations by nuclear norm minimization with an ellipsoidal constraint. Technical report, UIUC. Available at arXiv:0903.4742.
38.LIU, Z. and VANDENBERGHE, L. (2009). Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31 1235–1256. MR2558821
39.LOUNICI, K., PONTIL, M., TSYBAKOV, A. B. and VAN DE GEER, S. (2009). Taking advantage of sparsity in multitask learning. Technical report, ETH Zurich. Available at arXiv:0903.1468.
40.LUSTIG, M., DONOHO, D., SANTOS, J. and PAULY, J. (2008). Compressed sensing MRI. IEEE Signal Processing Magazine 27 72–82.
41.MCCOY, M. and TROPP, J. (2011). Two proposals for robust PCA using semidefinite programming. Electron. J. Stat. 5 1123–1160.
42.MEHTA, M. L. (1991). Random Matrices, 2nd ed. Academic Press, Boston, MA. MR1083764
43.MEIER, L., VAN DE GEER, S. and BÜHLMANN, P. (2009). High-dimensional additive modeling. Ann. Statist. 37 3779–3821. MR2572443
44.MEINSHAUSEN, N. (2008). A note on the Lasso for Gaussian graphical model selection. Statist. Probab. Lett. 78 880–884. MR2398362
45.MEINSHAUSEN, N. and BÜHLMANN, P. (2006). High-dimensional graphs and variable selection with the lasso. Ann. Statist. 34 1436–1462. MR2278363
46.MEINSHAUSEN, N. and YU, B. (2009). Lasso-type recovery of sparse representations for high-dimensional data. Ann. Statist. 37 246–270. MR2488351
47.NARDI, Y. and RINALDO, A. (2008). On the asymptotic properties of the group lasso estimator for linear models. Electron. J. Stat. 2 605–633. MR2426104
48.NEGAHBAN, S., RAVIKUMAR, P., WAINWRIGHT, M. J. and YU, B. (2009). A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers. In NIPS Conference, Vancouver, Canada.
49.NEGAHBAN, S., RAVIKUMAR, P., WAINWRIGHT, M. J. and YU, B. (2012). Supplement to “A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers.” DOI:10.1214/12-STS400SUPP.
50.NEGAHBAN, S. and WAINWRIGHT, M. J. (2011). Simultaneous support recovery in high-dimensional regression: Benefits and perils of 1,∞-regularization. IEEE Trans. Inform. Theory 57 3481–3863.
51.NEGAHBAN, S. and WAINWRIGHT, M. J. (2011). Estimation of (near) low-rank matrices with noise and high-dimensional scaling. Ann. Statist. 39 1069–1097. MR2816348
52.NEGAHBAN, S. and WAINWRIGHT, M. J. (2012). Restricted strong convexity and (weighted) matrix completion: Optimal bounds with noise. J. Mach. Learn. Res. 13 1665–1697.
53.OBOZINSKI, G., WAINWRIGHT, M. J. and JORDAN, M. I. (2011). Support union recovery in high-dimensional multivariate regression. Ann. Statist. 39 1–47. MR2797839
54.PASTUR, L. A. (1972). The spectrum of random matrices. Teoret. Mat. Fiz. 10 102–112. MR0475502
55.RASKUTTI, G., WAINWRIGHT, M. J. and YU, B. (2010). Restricted eigenvalue properties for correlated Gaussian designs. J. Mach. Learn. Res. 11 2241–2259. MR2719855
56.RASKUTTI, G., WAINWRIGHT, M. J. and YU, B. (2011). Minimax rates of estimation for high-dimensional linear regression over q -balls. IEEE Trans. Inform. Theory 57 6976–6994. MR2882274
57.RASKUTTI, G., WAINWRIGHT, M. J. and YU, B. (2012). Minimax-optimal rates for sparse additive models over kernel classes via convex programming. J. Mach. Learn. Res. 13 389–427. MR2913704
58.RAVIKUMAR, P., LAFFERTY, J., LIU, H. and WASSERMAN, L. (2009). Sparse additive models. J. R. Stat. Soc. Ser. B Stat. Methodol. 71 1009–1030. MR2750255
59.RAVIKUMAR, P., WAINWRIGHT, M. J. and LAFFERTY, J. D. (2010). High-dimensional Ising model selection using 1-regularized logistic regression. Ann. Statist. 38 1287–1319. MR2662343
60.RAVIKUMAR, P., WAINWRIGHT, M. J., RASKUTTI, G. and YU, B. (2011). High-dimensional covariance estimation by minimizing 1-penalized log-determinant divergence. Electron. J. Stat. 5 935–980. MR2836766
61.RECHT, B. (2011). A simpler approach to matrix completion. J. Mach. Learn. Res. 12 3413–3430. MR2877360
62.RECHT, B., FAZEL, M. and PARRILO, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52 471–501. MR2680543
63.ROHDE, A. and TSYBAKOV, A. B. (2011). Estimation of high-dimensional low-rank matrices. Ann. Statist. 39 887–930. MR2816342
64.ROTHMAN, A. J., BICKEL, P. J., LEVINA, E. and ZHU, J. (2008). Sparse permutation invariant covariance estimation. Electron. J. Stat. 2 494–515. MR2417391
65.RUDELSON, M. and ZHOU, S. (2011). Reconstruction from anisotropic random measurements. Technical report, Univ. Michigan.
66.STOJNIC, M., PARVARESH, F. and HASSIBI, B. (2009). On the reconstruction of block-sparse signals with an optimal number of measurements. IEEE Trans. Signal Process. 57 3075–3085. MR2723043
67.TIBSHIRANI, R. (1996). Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. Ser. B Stat. Methodol. 58 267–288. MR1379242
68.TIBSHIRANI, R., SAUNDERS, M., ROSSET, S., ZHU, J. and KNIGHT, K. (2005). Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B Stat. Methodol. 67 91–108. MR2136641
69.TROPP, J. A., GILBERT, A. C. and STRAUSS, M. J. (2006). Algorithms for simultaneous sparse approximation. Signal Process. 86 572–602. Special issue on “Sparse approximations in signal and image processing.”
70.TURLACH, B. A., VENABLES, W. N. and WRIGHT, S. J. (2005). Simultaneous variable selection. Technometrics 47 349–363. MR2164706
71.VAN DE GEER, S. A. (2008). High-dimensional generalized linear models and the lasso. Ann. Statist. 36 614–645. MR2396809
72.VAN DE GEER, S. A. and BÜHLMANN, P. (2009). On the conditions used to prove oracle results for the Lasso. Electron. J. Stat. 3 1360–1392. MR2576316
73.WAINWRIGHT, M. J. (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery using 1-constrained quadratic programming (Lasso). IEEE Trans. Inform. Theory 55 2183–2202. MR2729873
74.WAINWRIGHT, M. J. (2009). Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting. IEEE Trans. Inform. Theory 55 5728–5741. MR2597190
75.WIGNER, E. P. (1955). Characteristic vectors of bordered matrices with infinite dimensions. Ann. of Math. (2) 62 548–564. MR0077805
76.XU, H., CARAMANIS, C. and SANGHAVI, S. (2012). Robust PCA via outlier pursuit. IEEE Trans. Inform. Theory 58 3047–3064.
77.YUAN, M., EKICI, A., LU, Z. and MONTEIRO, R. (2007). Dimension reduction and coefficient estimation in multivariate linear regression. J. R. Stat. Soc. Ser. B Stat. Methodol. 69 329–346. MR2323756
78.YUAN, M. and LIN, Y. (2006). Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B Stat. Methodol. 68 49–67. MR2212574
79.ZHANG, C.-H. and HUANG, J. (2008). The sparsity and bias of the LASSO selection in high-dimensional linear regression. Ann. Statist. 36 1567–1594. MR2435448
80.ZHAO, P., ROCHA, G. and YU, B. (2009). The composite absolute penalties family for grouped and hierarchical variable selection. Ann. Statist. 37 3468–3497. MR2549566
81.ZHAO, P. and YU, B. (2006). On model selection consistency of Lasso. J. Mach. Learn. Res. 7 2541–2563. MR2274449
82.ZHOU, S., LAFFERTY, J. and WASSERMAN, L. (2008). Time-varying undirected graphs. In 21st Annual Conference on Learning Theory (COLT), Helsinki, Finland.

Citation

MLA

Negahban, S. N., et al. “A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers”. Statistical Science, vol. 27, no. 4, 2012, https://doi.org/10.1214/12-STS400.

APA

Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012). A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers. Statistical Science, 27(4). https://doi.org/10.1214/12-STS400

Chicago

Negahban, S. N., P. Ravikumar, M. J. Wainwright, and B. Yu. 2012. “A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers”. Statistical Science 27 (4). https://doi.org/10.1214/12-STS400.

Harvard

Negahban, S.N. et al. (2012) “A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers”, Statistical Science, 27(4). Available at: https://doi.org/10.1214/12-STS400.

Vancouver

1. Negahban SN, Ravikumar P, Wainwright MJ, Yu B (2012) A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers. Statistical Science. https://doi.org/10.1214/12-STS400

BibTeX

@article{Negahban_2012, title={A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers}, volume={27}, ISSN={0883-4237}, url={http://dx.doi.org/10.1214/12-STS400}, DOI={10.1214/12-sts400}, number={4}, journal={Statistical Science}, publisher={Institute of Mathematical Statistics}, author={Negahban, Sahand N. and Ravikumar, Pradeep and Wainwright, Martin J. and Yu, Bin}, year={2012}, month=Nov }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Master Error Bound for Regularized M-Estimators with Decomposable Norms

Knowl 2 — Error Bounds Under Exact Model Subspace Membership

Knowl 3 — Decomposability of Regularization Norms

Knowl 4 — Restricted Strong Convexity (RSC)

Knowl 5 — Error Confinement Under Dual Regularization Scaling

Knowl 6 — Subspace Compatibility Constant

Knowl 7 — Lasso Convergence Rates for Exactly Sparse Linear Regression

Knowl 8 — Lasso Convergence Rates for Weakly Sparse ($\ell_q$-Ball) Linear Models

Knowl 9 — Restricted Strong Convexity for Correlated Gaussian Designs and GLMs

Knowl 10 — Convergence Rates for Group Lasso and Block-Structured Regularizers

References

Citation

BibTeX

Access the Paper