Dimension free ridge regression

Bias and variance are derivatives of a single resolvent trace. Approximate one object, $R_k(\zeta,\mu;Q)=\mathrm{Tr}\,\Sigma^{1/2}Q\Sigma^{1/2}(\zeta I+\mu\Sigma+X_k^\top X_k)^{-1}$ with $X_k$ the first $k$ rows and $F_k=\zeta R_k$. The $\zeta$-derivative gives the variance, and the derivative in the coefficient of $\Sigma$ inserts the $\Sigma$ between two resolvents that the bias needs: at $\zeta=n\lambda$, $$V_X=\tau^2\partial_\zeta F_n(\zeta,0;I),\qquad B_X=-\zeta\,\partial_\mu F_n(\zeta,\mu;\theta\theta^\top)\big|_{\mu=0}.$$ The deterministic side is the same functional with no data and coefficient $\mu_*$, solving $\mu_*=\mu+n/(1+R_0(\zeta,\mu_*;I))$; the same derivatives give $V_n,B_n$, with their denominators from the chain rule ($\partial_\mu\mu_*=n/(n-\mathrm{df}_2)$). It suffices to show $R_n(\zeta,\mu;Q)\approx R_0(\zeta,\mu_*;Q)$ for $Q\in\{I,\theta\theta^\top\}$.

Close function values on a grid give close derivatives. Inverting the Vandermonde system of Taylor expansions on a one-sided grid (the bias derivative is taken at $\mu=0$ with $\mu\ge0$) gives $$|f'(0)|\le O_k\Big(\frac{\max_{j\le k}|f(j\delta)|}{\delta}+\delta^k\sup_{[0,k\delta]}|f^{(k+1)}|\Big).$$ For $f=F_n-F_0$ the first term is the value error over $\delta$, and the second needs deterministic bounds on high derivatives, which grow by $\kappa^{-2}$ per derivative for $F_0$ (through the inverse function $\lambda_*(\zeta)$); these give the large powers of $\kappa$ in Theorem 1.

The fixed-point equation is a counting identity along an interpolating path. Add rows one at a time, each time removing from the coefficient of $\Sigma$ what the new row contributes in conditional mean: from $\mu_0=\mu_*$ set $$\mu_{i+1}=\mu_i-\frac{1}{1+S_i(I)},$$ where $S_i$ is the trace at the next coefficient. If every $S_i(I)$ equaled $R_0(I)$, the path would be the line $\bar\mu_i=\mu_*-i/(1+R_0(I))$, and the fixed-point equation says exactly that $\bar\mu_n=\mu$: $n$ steps of size $1/(1+R_0(I))$ carry $\mu_*$ down to $\mu$. The proof must keep $R_i(Q)$ near $R_0(Q)$ and $\mu_i$ near $\bar\mu_i$.

Each new row leaves the trace unchanged to first order in conditional mean. By Sherman-Morrison, adding row $i$ lowers the trace by $z_i^\top BQBz_i/(1+z_i^\top Bz_i)$, whose conditional mean is about $\mathrm{Tr}\,QB^2/(1+S)$ because $z_i$ is isotropic and independent of the past. Lowering $\mu$ by $1/(1+S)$ raises it by $\mathrm{Tr}\,QBA/(1+S)$. The two cancel up to $O(\gamma^2R_0(Q)/(1+R_0(I))^2)$, second order in $\gamma\approx1/n$. So inside the resolvent $x_ix_i^\top$ acts like $\Sigma/(1+\mathrm{Tr}\,B)$, and the deterministic equivalent is a multiple of $\Sigma$.

