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

Question

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.

Answer 1

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} $$