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

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.

• Publication year

  2009

• Venue

  Neural Information Processing Systems

• Publication date

  2009-12-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/12-STS400arXiv 1010.2731
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Minimax rates of estimation for high-dimensional linear regression over l q-balls

  2011cited by this paper
• Robust Matrix Decomposition With Sparse Corruptions

  2011cited by this paper
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions

  2011cited by this paper
• Null space conditions and thresholds for rank minimization

  2011cited by this paper
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements

  2010cited by this paper
• Optimal selection of reduced rank estimators of high-dimensional matrices

  2010cited by this paper
• Two proposals for robust PCA using semidefinite programming

  2010cited by this paper
• High-dimensional Ising model selection using ℓ1-regularized logistic regression

  2010cited by this paper
• Proximal Methods for Hierarchical Sparse Coding

  2010cited by this paper
• Restricted Eigenvalue Properties for Correlated Gaussian Designs

  2010cited by this paper
• Adaptive Rank Penalized Estimators in Multivariate Regression

  2010cited by this paper
• SPARSITY IN MULTIPLE KERNEL LEARNING

  2010cited by this paper
• Spectral Regularization Algorithms for Learning Large Incomplete Matrices

  2010cited by this paper
• Stable Principal Component Pursuit

  2010cited by this paper
• Estimation of high-dimensional low-rank matrices

  2009cited by this paper
• On the conditions used to prove oracle results for the Lasso

  2009influential reference
• An overview of recent developments in genomics and associated statistical methods

  2009cited by this paper
• Self-concordant analysis for logistic regression

  2009cited by this paper
• Primal-dual subgradient methods for convex problems

  2009cited by this paper
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over q -Balls

  2009cited by this paper
• The Benefit of Group Sparsity

  2009influential reference
• Covariance regularization by thresholding

  2009cited by this paper
• Taking Advantage of Sparsity in Multi-Task Learning

  2009cited by this paper
• Interior-Point Method for Nuclear Norm Approximation with Application to System Identification

  2009cited by this paper
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso)

  2009cited by this paper
• Group lasso with overlap and graph lasso

  2009cited by this paper
• A Simpler Approach to Matrix Completion

  2009cited by this paper
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint

  2009cited by this paper
• Matrix completion from a few entries

  2009cited by this paper
• Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix

  2009cited by this paper
• Interior-Point Method for Nuclear Norm Approximation with Application to System Identification

  2009cited by this paper
• Simultaneous support recovery in high dimensions: Benefits and perils of block $\ell_1/\ell_\infty$-regularization

  2009cited by this paper
• The composite absolute penalties family for grouped and hierarchical variable selection

  2009cited by this paper
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling

  2009influential reference
• Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity

  2009cited by this paper
• Rank-Sparsity Incoherence for Matrix Decomposition

  2009cited by this paper
• Matrix Completion from Noisy Entries

  2009cited by this paper
• Restricted Eigenvalue Conditions on Subgaussian Random Matrices

  2009cited by this paper
• Operator norm consistent estimation of large-dimensional sparse covariance matrices

  2008cited by this paper
• Time varying undirected graphs

  2008cited by this paper
• High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence

  2008cited by this paper
• Model-Based Compressive Sensing

  2008influential reference
• Compressed Sensing MRI

  2008cited by this paper
• A note on the Lasso for Gaussian graphical model selection

  2008cited by this paper
• On the asymptotic properties of the group lasso estimator for linear models

  2008cited by this paper
• HIGH-DIMENSIONAL GENERALIZED LINEAR MODELS AND THE LASSO

  2008cited by this paper
• SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR

  2008influential reference
• Exact Matrix Completion via Convex Optimization

  2008cited by this paper
• LASSO-TYPE RECOVERY OF SPARSE REPRESENTATIONS FOR HIGH-DIMENSIONAL DATA

  2008cited by this paper
• The sparsity and bias of the Lasso selection in high-dimensional linear regression

  2008cited by this paper
• Sparse Recovery in Large Ensembles of Kernel Machines On-Line Learning and Bandits

  2008cited by this paper
• On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements

  2008cited by this paper
