2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – jlewk
    Dec 5, 2021 at 1:18
  • $\begingroup$ 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. $\endgroup$
    – jlewk
    Dec 5, 2021 at 1:23

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.