# High-probability lower bound for norm of least squares solution when both design matrix $X$ and response vector $y$ are random (and independent)

Let $$n,d \to \infty$$ with $$n/d \to \gamma \in (0,\infty)$$. Let $$X$$ be a random $$n \times d$$ matrix independent rows uniformly distributed on the the unit-sphere in $$\mathbb R^d$$ and let $$y$$ be a random vector in $$\mathbb R^n$$ independent of $$X$$, with iid entries uniformly distributed on $$\{\pm 1\}$$. If it helps, I'm fine with instead assuming that $$y_1,\ldots,y_n \sim N(0,1)$$.

Now, for $$\lambda \ge 0$$ let $$Q_\lambda(\omega) := (\omega + \lambda I_n)^{-1}$$ and set $$\beta_\lambda := X^\top Q_\lambda(XX^\top) y \in \mathbb R^d$$, the unique solution to the (random) ridge-regression problem

$$\arg\min_{\beta \in \mathbb R^d}\frac{1}{2}\|y-X\beta\|^2 + \lambda \|\beta\|^2.$$

Question. What is a good asymptotic lower-bound for $$\|\beta_\lambda\|^2$$ (valid with high probability or almost-surely) ?

N.B.: I'm particularly interested in the "ridgeless" limit $$\lambda \to 0^+$$.

## Attempt 1

Note that $$\beta_\lambda$$ has centered multivariate distribytion with covariance matrix $$R_\lambda(XX^T)$$, where $$R_\lambda(\omega) := Q_\lambda(\omega)\omega Q_\lambda(\omega),$$ and so one may write $$\dfrac{\|\beta_\lambda\|^2}{d} \to \dfrac{1}{d}\mbox{Tr}(R_\lambda(XX^\top)) = \mbox{tr}_d(R_\lambda(XX^\top)),$$ where $$\mbox{tr} = (1/d)\mbox{Tr}$$ is a normalized trace operator. Since $$XX^\top$$ is a "free random variable" (in the sense of free probability), and $$R_\lambda(XX^\top)$$ is a rational expression in $$\omega=XX^\top$$, one would expect $$\|\beta_\lambda\|^2$$ to have a complete analytic description via free probability.

• Assuming you are mostly interested in $d>n$, if X has iid N(0,1) entries (or N(0,1/d)), you can have exact formula for $\hat\beta=X^T(XX^T)^{-1}y$ in expectation using the formula for the expectation of an inverse Wishart matrix given in en.wikipedia.org/wiki/Inverse-Wishart_distribution ; I don't think rows uniformly distributed on the sphere should be much different but such nice exact formulae in expectation may not be available. Dec 5, 2021 at 1:18
• E.g., using first $E[y^TMy]=trace[M]$ we have $E[\|\hat\beta\|^2]=trace[(XX^T)^{-1}]=\frac{n}{d-n-1}$ if X has iid entries and $\hat\beta=X^T(XX^T)^{-1}y$. This conclusion as yours if $n/d\to\gamma$. Your argument with the MP law sounds fine by the way. Dec 5, 2021 at 1:23

## A heuristic argument

Disclaimer: I'm not 100% sure of what I'm written. I'd be grateful if an expert could kindly take a close look.

Using the computations done here For fixed $\lambda \ge 0$, Integrate the function $f_\lambda(x):=x/(x + \lambda)^2$ w.r.t. Marchenko-Pastur density, one may proceed as follows. By [Remark 3.4, Pajor and Pastur(2007)], the empirical eigenvalue distribution of $$XX^\top$$ converges weakely to $$\mu_\gamma$$, the Marchenko-Pastur distribution with density given by $$d\mu_\gamma(t) = \frac{\sqrt{(t-t_-)(t_+-t)}}{2\pi \gamma t}1_{[t_-,t_+]}(t),$$ where $$t_\pm = (1 \pm \sqrt{\gamma})^2$$.

Now, define the decreasing funciton $$I_\gamma:[0,\infty) \to [0,\infty]$$ by $$I_\gamma(\lambda) := \int_{t_-}^{t_+} \frac{t}{(t+\lambda)^2}d\mu_\gamma(t).$$ Note that $$\gamma\mbox{tr}_d(R_\lambda(XX^\top)) \to I_\gamma(n\lambda)$$ a.s.

Now, thanks to the computations here (MO link), one has $$I_\gamma(\lambda)=\int_{t_-}^{t_+}\frac{\sqrt{\left(t_+-t\right) \left(t-t_-\right)}}{2 \pi {\gamma} (t+\lambda)^2}\,dt =\frac{-\sqrt{ {\gamma}^2+2 {\gamma} ( {\lambda}-1)+( {\lambda}+1)^2}+ {\gamma}+ {\lambda}+1}{2 {\gamma} \sqrt{ {\gamma}^2+2 {\gamma} ( {\lambda}-1)+( {\lambda}+1)^2}}.$$

• Case 1: $$\lambda \to 0^+$$. One recognizes $$I_\gamma(0^+) = \lim_{\lambda \to 0^+}\int_{t_-}^{t_+}\dfrac{1}{t + \lambda}d\mu_\gamma(t) = \lim_{\lambda \to 0^+}m_\gamma(-\lambda)=\dfrac{1}{1-\gamma}.$$

• Case 2: Positive $$\lambda$$. Likewise, pluggin $$n\lambda$$ for $$\lambda$$ and simplifying, one obtains $$I_\gamma(n\lambda) \to 1/(n\lambda)^2$$.

Putting things together, we obtain the following

Asymptotics of squared norm of Ridge(less) solution. In the asymptotic regime where $$n,d \to \infty$$ with $$n/d = \gamma \in [0,1)$$, it holds almost surely that $$\begin{split} \frac{\|\hat{\beta}_0\|}{\sqrt{n}} &= \sqrt{\dfrac{1}{1-\gamma}},\\ \sqrt{n}\lambda \|\hat{\beta}_\lambda\| &\to 1. \end{split}$$