Lasso Regularization (L1 Regularization) › Math and Optimality Conditions

Let's look at how LASSO finds the optimal coefficients, starting with the optimization process. LASSO solves the following optimization problem, here defined in summation form:

$$\min_{\beta_0, \beta_1, \ldots, \beta_p} \left\{ \sum_{i=1}^n \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right)^2 + \lambda \sum_{j=1}^p |\beta_j| \right\}$$

To find the minimum, we set the partial derivatives (where they exist) to zero. The absolute value term $|\beta_j|$ is not differentiable at $\beta_j = 0$, so we use subgradients there. We'll use the chain rule for the differentiable part. The main reason why there is no closed-form solution for LASSO is because the absolute value term is not differentiable at $\beta_j = 0$.

For $\beta_j > 0$: The partial derivative with respect to $\beta_j$ is:

$$\frac{\partial}{\partial \beta_j} \left[ \sum_{i=1}^n \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right)^2 + \lambda \sum_{j=1}^p |\beta_j| \right] = 0$$

Step 1: Differentiate the SSE term

The first term $\sum_{i=1}^n \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right)^2$ is the SSE. When we take the partial derivative with respect to $\beta_j$, we use the chain rule:

$$\frac{\partial}{\partial \beta_j} \left[ \sum_{i=1}^n \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right)^2 \right] = \sum_{i=1}^n 2 \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right) \cdot \frac{\partial}{\partial \beta_j} \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right)$$

Step 2: Differentiate the inner expression

The derivative of the inner expression with respect to $\beta_j$ is:

$$\frac{\partial}{\partial \beta_j} \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right) = -x_{ij}$$

This is because:

• $y_i$ and $\beta_0$ are constants with respect to $\beta_j$ (derivative = 0)
• $\sum_{j=1}^p \beta_j x_{ij}$ becomes $x_{ij}$ when differentiated with respect to $\beta_j$ (all other terms become 0)

Step 3: Differentiate the penalty term

Let's solve for the partial derivative step by step when $\beta_j > 0$. Start with what we need to differentiate:

$$\frac{\partial}{\partial \beta_j} \left[ \lambda \sum_{j=1}^p |\beta_j| \right]$$

Apply the constant multiple rule

Since $\lambda$ is a constant, we can pull it out:

$$= \lambda \cdot \frac{\partial}{\partial \beta_j} \left[ \sum_{j=1}^p |\beta_j| \right]$$

Focus on the relevant term. When taking the derivative with respect to $\beta_j$, only the $j$-th term in the sum matters:

$$= \lambda \cdot \frac{\partial}{\partial \beta_j} [|\beta_j|]$$

Handle the absolute value. When $\beta_j > 0$, we have $|\beta_j| = \beta_j$ (the absolute value doesn't change positive numbers):

$$= \lambda \cdot \frac{\partial}{\partial \beta_j} [\beta_j]$$

Take the derivative

The derivative of $\beta_j$ with respect to itself is 1:

$$= \lambda \cdot 1 = \lambda$$

Final result for $\beta_j > 0$:

$$\frac{\partial}{\partial \beta_j} \left[ \lambda \sum_{j=1}^p |\beta_j| \right] = \lambda$$

For $\beta_j < 0$: The partial derivative becomes:

$$-2 \sum_{i=1}^n x_{ij} \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right) - \lambda = 0$$

We have $|\beta_j| = -\beta_j$ when $\beta_j < 0$, so:

$$\frac{\partial}{\partial \beta_j} \left[ \lambda \sum_{j=1}^p |\beta_j| \right] = \lambda \cdot \frac{\partial}{\partial \beta_j} [-\beta_j] = -\lambda$$

This gives us the negative sign in front of $\lambda$ in the final equation.

Step 4: Combine the results

Putting it all together:

$$\sum_{i=1}^n 2 \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right) \cdot (-x_{ij}) + \lambda = 0$$

Step 5: Simplify

$$-2 \sum_{i=1}^n x_{ij} \left( y_i - \beta_0 - \sum_{j=1}^p \beta_j x_{ij} \right) + \lambda = 0$$

To understand why LASSO sets coefficients exactly to zero while Ridge regression does not, we can visualize the geometry of the optimization problem. The following plot shows how the constraint regions differ between L1 (LASSO) and L2 (Ridge) regularization.