Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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 at 12:41

1 Answer 1

Have you tried using the shooting algorithm for optimizing the lasso regularized loss instead of gradient descent?

It involves using a coordinate wise search for the minimizer. This link has some details and also a link to their code.

Hope this helps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.