• The group lasso for logistic regression

  2008influential reference
• Union support recovery in high-dimensional multivariate regression

  2008cited by this paper
• High-dimensional additive modeling

  2008cited by this paper
• Honest variable selection in linear and logistic regression models via $\ell_1$ and $\ell_1+\ell_2$ penalization

  2008cited by this paper
• Grouped and Hierarchical Model Selection through Composite Absolute Penalties

  2007cited by this paper
• SpAM: Sparse Additive Models

  2007cited by this paper
• Sparsistency and Rates of Convergence in Large Covariance Matrix Estimation.

  2007cited by this paper
• Consistency of trace norm minimization

  2007cited by this paper
• Sparsity oracle inequalities for the Lasso

  2007cited by this paper
• Consistency of the group Lasso and multiple kernel learning

  2007cited by this paper
• Sparse additive models

  2007cited by this paper
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007cited by this paper
• Gradient methods for minimizing composite objective function

  2007cited by this paper
• Dimension reduction and coefficient estimation in multivariate linear regression

  2007cited by this paper
• Aggregation for Gaussian regression

  2007cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007cited by this paper
• Model selection and estimation in regression with grouped variables

  2006influential reference
• Just relax: convex programming methods for identifying sparse signals in noise

  2006cited by this paper
• ALGORITHMS FOR SIMULTANEOUS SPARSE APPROXIMATION

  2006cited by this paper
• High-dimensional graphs and variable selection with the Lasso

  2006cited by this paper
• On Model Selection Consistency of Lasso

  2006cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• Sparsity and smoothness via the fused lasso

  2005influential reference
• Random Matrices

  2005cited by this paper
• Simultaneous Variable Selection

  2005influential reference
• Neighborliness of randomly projected simplices in high dimensions.

  2005cited by this paper
• Decoding by linear programming

  2005cited by this paper
• Convex Optimization

  2004cited by this paper
• Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices

  2004cited by this paper
• Persistence in high-dimensional linear predictor selection and the virtue of overparametrization

  2004cited by this paper
• Hyperspectral Image Data Analysis as a High Dimensional Signal Processing Problem

  2002cited by this paper
• Hyperspectral image data analysis

  2002cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998influential reference
• Semidefinite Programming

  1996cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Statistical analysis of observations of increasing dimension

  1995cited by this paper
• Probability in Banach Spaces: Isoperimetry and Processes

  1991influential reference
• Asymptotic behavior of M-estimators of p regression parameters when p

  1985cited by this paper
• Asymptotic Behavior of $M$-Estimators of $p$ Regression Parameters when $p^2/n$ is Large. I. Consistency

  1984cited by this paper
• On the spectrum of random matrices

  1972cited by this paper
• Characteristic Vectors of Bordered Matrices with Infinite Dimensions I

  1955cited by this paper
• Covariance Estimation

  year unknowncited by this paper

• Inference on the Significance of Modalities in Multimodal Generalized Linear Models

  2026cites this paper
• Covariate Selection for Joint Latent Space Modeling of Sparse Network Data

  2026cites this paper
• High-dimensional conditional factor model

  2026cites this paper
• Iterative sequential screening strategies for sparse recovery with computational advantages

  2026cites this paper
• Smooth, Sparse, and Stable: Finite-Time Exact Skeleton Recovery via Smoothed Proximal Gradients

  2026cites this paper
• Robust low-rank estimation with multiple binary responses using pairwise AUC loss

  2026cites this paper
• Adaptive Penalized Doubly Robust Regression for Longitudinal Data

  2026cites this paper
• Sparsity Is Necessary: Polynomial-Time Stability for Agentic LLMs in Large Action Spaces

  2026cites this paper
• Low-rank regularization of global fréchet regression models for distributional responses

  2026cites this paper
• A Generalized Adaptive Joint Learning Framework for High-Dimensional Time-Varying Models

  2026influential citation
• Quantum-stable robust principal component analysis: theory and evidence from NISQ regimes

  2026cites this paper
• Learning Conditional Independence Differential Graphs From Time-Dependent Data

  2025influential citation
• Estimation of High-Dimensional Nonlinear Vector Autoregressive Models

  2025cites this paper
