lasso, smoothing, and kernels

This is an excerpt from some notes I took for Yale’s S&DS 365 Class (Intermediate Machine Learning)

For low dimensional prediction, we can use least squares. For high dimensional linear regression, there is a bias-variance tradeoff because no closed solution exists: omitting too many variables leads to high bias, and selecting too many leads to high variance. To mitigate this, we need to select a good subset of variables. The lasso is a fast way to select variables.

---

Sparse linear regression

• Ridge regression doesn’t take advantage of sparsity. Maybe only a small number of covariates are good predictors. How do we find them?
• Lasso:

$$\begin{array}{rl}\hat{\beta }& =\mathrm{argmin}\left(\frac{1}{2n}\sum _{i=1}^n{\left(Y_i-{\beta }^{\top }{X}_i\right)}^2+\lambda \Vert \beta {\Vert }_1\right)\end{array}$$

• L1 measures sparsity and keeps the optimization convex.

Definition. For a particular $\lambda$, we call $\hat{\beta }(\lambda )$ the lasso estimator.

The selected set of variables are $j$ where ${\hat{\beta }}_j$ nonzero

How can we select $\lambda$?

In general, we can approximate risk by approx. leave-one-out cross-validation and select lambda that minimizes risk.

LASSO

1. Find $\hat{\beta }(\lambda )$ and $\hat{S}(\lambda )$ for each $\lambda$.
2. Compute $\hat{R}(\lambda )$ for each $\lambda$ using LOOCV.
3. Choose $\hat{\lambda }$ to minimize estimated risk
4. Let $\hat{S}(\hat{\lambda })$
5. Linear regression on chosen variables

Algorithm for the LASSO: derived in steps

• One dimension, one data point

$$\begin{array}{rl}f(\beta )& =\frac{1}{2}(y-\beta {)}^2+\lambda |\beta |\end{array}$$

However, we can’t differentiate the norm at $0$. We have to use a sub-differential, sub-gradient hyperplanes that don’t intersect? So sub-differential of the absolute value is anything $\in [-1,1]$ slope. So we write the derivative

$$\begin{array}{rl}\beta -y+\lambda v& =0\end{array}$$

If $\beta >0⟹v=1,\beta <0⟹v=-1,\beta =0⟹v=[-1,1]$

$$\begin{array}{rl}\beta & =y-\lambda v\end{array}$$

If $|y|\ge \lambda$, then $v=\mathrm{sgn}y$. If $y\le \lambda$, then $v=\frac{y}{\lambda }$ so $\beta =1$.

$$\begin{array}{rl}\hat{\beta }& ={\mathrm{soft}}_{\lambda }(y)=\mathrm{sgn}(y)\cdot \max (|y|-\lambda ,0)\end{array}$$

• Now, with $x\ne 1$, the derivative becomes

$$\begin{array}{rl}-yx+\beta x^2+\lambda v& =0\\ -\frac{y}{x}+\beta +\frac{\lambda }{x^2}v& =0\end{array}$$

This is identical to earlier, but substituting in $y=y/x$ and $\lambda =\lambda /x^2$, so we get

$$\begin{array}{rl}\hat{\beta }& ={\mathrm{soft}}_{\lambda /x^2}(y/x)=\mathrm{sgn}\left(\frac{y}{x}\right)\cdot \max \left(\left|\frac{y}{x}\right|-\frac{\lambda }{x^2},0\right)\end{array}$$

• Now, with many data points

$$\begin{array}{rl}f(\beta )& =\frac{1}{2}\frac{1}{n}\sum _{i=1}^n{\left(y_i-\beta x_i\right)}^2+\lambda |\beta |\end{array}$$

The derivative is

$$\begin{array}{rl}f(\beta )& =\frac{1}{n}\sum _{i=1}^n\left(\beta x_i^2-y_i{x}_i\right)+\lambda v=0\\ f(\beta )& =-\frac{1}{n}\sum _{i=1}^n{y}_i{x}_i+\frac{1}{n}\sum _{i=1}^n\left(\beta x_i^2\right)+\lambda v=0\end{array}$$

We get

$$\begin{array}{rl}\hat{\beta }& ={\mathrm{soft}}_{\lambda /\frac{1}{n}{\sum }_i{x}_i^2}\left(\frac{{\sum }_i{y}_i{x}_i}{{\sum }_i{x}_i^2}\right)\end{array}$$

• When we have $p$ variables there is no closed-form solution, so we use coordinate descent. We start by choosing one variable, and freeze all the rest and take the closed form solution. Then we move on and iterate until convergence.
• Then, use least squares on the selected subset.

---

Nonparametric Regression

Assume only that $Y_i=m(X_i)+ϵ$, where $m(x)$ is a smooth function of $x$.

The most popular methods are kernel methods

1. Smoothing kernels
2. Penalization (Mercer) kernels

Smoothing kernels implements a sort of averaging among data points.