3
$\begingroup$

I am trying to understand how the graphical solution path to the optimum would look in the case of Lasso Regression. I can find only Pictures for the differentiable or non differentiable case. The picture below is the solution path for a convex and differentiable function.

How would the solution path look for the lasso case? Would there be a way to produce such a graph including the solution path in R?

enter image description here

The contours would look like this:

enter image description here

$\endgroup$
7
$\begingroup$

Context and background

Recall that the Lasso minimization problem can be expressed as:

$$ \hat \theta_{lasso} = argmin_{\theta \in \mathbb{R}^n} \sum_{i=1}^m (y_i - \mathbf{x_i}^T \theta)^2 + \lambda \sum_{j=1}^n | \theta_j| \ $$

Which can be viewed as the minimization of two terms: $OLS + L_1$.

  • The first OLS term can be written as $(y - X \theta)^T(y - X \theta) $ which gives rise to an elipse contour plot centered around the Maximum Likelihood Estimator.
  • The second $L_1$ term is the equation of a diamond centered around 0 (or a romboid in higher dimensions)
  • The solution to the constrained optimization lies at the intersection between the contours of the two functions, and this intersection varies as a function of $\lambda$. For $\lambda = 0$ the solution is the MLE (as usual) and for $\lambda = \infty$ the solution is at $[0,0]$.
  • Since at the vertices of the diamond, one or many of the variables have value 0, there is a probability that one or many of the features will have a value exactly equal to 0.
  • In fact, I have read on this website that in higher dimensions, the probability of the intersection taking place at the vertices increases, but I will leave it to someone else to explain this intuition.

Vsualizing the solution as a function of $\lambda$

Intuitively, as we increase $\lambda$ from 0 to $\infty$ we would expect the lasso solution to move from the OLS solution to the $L_1$ solution, which is $0$. You will find below the result of a simulation I have run for Ridge and Lasso regression on simulated data.

enter image description here

Some comments on this simulation

The data is simulated from a sine curve with uniform noise added. The data is normalized, to facilitate the lasso coordinate descent, and centered, to remove the need for an intercept coefficient. I have added a polynomial term as the second feature:

$$ y = \theta_1 x + \theta_2 x^2$$

This means that due to the polynomial feature, the $x_1$ and $x_2$ features are highly correlated, in fact a quick check gives the following:

  • Condition number of matrix $X$: $= 7.87$
  • Covariance matrix $X.T @ X = \begin{bmatrix}1. & 0.968 \\ 0.968 & 1. \end{bmatrix}$

This will translate into a "flattened" OLS solution in the shape of a valley.

As you see, the coefficient path moves towards the $(0,0)$ point until hitting a vertex, at which point, one of the two coefficient is equal to zero. This can be seen by using a lasso path diagram

enter image description here

Visualizing the coordinate descent algorithm steps

Coordinate descent minimizes along coordinate directions. At each iteration, the algorithm determines a coordinate, then minimizes over the corresponding hyperplane while fixing all other coordinates.

Here are two versions of coordinate descent on the same dataset as previously, the first for a low value of $\lambda$, the second for a high value of $\lambda$

enter image description here

enter image description here

Source

For anyone interested, you can find most of the code and associated mathematical derivations on my blog and at this page

$\endgroup$
4
  • $\begingroup$ What a great comment ! Just two notes. 1) Could you share exactly this Code here, since I am not familiar with python. Just want to play a bit with the lambda to produce various graphs 2) In your simulation case: The contour lines should be circles, since the two predictors are uncorrelated or am I wrong ? $\endgroup$
    – rook1996
    Jun 16 '18 at 19:17
  • 1
    $\begingroup$ You will find the link here - you were right the two features are highly correlated - I have edited the post $\endgroup$ Jun 18 '18 at 7:30
  • $\begingroup$ @XavierBourretSicotte I've one small question regarding to the picture. In left graph ist the axis error equal to the value of the Lasso-Regression for a given theta1,theta2 and lambda? $\endgroup$
    – Leo96
    Jul 1 '18 at 19:55
  • $\begingroup$ Yes well spotted for the 3d graph the z axis (pointing up) is the value of the cost function - which i labeled errror but you are right $\endgroup$ Jul 2 '18 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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