Skip to content

Charles Hernandez, Hung-Yi Lee, Jindong Tong, Hongcheng Liu, Fully polynomial-time randomized approximation schemes for global optimization of high-dimensional minimax concave penalized generalized linear models

Full Text: PDF
DOI: 10.23952/jnva.8.2024.6.05

Volume 8, Issue 6, 1 December 2024, Pages 909-934

 

Abstract. Global solutions to high-dimensional sparse estimation problems with a folded concave penalty (FCP) have been shown to be statistically desirable but are strongly NP-hard to compute which implies the non-existence of pseudo-polynomial time global optimization schemes in the worst case. This paper shows that, with high probability, a global solution to generalized linear models with minimax concave penalty (MCP), a specific type of FCP, coincides with a stationary point characterized by the significant subspace second order necessary conditions (S^3ONC). Given that the desired S^3ONC solution admits a fully polynomial-time randomized approximation scheme (FPRAS), we are able to demonstrate the existence of an FPRAS for this strongly NP-hard problem. We further demonstrate two versions of the FPRAS for generating the desired S^3ONC solutions. One follows the paradigm of an interior point trust region algorithm and the other is the well-studied local linear approximation (LLA). Our analysis thus provides new techniques for global optimization of certain NP-Hard problems and new insights on the effectiveness of LLA.

 

How to Cite this Article:
C. Hernandez, H.Y. Lee, J. Tong, H. Liu, Fully polynomial-time randomized approximation schemes for global optimization of high-dimensional minimax concave penalized generalized linear models, J. Nonlinear Var. Anal. 8 (2024), 909-934.