Exact results on high-dimensional linear regression via statistical physics

It is clear that conventional statistical inference protocols need to be revised to deal correctly with the high-dimensional data that are now common. Most recent studies aimed at achieving this revision rely on powerful approximation techniques that call for rigorous results against which they can be tested. In this context, the simplest case of high-dimensional linear regression has acquired significant new relevance and attention. In this paper we use the statistical physics perspective on inference to derive several exact results for linear regression in the high-dimensional regime.

Figure 1

High-dimensional phenomena in inference with the linear regression (LR) model in the teacher-student scenario (see text). Comparison between parameters inferred with maximum likelihood (ML) $(\widehat{\mathit{\theta }},\widehat{\sigma })$ and true values $({\mathit{\theta }}_0,{\sigma }_0)$. (a) Plot of the ordered set $\widehat{\theta }\left({\theta }_0\right)=\{[\widehat{\theta }\left(1\right),{\theta }_0\left(1\right)],...,[\widehat{\theta }\left(d\right),{\theta }_0\left(d\right)]\}$ for $d/N\in \{0.01,0.675,0.867\}$, represented by symbols $\{•,\times ,\square \}$, with $N\in \{26000,385,300\}$. For each value of $d/N$ the rows of $\mathbf{Z}$ were sampled from $\mathcal{N}(\mathbf{0},{\mathbf{I}}_d), \mathit{\epsilon }$ was sampled from $\mathcal{N}(\mathbf{0},{\sigma }_0^2{\mathbf{I}}_N)$, with ${\sigma }_0^2=0.1$, and ${\mathit{\theta }}_0$ was sampled from $\mathcal{N}(\mathbf{0},{\mathbf{I}}_d)$. (b) Plot of ${\widehat{\sigma }}^2$ versus ${\sigma }_0^2$, represented by points connected by lines, for $d/N\in \{0.01,0.675,0.867\}$ (top to bottom). Each point, together with $\pm$ one standard-deviation error-bars, represents an average over 250 samples. Note that in both plots the diagonal line corresponds to perfect inference.

Figure 2

Theoretical predictions for ML inference of the LR model $\mathbf{t}=\mathbf{Z}\mathit{\theta }+\sigma \mathit{\epsilon }$, where $\mathbf{t}\in {\mathrm{IR}}^N$ and $\mathbf{Z}\in {\mathrm{IR}}^{N\times d}$, in the high-dimensional regime $0<d/N<1$. For each sample the rows of $\mathbf{Z}$ were sampled from the Gaussian $\mathcal{N}\left(\mathbf{0},\mathit{\Sigma }\right)$. The covariance matrix $\mathit{\Sigma }$ is such that ${\left[\mathit{\Sigma }\right]}_{\nu ,\nu }=1, {\left[\mathit{\Sigma }\right]}_{\nu ,\nu +1}={\left[\mathit{\Sigma }\right]}_{\nu +1,\nu }=\epsilon$ with $0\le \epsilon <1$ for $\nu$ odd, and ${\left[\mathit{\Sigma }\right]}_{{\nu }_1,{\nu }_2}=0$ for all other ${\nu }_1\ne {\nu }_2$. The density of eigenvalues of $\mathit{\Sigma }$ is given exactly by $\rho \left(\lambda \right)=\frac{1}{2}\delta (\lambda -1-\epsilon )+\frac{1}{2}\delta (\lambda -1+\epsilon )$ for any even $d$. For each sample the noise vector $\mathit{\epsilon }$ was sampled from $\mathcal{N}\left(\mathbf{0},{\sigma }_0^2{\mathbf{I}}_N\right)$. For each value of $d/N$ the (true) parameter ${\mathit{\theta }}_0$ was sampled from $\mathcal{N}\left(\mathbf{0},{\mathbf{I}}_d\right)$ only once. (a) Inferred noise parameter ${\sigma }^2$ as a function of $d/N$, where $(d,N)$ pairs range from $(10,{10}^4)$ to (310,323), plotted for true value of noise ${\sigma }_0^2\in \{0.05,0.10,0.20\}$ (top to bottom). Solid lines are the averages predicted by the theory in Eq. (32) and symbols, with $\pm$ one standard-deviation error-bars, are empirical averages over the 250 samples of data $\{\mathbf{t},\mathbf{Z}\}$. Error-bars are consistent with the variance predicted by the theory in Eq. (32). (b) MSE as a function of $d/N$ plotted for $\epsilon \in \{0,0.75,0.9\}$ (bottom to top) and ${\sigma }_0^2=0.1$. Solid lines correspond to the theoretical prediction $\frac{\zeta {\sigma }_0^2}{1-\zeta -N^{-1}}\frac{1}{1-{\epsilon }^2}$ for average MSE, computed via Eq. (39), and symbols, with $\pm$ one standard-deviation error-bars, are empirical averages over the 250 samples. Note the logarithmic scale of the vertical axis. Error-bars are consistent with the variance, $\frac{2{\zeta }^2{\sigma }_0^4}{{(1-\zeta )}^2}\frac{1+{\epsilon }^2}{d{(1+\epsilon )}^2{(1-\epsilon )}^2}$, as predicted by Eq. (39).

Figure 3

Asymptotic free-energy density $f_{\beta }={lim}_{N\to \infty }{f}_{\beta }\left[\mathcal{D}\right]$ of finite temperature ML inference as a function of temperature $T=1/\beta$, plotted for $\zeta \in \{1/10,2/10,...,9/10\}$ (from right to left) in the high-dimensional regime where $N,d\to \infty$ with fixed ratio $\zeta =d/N$. For $\beta \to \infty$ it approaches the value $\frac{1}{2}log\left[2\pi e{\sigma }_0^2(1-\zeta )\right]$. For $\beta \to \zeta$ it approaches $\frac{1}{2\zeta }[\zeta log(1-\zeta )-log(1-\zeta )-\zeta ]$, and for $\beta \in (0,\zeta )$, i.e., in the high “temperature” region $T\in (1/\zeta ,\infty )$, the free-energy density is $-\infty$. Here the true noise parameter is ${\sigma }_0^2=1$ and the true data covariance matrix is ${\mathbf{I}}_d$.