Optimal computational and statistical rates of convergence for sparse nonconvex learning problems

Abstract

We provide theoretical analysis of the statistical and computational properties of penalized $M$-estimators that can be formulated as the solution to a possibly nonconvex optimization problem. Many important estimators fall in this category, including least squares regression with nonconvex regularization, generalized linear models with nonconvex regularization and sparse elliptical random design regression. For these problems, it is intractable to calculate the global solution due to the nonconvex formulation. In this paper, we propose an approximate regularization path-following method for solving a variety of learning problems with nonconvex objective functions. Under a unified analytic framework, we simultaneously provide explicit statistical and computational rates of convergence for any local solution attained by the algorithm. Computationally, our algorithm attains a global geometric rate of convergence for calculating the full regularization path, which is optimal among all first-order algorithms. Unlike most existing methods that only attain geometric rates of convergence for one single regularization parameter, our algorithm calculates the full regularization path with the same iteration complexity. In particular, we provide a refined iteration complexity bound to sharply characterize the performance of each stage along the regularization path. Statistically, we provide sharp sample complexity analysis for all the approximate local solutions along the regularization path. In particular, our analysis improves upon existing results by providing a more refined sample complexity bound as well as an exact support recovery result for the final estimator. These results show that the final estimator attains an oracle statistical property due to the usage of nonconvex penalty.

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

References in corpus (11)

• Nearly unbiased variable selection under minimax concave penalty
• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• Sparse permutation invariant covariance estimation
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Piecewise linear regularized solution paths
• High-dimensional generalized linear models and the lasso
• Strong oracle optimality of folded concave penalized estimation
• Calibrating nonconvex penalized regression in ultra-high dimension
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems

Cited by in corpus (10)

• Challenges of Big Data Analysis
• Robust PCA via Nonconvex Rank Approximation
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Successive Concave Sparsity Approximation for Compressed Sensing
• Global solutions to folded concave penalized nonconvex learning
• Sparse PCA with Oracle Property
• Fully Bayesian Logistic Regression with Hyper-Lasso Priors for High-dimensional Feature Selection
• Penalized Estimation of Frailty-Based Illness-Death Models for Semi-Competing Risks
• An unbiased approach to compressed sensing
• Fully Bayesian Classification with Heavy-tailed Priors for Selection in High-dimensional Features with Grouping Structure