Strong oracle optimality of folded concave penalized estimation

Abstract

Folded concave penalization methods have been shown to enjoy the strong oracle property for high-dimensional sparse estimation. However, a folded concave penalization problem usually has multiple local solutions and the oracle property is established only for one of the unknown local solutions. A challenging fundamental issue still remains that it is not clear whether the local optimum computed by a given optimization algorithm possesses those nice theoretical properties. To close this important theoretical gap in over a decade, we provide a unified theory to show explicitly how to obtain the oracle solution via the local linear approximation algorithm. For a folded concave penalized estimation problem, we show that as long as the problem is localizable and the oracle estimator is well behaved, we can obtain the oracle estimator by using the one-step local linear approximation. In addition, once the oracle estimator is obtained, the local linear approximation algorithm converges, namely it produces the same estimator in the next iteration. The general theory is demonstrated by using four classical sparse estimation problems, that is, sparse linear regression, sparse logistic regression, sparse precision matrix estimation and sparse quantile regression.

Published in at http://dx.doi.org/10.1214/13-AOS1198 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org). With Corrections

References in corpus (11)

• Nearly unbiased variable selection under minimax concave penalty
• Regularized estimation of large covariance matrices
• One-step sparse estimates in nonconcave penalized likelihood models
• Composite quantile regression and the oracle Model Selection Theory
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Strong oracle optimality of folded concave penalized estimation
• Adaptive robust variable selection
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• High-dimensional covariance estimation by minimizing ${\ell }_1$-penalized log-determinant divergence
• Nonconcave penalized composite conditional likelihood estimation of sparse Ising models
• Non-Concave Penalized Likelihood with NP-Dimensionality

Cited by in corpus (57)

• Guaranteed Matrix Completion via Non-convex Factorization
• Strong oracle optimality of folded concave penalized estimation
• High-Dimensional Inference: Confidence Intervals, $p$-Values and R-Software hdi
• Multi-Stage Multi-Task Feature Learning
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• Covariate assisted screening and estimation
• LogDet Rank Minimization with Application to Subspace Clustering
• Are Discoveries Spurious? Distributions of Maximum Spurious Correlations and Their Applications
• Global solutions to folded concave penalized nonconvex learning
• Distributed recovery of jointly sparse signals under communication constraints
• A General Theory of Hypothesis Tests and Confidence Regions for Sparse High Dimensional Models
• On Semiparametric Exponential Family Graphical Models
• QUADRO: A supervised dimension reduction method via Rayleigh quotient optimization
• Uniform Inference for High-dimensional Quantile Regression: Linear Functionals and Regression Rank Scores
• An unbiased approach to compressed sensing
• Simultaneous Feature Selection and Outlier Detection with Optimality Guarantees
• Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
• Multiple-Splitting Projection Test for High-Dimensional Mean Vectors
• High-dimensional Censored Regression via the Penalized Tobit Likelihood
• A Likelihood Ratio Framework for High Dimensional Semiparametric Regression
• I-LAMM for Sparse Learning: Simultaneous Control of Algorithmic Complexity and Statistical Error
• Pathwise Coordinate Optimization for Sparse Learning: Algorithm and Theory
• Functional Group Bridge for Simultaneous Regression and Support Estimation
• A nonparametric Bayesian analysis of heterogeneous treatment effects in digital experimentation
• Inference for a Large Directed Acyclic Graph with Unspecified Interventions
• Penalized pairwise pseudo likelihood for variable selection with nonignorable missing data
• Penalized Sparse Covariance Regression with High Dimensional Covariates
• Efficient Sparse Least Absolute Deviation Regression with Differential Privacy
• High Dimensional Semiparametric Latent Graphical Model for Mixed Data
• Bias Reduction in Compressed Sensing
• A Convex-Nonconvex Strategy for Grouped Variable Selection
• A Laplace Mixture Representation of the Horseshoe and Some Implications
• Non-convex Lasso-kind approach to compressed sensing for finite-valued signals
• Non-bifurcating phylogenetic tree inference via the adaptive LASSO
• Semiparametric Expectile Regression for High-dimensional Heavy-tailed and Heterogeneous Data
• On the Pervasiveness of Difference-Convexity in Optimization and Statistics
• Selection consistency of Lasso-based procedures for misspecified high-dimensional binary model and random regressors
• High-Dimensional Expected Shortfall Regression
• Mixed-Effect Time-Varying Network Model and Application in Brain Connectivity Analysis
• The folded concave Laplacian spectral penalty learns block diagonal sparsity patterns with the strong oracle property
• Nonparametric mixture of Gaussian graphical models
• Asymptotic properties of one-step $M$-estimators based on nonidentically distributed observations with applications to nonlinear regression problems
• Robust Estimation and Shrinkage in Ultrahigh Dimensional Expectile Regression with Heavy Tails and Variance Heterogeneity
• A proximal MM method for the zero-norm regularized PLQ composite optimization problem
• Structural Change in Sparsity
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
• Forward variable selection for sparse ultra-high dimensional varying coefficient models
• MSP: A Multi-step Screening Procedure for Sparse Recovery
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
• A proximal dual semismooth Newton method for computing zero-norm penalized QR estimator
• Diagonally-Dominant Principal Component Analysis
• Mean and variance estimation in high-dimensional heteroscedastic models with non-convex penalties
• Estimating high-dimensional Markov-switching VARs
• yaglm: a Python package for fitting and tuning generalized linear models that supports structured, adaptive and non-convex penalties
• Accelerated forward-backward method with fast convergence rate for nonsmooth convex optimization beyond differentiability
• Robust Learning for Optimal Treatment Decision with NP-Dimensionality