• Transfer learning for high dimensional data with discrete responses

  2025cites this paper
• Targeted learning via probabilistic subpopulation matching

  2025cites this paper
• Online Algorithms for Recovery of Low-Rank Parameter Matrix in Non-stationary Stochastic Systems

  2025cites this paper
• Binary Kernel Logistic Regression: a sparsity-inducing formulation and a convergent decomposition training algorithm

  2025cites this paper
• Adaptively robust classification via smoothed support matrix machine

  2025cites this paper
• Inferring Diffusion Structures of Heterogeneous Network Cascade

  2025cites this paper
• Robust ℓ2,0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{2,0}$$\end{document}-penalized rank regression for h

  2025cites this paper
• Supervised factor modeling for high-dimensional linear time series

  2025cites this paper
• Sparse estimation and inference for prediction-powered semi-supervised linear regression

  2025cites this paper
• Efficiently Learning Synthetic Control Models for High-dimensional Disaggregated Data

  2025influential citation
• Decentralized Nonconvex Low-rank Matrix Recovery

  2025cites this paper
• Lasso Penalization for High‐Dimensional Beta Regression Models: Computation, Analysis, and Inference

  2025cites this paper
• Leveraging Shared Factor Structures for Enhanced Matrix Completion with Nonconvex Penalty Regularization

  2025cites this paper
• Causal Inference in High-Dimensional Generalized Linear Models with Binary Outcomes

  2025cites this paper
• Robust multitask feature learning with adaptive Huber regressions

  2025cites this paper
• Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints

  2025cites this paper
• Efficient Group Lasso Regularized Rank Regression with Data-Driven Parameter Determination

  2025cites this paper
• Communication-Efficient Distributed Sparse Learning with Oracle Property and Geometric Convergence

  2025cites this paper
• Early-Stopped Mirror Descent for Linear Regression over Convex Bodies

  2025cites this paper
• Using penalized-distance likelihood functions to analyze high-dimensional sparse/non-sparse data

  2025cites this paper
• The half-quadratic approach for high-dimensional robust M-estimation

  2025cites this paper
• A sparse estimate to varying-coefficient additive models for functional and longitudinal data

  2025cites this paper
• Covariate-assisted graph matching

  2025cites this paper
• Transfer Learning for Matrix Completion

  2025influential citation
• High-Dimensional Regularized Additive Matrix Autoregressive Model

  2025cites this paper
• Collaborative Inference for Sparse High-Dimensional Models with Non-Shared Data

  2025influential citation
• Regression and autoregressive models via sparse Laplacian Shrinkage

  2025cites this paper
• Graphical Models and Efficient Inference Methods for Multivariate Phase Probability Distributions

  2025cites this paper
• Nuclear Norm Regularization

  2025cites this paper
• Learning Multi-Attribute Differential Graphs With Non-Convex Penalties

  2025cites this paper
• Burer-Monteiro factorizability of nuclear norm regularized optimization

  2025cites this paper
• Quantile Predictions for Equity Premium using Penalized Quantile Regression with Consistent Variable Selection across Multiple Quantiles

  2025influential citation
• Nonlinear Causal Discovery for Grouped Data

  2025cites this paper
• Sparse classification with positive-confidence data in high dimensions

  2025influential citation
• Robust Multi-Task Regression with Shifting Low-Rank Patterns

  2025cites this paper
• Low-Rank Matrix Recovery Via Nonconvex Optimization Methods with Application to Errors-in-Variables Matrix Regression

  2025cites this paper
• Kernelized Discriminant Analysis for Joint Modeling of Multivariate Categorical Responses

  2025cites this paper
• Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation

  2025cites this paper
• Regularized Adaptive Huber Matrix Regression and Distributed Learning

  2025cites this paper
• Residual Balancing for Non-Linear Outcome Models in High Dimensions

  2025influential citation
• Efficient and Robust Semi-supervised Estimation of Average Treatment Effect with Partially Annotated Treatment and Response

  2025cites this paper
• Distributed Semi-Supervised Inference for Generalized Linear Models With Block-Wise Missing Covariates

  2025influential citation
• Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

  2025cites this paper
• Lasso and Partially-Rotated Designs

  2025cites this paper
• Bayesian compressive sensing using generative models

  2025cites this paper
• Variable Selection for Additive Global Fr\'echet Regression

  2025cites this paper
• Sparse Deep Additive Model with Interactions: Enhancing Interpretability and Predictability

  2025cites this paper
• Spectral Thresholds for Identifiability and Stability:Finite-Sample Phase Transitions in High-Dimensional Learning

  2025cites this paper
• Navigating Sparsities in High-Dimensional Linear Contextual Bandits

  2025cites this paper
• Digital Adoption and Cyber Security: An Analysis of Canadian Businesses

  2025cites this paper
• DisC2o-HD: Distributed causal inference with covariates shift for analyzing real-world high-dimensional data

  2025cites this paper
• TransFusion: Covariate-Shift Robust Transfer Learning for High-Dimensional Regression

  2024cites this paper
• Identifying sparse treatment effects in high-dimensional outcome spaces

  2024cites this paper
• Covariance Regression with High-Dimensional Predictors

  2024cites this paper
• High-Dimensional Tail Index Regression: with An Application to Text Analyses of Viral Posts in Social Media

  2024cites this paper
• D4R: Doubly robust reduced rank regression in high dimension

  2024cites this paper
• Regularised Spectral Estimation for High-Dimensional Point Processes

  2024influential citation
• Sparse Linear Regression and Lattice Problems

  2024influential citation
• High-dimensional nonconvex LASSO-type M-estimators

  2024cites this paper
• Linear convergence of decentralized estimation for statistical estimation using gradient method

  2024cites this paper
• Doubly regularized generalized linear models for spatial observations with high-dimensional covariates

  2024cites this paper
• Integrated subgroup identification from multi-source data

  2024cites this paper
• A note on the minimax risk of sparse linear regression

  2024cites this paper
• Hierarchical Bayesian Inverse Problems: A High-Dimensional Statistics Viewpoint

  2024influential citation
• High-dimensional penalized Bernstein support vector classifier

  2024cites this paper
• Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming

  2024cites this paper
• Enmsp: an elastic-net multi-step screening procedure for high-dimensional regression

  2024cites this paper
• Efficient variable selection for high-dimensional multiplicative models: a novel LPRE-based approach

  2024cites this paper
• Multi-response Regression for Block-missing Multi-modal Data without Imputation.

  2024cites this paper
• A Generalized Formulation for Group Selection via ADMM

  2024cites this paper
• Robust group and simultaneous inferences for high-dimensional single index model

  2024cites this paper
• Sketching for Distributed Deep Learning: A Sharper Analysis

  2024cites this paper
• A Debiased Estimator for the Mediation Functional in Ultra-High-Dimensional Setting in the Presence of Interaction Effects

  2024cites this paper
• Spectral Differential Network Analysis for High-Dimensional Time Series

  2024influential citation
• Statistical inference for smoothed quantile regression with streaming data

  2024cites this paper
• Adaptive debiased SGD in high-dimensional GLMs with streaming data

  2024cites this paper
• Statistical Inference in High-dimensional Poisson Regression with Applications to Mediation Analysis

  2024cites this paper
• Universality in Block Dependent Linear Models With Applications to Nonlinear Regression

  2024cites this paper
• Sparse Linear Regression: Sequential Convex Relaxation, Robust Restricted Null Space Property, and Variable Selection

  2024influential citation
• Subspace decompositions for association structure learning in multivariate categorical response regression

  2024influential citation
• Asymptotically faster estimation of high‐dimensional additive models using subspace learning

  2024cites this paper
• Discrete distributions are learnable from metastable samples

  2024cites this paper
• Asymptotics for estimating a diverging number of parameters -- with and without sparsity

  2024cites this paper
• Discovering significant topics from legal decisions with selective inference

  2024cites this paper
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems

  2024cites this paper
• Multi-source Stable Variable Importance Measure via Adversarial Machine Learning

  2024cites this paper
• Structure learning for continuous time Bayesian networks via penalized likelihood

  2024cites this paper