# $l_\infty$ error of linear regression

Consider the fixed design multidimensional linear regression: $$Y = X \beta^* + \epsilon$$, where $$\beta^* \in \mathbb {R}^d$$, $$X \in \mathbb {R}^{n\times d}$$, and $$\epsilon \sim \mathcal{N}(0, \sigma I)$$. For example if we use the regular least squares estimator, under what conditions can we get an $$O(1/n)$$ bound on $$\left\|\hat{\beta} - \beta^*\right\|_\infty^2$$?

• None. But if you can accept a probabilistic guarantee, one is straightforward to calculate from the Normal distribution of $\hat\beta-\hat\beta^{*}.$ So: what kind of answer are you looking for?
– whuber
Jan 21, 2022 at 17:57
• I just realized your notation is ambiguous: would $\left\|\hat{\beta} - \beta^*\right\|_\infty^2 = \left(\hat\beta-\beta^{*}\right)^2$ (a random variable) or would it equal the square of $E\left[\big|\hat\beta-\beta^{*}\big|\right]$ (a number)?
– whuber
Jan 22, 2022 at 15:36

### Simple example when it is bounded

A simple example would be when we consider the estimate of a mean. In that case, the distribution of the estimate follows

$$\hat{\beta_n}-\beta^\star \sim N(0,\sigma/\sqrt{n})$$

and the cost function

$$\frac{n}{{\sigma}^2} \left\|\hat{\beta}_n - \beta^*\right\|_\infty^2 = \frac{n}{{\sigma}^2} (\hat{\beta}_n-\beta^\star)^2 \sim \chi^2(1)$$

This does indicate that $$\left\|\hat{\beta}_n - \beta^*\right\|_\infty^2$$ is bounded by $$1/n$$.

The requirement is namely that for any positive probability $$p$$ there is a finite boundary $$M$$ and a positive $$N$$ such that for any $$n>N$$ $$P(n \left\|\hat{\beta}_n - \beta^*\right\|_\infty^2 < M) < p$$

Since $$n \left\|\hat{\beta}_n - \beta^*\right\|_\infty^2$$ is a fixed distribution (it is independent of $$n$$), namely a scaled chi-squared distribution (a gamma distribution), you can get this condition by setting $$M$$ equal to the CDF of the chi-qured distribution.

### Counter example

A counter example would be when we consider the estimate of a line where the points $$X$$ are either $$x_i=0$$ or $$x_i=1$$. But we have only one point with $$x_i = 1$$ and all the other $$n-1$$ points have $$x_i = 0$$.

In this case, the intercept can be estimated very accurately.

But, the estimate of the slope will approach the distribution $$N(0,\sigma)$$ and will not improve much with increasing $$n$$.

So $$\left\|\hat{\beta}_n - \beta^*\right\|_\infty^2 = \max(\hat{\beta}_n - \beta^*)^2$$ will not improve beyond some point and you will not have the $$O(1/n)$$ bound.

### In between the two examples

Eventually, you will need to get that the entries in the matrix $$(X^tX)^{-1}$$, which determines the variance of the $$\hat{\beta} - \beta^*$$, are all scaling with a factor $$1/n$$.

In the previous two examples, the scaling is easy to determine and in the first case, it is clear that the variance scales with $$1/n$$ while in the second case it is not. We can imagine all kinds of variants of the above situations, but the interesting case would be when it is not so clear. For instance what if the $$X$$ is random?

Example of difficult case: Say we have $$X = -1$$ or $$X = 1$$ with equal probability and we model a quadratic function $$Y = a + bX + \epsilon$$ where $$\beta_0 = \beta_1 = 0$$. Is the norm $$\left\|\hat{\beta}_n - \beta^*\right\|_\infty^2$$ still stochastically bounded by $$1/n$$? The simulation below shows that the scaled cost is not so much influenced by $$n$$ but will this held for $$n\to \infty$$?

Intuitively you can imagine that the estimate of the coefficients will improve by a factor that is close to $$n$$ and the variability in this factor will decrease as $$n$$ decreases.

layout(matrix(1:3,3))

### compute cost of error in estimate from linear model
sim = function(n) {
### generate data
X = rbinom(n,1,0.5)-0.5
Y = rnorm(n)

### model
mod = lm(Y~X)

### return cost function
return(max(mod$coefficients^2)) } set.seed(1) for (n in c(20,200,2000)){ ### perform simulations to estimate distribution x = replicate(10^4,sim(n)) ### plot histogram of simulations br = seq(0,ceiling(max(n*x+2)),2) hist(n*x, breaks = br,xlim=c(0,100), freq = 0, ylim = c(0,0.2), main = paste0("n = ", n)) }  • Could you clarify the sense in which you mean "bounded by$1/n$"? After all, your initial expression for$\left\|\hat{\beta} - \beta^*\right\|_\infty^2$is an unbounded random variable. – whuber Jan 22, 2022 at 15:38 • @whuber I have added subscripts to clarify that I mean$\left\|\hat{\beta}_n - \beta^*\right\|_\infty^2$and not$\left\|\hat{\beta} - \beta^*\right\|_\infty^2$. The former can be bounded in the sense of$O(1/n)\$, as I demonstrate in the first section. Jan 22, 2022 at 15:53