Piecewise linear regularized solution paths

We consider the generic regularized optimization problem β̂(λ)=arg minβ L(y, Xβ)+λJ(β). Efron, Hastie, Johnstone and Tibshirani [Ann. Statist. 32 (2004) 407–499] have shown that for the LASSO—that is, if L is squared error loss and J(β)=‖β‖1 is the ℓ1 norm of β—the optimal coefficient path is piecewise linear, that is, ∂β̂(λ)/∂λ is piecewise constant. We derive a general characterization of the properties of (loss L, penalty J) pairs which give...