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\to 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 ${\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.

Published in at http://dx.doi.org/10.1214/12-STS400 the Statistical Science (http://www.imstat.org/sts/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (28)

• Covariance regularization by thresholding
• A Simpler Approach to Matrix Completion
• On the conditions used to prove oracle results for the Lasso
• Consistency of the group Lasso and multiple kernel learning
• Rank-Sparsity Incoherence for Matrix Decomposition
• The composite absolute penalties family for grouped and hierarchical variable selection
• Sparse permutation invariant covariance estimation
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Lasso-type recovery of sparse representations for high-dimensional data
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• High-dimensional generalized linear models and the lasso
• Estimation of high-dimensional low-rank matrices
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Proximal Methods for Hierarchical Sparse Coding
• Sparsity oracle inequalities for the Lasso
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Sparsity in multiple kernel learning
• Consistency of trace norm minimization
• Aggregation for Gaussian regression
• Optimal rates of convergence for sparse covariance matrix estimation
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Two Proposals for Robust PCA using Semidefinite Programming
• Honest variable selection in linear and logistic regression models via ${\ell }_1$ and ${\ell }_1+{\ell }_2$ penalization
• Restricted Eigenvalue Conditions on Subgaussian Random Matrices
• High-dimensional covariance estimation by minimizing ${\ell }_1$-penalized log-determinant divergence
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity

Cited by in corpus (58)

• Structured Variable Selection with Sparsity-Inducing Norms
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
• Network Flow Algorithms for Structured Sparsity
• Oracle inequalities for the lasso in the Cox model
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Convex and Network Flow Optimization for Structured Sparsity
• Low Rank and Structured Modeling of High-dimensional Vector Autoregressions
• Global and Simultaneous Hypothesis Testing for High-Dimensional Logistic Regression Models
• Distributed Estimation and Inference with Statistical Guarantees
• Nonparametric sparsity and regularization
• On Learning Discrete Graphical Models Using Greedy Methods
• A Tight Bound of Hard Thresholding
• Orthogonal Matching Pursuit with Replacement
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Change-Point Estimation in High-Dimensional Markov Random Field Models
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Selective Sequential Model Selection
• Learning Model-Based Sparsity via Projected Gradient Descent
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• Learning Single Index Models in High Dimensions
• Reconstructing DNA copy number by penalized estimation and imputation
• Testability of high-dimensional linear models with non-sparse structures
• Tight convex relaxations for sparse matrix factorization
• A general theory of regression adjustment for covariate-adaptive randomization: OLS, Lasso, and beyond
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• The generalized Lasso with non-linear observations
• Minimax Optimal Sparse Signal Recovery with Poisson Statistics
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• Learning from Comparisons and Choices
• Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit
• Double Robust Semi-Supervised Inference for the Mean: Selection Bias under MAR Labeling with Decaying Overlap
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Inference for the Case Probability in High-dimensional Logistic Regression
• Unified View of Matrix Completion under General Structural Constraints
• Efficient Mixed-Norm Regularization: Algorithms and Safe Screening Methods
• The Highest Dimensional Stochastic Blockmodel with a Regularized Estimator
• A data-dependent weighted LASSO under Poisson noise
• Prior Adaptive Semi-supervised Learning with Application to EHR Phenotyping
• A Geometric View on Constrained M-Estimators
• On Coresets for Regularized Loss Minimization
• A Fast and Scalable Joint Estimator for Integrating Additional Knowledge in Learning Multiple Related Sparse Gaussian Graphical Models
• The Knowledge Gradient Policy Using A Sparse Additive Belief Model
• Sparse Partially Linear Additive Models
• Structural Change in Sparsity
• Consistent regression when oblivious outliers overwhelm
• Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics
• Directional FDR Control for Sub-Gaussian Sparse GLMs
• Stochastic Hard Thresholding Algorithms for AUC Maximization
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization
• High-Dimensional Dynamic Systems Identification with Additional Constraints
• Joint Network Topology Inference via Structured Fusion Regularization
• A Knowledge Transfer Framework for Differentially Private Sparse Learning
• Inference for Large Panel Data with Many Covariates