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

By Sahand N. Negahban, Pradeep Ravikumar, Martin J. Wainwright, Bin Yu. 2009

1,470 citations recorded by the source corpus.

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 structure (e.g., sparse vectors; block-structured matrices; low-rank matrices; Markov assumptions). In such settings, a general approach to estimation is to solve a regularized convex program (known as a regularized M-estimator) which combines a loss function (measuring how well the model fits the data) with some regularization function that encourages the assumed structure. The goal of this paper is to provide 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 several existing results, and also to obtain several new results on consistency and convergence rates. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure the corresponding regularized M-estimators have fast convergence rates.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Generalized Sparse Additive Models (2019, background): “(cid:107) (cid:107) This is another common condition in the literature for handling general convex loss functions [see e.g., Negahban et al., 2011, van de Geer, 2008].”
Sparse Partially Linear Additive Models (2014, background): “These results follow from the unified framework of Negahban et al. (2012), which gives both oracle inequalities and recovery guarantees for a wide class of estimators based on decomposable regularizers.”
Approximate residual balancing: debiased inference of average treatment effects in high dimensions (2016, methodology): “Thus, pairing these two fact about Xc with sparsity as in Assumption 4 and the sub-Gaussianity of the noise smashεi(w), we can use the results of Negahban et al. [2012] to bound the L1-risk of the lasso.”
Optimization with Sparsity-Inducing Penalties (2011, background): “It notably arises in the analysis of estimation bounds [99], and in the design of working-set strategies Full text available at: http://dx.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “This assumption is a natural extension of the RE condition and restricted strong convexity considered in [10], [37], and [38].”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, background): “The vast majority of work has been pursued for point estimation such as consistency for prediction [7, 21], oracle inequalities and estimation of a highdimensional parameter [6, 11, 12, 24, 33, 34, 47, 51] or variable selection [17, 30, 49, 53].”
A Simple Method for Detecting Interactions between a Treatment and a Large Number of Covariates (2012, background): “where ‖γ‖(2)2 = ∑p j=1 γ 2 j , γ̂λN is the corresponding lasso regularized estimator, #γ ∗ is the number of non-zero components in the vector γ∗, and ci, i = 1, 2, 3 are positive constants depending on the joint distribution of (Y,W(Z), T ) [Negahban et al., 2012]. Therefore, although the dimension ”
Efficient Policy Learning (2017, background): “10See Nickl and Pötscher (2007) for an argument that holds for arbitrary distributions P supported on [0, 1]s.”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, methodology): “A careful tracking of constants in Negahban et al. [40, 41, Sec.”
Efficient Distributed Learning with Sparsity (2016, methodology): “The logistic loss is 14 -smooth, let Ljpβq 1n ° iPrns logp1 expp yjixβ,xjiyqq, (Negahban et al., 2012) showed that if xji are drawn from mean zero distribution with sub-Gaussian tails, then L1pβq satisfies the restricted strong condition (3.2).”
Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression (2018, methodology): “The following is a general result of Negahban et al. (2012) and this form is taken from Hastie, Tibshirani and Wainwright (2015).”
Robust Joint Graph Sparse Coding for Unsupervised Spectral Feature Selection (2017, methodology): “We then selected one subset for testing and used the remaining nine subsets for training [61].”
Asymptotics of Selective Inference (2015, methodology): “Proof of Theorem 3 We first introduce the following Lemma in Negahban et al. (2012).”