A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Statistical SciencePublished 1 November 2012Open access
Sahand Negahban, Bin Yu, Martin J. Wainwright, Pradeep Ravikumar
Citations300
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A unified framework for establishing consistency and convergence rates for regularized M-estimators under high-dimensional scaling is provided and one main theorem is state and shown how it can be used to re-derive several existing results, and also to obtain several new results.
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\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.
Keywords
Computer ScienceMathematicsEngineering
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
IEEE Transactions on Information TheoryCompressed sensing
23,147 Citations2006David L. Donoho
It is shown that "most" subspaces in Ropfm are near-optimal, and that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.
Compressed sensing
17,129 Citations2004David L. Donoho
Journal of the Royal Statistical Society Series B (Statistical Methodology)Model Selection and Estimation in Regression with Grouped Variables
7,467 Citations2005Ming Yuan, Yi Lin
IEEE Transactions on Information TheoryDecoding by Linear Programming
7,181 Citations2005Emmanuel J. Candès, Terence Tao
F can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program) and numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted.
SIAM Journal on Scientific ComputingAtomic Decomposition by Basis Pursuit
6,899 Citations1998Scott Shaobing Chen, David L. Donoho +1 more
Basis Pursuit (BP) is a principle for decomposing a signal into an "optimal" superposition of dictionary elements, where optimal means having the smallest l1 norm of coefficients among all such decompositions.
Foundations of Computational MathematicsExact Matrix Completion via Convex Optimization
5,061 Citations2009Emmanuel J. Candès, Benjamin Recht
SIAM ReviewSemidefinite Programming
4,021 Citations1996Lieven Vandenberghe, Stephen Boyd
A survey of the theory and applications of semidefinite programs and an introduction to primaldual interior-point methods for their solution are given.
SIAM ReviewGuaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
3,533 Citations2010Benjamin Recht, Maryam Fazel +1 more
It is shown that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum-rank solution can be recovered by solving a convex optimization problem, namely, the minimization of the nuclear norm over the given affine space.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Sparsity and Smoothness Via the Fused Lasso
2,805 Citations2004Robert Tibshirani, Michael A. Saunders +3 more
The fused lasso is proposed, a generalization that is designed for problems with features that can be ordered in some meaningful way, and is especially useful when the number of features p is much greater than N, the sample size.
The Annals of StatisticsSimultaneous analysis of Lasso and Dantzig selector
2,536 Citations2009Peter J. Bickel, Ya’acov Ritov +1 more
It is shown that, under a sparsity scenario, the Lasso estimator and the Dantzig selector exhibit similar behavior and derive, in parallel, oracle inequalities for the prediction risk in the general nonparametric regression model as well as bounds on the l p estimation loss in the linear model.
The Annals of StatisticsHigh-dimensional graphs and variable selection with the Lasso
2,406 Citations2006Nicolai Meinshausen, Peter Bühlmann
It is shown that neighborhood selection with the Lasso is a computationally attractive alternative to standard covariance selection for sparse high-dimensional graphs and is hence equivalent to variable selection for Gaussian linear models.
IEEE Signal Processing MagazineCompressed Sensing MRI
2,290 Citations2008Michael Lustig, David L. Donoho +2 more
The authors emphasize on an intuitive understanding of CS by describing the CS reconstruction as a process of interference cancellation, and there is also an emphasis on the understanding of the driving factors in applications.
On Model Selection Consistency of Lasso
2,015 Citations2006Peng Zhao, Bin Yu
It is proved that a single condition, which is called the Irrepresentable Condition, is almost necessary and sufficient for Lasso to select the true model both in the classical fixed p setting and in the large p setting as the sample size n gets large.
arXiv (Cornell University)The Dantzig selector: Statistical estimation when $p$ is much larger than $n$
1,725 Citations2005Candes, Emmanuel, Tao, Terence
Is it possible to estimate β reliably based on the noisy data y?
Journal of the Royal Statistical Society Series B (Statistical Methodology)The Group Lasso for Logistic Regression
1,720 Citations2008Lukas Meier, Sara van de Geer +1 more
An efficient algorithm is presented, that is especially suitable for high dimensional problems, which can also be applied to generalized linear models to solve the corresponding convex optimization problem.
IEEE Transactions on Information TheoryJust relax: convex programming methods for identifying sparse signals in noise
1,427 Citations2006Joel A. Tropp
A method called convex relaxation, which attempts to recover the ideal sparse signal by solving a convex program, which can be completed in polynomial time with standard scientific software.
Signal ProcessingAlgorithms for simultaneous sparse approximation. Part I: Greedy pursuit
1,347 Citations2005Joel A. Tropp, Anna C. Gilbert +1 more
This paper proposes a greedy pursuit algorithm, called simultaneous orthogonal matching pursuit (S-OMP), for simultaneous sparse approximation, and presents some numerical experiments that demonstrate how a sparse model for the input signals can be identified more reliably given several input signals.
IEEE Transactions on Information TheoryModel-Based Compressive Sensing
1,279 Citations2010Richard G. Baraniuk, Volkan Cevher +2 more
A model-based CS theory is introduced that parallels the conventional theory and provides concrete guidelines on how to create model- based recovery algorithms with provable performance guarantees and a new class of structured compressible signals along with a new sufficient condition for robust structured compressable signal recovery that is the natural counterpart to the restricted isometry property of conventional CS.
Probability in Banach Spaces: Isoperimetry and Processes
1,276 Citations1991Michel Ledoux, Michel Talagrand
IEEE Transactions on Information TheorySharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
1,252 Citations2009Martin J. Wainwright
This work analyzes the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern of a vector beta* based on observations contaminated by noise, and establishes precise conditions on the problem dimension p, the number k of nonzero elements in beta*, and the number of observations n.
Covariance regularization by thresholding
1,171 Citations2007Peter J. Bickel, Elizaveta Levina
IEEE Signal Processing MagazineHyperspectral image data analysis
1,102 Citations2002D. A. Landgrebe
The article includes an example of an image space representation, using three bands to simulate a color IR photograph of an airborne hyperspectral data set over the Washington, DC, mall.
PubMedSpectral Regularization Algorithms for Learning Large Incomplete Matrices.
974 Citations2010Rahul Mazumder, Trevor Hastie +1 more
RePEc: Research Papers in EconomicsGradient methods for minimizing composite objective function
922 Citations2007Yu. Nesterov
This paper analyzes several new methods for solving optimization problems with the objective function formed as a sum of two convex terms: one is smooth and given by a black-box oracle, and another is general but simple and its structure is known.
The Annals of StatisticsCovariance regularization by thresholding
862 Citations2008Peter J. Bickel, Elizaveta Levina
It is shown that the thresholded estimate is consistent in the operator norm as long as the true covariance matrix is sparse in a suitable sense, the variables are Gaussian or sub-Gaussian, and $(\log p)/n\to0$, and obtain explicit rates.
Group lasso with overlap and graph lasso
859 Citations2009Laurent Jacob, Guillaume Obozinski +1 more
A new penalty function is proposed which, when used as regularization for empirical risk minimization procedures, leads to sparse estimators and is studied theoretical properties of the estimator, and illustrated on simulated and breast cancer gene expression data.
HIGH-DIMENSIONAL ISING MODEL SELECTION USING ℓ1-REGULARIZED LOGISTIC REGRESSION
853 Citations2010Pradeep Ravikumar, Martin J. Wainwright +2 more
Mathematical ProgrammingPrimal-dual subgradient methods for convex problems
852 Citations2007Yurii Nesterov
Electronic Journal of StatisticsHigh-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence
793 Citations2011Pradeep Ravikumar, Martin J. Wainwright +2 more
The first result establishes consistency of the estimate b � in the elementwise maximum-norm, which allows us to derive convergence rates in Frobenius and spectral norms, and shows good correspondences between the theoretical predictions and behavior in simulations.
Sparse Permutation Invariant Covariance Estimation
764 Citations2007Adam J. Rothman, Peter J. Bickel +1 more
UC BerkeleyLasso-type recovery of sparse representations for high-dimensional data
751 Citations2006Meinshausen, Nicolai, Yu, Bin
Electronic Journal of StatisticsOn the conditions used to prove oracle results for the Lasso
707 Citations2009Sara A. van de Geer, Peter Bühlmann
arXiv (Cornell University)Consistency of the group Lasso and multiple kernel learning
704 Citations2007Francis Bach
This paper derives necessary and sufficient conditions for the consistency of group Lasso under practical assumptions, and proposes an adaptive scheme to obtain a consistent model estimate, even when the necessary condition required for the non adaptive scheme is not satisfied.
Characteristic Vectors of Bordered Matrices with Infinite Dimensions II
686 Citations1993E. P. Wigner
SIAM Journal on OptimizationRank-Sparsity Incoherence for Matrix Decomposition
657 Citations2011Venkat Chandrasekaran, Sujay Sanghavi +2 more
This paper decomposes a matrix formed by adding an unknown sparse matrix to an unknown low-rank matrix into its sparse and low- rank components.
The Annals of StatisticsThe composite absolute penalties family for grouped and hierarchical variable selection
649 Citations2009Peng Zhao, Guilherme V. Rocha +1 more
CAP is shown to improve on the predictive performance of the LASSO in a series of simulated experiments, including cases with $p\gg n$ and possibly mis-specified groupings, and iCAP is seen to be parsimonious in the experiments.
The Annals of StatisticsEstimation of (near) low-rank matrices with noise and high-dimensional scaling
578 Citations2011Sahand Negahban, Martin J. Wainwright
Simulations show excellent agreement with the high-dimensional scaling of the error predicted by the theory, and illustrate their consequences for a number of specific learning models, including low-rank multivariate or multi-task regression, system identification in vector autoregressive processes, and recovery of low- rank matrices from random projections.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Sparse Additive Models
553 Citations2009Pradeep Ravikumar, John Lafferty +2 more
An algorithm for fitting the models is derived that is practical and effective even when the number of covariates is larger than the sample size, and empirical results show that they can be effective in fitting sparse non‐parametric models in high dimensional data.
Electronic Journal of StatisticsSparse permutation invariant covariance estimation
537 Citations2008Adam J. Rothman, Peter J. Bickel +2 more
A method for constructing a sparse estimator for the inverse covariance (concentration) matrix in high-dimensional settings using a penalized normal likelihood approach and forces sparsity by using a lasso-type penalty is proposed.
Stable Principal Component Pursuit
534 Citations2010Zihan Zhou, Xiaodong Li +3 more
This result shows that the proposed convex program recovers the low-rank matrix even though a positive fraction of its entries are arbitrarily corrupted, with an error bound proportional to the noise level, the first result that shows the classical Principal Component Analysis, optimal for small i.i.d. noise, can be made robust to gross sparse errors.
The Annals of StatisticsHigh-dimensional Ising model selection using ℓ1-regularized logistic regression
518 Citations2010Pradeep Ravikumar, Martin J. Wainwright +1 more
It is proved that consistent neighborhood selection can be obtained for sample sizes $n=\Omega(d^3\log p)$ with exponentially decaying error, and when these same conditions are imposed directly on the sample matrices, it is shown that a reduced sample size suffices for the method to estimate neighborhoods consistently.
SIAM Journal on Matrix Analysis and ApplicationsInterior-Point Method for Nuclear Norm Approximation with Application to System Identification
506 Citations2009Zhang Liu, Lieven Vandenberghe
It is shown that problem structure in the semidefinite programming formulation can be exploited to develop more efficient implementations of interior-point methods, and a variant of a simple subspace algorithm is presented in which low-rank matrix approximations are computed via nuclear norm minimization instead of the singular value decomposition.
The Annals of StatisticsThe benefit of group sparsity
505 Citations2010Junzhou Huang, Tong Zhang
The result shows that group Lasso is superior to standard Lasso for strongly group-sparse signals, and provides a convincing theoretical justification for using group sparse regularization when the underlying group structure is consistent with the data.
The Annals of StatisticsThe sparsity and bias of the Lasso selection in high-dimensional linear regression
494 Citations2008Cun-Hui Zhang, Jian Huang
It is proved that the sum of error squares for the mean response and the l α -loss for the regression coefficients converge at the best possible rates under the given conditions, and the logarithm of the number of variables can be of the same order as the sample size for certain random dependent designs.
IEEE Transactions on Information TheoryMinimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
485 Citations2011Garvesh Raskutti, Martin J. Wainwright +1 more
The results show that although computationally efficient l1-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix X than optimal algorithms involving least-squares over the l0-ball.
The Annals of StatisticsLasso-type recovery of sparse representations for high-dimensional data
479 Citations2009Nicolai Meinshausen, Bin Yu
Even though the Lasso cannot recover the correct sparsity pattern, the estimator is still consistent in the ‘2-norm sense for fixed designs under conditions on (a) the number sn of non-zero components of the vector n and (b) the minimal singular values of the design matrices that are induced by selecting of order sn variables.
The Annals of StatisticsHigh-dimensional additive modeling
475 Citations2009Lukas Meier, Sara van de Geer +1 more
A computationally efficient algorithm, with provable numerical convergence properties, is presented, for optimizing the penalized likelihood of a new sparsity-smoothness penalty for high-dimensional generalized additive models.
Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix
472 Citations2009Zhouchen Lin, Arvind Ganesh +4 more
Two complementary approaches for solving the problem of recovering a low-rank matrix with a fraction of its entries arbitrarily corrupted are developed and compared, both several orders of magnitude faster than the previous state-of-the-art algorithm for this problem.
IEEE Transactions on Information TheoryRobust PCA via Outlier Pursuit
449 Citations2012Huan Xu, Constantine Caramanis +1 more
This work presents an efficient convex optimization-based algorithm that it calls outlier pursuit, which under some mild assumptions on the uncorrupted points recovers the exact optimal low-dimensional subspace and identifies the corrupted points.
arXiv (Cornell University)Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
439 Citations2010Sahand Negahban, Martin J. Wainwright
The matrix completion problem under a form of row/column weighted entrywise sampling is considered, including the case of uniformentrywise sampling as a special case, and it is proved that with high probability, it satisfies a forms of restricted strong convexity with respect to weighted Frobenius norm.
IEEE Transactions on Signal ProcessingOn the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
438 Citations2009Mihailo Stojnic, Farzad Parvaresh +1 more
IEEE Transactions on Information TheoryInformation-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
425 Citations2009Martin J. Wainwright
For a noisy linear observation model based on random measurement matrices drawn from general Gaussian measurementMatrices, this paper derives both a set of sufficient conditions for exact support recovery using an exhaustive search decoder, as well as aset of necessary conditions that any decoder must satisfy for exactSupport set recovery.
Sparsity oracle inequalities for the Lasso
421 Citations2012Florentina Bunea, Alexandre B. Tsybakov +1 more
Journal of Machine Learning ResearchRestricted Eigenvalue Properties for Correlated Gaussian Designs
404 Citations2010Garvesh Raskutti, Martin J. Wainwright +1 more
This paper proves directly that the restricted nullspace and eigenvalue conditions hold with high probability for quite general classes of Gaussian matrices for which the predictors may be highly dependent, and hence restricted isometry conditions can be violated with high probabilities.
TechnometricsSimultaneous Variable Selection
399 Citations2005Berwin A. Turlach, W. N. Venables +1 more
A new method for selecting a common subset of explanatory variables where the aim is to model several response variables based on the (joint) residual sum of squares while constraining the parameter estimates to lie within a suitable polyhedral region is proposed.
The Annals of StatisticsSparsistency and rates of convergence in large covariance matrix estimation
398 Citations2009Clifford Lam, Jianqing Fan
To guarantee the sparsistency and optimal rate of convergence, the number of nonzero elements should be small: sn'=O(pn) at most, among O(pn2) parameters, for estimating sparse covariance or correlation matrix, sparse precision or inverse correlation matrix or sparse Cholesky factor.
The Annals of StatisticsHigh-dimensional generalized linear models and the lasso
396 Citations2008Sara A. van de Geer
A nonasymptotic oracle inequality is proved for the empirical risk minimizer with Lasso penalty for high-dimensional generalized linear models with Lipschitz loss functions, and the penalty is based on the coefficients in the linear predictor, after normalization with the empirical norm.
Proceedings of the National Academy of SciencesNeighborliness of randomly projected simplices in high dimensions
373 Citations2005David L. Donoho, Jared Tanner
There is a "phase transition" in the ability of linear programming to find the sparsest nonnegative solution to systems of underdetermined linear equations.
The Annals of StatisticsSupport union recovery in high-dimensional multivariate regression
367 Citations2010Guillaume Obozinski, Martin J. Wainwright +1 more
This sparsity-overlap function reveals that, if the design is uncorrelated on the active rows, block lscr1/lscr2 regularization for multivariate regression never harms performance relative to an ordinary Lasso approach, and can yield substantial improvements in sample complexity when the regression vectors are suitably orthogonal.
Operator norm consistent estimation of large-dimensional sparse covariance matrices
366 Citations2012Noureddine El Karoui
ALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATION
359 Citations2006Joel A. Tropp
BernoulliPersistence in high-dimensional linear predictor selection and the virtue of overparametrization
359 Citations2004Eitan Greenshtein, Ya’acov Ritov
Under various sparsity assumptions on the optimal predictor there is “asymptotically no harm” in introducing many more explanatory variables than observations, and such practice can be beneficial in comparison with a procedure that screens in advance a small subset of explanatory variables.
The Annals of StatisticsEstimation of high-dimensional low-rank matrices
352 Citations2011Angelika Rohde, Alexandre B. Tsybakov
This work investigates penalized least squares estimators with a Schatten-p quasi-norm penalty term and derives bounds for the kth entropy numbers of the quasi-convex Schatten class embeddings S M p → S M 2 , p < 1, which are of independent interest.
The Annals of StatisticsOracle inequalities and optimal inference under group sparsity
347 Citations2011Karim Lounici, Massimiliano Pontil +2 more
The Group Lasso can achieve an improvement in the prediction and estimation properties as compared to the Lasso, and it is proved that the rate of convergence of the upper bounds is optimal in a minimax sense.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
327 Citations2007Ming Yuan, Ali Ekici +2 more
Aggregation for Gaussian regression
317 Citations2016Florentina Bunea, Re B. Tsybakov +1 more
Statistical ScienceA Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
300 Citations2012Sahand Negahban, Bin Yu +2 more
A unified framework for establishing consistency and convergence rates for regularized M-estimators under high-dimensional scaling is provided and one main theorem is state and shown how it can be used to re-derive several existing results, and also to obtain several new results.
arXiv (Cornell University)Proximal Methods for Hierarchical Sparse Coding
276 Citations2010Rodolphe Jenatton, Julien Mairal +2 more
The Annals of StatisticsAsymptotic Behavior of $M$-Estimators of $p$ Regression Parameters when $p^2/n$ is Large. I. Consistency
273 Citations1984Stephen Portnoy
The Annals of StatisticsOperator norm consistent estimation of large-dimensional sparse covariance matrices
244 Citations2008Noureddine El Karoui
The estimator is shown to be consistent in operator norm, when, for instance, the authors have p ?
Electronic Journal of StatisticsSparsity oracle inequalities for the Lasso
240 Citations2007Florentina Bunea, Alexandre Tsybakov +1 more
It is shown that the penalized least squares estimator satisfies sparsity oracle inequalities, i.e., bounds in terms of the number of non-zero components of the oracle vector, in nonparametric regression setting with random design.
IEEE Transactions on Information TheoryRobust Matrix Decomposition With Sparse Corruptions
222 Citations2011Daniel Hsu, Sham M. Kakade +1 more
This work studies conditions under which recovering a given observation matrix as the sum of a low-rank matrix and a sparse matrix is possible via a combination of ℓ1 norm and trace norm minimization and obtains stronger recovery guarantees than previous studies.
UC BerkeleyMinimax-optimal rates for sparse additive models over kernel classes via convex programming
220 Citations2012Garvesh Raskutti, Martin J. Wainwright +1 more
This paper considers the case where each univariate component function fj* lies in a reproducing kernel Hilbert space (RKHS), and analyzes a method for estimating the unknown function f* based on kernels combined with l1-type convex regularization, obtaining optimal minimax rates for many interesting classes of sparse additive models.
IEEE Transactions on Information TheoryReconstruction From Anisotropic Random Measurements
208 Citations2013Mark Rudelson, Shuheng Zhou
Grouped and Hierarchical Model Selection through Composite Absolute Penalties
201 Citations2007Peng Zhao, Guilherme V. Rocha +1 more
This paper introduces the Composite Absolute Penalties (CAP) family which allows the grouping and hierarchical relationships between the predictors to be expressed and combined norms including L1 to form an intelligent penalty in order to add side information to the fitting of a regression or classification model to obtain reasonable estimates.
The Annals of StatisticsSparsity in multiple kernel learning
198 Citations2010Vladimir Koltchinskii, Ming Yuan
The goal is to establish oracle inequalities for the excess risk of the resulting prediction rule showing that the method is adaptive both to the unknown design distribution and to the sparsity of the problem.
Electronic Journal of StatisticsOn the asymptotic properties of the group lasso estimator for linear models
192 Citations2008Yuval Nardi, Alessandro Rinaldo
The Annals of StatisticsAggregation for Gaussian regression
172 Citations2007Florentina Bunea, Alexandre B. Tsybakov +1 more
Mathematical ProgrammingNull space conditions and thresholds for rank minimization
157 Citations2010Benjamin Recht, Weiyu Xu +1 more
This paper characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed, and obtains dimension-free bounds under which these null space properties hold almost surely as the matrix dimensions tend to infinity.
Neural Information Processing SystemsSpAM: Sparse Additive Models
153 Citations2007Han Liu, Larry Wasserman +2 more
A statistical analysis of the properties of SpAM and empirical results on synthetic and real data show that SpAM can be effective in fitting sparse nonparametric models in high dimensional data.
Taking Advantage of Sparsity in Multi-Task Learning
151 Citations2009Karim Lounici, Massimiliano Pontil +2 more
The Group Lasso is considered as a candidate estimation method and it is shown that this estimator enjoys nice sparsity oracle inequalities and variable selection properties and can be extended to more general noise distributions, of which it only requires the variance to be finite.
The Annals of StatisticsOptimal rates of convergence for sparse covariance matrix estimation
145 Citations2012T. Tony Cai, Harrison H. Zhou
This paper develops a lower bound technique that is particularly well suited for treating “two-directional” problems such as estimating sparse covariance matrices and establishes the optimal rate of convergence under a range of matrix operator norm and Bregman divergence losses.
arXiv (Cornell University)Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
141 Citations2010Emmanuel J. Candès, Yaniv Plan
It is shown that properly constrained nuclear-norm minimization stably recovers a low-rank matrix from a constant number of noisy measurements per degree of freedom; this seems to be the first result of this nature.
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices
126 Citations2004Nathan Srebro, Noga Alon +1 more
It is proved that generalization error bounds for predicting entries in a partially observed matrix are generalized by fitting the observed entries with a low-rank matrix.
IEEE Transactions on Information TheorySimultaneous Support Recovery in High Dimensions: Benefits and Perils of Block $\ell _{1}/\ell _{\infty} $-Regularization
114 Citations2011Sahand Negahban, Martin J. Wainwright
The results show that caution must be exercised in applying ℓ/ℓ∞ block regularization: if the data does not match its structure very closely, it can impair statistical performance relative to computationally less expensive schemes.
Electronic Journal of StatisticsTwo proposals for robust PCA using semidefinite programming
92 Citations2011Michael McCoy, Joel A. Tropp
Two novel approaches for robust principal component analysis based on semidefinite programming are proposed, the first of which seeks directions of large spread in the data while damping the effect of outliers, and the second produces a low-leverage decomposition of the data that attempts to form a high-rank model for the data by separating out corrupted observations.
Electronic Journal of StatisticsSelf-concordant analysis for logistic regression
89 Citations2010Francis Bach
This paper uses and extends tools from the convex optimization literature, namely self-concordant functions, to provide simple extensions of theoretical results for the square loss to the logistic loss, showing that new results for binary classification through logistic regression can be easily derived from corresponding results for least-squares regression.
Electronic Journal of StatisticsHonest variable selection in linear and logistic regression models via ℓ1 and ℓ1+ℓ2 penalization
78 Citations2008Florentina Bunea
It is shown that in identifiable models, both methods can recover coefficients of size $\frac{1}{\sqrt{n}}$, up to small multiplicative constants and logarithmic factors in $M$ and $\delta}$.
Statistical Analysis of Observations of Increasing Dimension
74 Citations1995Vyacheslav L. Girko
arXiv (Cornell University)Restricted Eigenvalue Conditions on Subgaussian Random Matrices
64 Citations2009Shuheng Zhou
This paper associates the RE condition (Bickel-Ritov-Tsybakov 09) with the complexity of a subset of the sphere in R p, and shows that a class of random matrices with independent rows, but not necessarily independent columns, satisfy theRE condition, when the sample size is above a certain lower bound.
Statistics & Probability LettersA note on the Lasso for Gaussian graphical model selection
57 Citations2007Nicolai Meinshausen
Inspired by the success of the Lasso for regression analysis, it seems attractive to estimate the graph of a multivariate normal distribution by l1-norm penalized likelihood maximization by examining some properties of the estimator and showing that care has to be taken with interpretation of results.
arXiv (Cornell University)High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence
47 Citations2008Pradeep Ravikumar, Martin J. Wainwright +2 more
Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering SciencesAn overview of recent developments in genomics and associated statistical methods
38 Citations2009Peter J. Bickel, James B. Brown +2 more
Union support recovery in high-dimensional multivariate regression
38 Citations2008Guillaume Obozinski, Martin J. Wainwright +1 more
arXiv (Cornell University)Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
37 Citations2009Kiryung Lee, Yoram Bresler
An explicit performance guarantee is derived, bounding the error in the approximate solution provided by nuclear norm minimization with an ellipsoidal constraint, in the presence of measurement noise, or with only approximately low rank generative model.
arXiv (Cornell University)Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity
22 Citations2009Sham M. Kakade, Ohad Shamir +2 more
…