$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$?
 A: 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))
}

