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 (). Given that the desired 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 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.