1-norm Regularization: Efficient and Effective

• Activity Number: 364
• Type: Invited
• Date/Time: Wednesday, August 11, 2004 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Saharon Rosset*+ and Ji Zhu
• Companies: IBM T.J. Watson Research Center and Stanford University
• Keywords: l_1 regularization ; flexible fitting ; robust modeling ; boosting ; LARS ; lasso

Abstract

We consider the general regularized optimization problem of minimizing loss+penalty, where the loss depends on the data and the model, and the penalty on the model only. We illustrate that the choice of l_1 (lasso) penalty, in combination with appropriate loss, leads to several desirable properties: (1) Approximate or exact l_1 regularization has given rise to highly successful modeling tools: the lasso, boosting, wavelets and 1-norm support vector machines. (2) l_1 regularization creates sparse models, a property that is especially desirable in high-dimensional predictor spaces. We formulate and prove sparsity results. (3) l_1 regularization facilitates efficient methods for solving the regularized optimization problem. The LARS algorithm takes advantage of this property. We present a general formulation of regularized optimization problems for which efficient methods can be designed. We show how we can create modeling tools which are robust (because of the loss function selected), efficient (because we solve the regularized problem efficiently) and adaptive (because we select the regularization parameter adaptively). (Joint work with Trevor Hastie and Rob Tibshirani.)