# Comparing bound between lasso and OLS

Assume fixed design regression model $Y = \mathbf{X} \beta + \epsilon$ with common assumptions. Lasso estimator $\hat{\beta}_\lambda$ can be shown to have the following bound.

For any $\delta > 0$, define $\lambda_0 = \sigma\sqrt{\frac{\log\left(p/\delta\right)}{n}}$. Let $A_0 \ge 1$. With With probability at least $1-2\delta$,$$\frac{1}{2n}\left\| \mathbf{X}\hat{\beta}_\lambda - \mathbf{X}\beta^*\right\|_2^2 \le 2A_0 \lambda_0 \left\| \beta^*\right\|_1$$ holds.

What would be a similar bound for $\frac{1}{2n}\left\|\mathbf{X} \hat{\beta}_\text{OLS} - \mathbf{X} \beta^*\right\|_2^2$? An easy application of Markov inequality yiels $$\mathbb{P}\left\{ \left\|\mathbf{X}\hat{\beta}_\text{OLS} -\mathbf{X}\beta^*\right\|_2^2 \le \frac{\sigma^2 p}{2\delta}\right\} \ge 1-2\delta$$

However I doubt that this is the best thing we can get.

Alternatively, I think it's also true that $$\frac{1}{2n} \left\|\mathbf{X}\beta^* - \mathbf{X} \hat{\beta}_\text{OLS}\right\|_2^2 \le \lambda_0 \left\|\hat{\beta}_\text{OLS} - \beta^*\right\|_1$$

with high probability. But I don't know how to control $\left\|\hat{\beta}_\text{OLS} - \beta^*\right\|_1$.

My ultimate goal is to show/disprove that in situation where $n > p$ but still many true coefficients are zero or small, lasso will be "better" than OLS. Any suggestion would be appreciated. Thank you.

• What is $p$? What is $A_0$? Where does the $\lambda$ associated with $\hat{\beta}_{\lambda}$ come into play? As it is, one could simply observe that $\hat{\beta}_{\text{OLS}} = \hat{\beta}_0$, and there's no apparent reason why the bound wouldn't be exactly the same. – jbowman Mar 30 '18 at 17:25
• $p$ is the dimension of the true parameter $\beta*$. $A_0$ is some real number s.t. $A_0 \ge 1$. $\lambda$ obviously is the tuning parameter and $\lambda_0 = \sigma \sqrt{2\log (p/\delta) / n}$ – 3x89g2 Mar 30 '18 at 17:27
• Since $\lambda$ appears nowhere in the expression for the bound, one assumes it holds for all $\lambda$, including $\lambda = 0$, which corresponds to the OLS estimator... so the bound you have already works for the OLS estimator, which clearly satisfies the requirement of a "similar bound"! – jbowman Mar 30 '18 at 17:30
• @jbowman Not sure if I understand you... There is no $\lambda$ in $\frac{\sigma^2 p}{2\delta}$...? – 3x89g2 Mar 30 '18 at 17:34
• Do you see a $\lambda$ there? I don't. I see a $p$, a $\delta$, a $\sigma$, and a $2$. This relates back to my initial comment, repeated in my second one: where does $\lambda$ come into play? – jbowman Mar 30 '18 at 17:52