The DOI matches its Crossref record; 90 of the 90 references it cites were found in a registry or an index.
A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Open accessAbstract
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\rightarrow0$, 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 $\ell_{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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
Model Selection and Estimation in Regression with Grouped Variables
Yuan, M., & Lin, Y. (2006) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00532.x · Cited by 7,261
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,105
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Sparsity and Smoothness Via the Fused Lasso
Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., & Knight, K. (2005) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00490.x · Cited by 2,724
High dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · Cited by 2,539
High-dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · The Annals of Statistics · doi:10.1214/009053606000000281 · Cited by 2,521
Simultaneous analysis of Lasso and Dantzig selector
Bickel, P. J., Ritov, Y., & Tsybakov, A. B. (2009) · The Annals of Statistics · doi:10.1214/08-aos620 · Cited by 2,396
Lustig, M., Donoho, D. L., Santos, J. M., & Pauly, J. M. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914728 · Cited by 2,246
The Dantzig selector: Statistical estimation when p is much larger than n
Candes, E., & Tao, T. (2007) · The Annals of Statistics · doi:10.1214/009053606000001523 · Cited by 1,747
The Group Lasso for Logistic Regression
Meier, L., Van De Geer, S., & Bühlmann, P. (2008) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2007.00627.x · Cited by 1,674
Regularization methods for learning incomplete matrices
Mazumder, R., Hastie, T. J., & Tibshirani, R. J. (2009) · Journal of Machine Learning Research · doi:10.48550/arxiv.0906.2034 · Cited by 1,639
Characteristic Vectors of Bordered Matrices With Infinite Dimensions
Wigner, E. P. (1955) · The Annals of Mathematics · doi:10.2307/1970079 · Cited by 1,572
Just relax: convex programming methods for identifying sparse signals in noise
Tropp, J. A. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.864420 · Cited by 1,407
Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit
Tropp, J. A., Gilbert, A. C., & Strauss, M. J. (2006) · Signal Processing · doi:10.1016/j.sigpro.2005.05.030 · Cited by 1,347
Model-Based Compressive Sensing
Baraniuk, R. G., Cevher, V., Duarte, M. F., & Hegde, C. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2040894 · Cited by 1,308
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016018 · Cited by 1,198
Self-citationLedoux, M., & Talagrand, M. (1991) · doi:10.1007/978-3-642-20212-4 · Cited by 1,160
Hyperspectral image data analysis
Landgrebe, D. (2002) · IEEE Signal Processing Magazine · doi:10.1109/79.974718 · Cited by 1,152
Covariance regularization by thresholding
Bickel, P. J., & Levina, E. (2007) · Cited by 1,118
On Model Selection Consistency of Lasso
ZhaoPeng, & Yubin, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248637 · Cited by 996
Covariance regularization by thresholding
Bickel, P. J., & Levina, E. (2008) · The Annals of Statistics · doi:10.1214/08-aos600 · Cited by 893
High-dimensional Ising model selection using ℓ1-regularized logistic regression
Ravikumar, P., Wainwright, M. J., & Lafferty, J. D. (2010) · The Annals of Statistics · doi:10.1214/09-aos691 · Cited by 892
Self-citationGradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
Primal-dual subgradient methods for convex problems
Nesterov, Y. (2009) · Mathematical Programming · doi:10.1007/s10107-007-0149-x · Cited by 835
Group lasso with overlap and graph lasso
Jacob, L., Obozinski, G., & Vert, J.-P. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553431 · Cited by 833
High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence
Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs631 · Cited by 744
Self-citationLasso-type recovery of sparse representations for high-dimensional data
Meinshausen, N., & Yu, B. (2006) · Cited by 744
Self-citationRank-Sparsity Incoherence for Matrix Decomposition
Chandrasekaran, V., Sanghavi, S., Parrilo, P. A., & Willsky, A. S. (2011) · SIAM Journal on Optimization · doi:10.1137/090761793 · Cited by 686
Sparse Permutation Invariant Covariance Estimation
Rothman, A., Bickel, P. J., Levina, E., & Zhu, J. (2007) · Cited by 686
On the conditions used to prove oracle results for the Lasso
van de Geer, S. A., & Bühlmann, P. (2009) · Electronic Journal of Statistics · doi:10.1214/09-ejs506 · Cited by 684
A Simpler Approach to Matrix Completion
Recht, B. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.0651 · Cited by 673
Consistency of the group Lasso and multiple kernel learning
Bach, F. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0707.3390 · Cited by 669
Characteristic Vectors of Bordered Matrices with Infinite Dimensions II
Wigner, E. P. (1993) · The Collected Works of Eugene Paul Wigner · doi:10.1007/978-3-662-02781-3_36 · Cited by 668
The composite absolute penalties family for grouped and hierarchical variable selection
Zhao, P., Rocha, G., & Yu, B. (2009) · The Annals of Statistics · doi:10.1214/07-aos584 · Cited by 631
Self-citationSparse permutation invariant covariance estimation
Rothman, A. J., Bickel, P. J., Levina, E., & Zhu, J. (2008) · Electronic Journal of Statistics · doi:10.1214/08-ejs176 · Cited by 560
Estimation of (near) low-rank matrices with noise and high-dimensional scaling
Negahban, S., & Wainwright, M. J. (2011) · The Annals of Statistics · doi:10.1214/10-aos850 · Cited by 537
Self-citationRavikumar, P., Lafferty, J., Liu, H., & Wasserman, L. (2009) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2009.00718.x · Cited by 535
Self-citationHuang, J., & Zhang, T. (2010) · The Annals of Statistics · doi:10.1214/09-aos778 · Cited by 521
The sparsity and bias of the Lasso selection in high-dimensional linear regression
Zhang, C.-H., & Huang, J. (2008) · The Annals of Statistics · doi:10.1214/07-aos520 · Cited by 506
Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
Liu, Z., & Vandenberghe, L. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090755436 · Cited by 490
Lasso-type recovery of sparse representations for high-dimensional data
Meinshausen, N., & Yu, B. (2009) · The Annals of Statistics · doi:10.1214/07-aos582 · Cited by 489
Self-citationFast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix
Lin, Z., Ganesh, A., Wright, J. N., Wu, L., Chen, M., & Ma, Y. (2009) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 462
High-dimensional additive modeling
Meier, L., van de Geer, S., & Bühlmann, P. (2009) · The Annals of Statistics · doi:10.1214/09-aos692 · Cited by 458
Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
Raskutti, G., Wainwright, M. J., & Yu, B. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165799 · Cited by 455
Self-citationRobust PCA via Outlier Pursuit
Xu, H., Caramanis, C., & Sanghavi, S. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2173156 · Cited by 445
Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2032816 · Cited by 420
Self-citationSparsistency and rates of convergence in large covariance matrix estimation
Lam, C., & Fan, J. (2009) · The Annals of Statistics · doi:10.1214/09-aos720 · Cited by 418
High-dimensional generalized linear models and the lasso
van de Geer, S. A. (2008) · The Annals of Statistics · doi:10.1214/009053607000000929 · Cited by 414
Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
Negahban, S. N., & Wainwright, M. J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.2118 · Cited by 402
Self-citationFundamentals of Statistical Exponential Families
Brown, L. D. (1987) · Cited by 393
Sparsity oracle inequalities for the Lasso
Bunea, F., Tsybakov, A. B., & Wegkamp, M. H. (2007) · HAL · Cited by 389
Simultaneous Variable Selection
Turlach, B. A., Venables, W. N., & Wright, S. J. (2005) · Technometrics · doi:10.1198/004017005000000139 · Cited by 386
Restricted Eigenvalue Properties for Correlated Gaussian Designs
Raskutti, G., Wainwright, M. J., & Yu, B. (2010) · doi:10.5555/1756006.1859929 · Cited by 367
Self-citationPersistence in high-dimensional linear predictor selection and the virtue of overparametrization
Greenshtein, E., & Ritov, Y. (2004) · Bernoulli · doi:10.3150/bj/1106314846 · Cited by 362
Support union recovery in high-dimensional multivariate regression
Obozinski, G., Wainwright, M. J., & Jordan, M. I. (2011) · The Annals of Statistics · doi:10.1214/09-aos776 · Cited by 350
Self-citationALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATIONPreprint
Tropp, J. A. (2006) · Cited by 350
Operator norm consistent estimation of large-dimensional sparse covariance matricesPreprint
Karoui, N. E. (2012) · Cited by 342
Oracle inequalities and optimal inference under group sparsity
Lounici, K., Pontil, M., van de Geer, S., & Tsybakov, A. B. (2011) · The Annals of Statistics · doi:10.1214/11-aos896 · Cited by 341
Estimation of high-dimensional low-rank matrices
Rohde, A., & Tsybakov, A. B. (2011) · The Annals of Statistics · doi:10.1214/10-aos860 · Cited by 330
Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
Yuan, M., Ekici, A., Lu, Z., & Monteiro, R. (2007) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2007.00591.x · Cited by 310
On the spectrum of random matrices
Pastur, L. A. (1972) · Theoretical and Mathematical Physics · doi:10.1007/bf01035768 · Cited by 305
Self-concordant analysis for logistic regression
Bach, F. (2010) · Electronic Journal of Statistics · doi:10.1214/09-ejs521 · Cited by 298
Aggregation for Gaussian regressionPreprint
Bunea, F., Tsybakov, A. B., & Wegkamp, M. H. (2016) · Cited by 297
Proximal Methods for Hierarchical Sparse Coding
Jenatton, R., Mairal, J., Obozinski, G., & Bach, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.2139 · Cited by 272
Portnoy, S. (1984) · The Annals of Statistics · doi:10.1214/aos/1176346793 · Cited by 262
Sparsity oracle inequalities for the Lasso
Bunea, F., Tsybakov, A., & Wegkamp, M. (2007) · Electronic Journal of Statistics · doi:10.1214/07-ejs008 · Cited by 253
Operator norm consistent estimation of large-dimensional sparse covariance matrices
El Karoui, N. (2008) · The Annals of Statistics · doi:10.1214/07-aos559 · Cited by 244
Optimal rates of convergence for sparse covariance matrix estimation
Cai, T., & Zhou, H. H. (2012) · The Annals of Statistics · doi:10.1214/12-aos998 · Cited by 235
Reconstruction From Anisotropic Random Measurements
Rudelson, M., & Zhou, S. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2243201 · Cited by 199
Grouped and Hierarchical Model Selection through Composite Absolute Penalties
Zhao, P., Rocha, G. V., & Yu, B. (2007) · Cited by 195
Self-citationConsistency of trace norm minimization
Bach, F. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0710.2848 · Cited by 182
Aggregation for Gaussian regression
Bunea, F., Tsybakov, A. B., & Wegkamp, M. H. (2007) · The Annals of Statistics · doi:10.1214/009053606000001587 · Cited by 179
Taking Advantage of Sparsity in Multi-Task Learning
Lounici, K., Pontil, M., Tsybakov, A. B., & van de Geer, S. (2009) · Cited by 179
On the asymptotic properties of the group lasso estimator for linear models
Nardi, Y., & Rinaldo, A. (2008) · Electronic Journal of Statistics · doi:10.1214/08-ejs200 · Cited by 173
Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1+ℓ2 penalization
Bunea, F. (2008) · Electronic Journal of Statistics · doi:10.1214/08-ejs287 · Cited by 156
Two proposals for robust PCA using semidefinite programming
McCoy, M., & Tropp, J. A. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs636 · Cited by 141
Honest variable selection in linear and logistic regression models via ℓ1 and ℓ1 + ℓ2 penalizationPreprint
Bunea, F. (2008) · Cited by 136
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices
Srebro, N., Alon, N., & Jaakkola, T. (2004) · Cited by 124
Negahban, S. N., & Wainwright, M. J. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2144150 · Cited by 122
Self-citationA note on the Lasso for Gaussian graphical model selection
Meinshausen, N. (2007) · Statistics & Probability Letters · doi:10.1016/j.spl.2007.09.014 · Cited by 66
An overview of recent developments in genomics and associated statistical methods
Bickel, P. J., Brown, J. B., Huang, H., & Li, Q. (2009) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2009.0164 · Cited by 54
High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergencePreprint
Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0811.3628 · Cited by 45
Self-citationUnion support recovery in high-dimensional multivariate regression
Obozinski, G., Wainwright, M. J., & Jordan, M. I. (2008) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2008.4797530 · Cited by 38
Self-citation
Cited by
Optimization for Machine Learning
(2011) · The MIT Press eBooks · doi:10.7551/mitpress/8996.001.0001 · Cited by 875
Optimization with Sparsity-Inducing Penalties
Bach, F. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985118 · Cited by 608
Candès, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2111771 · Cited by 569
Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
Raskutti, G., Wainwright, M. J., & Yu, B. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165799 · Cited by 455
Self-citationStructured Variable Selection with Sparsity-Inducing Norms
Jenatton, R., Audibert, J.-Y., & Bach, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0904.3523 · Cited by 431
Metadata
- Authors
- Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B.
- Venue
- Statistical Science
- Publisher
- Institute of Mathematical Statistics
- Published
- 2012-11-01
- Volume
- 27
- Issue
- 4
- Pages
- 538-557
- ISSN
- 0883-4237 (ISSN-L)
- OpenAlex
- W2151825876
- Cited by
- 287
- References
- 90
- FWCI
- 32.06
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.