Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection

Abstract

Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-norm penalty is computationally intractable for larger scale problems, so dif- ferent sparsity-inducing penalty functions that approximate the l0-norm have been introduced. In this paper, we show that viewing the problem from a convex relaxation perspective offers new insights. In particular, we show that a popular sparsity-inducing concave penalty function known as the Minimax Concave Penalty (MCP), and the reverse Huber penalty derived in a recent work by Pilanci, Wainwright and Ghaoui, can both be derived as special cases of a lifted convex relaxation called the perspective relaxation. The optimal perspective relaxation is a related minimax problem that balances the overall convexity and tightness of approximation to the l0 norm. We show it can be solved by a semidefinite relaxation. Moreover, a probabilistic interpretation of the semidefinite relaxation reveals connections with the boolean quadric polytope in combinatorial optimization. Finally by reformulating the l0-norm pe- nalized problem as a two-level problem, with the inner level being a Max-Cut problem, our proposed semidefinite relaxation can be realized by replacing the inner level problem with its semidefinite relaxation studied by Goemans and Williamson. This interpretation suggests using the Goemans-Williamson rounding procedure to find approximate solutions to the l0-norm penalized problem. Numerical experiments demonstrate the tightness of our proposed semidefinite relaxation, and the effectiveness of finding approximate solutions by Goemans-Williamson rounding.

Also available on optimization online {http://www.optimization-online.org/DB_HTML/2015/05/4932.html}

References in corpus (4)

• Nearly unbiased variable selection under minimax concave penalty
• Pathwise coordinate optimization
• On the adaptive elastic-net with a diverging number of parameters
• Asymptotic properties of bridge estimators in sparse high-dimensional regression models

Cited by in corpus (14)

• A Scalable Algorithm For Sparse Portfolio Selection
• Rank-one Convexification for Sparse Regression
• Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality
• A new perspective on low-rank optimization
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks
• Ideal formulations for constrained convex optimization problems with indicator variables
• 2x2 convexifications for convex quadratic optimization with indicator variables
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• On the exact recovery of sparse signals via conic relaxations
• Scalable Algorithms for the Sparse Ridge Regression
• Safe Screening Rules for ${\ell }_0$-Regression
• Compact extended formulations for low-rank functions with indicator variables