# Lp regularization with p < 1?

Lasso regularization has the nice property of creating coefficient sparsity. Generalizing to Lp regularization, is it possible to regularize a logistic regression with p < 1? I would like to control the sparsity, possibly at the expense of performance. Is there a way to do this in Python? Scikit-Learn only has L1/L2.

• Why don't you just increase the penalty parameter ($\lambda$) rather than possibly making the problem a non convex optimization problem?
– Josh
Dec 11 '17 at 23:52
• well, from what I understand, that won't increase the sparsity. Changing the penalty parameter simply scales the model weights. It's the regularizer's contour lines that controls sparsity. Going from circle (l2) to diamond (l1) that we increase sparsity, so I wonder if we can keep going with that idea by decreases p to below 1.
– vega
Dec 12 '17 at 0:22
• For L1 it will, by definition.
– Josh
Dec 12 '17 at 0:23
• You get the ultimate in sparsity with p = 0. That presents a non-convex combinatorial problem. p = 1 can be used as a convex "proxy" for p = 0, which does not necessarily do as well relative to sparseness, but is much easier to compute with, Dec 12 '17 at 0:54
• @MarkL.Stone, and what of p < 1? Wouldn't that be a better proxy?
– vega
Dec 12 '17 at 1:34

In the context of linear regression, Frank and Friedman (1993) introduced 'bridge regression'. The goal is to minimize the squared error plus a penalty on the $\ell_p$ norm of the weights.

$$\min_w \sum_{i=1}^n (y - w \cdot x_i)^2 + \lambda \|w\|_p$$

$p=2$ corresponds to ridge regression, $p=2$ to the lasso, and $p=0$ to subset selection. As discussed by Tibshirani (1996) and Fu (1998), $p \le 1$ yields sparse solutions, and smaller values of $p$ correspond to priors on the weights that are increasingly concentrated around the axes. That is, smaller values of $p$ correspond to a preference for increasingly sparse solutions. There are also similarities between bridge regression with $1 \le p \le 2$ and elastic net regression (a combination of $\ell_1$ and $\ell_2$ penalties), which I discuss here.

The penalty term is convex for $p \ge 1$, but not for $p < 1$, which makes solving the optimization problem much more difficult in the latter case. Heuristic strategies have been developed. For example, Orthogonal Matching Pursuit (Pati et al. 1993) is a greedy strategy for obtaining approximate solutions when $p=0$ (which is an NP-hard problem). However, the lasso and elastic net are currently preferred in most circumstances. They work well in practice, they have well understood properties, and efficient solvers are available.

If your goal is to control the sparsity, it would make sense to start by penalizing the $\ell_1$ norm, and adjusting the strength of the penalty term (as mentioned in the comments). This is much simpler than dealing with the nasty, nonconvex optimization problem you'd have with $p < 1$.

References

Frank and Friedman (1993). A Statistical View of Some Chemometrics Regression Tools.

Fu (1998). Penalized Regressions: The Bridge versus the Lasso.

Pati et al. (1993). Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition.

Tibshirani (1996). Regression Shrinkage and Selection via the Lasso.

Zou and Hastie (2005). Regularization and variable selection via the elastic net.

• I see, so it's more difficult because it is non-convex. But why can't we solve it with methods like gradient descent as we do with neural nets?
– vega
Dec 12 '17 at 18:56
• Convex optimization tools like gradient descent could be used to find a local minimum for $0<p<1$, but there's no guarantee that it would be globally optimal. One issue is that neural nets are primarily used for prediction, whereas people often use linear/logistic regression when the goal is to interpret the weights. In this context, you wouldn't want the weights to simply reflect a quirk of the optimization problem, so further steps would have to be taken (ranging from multiple restarts to more principled global optimization algorithms). (continued…) Dec 12 '17 at 20:34
• In the context of prediction, it has been shown for neural nets that local minima become less of a problem as network size grows (and may even have better generalization performance than the global minimum). Linear/logistic regression can actually be formulated as shallow neural nets. But it’s not clear to me that this result would apply to them because the nonconvexity comes from the penalty. All in all, I’m not saying that one shouldn’t penalize the $\ell_p$ norm. Just that there are more convenient places to start. Dec 12 '17 at 20:35
• Ah! Very interesting. So because we would use methods for non-convex functions, the resulting coefficients are not to be interpreted as with lasso, i.e. they don't necessarily indicate contribution to classification. Do I get it?
– vega
Dec 13 '17 at 16:06
• @vega I think it's slightly more subtle. Because of the linear structure of the model, any set of weights represents the the contribution to the classification by that particular classifier (change in predicted log odds per input unit). The issue is that, if you can't be sure whether you've converged to a local minimum, you don't know whether the particular weights you've found best represent the data. Dec 13 '17 at 22:12