0
$\begingroup$

Let us consider the following lasso estimator: $$ \hat{\beta}_{L} = \arg\min \, \frac{1}{n}\sum_{i}^{n}||y_{i} - \textbf{x}_{i}\beta||_{2}^{2} + \frac{\lambda_{n}}{n}\sum_{j=1}^{p}|\beta_{j}| $$ For any $\lambda_{n}$ the problem above is equivalent to $$ \hat{\beta}_{L} = \arg\min \, \frac{1}{n}\sum_{i}^{n}||y_{i} - \textbf{x}_{i}\beta||_{2}^{2}, $$ subject to $$ \sum_{j=1}^{p}|\beta_{j}| \leq t_{n} $$ for some $t_{n}$.

Next, assume that the sequence $\{\lambda_{n}\}$ is $o(n)$. What is about $\{t_{n}\}$?

Edit: For the start, we can assume for simplicity, that $\textbf{X} = \textbf{I}$.

$\endgroup$
4
  • $\begingroup$ you mean, "What is the assumption about {t_n}? $\endgroup$ Mar 2, 2020 at 14:42
  • $\begingroup$ I mean what would be the sequence $\{t_{n}\}$ (the rate of it) corresponding to $\{\lambda_{n}\}$ $\endgroup$
    – ABK
    Mar 2, 2020 at 15:04
  • 1
    $\begingroup$ IIRC, the equivalence depends on the data, so you may need some assumptions about $\mathbf{x}, y$? $\endgroup$ Jan 7, 2021 at 17:06
  • $\begingroup$ Dear @BenReiniger, I have updated the question. Thank you. $\endgroup$
    – ABK
    Jan 8, 2021 at 10:13

1 Answer 1

1
+50
$\begingroup$

The SSE of the LASSO solution $\tilde\beta$ in comparison to the SSE of the OLS solution $\hat{\beta}$ can be expressed as

$$(X (\tilde\beta-\hat{\beta})) \cdot (X (\tilde\beta-\hat{\beta})) = (\tilde\beta-\hat{\beta}) X^TX (\tilde\beta-\hat{\beta}) $$

You can see this graphically as some ellipsoid surface (as the image below which I copied from this question).

  • Limit behaviour of $ \frac{1}{n}\sum_{i}^{n}||y_{i} - \textbf{x}_{i}\tilde\beta||_{2}^{2} $

    This ellipsoid will depend on the particular sample (based on which $\hat\beta$ and $X^TX$ will vary) but for $n \to \infty$ you will get that the variation in this surface becomes smaller.

  • Limit behaviour of $ \frac{\lambda_{n}}{n}\sum_{j=1}^{p}|\tilde\beta_{j}|$

    If $\{\lambda_{n}\}$ is $o(n)$ then $\lbrace\frac{\lambda_{n}}{n}\rbrace$ is $o(1)$ and approaches zero.

So the first term in the cost function will approach some quadratic function of $\tilde\beta$ and the second term will approach zero. The lasso solution that minimises the sum of these terms will approach the true $\beta$ (The reasoning here is very intuitive but I am sure there is some reference for that).

The consequence is that $\{t_n\} - \sum_{j=1}^{p}|\beta_{j}| $ will approach zero (where $\beta_j$ refers to the true coefficients).

intuitive view of lasso path

$\endgroup$
4
  • $\begingroup$ Dear @Sextus Empiricus, I didn't understand the conclusion about $t_{n}$. Could you, please, clarify it? $\endgroup$
    – ABK
    Jan 12, 2021 at 13:31
  • $\begingroup$ @ABK I had a misunderstanding about your meaning of $\{\lambda_n\} \in o(n)$ and thought of $\lambda_n/n$ approaching a constant instead of zero. I have edited the answer now. $\endgroup$ Jan 12, 2021 at 14:27
  • $\begingroup$ ok, again it is a bit confusing. If I understood correctly, the conclusion is that both $\{ \frac{\lambda_{n}}{n}\}$ and $\{t_{n} \}$ have the same rate of convergence $\endgroup$
    – ABK
    Jan 12, 2021 at 15:49
  • $\begingroup$ @ABK I am not sure about the rate of convergence of $t_n$, but if $n \to \infty$ and $\frac{\lambda_n}{n} \to 0$ then $t_n \to \sum_{j=1}^{p}|\beta_{j}|$. $\endgroup$ Jan 12, 2021 at 16:21

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.