Global solutions to folded concave penalized nonconvex learning

Abstract

This paper is concerned with solving nonconvex learning problems with folded concave penalty. Despite that their global solutions entail desirable statistical properties, they lack optimization techniques that guarantee global optimality in a general setting. In this paper, we show that a class of nonconvex learning problems are equivalent to general quadratic programs. This equivalence facilitates us in developing mixed integer linear programming reformulations, which admit finite algorithms that find a provably global optimal solution. We refer to this reformulation-based technique as the mixed integer programming-based global optimization (MIPGO). To our knowledge, this is the first global optimization scheme with a theoretical guarantee for folded concave penalized nonconvex learning with the SCAD penalty [J. Amer. Statist. Assoc. 96 (2001) 1348-1360] and the MCP penalty [Ann. Statist. 38 (2001) 894-942]. Numerical results indicate a significant outperformance of MIPGO over the state-of-the-art solution scheme, local linear approximation and other alternative solution techniques in literature in terms of solution quality.

arXiv commentPublished at http://dx.doi.org/10.1214/15-AOS1380 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional graphs and variable selection with the Lasso
• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• Variable selection using MM algorithms
• Strong oracle optimality of folded concave penalized estimation
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Calibrating nonconvex penalized regression in ultra-high dimension
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems

Cited by in corpus (8)

• The Trimmed Lasso: Sparsity and Robustness
• Learning non-smooth models: instrumental variable quantile regressions and related problems
• Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data
• Doubly Robust Feature Selection with Mean and Variance Outlier Detection and Oracle Properties
• An Efficient ADMM-Based Algorithm to Nonconvex Penalized Support Vector Machines
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• MSP: A Multi-step Screening Procedure for Sparse Recovery
• On an improvement of LASSO by scaling