# How is L1 regularization derived?

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?

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).

• Please don't get me wrong, but getting from (2) to (3) in the paper you linked is a very basic step in matrix algebra or OLS, so if you have problems with this, you have problems with fundamental statistics. Giving an answer that starts out at this fundamental level and gets to regularization is not a good fit to SE. I'd recommend that you look at some elementary statistics textbooks or MOOCs so you understand the matrix algebra better, then continue to regularization (this textbook is good for the lasso)... – S. Kolassa - Reinstate Monica May 4 '16 at 11:48
• ... If you have specific questions about the material - like how to get from (2) to (3) in that paper - please don't hesitate to ask them here. We can and will answer well-asked specific questions, whether fundamental or advanced. – S. Kolassa - Reinstate Monica May 4 '16 at 11:49
• edited the question @StephanKolassa – user98374 May 5 '16 at 9:59
• Thanks, it's much better now. I have upvoted the question and nominated it for reopening. If it is reopened, I'll try to take a stab at it. – S. Kolassa - Reinstate Monica May 5 '16 at 10:44
• I've re-opened the question to expedite an answer, but note that it also needs to be edited so that it makes sense without reference to an external link. – Scortchi - Reinstate Monica May 5 '16 at 10:57

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$).

• My bad. I thought it was equation (2). It should have occurred to me, but it didn't. thanks for clearing this up. – user98374 May 6 '16 at 5:36