A modified local quadratic approximation algorithm for penalized optimization problems. (English) Zbl 1468.62114
Summary: In this paper, we propose an optimization algorithm called the modified local quadratic approximation algorithm for minimizing various \(\ell_1\)-penalized convex loss functions. The proposed algorithm iteratively solves \(\ell_1\)-penalized local quadratic approximations of the loss function, and then modifies the solution whenever it fails to decrease the original \(\ell_1\)-penalized loss function. As an extension, we construct an algorithm for minimizing various nonconvex penalized convex loss functions by combining the proposed algorithm and convex concave procedure, which can be applied to most nonconvex penalty functions such as the smoothly clipped absolute deviation and minimax concave penalty functions. Numerical studies show that the algorithm is stable and fast for solving high dimensional penalized optimization problems.
MSC:
| 62-08 | Computational methods for problems pertaining to statistics |
| 62J07 | Ridge regression; shrinkage estimators (Lasso) |
Keywords:
local quadratic approximation; \(\ell_1\)-penalization; nonconvex penalization; Lasso; SCAD; MCPReferences:
| [1] | Alon, U.; Barkai, N.; Notterman, D. A.; Gish, K.; Ybarra, S.; Mack, D.; Levine, A. J., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Proc. Natl. Acad. Sci., 96, 6745-6750, (1999) |
| [2] | Bishop, C. M., Neural networks for pattern recognition, (1995), Clarendon Press Oxford |
| [3] | Böhning, D.; Lindsay, B. G., Monotonicity of quadratic approximation algorithms, Ann. Inst. Statist. Math., 40, 641-663, (1988) · Zbl 0723.65150 |
| [4] | Breheny, P.; Huang, J., Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection, Ann. Appl. Stat., 5, 232-253, (2011) · Zbl 1220.62095 |
| [5] | Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1999) · Zbl 0919.94002 |
| [6] | De Borst, R.; Crisfield, M. A.; Remmers, J. J.; Verhoosel, C. V., Nonlinear finite element analysis of solids and structures, (2012), John Wiley and Sons · Zbl 1300.74002 |
| [7] | Dudoit, S.; Fridlyand, J.; Speed, T. P., Comparison of discrimination methods for the classifcation of tumors using gene expression data, J. Amer. Statist. Assoc., 97, 77-87, (2002) · Zbl 1073.62576 |
| [8] | Efron, B.; Hastie, T.; Johnstone, I.; Tibshirani, R., Least angle regression, Ann. Statist., 32, 407-499, (2004) · Zbl 1091.62054 |
| [9] | Fan, J.; Li, R., Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96, 1348-1360, (2001) · Zbl 1073.62547 |
| [10] | Friedman, J.; Hastie, T.; Höfling, H.; Tibshirani, R., Pathwise coordinate optimization, Ann. Appl. Stat., 1, 302-332, (2007) · Zbl 1378.90064 |
| [11] | Friedman, J.; Hastie, T.; Tibshirani, R., Regularization paths for generalized linear models via coordinate descent, J. Stat. Softw., 33, 1-22, (2010) |
| [12] | Gunn, S. R.; Kandola, J. S., Structural modeling with sparse kernels, Mach. Learn., 48, 115-136, (2002) · Zbl 0998.68119 |
| [13] | Kim, Y.; Choi, H.; Oh, H. S., Smoothly clipped absolute deviation on high dimensions, J. Amer. Statist. Assoc., 103, 1665-1673, (2008) · Zbl 1286.62062 |
| [14] | Kim, J.; Kim, Y.; Kim, Y., A gradient-based optimization algorithm for LASSO, J. Comput. Graph. Statist., 17, 994-1009, (2008) |
| [15] | Kim, Y.; Kwon, S.; Song, S., Multiclass sparse logistic regression for classification of multiple cancer types using gene expression data, Comput. Statist. Data Anal., 51, 1643-1655, (2006) · Zbl 1157.62535 |
| [16] | Krishnapuram, B.; Carin, L.; Figueiredo, M.; Hartemink, A., Sparse multinomial logistic regression: fast algorithms and generalization bounds, IEEE Trans. Pattern Anal. Mach. Intell., 27, 957-968, (2005) |
| [17] | Lokhorst, J., Turlach, B.A., Venables, W.N., Lasso2: An S-Plus library to solve regression problems while imposing an \(\ell_1\)-constraint on the parameters. Documentation in R-lasso2 Library, 2006. |
| [18] | Osborne, M. R.; Presnell, B.; Turlach, B. A., A new approach to variable selection in least squares problems, IMA J. Numer. Anal., 20, 389-404, (2000) · Zbl 0962.65036 |
| [19] | Park, M.; Hastie, T., \(L_1\)-regularization path algorithm for generalized linear models, J. R. Stat. Soc. Ser. B, 69, 659-667, (2007) · Zbl 07555370 |
| [20] | Piazza, J. A., The opium trade and patterns of terrorism in the provinces of afghanistan: an empirical analysis, Terror. Polit. Violence, 24, 213-234, (2012) |
| [21] | Rosset, S.; Zhu, J., Piecewise linear regularized solution paths, Ann. Statist., 35, 1012-1030, (2007) · Zbl 1194.62094 |
| [22] | Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 267-288, (1996) · Zbl 0850.62538 |
| [23] | Yuan, G. X.; Ho, C. H.; Lin, C. J., An improved GLMNET for l1-regularized logistic regression, J. Mach. Learn. Res., 13, 1999-2030, (2012) · Zbl 1432.68404 |
| [24] | Yuille, A.; Rangarajan, A., The conceve-convex procedure, Neural Comput., 15, 915-936, (2003) · Zbl 1022.68112 |
| [25] | Zhang, C. H., Nearly unbiased variable selection under minimax concave penalty, Ann. Statist., 38, 894-942, (2010) · Zbl 1183.62120 |
| [26] | Zhang, H. H.; Wahba, G.; Lin, Y.; Voelker, M.; Ferris, M.; Rklein, R.; Klein, B., Variable selection and model building via likelihood basis pursuit, J. Amer. Statist. Assoc., 99, 659-672, (2004) · Zbl 1117.62459 |
| [27] | Zou, H.; Li, R., One-step sparse estimates in nonconcave penalized likelihood models, Ann. Statist., 36, 1509-1533, (2008) · Zbl 1142.62027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
