I would like to know what is the best concentration inequality we can use for the estimated least squares regression coefficients. Let $\hat \beta_0, \hat \beta_1$ be the estimated regression coefficients when we solve the following simple linear regression model with ordinary least squares: $$ Y_i = \beta_0 + \beta_1 X_i + \varepsilon_i, \quad \quad i=1,2,\dots,n, $$ where $E[\varepsilon_i|X] = 0$ and $\text{Var}[\varepsilon_i|X] = \sigma^2$.

Now consider $\hat \beta_1$ for example, Chebyshev's inequality gives us $$ P(|\hat \beta_1 - \beta| > t) \le \frac{\text{Var}(\hat \beta_1)}{t^2}. $$

Is this the only concentration inequality that we can use for $\hat \beta_1$? I was thinking that maybe we can exploit the fact that $\hat \beta_1$ is asymptotically normal, that is, $$ \beta_1 \stackrel{a}{\sim} \mathcal{N}\bigg(\beta_1,\frac{\sigma^2}{n} (X^TX)^{-1}\bigg). $$

Can we use this fact to state a concentration inequality that is tighter than Chebyshev's inequality in the case of a large number of samples?

  • $\begingroup$ Is $\sigma^2$ known or does it also have to be estimated? $\endgroup$ – Thomas Lumley Nov 19 '20 at 22:51
  • $\begingroup$ In practise I would estimate $\sigma^2$ based on the residuals. $\endgroup$ – Bertus101 Nov 20 '20 at 9:42
  • $\begingroup$ Estimating $\sigma^2$ does affect whether bounds hold -- Chebyshev's inequality is not valid with estimated variances, and the Normal bounds for $\hat\beta$ don't hold even if $Y$ is actually Normal (though they get closer to holding as $n$ increases for a fixed $Y$ distribution) $\endgroup$ – Thomas Lumley Nov 21 '20 at 3:53

If $\hat \beta_1$ is approximately normal with mean $\beta_1$, then $Z=|\hat \beta_1-\beta_1|$ is a Half Normal, that has distribution function

$$F_{HN}(z) = 2\Phi(z/\sigma_z) - 1$$

where $\sigma_z$ is the standard deviation of $\hat \beta_1-\beta_1$, and $\Phi$ is the standard Normal distribution function.


$${\rm Pr}(|\hat \beta_1-\beta_1| > t) = 1 - F_{HN}(t) = 2 \Phi\left(-\frac{t}{\sigma_z} \right).$$

This gives you the "exact" probability (given the Normal approximation), which in general should have a value below the Chebychev bound.

Does it?

  • $\begingroup$ Very good, I think that should definitely outperform the Chebychev bound since it decays exponentially with $t$. I will try an computationally confirm it that its an accurate approximation. $\endgroup$ – Bertus101 Nov 20 '20 at 9:49
  • $\begingroup$ In pages 13-19 of these notes, the author states (on page 15) that the approximation error of an asymptotically normal CLT approximation decays too slowly and cannot be ignored. He talks about alternatives such as Hoeffding's inequality and Chernoff's inequality but I am not sure they are applicable to my case or if they are just for Bernoulli random variables (which is what the author is concerned with). $\endgroup$ – Bertus101 Nov 20 '20 at 10:23
  • $\begingroup$ Actually I'm even more unsure Hoeffding or Chernoff inequalities can be used now as while $\hat \beta_1$ can be written as the sum of random variables $\sum_i Z_i$ where $Z_i = \frac{(X_i-\overline X)(Y_i-\overline Y)}{(\sum_j X_j-\overline X)^2}$, these variables appear to be correlated through the sample means $\overline X$ and overline $Y$. So maybe Chebychev is really the only bound we can use which would be disappointing. $\endgroup$ – Bertus101 Nov 20 '20 at 10:32

Depending on values of $X$ and the moments of $Y$ you can use higher moments in the same way as the second moment (if you pretend various moments are known rather than estimated, as you are doing with the variance)

$$\hat\beta = (X^TX)^{-1}\sum_{i=1}^n x_iy_i= n(X^TX)^{-1} \frac{1}{n}\sum_{i=1}^n x_iy_i$$ Using Markov's inequality on the $m$th power of the summands,

$$P(|\frac{1}{n}\sum_{i=1}^n x_iy_i- \frac{1}{n}\sum_{i=1}^n x_iE[y_i]|>t)\leq \frac{\kappa_m}{t^m}$$ where $\kappa_m$ is the $m$th central moment of $\frac{1}{n}\sum_{i=1}^n x_iy_i$, if that moment exists.

And if $\kappa_{\psi_1}=E[\exp( \frac{1}{n}\sum_{i=1}^n x_iy_i )]$ exists, $$P(|\frac{1}{n}\sum_{i=1}^n x_iy_i- \frac{1}{n}\sum_{i=1}^n x_iE[y_i]|>t)\leq \frac{\kappa_{\psi_1}}{e^t}$$

The problem with these, as I hinted above, is that the bounds involve the unknown moments, just as Chebyshev's inequality (the $m=2$ case) does. If you're happy with unknown constants in the bounds, that's fine. The bounds do not, in general, hold when estimates are plugged in for the constants.

For example, take Chebyshev's inequality. To get a bound when $\sigma^2$ is estimated, you need a bound for $\hat\sigma^2-\sigma^2$, and that's the same problem you started with, only harder. If you know a bound on the fourth moments, you can get a good bound on $\hat\sigma^2-\sigma^2$ -- but we've upgraded from second-moment assumptions to fourth-moment assumptions.

For another example, take the Normal bounds. As we all know, even if $Y$ is exactly Normal with constant (but unknown) variance, we end up with $t$-distributions in the bounds rather than Normals, and it gets worse if $Y$ is non-Normal.

The bounds with estimated constants get closer to holding as the sample size increases (for fixed distributions), but they don't (in general) hold for any finite $n$.

  • $\begingroup$ I don't mind having an unknown constant $C$ in the bounds as long as the bounds as long as $C$ is not dependent on both $t$ and $n$ since the dependence with respect to $t$ and $n$ is what I'm most interested in.. Do you know if it is possible to bound $E[\exp(\frac{1}{n}\sum_{i=1}^n x_i y_i)]$ in terms of $n$? Maybe there is some reasonable assumption that allows us to bound it? $\endgroup$ – Bertus101 Dec 1 '20 at 16:16
  • $\begingroup$ Also, how did did you get from the bound that decays as $t^{-m}$ to the bound that decays as $e^{-t}$? I'm not sure what step you took there. $\endgroup$ – Bertus101 Dec 1 '20 at 16:17

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.