The whitened resolvent has norm $\gamma\approx\chi_n/(n\kappa)$, and this bound uses $d_\Sigma$. Split $X=U+W$ along the top $\lfloor\eta n\rfloor$ eigendirections and the tail; completing the square shows it is enough that the top block is well conditioned (Yaskov's smallest-eigenvalue bound) and the tail small (Hanson-Wright truncation plus matrix Bernstein with intrinsic dimension at most $d_\Sigma$, giving $\|W^\top W\|\lesssim d_\Sigma\sigma_{\lfloor\eta n\rfloor}$ up to logarithms). At $\zeta=n\lambda$, $\mu_*\ge n\kappa$, so $\gamma=O(\chi_n(\lambda)/(n\kappa))$.

The two quadratic forms concentrate at each step. Given the past, $B_{i-1}$ is fixed and $z_i$ is fresh, so Hanson-Wright applies to $z_i^\top Bz_i$ and $z_i^\top BQBz_i$. If the earlier steps were good, $\|B\|_F^2\lesssim\gamma R_0(I)$ and $\|BQB\|_F^2\lesssim\gamma^3R_0(Q)$, so the deviations are $\log n\sqrt{\gamma R_0(I)}$ and $\log n\sqrt{\gamma^3R_0(Q)}$. The second scales like $\sqrt{R_0(Q)}$, more slowly than $R_0(Q)$; for rank-one $Q$ this is the source of the accuracy loss in Step 9.

The errors add up as a stopped martingale plus a second-order drift. Concentration at step $i$ needs closeness up to step $i-1$, so the argument is an induction on good events, with stopping times $T_E$, $T_F$ at the first failure of the Step 6 bounds and of closeness. Stopped there, the increments of $R_i(Q)$ are bounded martingale differences (Azuma-Hoeffding) plus second-order remainders, totaling $\beta_1$, and the path stays within $\beta_2=O(n\beta_1/(1+R_0(I))^2)$ of the line.

The path ends within $\beta_2$ of $\mu$, and the end can be moved to $\mu$, even at $\mu=0$. The trace is Lipschitz in the coefficient of $\Sigma$ with relative constant $\gamma$, so moving from $\mu_n$ to $\mu$ changes the trace by at most $\gamma\beta_2R_n(Q)$. The run needs $\beta_2\le\mu/2$, which fails at $\mu=0$, the variance case, so rerun Steps 3 to 7 from $\mu'\asymp\beta_2$; all scales change by constant factors, giving $|R_n-R_0|=O(\gamma\beta_2(1+R_0(I))R_0(Q)+\beta_1)$.

At the ridge scale the relative error is polynomially small, and for rank-one $Q$ it carries a factor $1/\sqrt\rho$. At $\zeta=n\lambda$ and small $\mu$, $R_0(I)\in[\kappa/2,1/\kappa]$ and $\gamma=O(\chi_n/(n\kappa))$, so with $\rho=R_0(Q)/R_0(I)$ $$|R_n(n\lambda,\mu;Q)-R_0(n\lambda,\mu_*;Q)|\le E_nR_0(Q),\qquad E_n=O\Big(\frac{\chi_n^3\log^2n}{n\kappa^{6.5}\sqrt\rho}\Big).$$ For $Q=I$, $\rho=1$; for the bias, $\rho\le1/(n\kappa)$, with $\rho\asymp1/n$ in the proportional regime, so the bias is approximated about $\sqrt n$ less accurately than the variance.

Assembling Theorem 1, where the conversion to $V_n,B_n$ is looser than the paper states. Feed Step 9 into Step 2, with a $\zeta$-grid for the variance and a $\mu$-grid on $[0,k\delta]$, $k\delta\le n\kappa^3/2$, for the bias, whose $F_0$ derivative bound supplies the $\lambda_*^{k+1}/(n\kappa^3)$ term. Caveat. The exact relations are $\tau^2F_0\le\frac{n\lambda}{\kappa}\frac{\mathrm{df}_1}{\mathrm{df}_2}V_n$ and $F_0(\theta\theta^\top)\ge(1-\mathrm{df}_2/n)(1+1/\lambda_*)B_n$, so the variance argument loses a factor $\mathrm{df}_1/\mathrm{df}_2$ (bounded in the proportional and $\alpha\gt1$ examples, of order $\log n$ for $\alpha=1$) and the bias argument a factor of order at least $1/\lambda_*$, large when $\lambda_*\to0$ as in Theorem 5. The paper's conversions use $\mathrm{df}_1\le\mathrm{df}_2$ and $F_0(\theta\theta^\top)\le(1-\mathrm{df}_2/n)B_n$, both the wrong way coordinatewise ($\sigma/(\sigma+\lambda_*)\gt\sigma^2/(\sigma+\lambda_*)^2$, and similarly for the bias since $\sigma\le1$). Whether a $\mu$-grid on the scale $\mu_*=n\lambda/\lambda_*$ repairs the stated rates is not checked here.

The ridgeless case follows from Theorem 1 at small $\lambda$ plus a bound on the gap to $\lambda=0$. For $d\gt n$, apply Theorem 1 at $\lambda=\kappa\lambda_*(\lambda)$ and bound the gap to $\lambda=0$. On the random side $|V_X(0)-V_X(\lambda)|\le(2\kappa\lambda_*/s_{\min})V_X(0)$, and the bias gap is bounded through $s_{\min}$ or Step 5 (the additive term); on the deterministic side $V_n,B_n$ move by a relative $O(\kappa/C_\Sigma^2)$. In the proportional case, balancing $\kappa$ against $\kappa^{-12.5}/n$ (times $\sqrt n$ for the bias) gives $\kappa=n^{-1/14}$ and $n^{-1/28}$. For $d\lt n$, $\lambda_*(0)=0$, so interpolate from $\lambda=\varepsilon$, with gaps $(2\varepsilon/s_{\min})V_X(0)$ and $O(\varepsilon/(C_\Sigma^2\sigma_d))V_n(0)$. Since $V_X(0)=\tau^2\mathrm{Tr}(Z^\top Z)^{-1}$ and $V_n(0)=\tau^2d/(n-d)$ do not depend on $\Sigma$, take $\Sigma=I$; then $\varepsilon\approx n^{-1/4}$ balances $\varepsilon$ against $\chi_n^3$. The bias vanishes on $\{\mathrm{rank}\,X=d\}$.

For power-law spectra the deterministic traces are Riemann sums. Regular variation gives $d_\Sigma=O(n)$ ($O(n\log n)$ when $\alpha=1$), and polynomial variation keeps $\chi_n$ polylogarithmic and $\kappa=\Theta(1)$, so Theorem 1 applies and the fixed point is a Beta integral: with $t=\lambda_*/\sigma_n$, $$\frac1n\mathrm{Tr}\,\Sigma(\Sigma+t\sigma_nI)^{-1}\to\int_0^\infty\frac{dx}{1+tx^\alpha}=t^{-1/\alpha}\frac{\pi/\alpha}{\sin(\pi/\alpha)},$$ so $t\to c_*$, and likewise $\mathrm{df}_2/n\to(1-\nu/c_*)(1-1/\alpha)$, which gives $V$. The decay condition on $\beta$ keeps $\rho$ large enough to control the $1/\sqrt\rho$ factor. In the log case $\mathrm{df}_2$ gets its mass from $l\sim n/\log n$, so $\mathrm{df}_2/n\approx1/(c_*\log n)\to0$.