0
$\begingroup$

Given the objective function $$\text{argmin}_{c}(\Vert y - Xc \Vert_2^2 + \lambda\Vert c \Vert_1)$$

by taking the derivate $$\frac{\partial}{\partial c}(\Vert y - Xc \Vert_2^2 + \lambda\Vert c \Vert_1)$$

it can be proved, $\lambda_{\min} = \max|\sum_{j}y^TX_j|$ is the smallest $\lambda$ that makes the solution to the objective a zero vector.

However, when I did it in practice, I found this $\lambda_{\min}$ is not the smallest, here is my code:

x_1 = np.linspace(-1, 1, 30)
x_2 = 2 * x_1 + 0.01 * np.random.rand(30)
x_3 = np.random.uniform(-1, 1, 30)
y = 0.1 * x_1 + 0.5 * x_2 

l1 = abs(np.inner(x_1, y))
l2 = abs(np.inner(x_2, y)) 
l3 = abs(np.inner(x_3, y))
lambda_min = max(l1, l2, l3)

x = np.ones((30, 3))
x[:, 0], x[:, 1], x[:, 2] = x_1, x_2, x_3
lambda_n = lambda_min

while True:
    lambda_n = lambda_n * 0.95
    lasso_test = Lasso(alpha=lambda_n, fit_intercept=False)
    lasso_test.fit(x, y)
    temp = lasso_test.coef_
    if np.sum(temp) != 0:
        print('lambda_n = ', lambda_n)
        break
print('lambda_min = ', lambda_min)

lambda_min is far greater than lambda_n which is the smallest lambda that makes lasso_test.coef_ a zero vector.

It is only when I change

lambda_min = max(l1, l2, l3) / 30 # number of examples

will lambda_min and lambda_n be the same.

Given this, the formula for calculating $\lambda_{\min}$ should be $$\frac{1}{N}\max|\sum_{j}y^TX_j|$$

I believe there is nothing wrong with the theory, then what is wrong with my code?

$\endgroup$
  • 1
    $\begingroup$ nothing wrong with your code. the objective function sklearn-kit lasso does minimize is not $\frac{1}{2}||y-Xc||_2^2$ but $\frac{1}{2n}||y-Xc||_2^2$, hence $\lambda_{min}= \frac{1}{n} \max_j|X_j^Ty|$. $\endgroup$ – chRrr Sep 11 '18 at 11:30
  • $\begingroup$ @ Thank you! I just overlooked the objective function in the documentation... $\endgroup$ – meTchaikovsky Sep 11 '18 at 11:32
5
$\begingroup$

Turning my comment into an answer:

There is nothing wrong with your code. The additional $\frac{1}{n}$-factor of $\lambda_{min}$, you observed in python using the sklearn Lasso function, is an immediate consequence of the objective function used in the python.

The Lasso-function from the sklearn-kit in python minimizes $$\frac{1}{2n}||y−Xc||_2^2 + \lambda||c||_1$$ instead of $$\frac{1}{2}||y−Xc||_2^2 + \lambda||c||_1.$$

As a consequence the smallest value of $\lambda$ at which the Lasso will result in all $0$-coeffcients is given by $$λ_{min}=\frac{1}{n}\max_j|X_j^Ty|.$$

(Note: Arguments leading to the value of $\lambda_{min}$ can for example be found here: Lasso and Ridge tuning parameter scope)

$\endgroup$
  • 1
    $\begingroup$ In many practical scenarios, this value of $\lambda$ does give you the optimal value. So, one standard practice that I have come across is the `three-sigma rule', where you compute the standard deviation of $\frac{1}{n} X^T(y - Xc)$ and set $\lambda = 3 \mathrm{std}(\frac{1}{n} X^T(y - Xc))$. $\endgroup$ – Maxtron Sep 11 '18 at 15:38
  • $\begingroup$ @Thank you for sharing this! I will try this in my code! $\endgroup$ – meTchaikovsky Sep 11 '18 at 23:52

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.