Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/87579
Title: | A constructive approach to L0 penalized regression | Authors: | Huang, J Jiao, Y Liu, Y Lu, X |
Issue Date: | 2018 | Source: | Journal of machine learning research, Aug. 2018, v. 19, p. 1-37 | Abstract: | We propose a constructive approach to estimating sparse, high-dimensional linear regression models. The approach is a computational algorithm motivated from the KKT conditions for the `0-penalized least squares solutions. It generates a sequence of solutions iteratively, based on support detection using primal and dual information and root _nding. We refer to the algorithm as SDAR for brevity. Under a sparse Riesz condition on the design matrix and certain other conditions, we show that with high probability, the `2 estimation error of the solution sequence decays exponentially to the minimax error bound in O(log(RpJ)) iterations, where J is the number of important predictors and R is the relative magnitude of the nonzero target coe_cients; and under a mutual coherence condition and certain other conditions, the `1 estimation error decays to the optimal error bound in O(log(R)) iterations. Moreover the SDAR solution recovers the oracle least squares estimator within a _nite number of iterations with high probability if the sparsity level is known. Computational complexity analysis shows that the cost of SDAR is O(np) per iteration. We also consider an adaptive version of SDAR for use in practical applications where the true sparsity level is unknown. Simulation studies demonstrate that SDAR outperforms Lasso, MCP and two greedy methods in accuracy and e_ciency. | Keywords: | Geometrical convergence KKT conditions Nonasymptotic error bounds |
Publisher: | MIT Press | Journal: | Journal of machine learning research | ISSN: | 1532-4435 | EISSN: | 1533-7928 | Rights: | © 2018 Jian Huang, Yuling Jiao, Yanyan Liu, and Xiliang Lu. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v19/17-194.html. The following publication Huang, J., Jiao, Y., Liu, Y., & Lu, X. (2018). A constructive approach to L0 penalized regression. Journal of Machine Learning Research, 19, 1-37 is available at http://www.jmlr.org/papers/v19/17-194.html |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Huang_L0_Penalized_Regression.pdf | 543.08 kB | Adobe PDF | View/Open |
Page views
67
Last Week
0
0
Last month
Citations as of May 5, 2024
Downloads
243
Citations as of May 5, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.