Sparse regression

1 LASSO

Linear or generalised linear regression under quadratic predictive loss penalty and absolute coefficient penalty.

In the classic form we estimate the regression coefficients $\beta$ by solving

$$\begin{array}{r}\hat{\beta }=\underset{\beta \in {\mathbb{R}}^p}{\text{argmin}}\frac{1}{2}\parallel y-\mathbf{X}\beta {\parallel }_2^2+\lambda \parallel \beta {\parallel }_1,\end{array}$$

The penalty coefficient $\lambda$ is left for you to choose, but one of the magical properties of the lasso is that it is easy to test many possible values of $\lambda$ at low marginal cost.

Popular because, amongst other reasons, it turns out to be fast and convenient, and amenable to various performance accelerations e.g. aggressive approximate variable selection.

2 In Model Interpretation

Sparse regression as a universal classifier explainer?

Local Interpretable Model-agnostic Explanations (Ribeiro, Singh, and Guestrin 2016) is a sparse regression model that explains the predictions of a black-box classifier; see model interpretation.

3 Adaptive LASSO

🏗 This is the one with famous oracle properties if you choose $\lambda$ correctly. Hsi Zou’s explanation (Zou 2006) is readable. I am having trouble digesting van de Geer’s paper (S. A. van de Geer 2008) on the Generalised Lasso, but it seems to offer me guarantees for something very similar to the Adaptive Lasso, with more general assumptions on the model and loss functions, and some finite sample guarantees.

4 LARS

A confusing one; LASSO and LARS are not the same thing but you can use one to calculate the other? Something like that? I need to work this one through with pencil and paper.

5 Graph LASSO

As used in graphical models. 🏗

6 Elastic net

Combination of $L_1$ and $L_2$ penalties. 🏗

7 Grouped LASSO

AFAICT this is the usual LASSO but with grouped factors. See (Yuan and Lin 2006).

8 Relaxed Lasso

🏗

9 Dantzig Selector

🏗

10 Garotte

🏗

11 Degrees-of-freedom penalties

See degrees of freedom.

12 FOCI

FOCI, a sparse model selection procedure (Azadkia and Chatterjee 2019) based on Chatterjee’s ξ statistic as an independence test. (Chatterjee 2020). Looks interesting.

13 FRISO

FRISO (Tucker, Wu, and Müller 2023) is a sparse model selection procedure for functional data.

14 Stability selection

🏗

For now see mplot for an introduction.

15 Debiased LASSO

There exist a few versions, but the one I have needed is (S. A. van de Geer 2008), section 2.1. See also (S. van de Geer 2014b). (🏗 relation to (S. A. van de Geer 2008)?)

16 Sparse basis expansions

Wavelets etc; mostly handled under sparse dictionary bases.

17 Sparse neural nets

That is, sparse regressions as the layers in a neural network? Sure thing. (Wisdom et al. 2016)

18 Other coefficient penalties

Put a weird penalty on the coefficients! E.g. “Smoothly Clipped Absolute Deviation” (SCAD). 🏗

19 Other prediction losses

Put a weird penalty on the error! MAD prediction penalty, lasso-coefficient penalty, etc.

See (H. Wang, Li, and Jiang 2007; Portnoy and Koenker 1997) for some implementations using e.g. maximum absolute prediction error.

20 Implementations

Hastie, Friedman et al.’s glmnet for R is fast and well-regarded, and has a MATLAB version. Here’s how to use it for adaptive lasso. Kenneth Tay has implemented elasticnet penalty for any GLM in glmnet.

SPAMS (C++, MATLAB, R, python) by Mairal looks interesting. It’s an optimisation library for many, many sparse problems.

liblinear also includes lasso-type solvers, as well as support-vector regression.

21 References