How is L1 regularization derived?

Question

I understand the basic idea of regularization. I am very curious to know the derivations behind it so that I get the complete picture.

I though a good place to start learning about regularization is Linear regression. So I was going though this paper and I got stuck in between. I didn't understand how equation 4 was derived from 3 and 2.

I understand from Gradient Descent method that, you first calculate the first derivative of the loss function and try to go down the path of decreasing gradient and stop when you have found the minimum. But here I don't understand why is derivative of a loss function is divided by itself?

Can some one please help me with this?

1. derivative of (3) should be $2X^T(Xw-y)$
2. dividing it by (2) should be $2X^T(Xw-y) / \sum\limits_{i=1}^n(y_i-w_0 - \sum\limits_{j=1}^p x_{ij}w_j)^2$

firs of all I don't understand why is it done? what is the purpose of this step and also I don't see how that is simplified to (4).

Answer 1

Equation (3) from the paper states:

$$RSS = \|Xw - y\|_2^2$$

This is the "residual sum of squared errors" that we want to minimize. Differentiating $RSS$ with respect to the parameter vector $w$ (sometimes called the "weights") gives:

$$u = 2X^T (Xw - y)$$

Note that $u$ is a vector where the $i^{th}$ element is the partial derivative of $RSS$ with respect to $w_i$. We differentiate with respect to $w$ because basic calculus tells us that the minimum will be obtained when the derivatives are all $0$. Thus, setting $u = 0$ allows us to solve for the $w$ which minimizes the squared error.

Now your question mistakes "dividing by $2$" from the paper with "dividing by (2)". There is a big difference, because $2$ is a number while (2) is an equation. If we divide $u$ by $2$, then we get (4):

$$X^T (Xw - y)$$

We divide by $2$ simply because this makes the derivation slightly cleaner without changing the results (because $0 / 2 = 0$).