# Minimizing L1 Regularization

I have given a high dimensional input $x \in \mathbb{R}^m$ where $m$ is a big number. Linear regression can be applied, but in generel it is expected, that a lot of these dimensions are actually irrelevant.

I ought to find a method to model the function $y = f(x)$ and at the same time uncover which dimensions contribute to the output. The overall hint is to apply the L1-norm Lasso regularization.

$$L^{\text lasso}(\beta) = \sum_{i=1}^n (y_i - \phi(x_i)^T \beta)^2 + \lambda \sum_{j = 1}^k | \beta_j |$$

Minimizing $L^{\text lasso}$ is in general hard, for that reason I should apply gradient descent. My approach so far is the following:

In order to minimize the term, I chose to compute the gradient and set it $0$, i.e.

$$\frac{\partial}{\partial \beta} L^{\text lasso}(\beta) = -2 \sum_{i = 1}^n \phi(x_i)(y_i - \beta)$$

Since this cannot be computed simply, I want to apply the gradient descent here. The gradient descent takes a function $f(x)$ as input, so in place of that will be put the $L(\beta)$ function.

My problems are:

• is the gradient I computed correct? I left out the regularizationt erm in the end, which I guess is a problem, but I also have problems to compute the gradient for this one

In addition I may replace $| \beta_j |$ by the function $l(x)$, which is $l(x) = x - \varepsilon/2$ if $|x| \geq \epsilon$, else $x^2/(2 \varepsilon)$

• one step in the gradient descent is: $\beta \leftarrow \beta - \alpha \cdot \frac{g}{|g|}$, where $g = \frac{\partial}{\partial \beta}f(x))^T$

I don't get this one, when I transpose the gradient I have computed the term cannot be resolved due to dimension mismatch

-
1. Yes, your gradient should be over the regularization term as well. But, I guess you have already realized that the regularization term is not differentiable. So how does one go about it? Subgradient descent is a reasonably good choice. You will see a lot of discussion on this here. 2. I don't understand your second problem. – TenaliRaman May 4 '12 at 20:13
Boyd and Parikh have recently published a monograph about proximal methods that explains techniques for solving non-differentiable convex optimization problems like this. For example, instead of using gradient descent one could use the proximal gradient method, which can handle the non-differentiable term. – littleO Nov 30 '13 at 0:02
I agree with littleO. Since $L^{\mathrm{lasso}}(\beta)$ is not differentiable, you should have a look at proximal gradient methods. Have also a look at this paper : bodonoghue.org/publications/adap_restart.pdf (especially at the "sparse regression" part). – jibounet Jan 30 '14 at 12:41
If doing gradient descent, yes you have to do all terms. The partial derivatives of $L_1$ term should not be too difficult to calculate. One other possible way would be with iteratively reweighted least squares. – mathreadler Oct 5 '15 at 6:14
Yes you can use Huber to get a smooth approximation of L_1: en.wikipedia.org/wiki/Huber_loss – mathreadler Oct 5 '15 at 6:39