Piecewise linear regularized solution paths. (English) Zbl 1194.62094

Rosset, Saharon; Zhu, Ji

Ann. Stat. 35, No. 3, 1012-1030 (2007).

Summary: We consider the generic regularized optimization problem \(\widehat{\beta}(\lambda)= \arg\min_\beta L(y,X\beta)+ \lambda J(\beta)\). B. Efron, T. Hastie, I. Johnstone and R. Tibshirani [Ann. Stat. 32, No. 2, 407–499 (2004; Zbl 1091.62054)] have shown that for the LASSO – that is, if \(L\) is the squared error loss and \(J(\beta)= \|\beta\|_1\) is the \(\ell_1\) norm of \(\beta\) – the optimal coefficient path is piecewise linear, that is, \(\partial\widehat{\beta}(\lambda)/ \partial\lambda\) is piecewise constant. We derive a general characterization of the properties of (loss \(L\), penalty \(J\)) pairs which give piecewise linear coefficient paths. Such pairs allow for efficient generation of the full regularized coefficient paths. We investigate the nature of efficient path following algorithms which arise. We use our results to suggest robust versions of the LASSO for regression and classification, and to develop new, efficient algorithms for existing problems in the literature, including Mammen and van de Geer’s locally adaptive regression splines.

MSC:

62J99	Linear inference, regression
65C60	Computational problems in statistics (MSC2010)
90C90	Applications of mathematical programming
62H30	Classification and discrimination; cluster analysis (statistical aspects)

Keywords:

polynomial splines; regularization; solution paths; sparsity; total variation

Citations:

Zbl 1091.62054

Software:

ftnonpar; ElemStatLearn

References:

[1]	Davies, P. L. and Kovac, A. (2001). Local extremes, runs, strings and multiresolution (with discussion). Ann. Statist. 29 1–65. · Zbl 1029.62038
[2]	Donoho, D., Johnstone, I., Kerkyacharian, G. and Picard, D. (1995). Wavelet shrinkage: Asymptopia? (with discussion). J. Roy. Statist. Soc. Ser. B 57 301–369. JSTOR: · Zbl 0827.62035
[3]	Efron, B., Hastie, T., Johnstone, I. M. and Tibshirani, R. (2004). Least angle regression (with discussion). Ann. Statist. 32 407–499. · Zbl 1091.62054
[4]	Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96 1348–1360. JSTOR: · Zbl 1073.62547
[5]	Fan, J. and Peng, H. (2004). Nonconcave penalized likelihood with a diverging number of parameters. Ann. Statist. 32 928–961. · Zbl 1092.62031
[6]	Freund, Y. and Schapire, R. E. (1996). Experiments with a new boosting algorithm. In Proc. 13th International Conference on Machine Learning 148–156. Morgan Kauffman, San Francisco.
[7]	Hastie, T., Rosset, S., Tibshirani, R. and Zhu, J. (2004). The entire regularization path for the support vector machine. J. Mach. Learn. Res. 5 1391–1415. · Zbl 1222.68213
[8]	Hastie, T., Tibshirani, R. and Friedman, J. (2001). The Elements of Statistical Learning : Data Mining , Inference and Prediction . Springer, New York. · Zbl 0973.62007
[9]	Hoerl, A. and Kennard, R. (1970). Ridge regression: Biased estimation for nonorthogonal problems. Technometrics 12 55–67. · Zbl 0202.17205
[10]	Huber, P. (1964). Robust estimation of a location parameter. Ann. Math. Statist. 35 73–101. · Zbl 0136.39805
[11]	Koenker, R. (2005). Quantile Regression . Cambridge Univ. Press. · Zbl 1111.62037
[12]	Koenker, R., Ng, P. and Portnoy, S. (1994). Quantile smoothing splines. Biometrika 81 673–680. JSTOR: · Zbl 0810.62040
[13]	Mammen, E. and van de Geer, S. (1997). Locally adaptive regression splines. Ann. Statist. 25 387–413. · Zbl 0871.62040
[14]	Osborne, M., Presnell, B. and Turlach, B. (2000). On the LASSO and its dual. J. Comput. Graph. Statist. 9 319–337. JSTOR:
[15]	Rosset, S., Zhu, J. and Hastie, T. (2004). Boosting as a regularized path to a maximum margin classifier. J. Mach. Learn. Res. 5 941–973. · Zbl 1222.68290
[16]	Shen, X., Tseng, G., Zhang, X. and Wong, W. H. (2003). On \(\psi\)-learning. J. Amer. Statist. Assoc. 98 724–734. · Zbl 1052.62095
[17]	Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B 58 267–288. JSTOR: · Zbl 0850.62538
[18]	Tibshirani, R., Saunders, M., Rosset, S., Zhu, J. and Knight, K. (2005). Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. Ser. B Stat. Methodol. 67 91–108. · Zbl 1060.62049
[19]	Tsuda, K. and Ratsch, G. (2005). Image reconstruction by linear programming. IEEE Trans. Image Process. 14 737–744.
[20]	Vapnik, V. (1995). The Nature of Statistical Learning Theory . Springer, New York. · Zbl 0833.62008
[21]	Zhu, J., Rosset. S., Hastie, T. and Tibshirani, R. (2003). 1-norm support vector machines. In Advances in Neural Information Processing Systems 16 .