betaFeedback

WorksMathematics

Optimal spectral shrinkage via Krylov approximation

Abstract

Spectral shrinkage encompasses a broad family of estimators for high-dimensional linear regression that regularize estimation and prediction by applying spectral filters to the sample covariance matrix. Despite its widespread use, achieving oracle-optimal prediction risk under general covariance structures remains challenging, as the oracle filter requires unknown population quantities and has a closed form only for specific covariance models such as isotropic and spiked models. We propose risk-targeted Krylov fitting (RTK), a data-driven spectral estimator that adapts to the unknown covariance structure and attains the oracle risk asymptotically. Like partial least squares, RTK operates in an mm-dimensional Krylov space, but it targets the oracle risk directly by minimizing the leave-one-out risk, which we compute exactly without refitting the model nn times. Under general distributions and covariance structures, RTK attains the optimal prediction risk in the Krylov space up to O(1/n)O(1/n). Furthermore, its risk approaches that of the optimal analytic filter with mm of order log⁡n\log n. In simulations over a wide range of covariance structures, RTK and a truncated variant were robust to the choice of mm and consistently among the spectral estimators closest to the oracle. In applications to single-cell sequencing data and large-scale neural recordings, the proposed methods achieved higher prediction accuracy than competing estimators on most tasks.

Introduction

We study high-dimensional linear regression, where the number of covariates pp and the number of observations nn are of the same order. The data are nn independent observations from the linear model y=xTβ⋆+ϵy = x^{T}\beta^\star+ \epsilon, written in the design matrix X∈Rn×pX \in\mathbb{R}^{n \times p} and the response vector y∈Rny \in\mathbb{R}^{n}. Here β⋆∈Rp\beta^\star\in\mathbb{R}^{p} is the true regression coefficient and the noise ϵ\epsilon has mean zero given xx and variance σ2\sigma^2.

The performance of an estimator β\beta is measured by its prediction risk, the expected squared error at a new observation (x0,y0)(x_0, y_0) independent of (X,y)(X, y),

R(β)=E((y0−x0Tβ)2∣X,y)=σ2+(β−β⋆)TΣ(β−β⋆),(1)R(\beta) = E\left((y_0 - x_0^{\mathsf{T}}\beta)^2 \mid X, y\right) = \sigma^2 + (\beta- \beta^\star)^{\mathsf{T}}\Sigma(\beta- \beta^\star), \tag*{(1)}

where Σ=E(xxT)\Sigma= E(xx^{\mathsf{T}}) is the population covariance matrix.

An important class of estimators, known as spectral estimators, takes the form β^h=h(Sn)sn\hat{\beta}_h = h(S_n)s_n, where Sn=XTX/nS_n = X^{\mathsf{T}}X/n and sn=XTy/ns_n = X^{\mathsf{T}}y/n. The spectral filter h(⋅)h(\cdot) is a scalar function applied to the eigenvalues of SnS_n. Along a sample eigendirection with eigenvalue λ\lambda, such an estimator multiplies the least squares coefficient by the shrinkage factor λh(λ)\lambda h(\lambda) [20], which is below one where the estimator shrinks and above one where it amplifies. Ridge regression, principal component regression, early-stopped gradient descent and partial least squares (PLS) are all of this form and differ in the shape of the filter. The risk of a spectral estimator depends critically on the choice of the filter hh, which governs how the sample eigendirections are weighted.

This raises a natural question: which filter gives the smallest risk, and how can we achieve the smallest risk given a limited amount of data? In the proportional regime n,p→∞n, p \to\infty with p/n→γ∈(0,∞)p/n \to\gamma\in(0, \infty), the risk R(β^h)R(\hat{\beta}_h) is asymptotically deterministic for ridge regression and many other spectral estimators [17, 26, 22]. Let F\mathcal{F} be the class of fixed filters hh for which R(β^h)R(\hat{\beta}_h) converges in probability to a deterministic limit. The oracle filter is the filter in F\mathcal{F} with the smallest limiting risk,

h⋆=arg min⁡h∈FR∞(h),R(β^h)→pR∞(h),(2)h^\star= \underset{h \in\mathcal{F}}{\operatorname{arg\,min}} R_\infty(h), \qquad R(\hat{\beta}_h) \xrightarrow{p} R_\infty(h), \tag*{(2)}

and is therefore a fixed function that does not depend on the realization of the data. Since β^h=h(Sn)sn\hat{\beta}_h = h(S_n)s_n depends linearly on hh and the prediction risk (1) is quadratic in β\beta, the risk R(β^h)R(\hat{\beta}_h) depends quadratically on hh, and so does its limit. Finding h⋆h^\star therefore amounts to minimizing a quadratic functional of hh determined by γ\gamma, σ2\sigma^2, the spectral distribution of Σ\Sigma and the distribution of the signal over the eigenvalues of Σ\Sigma, as shown by the limits derived for principal component regression [22] and spiked covariance (Lecoiu et al., 2026). Because h⋆h^\star involves the unknown population quantities σ2\sigma^2, Σ\Sigma and β⋆\beta^\star, the oracle estimator h⋆(Sn)snh^\star(S_n)s_n is generally unavailable. Moreover, closed forms of h⋆h^\star are known only in special cases, namely a ridge filter when the signal is isotropic [17] and a rational function when the covariance is spiked (Lecoiu et al., 2026). In the proportional regime, the population quantities required to evaluate h⋆h^\star are difficult to estimate accurately. For example, the spectral distribution of Σ\Sigma can be estimated from that of the sample covariance matrix SnS_n [19, 33, 39], but this inverse problem can be ill-posed when the dimension is comparable to the sample size.

Instead of computing h⋆h^\star from estimates of unknown population quantities such as Σ\Sigma and σ2\sigma^2, we ask whether a data-driven spectral estimator can attain the oracle risk R∞(h⋆)R_\infty(h^\star) without explicitly estimating these quantities. We construct such an estimator β^h^\hat{\beta}_{\hat{h}} from (2) by replacing the limiting risk R∞(h)R_\infty(h) by a risk estimate R^(h)\hat{R}(h) and the class F\mathcal{F} by a space of filters Fn\mathcal{F}_n,

h^=arg min⁡h∈FnR^(h).(3)\hat{h} = \underset{h \in\mathcal{F}_n}{\operatorname{arg\,min}} \hat{R}(h). \tag*{(3)}

Within this framework, we seek Fn\mathcal{F}_n and R^\hat{R} that satisfy two conditions:

  1. the minimum risk over Fn\mathcal{F}_n approaches R∞(h⋆)R_\infty(h^\star);

  2. R^(h)\hat{R}(h) is consistent for R(β^h)R(\hat{\beta}_h) uniformly over Fn\mathcal{F}_n.

Together, the two conditions ensure that β^h^\hat{\beta}_{\hat{h}} attains the oracle risk asymptotically. In general, condition (i) requires Fn\mathcal{F}_n to grow with nn, whereas condition (ii) limits how fast it may grow.

To meet conditions (i) and (ii), we minimize the leave-one-out risk over the Krylov space of spectral estimators, a procedure we call risk-targeted Krylov fitting (RTK). For condition (i), the space Fn\mathcal{F}_n must be flexible enough to reproduce the shape of the oracle filter, whose shrinkage factor λh⋆(λ)\lambda h^{\star}(\lambda) can be non-monotone and exceed one (Lecoiu et al., 2026), as the simulations of § 5 show. Optimally tuned ridge regression and principal component regression cannot approximate such an oracle filter, because their shrinkage factors are monotone and at most one. We take Fn\mathcal{F}_n to be the space of polynomials of degree less than mm, where mm may grow with nn, so that the corresponding estimators β^h=h(Sn)sn\hat{\beta}_h=h(S_n)s_n form the Krylov space

Km(Sn,sn)=span⁡{sn,Snsn,…,Snm−1sn},\mathcal{K}_m(S_n,s_n)=\operatorname{span}\{s_n,S_ns_n,\ldots,S_n^{m-1}s_n\},

which we abbreviate to Km\mathcal{K}_m. The best estimator in this space attains the smallest risk

min⁡deg⁡h<mR(β^h)=min⁡β∈Km(Sn,sn)R(β),(4)\min_{\deg h<m} R(\hat{\beta}_h)=\min_{\beta\in\mathcal{K}_m(S_n,s_n)}R(\beta), \tag*{(4)}

which approaches the oracle risk as mm grows whenever the oracle filter is continuous on the spectrum (Remark 5). For condition (ii), we take R^\hat{R} to be the leave-one-out risk. On Km\mathcal{K}_m, the leave-one-out predictions are linear in the polynomial coefficients and follow from a single eigendecomposition of the n×nn\times n matrix XXT/nXX^{T}/n, allowing RTK to minimize the leave-one-out risk directly over Km\mathcal{K}_m. When a few eigenvalues lie far above the bulk, using a single polynomial for the whole spectrum can lead to poor resolution, as much of the polynomial degree is devoted to a nearly empty spectral gap, where the filter values do not affect the risk. We therefore also introduce a truncated variant of RTK, whose filter fits a polynomial only near the bulk and gives each separated eigenvalue a free shrinkage factor.

Viewing RTK through conditions (i) and (ii) clarifies how it relates to and differs from two established methods: PLS and cross-validation. PLS was introduced by Wold [60] as an iterative latent-variable method and developed for chemometric calibration [61, 31]. It is now widely used for high-dimensional, correlated measurements in chemistry [62, 43] (Xu et al. 2025), genomics [7] and neuroscience [34, 52, 18, 28]. The mm-component PLS regression minimizes the empirical risk (the training error) over the same Krylov space as RTK,

β^mPLS=arg min⁡β∈Km(Sn,sn) n−1∥y−Xβ∥2.(5)\hat{\beta}^{\mathrm{PLS}}_m=\underset{\beta\in\mathcal{K}_m(S_n,s_n)}{\operatorname{arg\,min}}\ n^{-1}\lVert y-X\beta\rVert^2. \tag*{(5)}

PLS thus meets condition (i) but not condition (ii): the empirical risk it minimizes is not uniformly consistent for the prediction risk (1) in the proportional regime (§ 2.2), so the risk of PLS first decreases in mm and then rises toward that of the least squares solution [36]. Conversely, cross-validation methods meet condition (ii) but not condition (i). Leave-one-out or generalized cross-validation [1, 56, 14, 21] is commonly applied to spectral shrinkage [4, 41], where it tunes the parameter of a filter family fixed in advance (§ 2.1). These criteria and related risk estimates are consistent in the proportional regime for ridge regression [46, 49], gradient descent paths [47, 6] and ensembles of penalized estimators [5]. More generally, cross-validation determines the weights of candidate estimators in stacking [64, 8], the super learner [59] and jackknife model averaging [24]. In either case, the risk estimate only selects or weights candidate estimators, whose filters are fixed in advance or fitted to the empirical risk as for stacked PLS fits [37]. Without a closed form of the oracle filter, the resulting estimator cannot in general attain the oracle risk. RTK resembles stacking in form, but it determines the filter itself by minimizing a uniformly consistent risk estimate, so it can attain the oracle risk as mm grows (Remark 1).

Since RTK minimizes the leave-one-out risk over Km\mathcal{K}_m rather than evaluating it at a fixed estimator, it needs R^\widehat{R} to be consistent uniformly over Km\mathcal{K}_m as in condition (ii), not merely pointwise. In return, its finite-sample imprecision as a risk estimate [3] matters much less, because a criterion too noisy to estimate the risk can still locate the minimizer of the risk (Remark 4). Our main result is that the leave-one-out risk meets condition (ii): under moment conditions covering Gaussian, sub-Gaussian and bounded elliptical designs, it is consistent at rate n−1/2n^{-1/2} uniformly over bounded subsets of Km\mathcal{K}_m (Theorem 2). If the basis vectors of Km\mathcal{K}_m are not nearly collinear, RTK therefore attains the risk of the best estimator in Km\mathcal{K}_m up to a term of order n−1n^{-1}, whereas PLS does not in general (Corollaries 1 and 2). With mm of order log⁡n\log n, Km\mathcal{K}_m meets condition (i) whenever the oracle filter is analytic near the spectrum, and the risk of RTK then approaches the oracle risk at a polynomial rate in nn (Theorem 3). The only tuning parameter in RTK is mm. Unlike the level of ridge regression, it does not select a filter but only sets the dimension of Km\mathcal{K}_m, within which the leave-one-out risk determines the filter (Remark 1). Each unnecessary dimension costs only O(n−1)O(n^{-1}) (Corollary 1(b)), so mm can be fixed in advance. The truncated variant has analogous guarantees under a gap condition (Remark 6).

In simulations over a wide range of covariance structures and signals (§ 5), RTK and its truncated variant were more accurate than PLS in every setting, by up to 63%, and unlike that of PLS, the risk of RTK rose only mildly as mm grew (Fig. 1). The truncated variant was the most accurate among the spectral estimators compared in more than half of the settings. In the other settings its gap to the best estimator shrank as nn grew, also where a competing filter family contains the closed-form oracle. At n=1000n = 1000 its excess risk was never more than about 1% above the best (§ 5.4). In single-cell sequencing data and large-scale neural recordings, RTK and its truncated variant improved prediction over the competing spectral estimators in most tasks (§ 6).

Spectral shrinkage and partial least squares

Model and spectral estimators

Formally, the observations (xi,yi)(x_i,y_i) (i=1,…,ni = 1,\ldots,n) are independent copies of (x,y)∈Rp×R(x,y) \in\mathbb{R}^p \times\mathbb{R} following the linear model

y=xTβ∗+ϵ,E(x)=0,E(xxT)=Σ,E(ϵ∣x)=0,E(ϵ2)=σ2,(6)y = x^{\mathsf{T}}\beta^* + \epsilon,\qquad E(x)=0,\qquad E(xx^{\mathsf{T}})=\Sigma,\qquad E(\epsilon\mid x)=0,\qquad E(\epsilon^2)=\sigma^2, \tag*{(6)}

where the rows of XX are xiTx_i^{\mathsf{T}}, the entries of yy are yiy_i, and Sn=XTX/nS_n = X^{\mathsf{T}}X/n and sn=XTy/ns_n = X^{\mathsf{T}}y/n are the sample counterparts of Σ\Sigma and Σβ∗\Sigma\beta^*.

With the eigendecomposition Sn=∑j=1pλ^jv^jv^jTS_n = \sum_{j=1}^{p}\hat{\lambda}_j\hat{v}_j\hat{v}_j^{\mathsf{T}} and λ^1≥⋯≥λ^p≥0\hat{\lambda}_1 \geq\cdots\geq\hat{\lambda}_p \geq0, a spectral estimator is

β^h=h(Sn)sn=∑j=1ph(λ^j)(v^jTsn)v^j.\hat{\beta}_h = h(S_n)s_n = \sum_{j=1}^{p} h(\hat{\lambda}_j)(\hat{v}_j^{\mathsf{T}}s_n)\hat{v}_j.

For λ^j>0\hat{\lambda}_j > 0, its coefficient along v^j\hat{v}_j is the least squares coefficient v^jTsn/λ^j\hat{v}_j^{\mathsf{T}}s_n/\hat{\lambda}_j multiplied by the shrinkage factor gj=λ^jh(λ^j)g_j = \hat{\lambda}_j h(\hat{\lambda}_j). Ridge regression with level μ>0\mu> 0, principal component regression with threshold τ\tau and tt steps of gradient descent with step size η\eta have the filters

hridge(λ)=1λ+μ,hPCR(λ)=1{λ>τ}λ,hGD(λ)=1−(1−ηλ)tλ.h_{\mathrm{ridge}}(\lambda)=\frac{1}{\lambda+\mu},\qquad h_{\mathrm{PCR}}(\lambda)=\frac{\mathbb{1}\{\lambda>\tau\}}{\lambda},\qquad h_{\mathrm{GD}}(\lambda)=\frac{1-(1-\eta\lambda)^t}{\lambda}.

Their shrinkage factors are non-decreasing in λ\lambda and at most one, for gradient descent when ηλ^1≤1\eta\hat{\lambda}_1\leq1. PLS uses a polynomial filter of degree less than mm whose coefficients are fitted by least squares (§ 2.2).

Partial least squares and the Krylov space

We briefly review PLS to define the quantities in § 3 and to motivate risk-targeted Krylov fitting. By (5), PLS minimizes the empirical risk over the Krylov space Km(Sn,sn)={q(Sn)sn:deg⁡q<m}\mathcal{K}_m(S_n,s_n)=\{q(S_n)s_n:\deg q<m\}, which we abbreviate to Km\mathcal{K}_m. For a univariate response, this characterization and the equivalence of PLS with the mm-th iterate of conjugate gradients for Snβ=snS_n\beta=s_n started at zero are classical ([61, 27, 48]).

To parametrize Km\mathcal{K}_m, we pick a basis φ1,…,φm\varphi_1,\ldots,\varphi_m of the polynomials of degree less than mm, for instance the monomials φk(λ)=λk−1\varphi_k(\lambda)=\lambda^{k-1} or the Chebyshev polynomials φk(λ)=Tk−1(2λ/b−1)\varphi_k(\lambda)=T_{k-1}(2\lambda/b-1) on an interval [0,b][0,b] that contains the spectrum. The choice of basis affects only numerical stability. Theorem 1 and Algorithm 1 are stated in the monomial basis for clarity, whereas our implementation uses the Chebyshev basis (Remark 2).

Let bk=φk(Sn)snb_k=\varphi_k(S_n)s_n and B=(b1,…,bm)∈Rp×mB=(b_1,\ldots,b_m)\in\mathbb{R}^{p\times m}. Every β∈Km\beta\in\mathcal{K}_m is then β=Bc\beta=Bc for a coefficient vector c∈Rmc\in\mathbb{R}^m. With the in-sample features V=XBV=XB, that is, Vik=xiTbkV_{ik}=x_i^Tb_k (i=1,…,ni=1,\ldots,n; k=1,…,mk=1,\ldots,m), the empirical risk in (5) is the least squares criterion

n−1∥y−Vc∥2=n−1∥y∥2−2cTBTsn+cTBTSnBc,n^{-1}\lVert y-Vc\rVert^2=n^{-1}\lVert y\rVert^2-2c^TB^Ts_n+c^TB^TS_nBc,

so that β^mPLS=Bc^mPLS\hat{\beta}^{\mathrm{PLS}}_m=B\hat{c}^{\mathrm{PLS}}_m, where c^mPLS\hat{c}^{\mathrm{PLS}}_m solves its normal equations

VTVc=VTy.(7)V^TVc=V^Ty. \tag*{(7)}

However, our goal is to attain the smallest risk (4) in Km\mathcal{K}_m. By (1), the risk R(c)R(c) of β=Bc\beta=Bc is also a quadratic function of cc,

R(c)=E((y0−x0TBc)2∣X,y)=R(0)−2cTξ+cTGc,G=BTΣB,ξ=BTΣβ⋆,(8)R(c)=E((y_0-x_0^TBc)^2\mid X,y)=R(0)-2c^T\xi+c^TGc,\qquad G=B^T\Sigma B,\quad\xi=B^T\Sigma\beta^\star, \tag*{(8)}

with R(0)=σ2+β⋆TΣβ⋆R(0)=\sigma^2+\beta^{\star T}\Sigma\beta^\star. The empirical risk minimized by PLS has the form of (8) with (BTSnB,BTsn)(B^TS_nB,B^Ts_n) in place of (G,ξ)(G,\xi), that is, with Σ\Sigma and Σβ⋆\Sigma\beta^\star replaced by their sample counterparts SnS_n and sns_n. PLS thus minimizes a plug-in estimate of the risk built from the same SnS_n and sns_n that span Km\mathcal{K}_m. The plug-in is accurate in low-dimensional regimes.

In the proportional regime, BTSnBB^TS_nB and BTsnB^Ts_n do not estimate GG and ξ\xi consistently. PLS therefore searches a rich space, but optimizes a criterion that is not aligned with the target risk. In line with this, the PLS coefficient is inconsistent when p/np/n does not vanish ([10]), and its prediction rates depend on how the signal is aligned with the covariance ([12]). Analyses of conjugate gradients on random covariance matrices describe how fast the iterates approach the least squares solution ([16]), which itself is a poor estimator in high dimensions. Since PLS is the mm-th iterate of conjugate gradients, the non-monotone dependence of its risk on mm is an instance of the semi-convergence of Krylov methods for ill-posed problems ([25]). Hybrid methods aim to overcome semi-convergence by Tikhonov regularization of the projected problem at each iteration ([11] (Kilmer & O’Leary 2001)).

Risk-targeted Krylov fitting

This section introduces risk-targeted Krylov fitting, which minimizes the leave-one-out risk over the Krylov space Km\mathcal{K}_m instead of the empirical risk minimized by PLS (§ 3.1). The leave-one-out risk consistently estimates the prediction risk over the Krylov space, and its minimization is a least squares problem. The leave-one-out risk is computed without refitting by Theorem 1 and Algorithm 1 (§ 3.2), and Algorithm 2 summarizes the method. Section 3.3 proposes a truncated variant that adapts the polynomial filter to spectra with a few eigenvalues far above the bulk.

Leave-one-out risk over the Krylov space

Our goal is to find the coefficient vector c\mathbf{c} that minimizes the prediction risk R(c)R(\mathbf{c}) in (8), which is equivalent to minimizing the risk over polynomial filters in (4). Since R(c)R(\mathbf{c}) depends on the unknown Σ\boldsymbol{\Sigma} and β⋆\boldsymbol{\beta}^{\star}, it cannot be computed directly, and we estimate it from the observations (xi,yi)(x_i,y_i) (i=1,…,ni=1,\ldots,n) by the leave-one-out risk

R^(c)=n−1∑i=1n(yi−xiTβ(i))2,β(i)=∑k=1mckφk(Sn(i))sn(i).\widehat{R}(\mathbf{c})=n^{-1}\sum_{i=1}^{n}(y_i-x_i^{\mathsf T}\beta^{(i)})^2,\qquad\beta^{(i)}=\sum_{k=1}^{m}c_k\varphi_k(S_n^{(i)})s_n^{(i)}.

where Sn(i)S_n^{(i)} and sn(i)s_n^{(i)} are SnS_n and sns_n computed without observation ii, with the normalization 1/n1/n kept. The leave-one-out fit β(i)\beta^{(i)} keeps the coefficients c\mathbf{c} and rebuilds only the basis without observation ii, so R^(c)\widehat{R}(\mathbf{c}) is the cross-validation error of the fixed filter ∑kckφk\sum_k c_k\varphi_k. Since β(i)\beta^{(i)} is a function of the observations other than ii, the conditional expectation of the ii-th term given these observations is R(β(i))R(\beta^{(i)}) by (1), so that E(R^(c))=E(R(β(1)))E(\widehat{R}(\mathbf{c}))=E(R(\beta^{(1)})) for fixed c\mathbf{c}. The leave-one-out risk is thus unbiased for the expected risk of β\beta computed from n−1n-1 observations.

Risk-targeted Krylov fitting (RTK) chooses the coefficients c\mathbf{c} by minimizing the leave-one-out risk R^(c)\widehat{R}(\mathbf{c}),

c^mRTK=arg⁡min⁡c∈RmR^(c),β^mRTK=Bc^mRTK.(9)\widehat{\mathbf{c}}^{\mathrm{RTK}}_m=\underset{\mathbf{c}\in\mathbb{R}^{m}}{\arg\min}\widehat{R}(\mathbf{c}),\qquad\widehat{\beta}^{\mathrm{RTK}}_m=B\widehat{\mathbf{c}}^{\mathrm{RTK}}_m. \tag*{(9)}

The minimization in (9) is again a least squares problem over c\mathbf{c}. Indeed, the leave-one-out prediction xiTβ(i)=∑k=1mckUikx_i^{\mathsf T}\beta^{(i)}=\sum_{k=1}^{m}c_kU_{ik} is linear in c\mathbf{c}, where the leave-one-out features

Uik=xiTφk(Sn(i))sn(i)(i=1,…,n; k=1,…,m)U_{ik}=x_i^{\mathsf T}\varphi_k(S_n^{(i)})s_n^{(i)}\qquad(i=1,\ldots,n;\ k=1,\ldots,m)

are the predictions at xix_i of the basis of Km(Sn(i),sn(i))\mathcal{K}_m(S_n^{(i)},s_n^{(i)}). Hence R^\widehat{R} is the least squares criterion

R^(c)=n−1∥y−Uc∥2=R^(0)−2cTξ^+cTG^c,G^=UTU/n,ξ^=UTy/n,(10)\widehat{R}(\mathbf{c})=n^{-1}\lVert y-U\mathbf{c}\rVert^2=\widehat{R}(0)-2\mathbf{c}^{\mathsf T}\widehat{\xi}+\mathbf{c}^{\mathsf T}\widehat{G}\mathbf{c},\qquad\widehat{G}=U^{\mathsf T}U/n,\quad\widehat{\xi}=U^{\mathsf T}y/n, \tag*{(10)}

with R^(0)=∥y∥2/n\widehat{R}(0)=\lVert y\rVert^2/n, which has the form of (8) with (G^,ξ^)(\widehat{G},\widehat{\xi}) in place of (G,ξ)(G,\xi). Thus, the minimizer c^mRTK\widehat{\mathbf{c}}^{\mathrm{RTK}}_m in (9) solves the normal equations

UTUc=UTy.(11)U^{\mathsf T}U\mathbf{c}=U^{\mathsf T}y. \tag*{(11)}

Compared with the normal equations (7) of PLS, (11) replaces the in-sample features Vik=xiTbkV_{ik}=x_i^{\mathsf T}b_k by the leave-one-out features UikU_{ik}, while the Krylov basis BB is unchanged.

Note that unbiasedness of R^(c)\widehat{R}(\mathbf{c}) holds only for fixed c\mathbf{c}, whereas c^mRTK\widehat{\mathbf{c}}^{\mathrm{RTK}}_m depends on the data. Minimizing R^\widehat{R} therefore requires it to be consistent for RR uniformly over bounded sets of coefficients, which § 4.1 proves. Section 4.2 then shows that RTK attains the risk of the best Krylov estimator up to O(n−1)O(n^{-1}) whereas PLS does not, and § 4.3 shows that with a slowly growing dimension its risk approaches that of the best analytic filter, which is the oracle risk when the oracle filter is analytic. An unnecessary dimension costs only estimation error of order n−1n^{-1} rather than a drift toward interpolation as in PLS, so mm need not be tuned and can be fixed in advance, as long as it is small compared with nn.

Remark 1. We derived RTK from PLS by keeping its Krylov space and replacing its criterion, and analyzed its statistical properties along the same route. RTK also admits a stacking view. The columns of UU are the leave-one-out predictions of b1,…,bmb_1,\ldots,b_m and thus form the level-one data of stacking (Wolpert [64]; Breiman [8]). Like stacking, RTK regresses yy on these predictions by least squares in (9). Stacking usually constrains the weights to be nonnegative (Breiman [8]), whereas RTK leaves its coefficients unconstrained. This difference reflects two more fundamental distinctions. First, the candidates of stacking are estimators that predict well on their own. Their filters are fixed in advance or fitted to the empirical risk, as for ridge estimators at given levels or the PLS fits stacked by Kurnia et al. [37]. Stacking thus extends model selection by cross-validation, and only the stacking weights target the risk. In RTK, the vectors bkb_k are not good estimators but a basis of Km\mathcal{K}_m, and the spectral filter of RTK directly targets the risk. Since the leave-one-out risk is consistent uniformly over bounded coefficients (Theorem 2), the coefficients need no constraints. Second, the single parameter mm sets the size of the nested Krylov space without specifying the form of any candidate filter, which allows mm to grow with nn. With a slowly growing mm, the risk of RTK approaches the oracle risk when the oracle filter is analytic (Theorem 3).

Efficient computation of the leave-one-out features

By (9), risk-targeted Krylov fitting requires only the leave-one-out features UU. Computing UU by refitting would require nn fits, and we instead obtain it exactly and efficiently from full-sample quantities. Writing φk(λ)=∑a=0m−1φk,aλa\varphi_k(\lambda)=\sum_{a=0}^{m-1}\varphi_{k,a}\lambda^a, each feature is a fixed linear combination Uik=∑a=0m−1φk,aui,a+1U_{ik}=\sum_{a=0}^{m-1}\varphi_{k,a}u_{i,a+1} of the leave-one-out moments ui,a=xiT(Sn(i))a−1sn(i)u_{i,a}=x_i^\mathsf{T}(S_n^{(i)})^{a-1}s_n^{(i)} (a=1,…,m)(a=1,\ldots,m). Their full-sample counterparts are the local response moments vi,a=xiTSna−1sn=(Tny)iv_{i,a}=x_i^\mathsf{T}S_n^{a-1}s_n=(T_n y)_i with Tn=XXT/nT_n=XX^\mathsf{T}/n. The following theorem recovers the leave-one-out moments ui,au_{i,a} from two full-sample quantities, the local response moments vi,av_{i,a} and the local spectral moments (Tnj)ii(T_n^j)_{ii}.

Theorem 1. Let ui,a=xiT(Sn(i))a−1sn(i)u_{i,a}=x_i^\mathsf{T}(S_n^{(i)})^{a-1}s_n^{(i)} and vi,a=(Tnay)iv_{i,a}=(T_n^a y)_i for a≥1a\ge1, with ui,0=vi,0=yiu_{i,0}=v_{i,0}=y_i. Then for i=1,…,ni=1,\ldots,n and all a≥1a\ge1,

ui,a=vi,a−∑j=1a(Tnj)ii ui,a−j.(12)u_{i,a}=v_{i,a}-\sum_{j=1}^{a}(T_n^j)_{ii}\,u_{i,a-j}. \tag*{(12)}

The proof of Theorem 1 is purely algebraic and is given in the Appendix. By Theorem 1, the leave-one-out moments ui,au_{i,a} require only vi,av_{i,a} and (Tnj)ii(T_n^j)_{ii}, and both follow from one eigendecomposition Tn=Qdiag⁡(λ^)QTT_n=Q\operatorname{diag}(\hat{\lambda})Q^\mathsf{T} as (Tnj)ii=∑lQil2λ^lj(T_n^j)_{ii}=\sum_l Q_{il}^2\hat{\lambda}_l^j and vi,a=∑lQilλ^la(QTy)lv_{i,a}=\sum_l Q_{il}\hat{\lambda}_l^a(Q^\mathsf{T}y)_l. All leave-one-out features therefore cost O(n3+n2m)O(n^3+n^2m) operations, the cost of one singular value decomposition of XX.

Write Tn(i)T_n^{(i)} and y(i)y^{(i)} for TnT_n and yy without the ii-th row and column or entry, and tit_i for the ii-th column of TnT_n without its diagonal entry. Then ui,a=tiT(Tn(i))a−1y(i)u_{i,a}=t_i^\mathsf{T}(T_n^{(i)})^{a-1}y^{(i)}, and the proof uses only this form and the symmetry of TnT_n. The recursion (12) therefore holds for any symmetric matrix in place of TnT_n, which covers kernel regression with TnT_n replaced by K/nK/n for a kernel matrix KK and leave-one-out predictions along gradient descent paths with I−ηTnI-\eta T_n in place of TnT_n (§ S2 of the Supplementary Material).

The same form gives an algorithm that requires only matrix-vector products. Deleting observation ii amounts to setting the ii-th entry of a vector to zero before each multiplication by TnT_n, and keeping one column per observation carries out all nn deletions at once.

Algorithm 1 (Masked recursion). The input is Tn=XXT/nT_n = XX^{\mathsf T}/n, the response yy and the dimension mm.

Step 1. Set Y=y1nTY = y\mathbf{1}_n^{\mathsf T}, so that column ii of YY is a copy of yy.

Step 2. For a=1,…,ma = 1,\ldots,m, set the diagonal of YY to zero and replace YY by TnYT_nY. Record ui,a=Yiiu_{i,a}=Y_{ii} for i=1,…,ni=1,\ldots,n.

By induction, the ii-th column of YY after iteration aa is (TnDi)ay(T_nD_i)^ay with Di=I−eieiTD_i=I-e_ie_i^{\mathsf T}, so its ii-th entry is the moment ui,au_{i,a} of Theorem 1. Setting the diagonal Yii=ui,a−1Y_{ii}=u_{i,a-1} to zero thus removes the self-feedback ∑j=1a(Tnj)iiui,a−j\sum_{j=1}^{a}(T_n^j)_{ii}u_{i,a-j} of observation ii while the products are formed, in the spirit of the moment estimators of Kong & Valiant [33]. Theorem 1 instead lets the self-feedback occur and divides it out afterwards. The algorithm costs O(mn3)O(mn^3) operations, compared with O(n3+n2m)O(n^3+n^2m) through Theorem 1.

With the features of Theorem 1, RTK in (9) can be computed as follows.

Algorithm 2 (Risk-targeted Krylov fitting). The input is the data (X,y)(X,y) and the dimension mm.

Step 1. Form Tn=XXT/nT_n=XX^{\mathsf T}/n and its eigendecomposition Tn=Qdiag⁡(λ^)QTT_n=Q\operatorname{diag}(\hat{\lambda})Q^{\mathsf T}, and set b=1.01λ^1b=1.01\hat{\lambda}_1.

Step 2. Compute the features U∈Rn×mU\in\mathbb{R}^{n\times m} of φk(λ)=Tk−1(2λ/b−1)\varphi_k(\lambda)=T_{k-1}(2\lambda/b-1) by Theorem 1.

Step 3. Compute qk=φk(Tn)yq_k=\varphi_k(T_n)y for k=1,…,mk=1,\ldots,m and solve UTUc=UTyU^{\mathsf T}Uc=U^{\mathsf T}y.

Step 4. Output β^=XT(c1q1+⋯+cmqm)/n\hat{\beta}=X^{\mathsf T}(c_1q_1+\cdots+c_mq_m)/n.

The output equals BcBc because φk(Sn)XT=XTφk(Tn)\varphi_k(S_n)X^{\mathsf T}=X^{\mathsf T}\varphi_k(T_n).

Remark 2. Theorem 1 and Algorithm 1 are stated in the monomial basis for clarity. Since the change to the Chebyshev basis is ill-conditioned for large mm, our implementation works in the Chebyshev basis directly. Both results carry over to this basis and to models with an intercept (§ S6.1 of the Supplementary Material).

Remark 3. Theorem 1 also explains generalized cross-validation and why RTK does not use it. Exact leave-one-out corrects each observation by its own local spectral moments (Tnj)ii(T_n^j)_{ii}. For ridge regression with level μ\mu, the exact leave-one-out residual is ((Tn+μI)−1y)i/((Tn+μI)−1)ii((T_n+\mu I)^{-1}y)_i/((T_n+\mu I)^{-1})_{ii}, and the local spectral moments enter only through the denominator. Replacing it by its average tr⁡((Tn+μI)−1)/n\operatorname{tr}((T_n+\mu I)^{-1})/n gives the residual of generalized cross-validation [14, 21]. Such averaging is accurate only when the (Tnj)ii(T_n^j)_{ii} concentrate, which fails for high-order moments and under elliptical designs, where (Tn)ii=∥xi∥2/n(T_n)_{ii}=\lVert x_i\rVert^2/n varies with the radius (Table S10 of the Supplementary Material). Both cases matter for RTK, whose features involve moments up to order mm and whose theory covers bounded elliptical designs (Assumption 1). Under an elliptical design, the error of the averaged-diagonal approximation of G^\hat{G} did not decrease with nn in our simulations, whereas that of exact leave-one-out decreased at rate n−1/2n^{-1/2} (Fig. S2 of the Supplementary Material). Beyond ridge filters, averaging the moments is no longer equivalent to the scalar degrees-of-freedom correction of generalized cross-validation. Along gradient descent paths this correction fails to track the risk [47], whereas the averaged moments did in the Gaussian settings of Fig. S4 of the Supplementary Material.

Truncation to the bulk of the spectrum

The dimension mm in RTK depends on how well polynomials of degree less than mm approximate the oracle filter on the spectrum. Polynomials approximate smooth functions well on the compact support of the bulk, but not over a spectrum that spans several scales. When the top eigenvalues lie far above the bulk, an interval [0,b][0,b] that covers them places the bulk near its endpoint 00, where the approximation is poor. In particular, a filter that is singular within distance ε\varepsilon of an endpoint has polynomial approximation error no smaller than exp⁡(−2m(ε/b)1/2)\exp(-2m(\varepsilon/b)^{1/2}) (Lemma S4 of the Supplementary Material; see Trefethen, [58], Ch. 8), and ε/b\varepsilon/b is small when bb is set by the outliers. With two or more spikes, the rational oracle filter of Lecoiu et al. (2026) may moreover have a pole between consecutive outliers.

However, poles in the gaps do not affect the risk, because a spectral estimator depends on hh only through its values at the sample eigenvalues, which lie near the limiting spectrum. The filter may therefore take any value in the gaps of the spectrum, which contain no eigenvalues asymptotically. Polynomials can still match the oracle filter on the bulk and at the outliers, although the required degree grows with the spread of the spectrum. Truncation exploits the same freedom with fewer parameters. It fits the polynomial only on an interval close to the bulk, whose scale is much smaller than that of the whole spectrum. Each of the KK eigenvalues far above this interval receives a free shrinkage factor instead. The estimator is linear in these factors, so the leave-one-out risk stays quadratic and is minimized by least squares. A rational filter with poles among the outliers would instead require a nonconvex search over the pole locations, typically on a grid of candidates. On a spectrum of bounded range, truncation thus lowers the degree that is needed rather than the risk that can be attained, and RTK without truncation still approaches the oracle as nn grows, with a slightly larger dimension (§ S7.9 of the Supplementary Material).

Suppose that λ^1>⋯>λ^K>λ^K+1\hat{\lambda}_1 > \cdots> \hat{\lambda}_K > \hat{\lambda}_{K+1}, let PK=∑j≤Kv^jv^jTP_K = \sum_{j \le K} \hat{v}_j \hat{v}_j^{\mathsf{T}} and b′=1.01λ^K+1b' = 1.01\hat{\lambda}_{K+1}, and let φ~k(λ)=Tk−1(2λ/b′−1)\tilde{\varphi}_k(\lambda) = T_{k-1}(2\lambda/b' - 1) be the Chebyshev polynomials on the bulk interval [0,b′][0,b']. The truncated Krylov space of dimension m+Km+K consists of the spectral estimators

β=∑k=1mckφ~k(Sn)(I−PK)sn+∑j=1Kdjv^jv^jTsn(c∈Rm, d∈RK),(13)\beta= \sum_{k=1}^{m} c_k \tilde{\varphi}_k(S_n)(I-P_K)s_n + \sum_{j=1}^{K} d_j \hat{v}_j \hat{v}_j^{\mathsf{T}}s_n \qquad(c \in\mathbb{R}^{m},\ d \in\mathbb{R}^{K}), \tag*{(13)}

whose filter is a polynomial of degree less than mm on the bulk eigenvalues λ^l\hat{\lambda}_l (l>Kl > K) and takes a free value djd_j at each of the KK separated eigenvalues. The coefficient djd_j sets the shrinkage factor λ^jdj\hat{\lambda}_j d_j of the jj-th direction. The leave-one-out version of (13) keeps (c,d)(c,d) fixed and uses the top KK eigenvectors of Sn(i)S_n^{(i)}, so its leave-one-out risk is again a least squares criterion in (c,d)(c,d) with m+Km+K exact leave-one-out features. We call the method risk-targeted Krylov fitting with truncation (RTK-C), which reduces to RTK for K=0K=0. Let v^j(i)\hat{v}_j^{(i)} be the jj-th eigenvector of Sn(i)S_n^{(i)} and PK(i)=∑j≤Kv^j(i)v^j(i)TP_K^{(i)} = \sum_{j \le K} \hat{v}_j^{(i)}\hat{v}_j^{(i)\mathsf{T}}. The leave-one-out features of the two kinds of terms form the matrices U~∈Rn×m\tilde{U} \in\mathbb{R}^{n \times m} and O∈Rn×KO \in\mathbb{R}^{n \times K} with entries

U~ik=xiTφ~k(Sn(i))(I−PK(i))sn(i),oij=xiTv^j(i)v^j(i)Tsn(i).\tilde{U}_{ik} = x_i^{\mathsf{T}}\tilde{\varphi}_k(S_n^{(i)})(I-P_K^{(i)})s_n^{(i)}, \qquad o_{ij} = x_i^{\mathsf{T}}\hat{v}_j^{(i)}\hat{v}_j^{(i)\mathsf{T}}s_n^{(i)}.

RTK-C minimizes n−1∥y−U~c−Od∥2n^{-1}\lVert y-\tilde{U}c-Od\rVert^2, so its coefficients in (13) solve the normal equations

(U~TU~U~TOOTU~OTO)(cd)=(U~TyOTy).\begin{pmatrix} \tilde{U}^{\mathsf{T}}\tilde{U} & \tilde{U}^{\mathsf{T}}O \\ O^{\mathsf{T}}\tilde{U} & O^{\mathsf{T}}O \end{pmatrix} \begin{pmatrix} c \\ d \end{pmatrix} = \begin{pmatrix} \tilde{U}^{\mathsf{T}}y \\ O^{\mathsf{T}}y \end{pmatrix}.

The bulk features U~\tilde{U} differ from UU because they are deflated by the top KK leave-one-out eigenvectors, and the features OO of the separated directions are new.

Fitting RTK requires only the leave-one-out moments of Theorem 1. The truncated space further requires the leave-one-out eigenvalues and eigenvectors of the KK separated directions, which the following proposition obtains from the same full-sample eigendecomposition through Lemma A1 in the Appendix.

Proposition 1. Let Tn=Qdiag⁡(λ^)QTT_n = Q \operatorname{diag}(\widehat{\lambda})Q^T and y~=QTy\widetilde{y} = Q^T y, suppose λ^1>⋯>λ^K>λ^K+1\widehat{\lambda}_1 > \cdots> \widehat{\lambda}_K > \widehat{\lambda}_{K+1}, and suppose that Qil≠0Q_{il} \ne0 for l≤K+1l \le K + 1, that is, observation ii has a nonzero loading on each of the top K+1K + 1 eigenvectors of TnT_n. For j≤Kj \le K, the function ψi(θ)=∑lQil2/(λ^l−θ)\psi_i(\theta) = \sum_l Q_{il}^2/(\widehat{\lambda}_l - \theta) has exactly one root λ^j(i)\widehat{\lambda}^{(i)}_j in (λ^j+1,λ^j)(\widehat{\lambda}_{j+1},\widehat{\lambda}_j), which is the jj-th largest eigenvalue of Tn(i)T_n^{(i)} and is simple. The feature of the jj-th separated direction is

oij=∑lQily~l/(λ^l−λ^j(i))∑lQil2/(λ^l−λ^j(i))2,o_{ij} = \frac{\sum_l Q_{il}\widetilde{y}_l/(\widehat{\lambda}_l - \widehat{\lambda}^{(i)}_j)}{\sum_l Q_{il}^2/(\widehat{\lambda}_l - \widehat{\lambda}^{(i)}_j)^2},

and the bulk features are U~ik=xiTφ~k(Sn(i))sn(i)−∑j≤Kφ~k(λ^j(i))oij\widetilde{U}_{ik} = x_i^T\widetilde{\varphi}_k(S_n^{(i)})s_n^{(i)} - \sum_{j \le K}\widetilde{\varphi}_k(\widehat{\lambda}^{(i)}_j)o_{ij}, where the first term is given by Theorem 1.

The proof of Proposition 1 is given in the Appendix. The bulk feature is the Krylov feature from Theorem 1 minus the contributions of the KK separated leave-one-out directions. All leave-one-out features of RTK-C therefore still follow from one eigendecomposition used for Theorem 1, and since ψi\psi_i increases between consecutive full-sample eigenvalues, bisection finds the nKnK roots at cost O(n2K)O(n^2K) per step. Section S6.2 of the Supplementary Material details the numerically stable implementation for spectra spanning several orders of magnitude.

In practice, we set KK to the number of eigenvalues of TnT_n that exceed 4 times their 90% quantile, capped at 8. This rule, which we call the resolution rule, removes the directions that would stretch the polynomial interval far beyond the bulk and gives K=0K = 0 when no eigenvalue lies far above it. In the simulations, it separated the settings in which truncation helps (§ S7.8 of the Supplementary Material). The bulk dimension mm is fixed in advance as for RTK in § 3.1.

Theory

This section shows that RTK nearly attains the smallest prediction risk in the mm-dimensional Krylov space and approaches the oracle risk as mm grows with nn. The gap between the risk of RTK and the oracle risk splits into two parts. The estimation error is the gap between the risk of RTK and the smallest risk (4) in Km\mathcal{K}_m. It arises because RTK minimizes a data-driven risk estimate R^\widehat{R} instead of the unknown prediction risk RR, and it grows with mm. The approximation error is the gap between the smallest risk in Km\mathcal{K}_m and the oracle risk R∞(h⋆)R_{\infty}(h^\star), and it decreases as mm grows. If R^\widehat{R} is close to RR uniformly over bounded coefficients, then minimizing R^\widehat{R} nearly minimizes RR. Section 4.1 proves that the leave-one-out risk has this property, and § 4.2 uses it to bound the estimation error for fixed mm and to compare RTK with PLS. Section 4.3 shows that the approximation error decays geometrically in mm when the oracle filter is analytic near the spectrum. Balancing the two errors then leads to mm of order log⁡n\log n and a polynomial rate of convergence to the oracle risk.

Uniform consistency of the leave-one-out risk

Under the following conditions, we prove that the risk estimate R^\widehat{R} is close to the unknown prediction risk RR uniformly over estimators in Km\mathcal{K}_m with bounded coefficients.

Assumption 1. The observations follow the linear model (6), and n,p→∞n,p \to\infty with p/n→γ∈(0,∞)p/n \to\gamma\in(0,\infty). In addition, (i) ∥Σ∥op\|\Sigma\|_{\mathrm{op}} is bounded; (ii) sup⁡a≠0E((aTx)8)/(aTΣa)4\sup_{a \ne0} E((a^T x)^8)/(a^T\Sigma a)^4 and E(y8)E(y^8) are bounded; (iii) there are constants C1C_1 and C2C_2 such that P(∥Sn∥op>C1)≤C2n−2P(\|S_n\|_{\mathrm{op}} > C_1) \le C_2n^{-2} for all nn.

Conditions (ii) and (iii) of Assumption 1 hold for Gaussian and sub-Gaussian designs x=Σ1/2zx = \Sigma^{1/2}z and for elliptical designs x=rΣ1/2zx = r\Sigma^{1/2}z with a bounded radius rr. For the former, P(∥Sn∥op>C1)P(\|S_n\|_{\mathrm{op}} > C_1) is

even exponentially small in nn. Elliptical designs with unbounded radius can violate (iii), because ∥Sn∥op\|S_n\|_{\mathrm{op}} then grows with max⁡iri2\max_i r_i^2.

The bounds below hold for any basis φ1,…,φm\varphi_1,\ldots,\varphi_m of the polynomials of degree less than mm (§ 2.2) and depend on it only through the largest value of ∣φk∣|\varphi_k| on a fixed contour around the spectrum of SnS_n. We work on the event of a bounded sample spectrum, Ωn={∥Sn∥op≤C1}\Omega_n=\{\|S_n\|_{\mathrm{op}}\le C_1\}, whose probability tends to one by Assumption 1(iii). Fix δ∈(0,1]\delta\in(0,1] and let Γ\Gamma be the positively oriented boundary of the δ\delta-neighborhood of [0,C1][0,C_1] in C\mathbb{C}. On Ωn\Omega_n, Γ\Gamma encloses the spectrum of SnS_n at distance at least δ\delta, so that φk(Sn)=−(2πi)−1∮Γφk(z)(Sn−zI)−1dz\varphi_k(S_n)=-(2\pi i)^{-1}\oint_\Gamma\varphi_k(z)(S_n-zI)^{-1}\mathrm{d}z with ∥(Sn−zI)−1∥op≤δ−1\|(S_n-zI)^{-1}\|_{\mathrm{op}}\le\delta^{-1} on Γ\Gamma. We therefore measure the basis by MΦ=max⁡ksup⁡z∈Γ∣φk(z)∣M_\Phi=\max_k\sup_{z\in\Gamma}|\varphi_k(z)|. Below, CC denotes a constant that depends only on δ\delta, sup⁡np/n\sup_n p/n and the constants in Assumption 1, not on mm or the basis, so that mm can grow with nn in § 4.3.

Theorem 2. Let G^=UTU/n\widehat{G}=U^\mathsf{T}U/n, ξ^=UTy/n\widehat{\xi}=U^\mathsf{T}y/n and R^(0)=∥y∥2/n\widehat{R}(0)=\|y\|^2/n be the coefficients of the leave-one-out risk (10), and let G=BTΣBG=B^\mathsf{T}\Sigma B, ξ=BTΣβ⋆\xi=B^\mathsf{T}\Sigma\beta^\star and R(0)R(0) be those of the population risk (8). Under Assumption 1, for all k,l∈{1,…,m}k,l\in\{1,\ldots,m\},

E(1{Ωn}∣G^kl−Gkl∣)≤CMΦ2n−1/2,E(1{Ωn}∣ξ^k−ξk∣)≤CMΦn−1/2,E(∣R^(0)−R(0)∣)≤Cn−1/2.\mathbb{E}\left(1\{\Omega_n\}|\widehat{G}_{kl}-G_{kl}|\right)\le CM_\Phi^2n^{-1/2},\quad\mathbb{E}\left(1\{\Omega_n\}|\widehat{\xi}_k-\xi_k|\right)\le CM_\Phi n^{-1/2},\quad\mathbb{E}\left(|\widehat{R}(0)-R(0)|\right)\le Cn^{-1/2}.

Consequently, for every cˉ≥0\bar{c}\ge0,

1{Ωn}sup⁡∥c∥≤cˉ∣R^(c)−R(c)∣≤C(1+cˉmMΦ)2n−1/2.1\{\Omega_n\}\sup_{\|c\|\le\bar{c}}|\widehat{R}(c)-R(c)|\le C(1+\bar{c}mM_\Phi)^2n^{-1/2}.

The proof of Theorem 2 is given in § S3 of the Supplementary Material. The errors of G^\widehat{G} and ξ^\widehat{\xi} matter since they determine the estimation error of RTK. The leave-one-out risk R^\widehat{R} is the quadratic RR with estimated coefficients, so a minimizer c^\widehat{c} of R^\widehat{R} over a bounded set C\mathcal{C} satisfies

R(c^)−min⁡c∈CR(c)≤2sup⁡c∈C∣cT(G^−G)c−2cT(ξ^−ξ)∣,(14)R(\widehat{c})-\min_{c\in\mathcal{C}}R(c)\le2\sup_{c\in\mathcal{C}}|c^\mathsf{T}(\widehat{G}-G)c-2c^\mathsf{T}(\widehat{\xi}-\xi)|, \tag*{(14)}

where the constant terms cancel since they do not depend on cc. Since c^\widehat{c} depends on the data, R^\widehat{R} needs to be close to RR uniformly over C\mathcal{C}, not only at a fixed cc. The right-hand side of (14) depends only on G^−G\widehat{G}-G and ξ^−ξ\widehat{\xi}-\xi, which Theorem 2 bounds.

To bound these errors, the proof uses that each feature Uik=xiTφk(Sn(i))sn(i)U_{ik}=x_i^\mathsf{T}\varphi_k(S_n^{(i)})s_n^{(i)} is a function of the leave-one-out quantities Sn(i)S_n^{(i)} and sn(i)s_n^{(i)} evaluated at the held-out xix_i. By the contour representation above, φk(Sn(i))\varphi_k(S_n^{(i)}) is an integral of the resolvent (Sn(i)−zI)−1(S_n^{(i)}-zI)^{-1} over Γ\Gamma, and removing one observation changes the resolvent by a rank-one update. The classical resolvent techniques of random matrix theory [2 Ch. 9] therefore control the perturbation of these functions. Existing consistency results for ridge regression [46], gradient descent paths [47] and ensembles [5] assume x=Σ1/2zx=\Sigma^{1/2}z with independent coordinates of zz, under which the quadratic forms xiTAxi/nx_i^\mathsf{T}Ax_i/n concentrate around tr⁡(ΣA)/n\operatorname{tr}(\Sigma A)/n. Since the contour representation and the rank-one updates are deterministic, our proof needs only bounded moments of these quadratic forms, so Theorem 2 also covers elliptical designs, for which this concentration fails. For gradient descent with stable step sizes summing to TT, MΦ≤TeδTM_\Phi\le Te^{\delta T}, so the theorem covers paths with TT of order at most log⁡n\log n.

Risk bounds and comparison with partial least squares

Theorem 2 and inequality (14) bound the estimation error of RTK, and the bound improves when the Krylov space is well conditioned. If GG is invertible, the risk (8) is minimized over Km\mathcal{K}_m by c⋆=G−1ξc^\star=G^{-1}\xi, and every other β=Bc\beta=Bc in Km\mathcal{K}_m has excess risk over Bc⋆Bc^\star

R(c)−R(c⋆)=(c−c⋆)TG(c−c⋆)=(β−Bc⋆)TΣ(β−Bc⋆).(15)R(c)-R(c^\star)=(c-c^\star)^\mathsf{T}G(c-c^\star)=(\beta-Bc^\star)^\mathsf{T}\Sigma(\beta-Bc^\star). \tag*{(15)}

Corollary 1. Let C={c∈Rm:∥c∥≤cˉ}C = \{c \in\mathbb{R}^{m}: \lVert c\rVert\le\bar{c}\}. Under Assumption 1, the following hold.

(a) A minimizer c^\hat{c} of R^\hat{R} over CC satisfies R(c^)−min⁡c∈CR=Op((1+cˉmMΦ)2n−1/2)R(\hat{c}) - \min_{c \in C} R = O_p\left((1+\bar{c}mM_{\Phi})^{2}n^{-1/2}\right).

(b) If the Krylov space is well conditioned, i.e. λmin⁡(G)≥κ>0\lambda_{\min}(G) \ge\kappa> 0 with probability tending to one and ∥c∗∥≤cˉ\lVert c^*\rVert\le\bar{c}, then the coefficients c^mRTK=G^−1ξ^\hat{c}^{\mathrm{RTK}}_m = \hat{G}^{-1}\hat{\xi} of § 3.1 satisfy ∥c^mRTK−c∗∥=Op(n−1/2)\lVert\hat{c}^{\mathrm{RTK}}_m-c^*\rVert= O_p(n^{-1/2}) and R(c^mRTK)−R(c∗)=Op(n−1)R(\hat{c}^{\mathrm{RTK}}_m)-R(c^*)=O_p(n^{-1}).

The proof of Corollary 1 is given in § S4 of the Supplementary Material. Part (a) holds without conditions on GG and is the form used in § 4.3, where mm grows. The ball CC only makes the uniform bound of Theorem 2 applicable, and RTK itself is unconstrained. Part (b) is the analogue of least squares on mm well-conditioned regressors, which has excess risk of order mσ2/nm\sigma^2/n.

Remark 4. For ordinary least squares and other linearly invariant estimates, Bates et al. [3] show that cross-validation is asymptotically uncorrelated with the risk given the data, so that it estimates the risk averaged over training data realizations. Risk-targeted Krylov fitting is not linearly invariant, and the proof of Theorem 2 treats its leave-one-out fluctuation directly by a leave-two-out argument. In the errors of G^\hat{G} and ξ^\hat{\xi}, this fluctuation is of order n−1/2n^{-1/2}, whereas the bias from fitting on n−1n-1 rather than nn observations is of order n−1n^{-1}, so the fluctuation determines the rate n−1/2n^{-1/2} in Theorem 2. The difference from Bates et al. [3] is that the leave-one-out risk is minimized rather than reported. As for M-estimators (Huber, [30]), a criterion too noisy to estimate the risk can still locate the minimizer of the risk. Since the risk is flat at its minimizer c∗c^*, a fluctuation of order n−1/2n^{-1/2} moves the minimizer by Op(n−1/2)O_p(n^{-1/2}) but raises the risk by only Op(n−1)O_p(n^{-1}) (Corollary 1(b)). This holds whether or not the fluctuation is correlated with the risk given the data.

The next result compares RTK and PLS in the same Krylov space.

Corollary 2. Under the conditions of Corollary 1(b),

R(β^mPLS)−R(β^mRTK)=(c^mPLS−c∗)TG(c^mPLS−c∗)−Op(n−1).R(\hat{\beta}^{\mathrm{PLS}}_m)-R(\hat{\beta}^{\mathrm{RTK}}_m)=(\hat{c}^{\mathrm{PLS}}_m-c^*)^{T}G(\hat{c}^{\mathrm{PLS}}_m-c^*)-O_p(n^{-1}).

The proof of Corollary 2 is given in § S4 of the Supplementary Material. By (15), the excess risk of PLS over R(c∗)R(c^*) is exactly (c^mPLS−c∗)TG(c^mPLS−c∗)(\hat{c}^{\mathrm{PLS}}_m-c^*)^{T}G(\hat{c}^{\mathrm{PLS}}_m-c^*), and that of RTK is Op(n−1)O_p(n^{-1}) by Corollary 1(b). Since BTSnBB^{T}S_nB and BTsnB^{T}s_n do not estimate GG and ξ\xi consistently, c^mPLS\hat{c}^{\mathrm{PLS}}_m does not converge to c∗c^* in general. The gap therefore persists as nn grows, while the excess risk of RTK decays like n−1n^{-1} (fig:S3 of the Supplementary Material).

Approximation of the oracle filter

Theorem 2 controls the estimation error over a fixed Krylov dimension. To approximate the oracle filter in general covariance, the dimension needs to grow with nn. A larger mm lowers the approximation error but raises the estimation error, and we quantify both by Bernstein ellipses around an interval that contains the spectrum. Let b>C1b>C_1 be fixed, so that [0,b][0,b] contains the spectrum of SnS_n on Ωn\Omega_n. For ρ>1\rho>1, let Eρ\mathcal{E}_{\rho} be the closed Bernstein ellipse of [0,b][0,b] centered at b/2b/2 with semi-axes b(ρ+ρ−1)/4b(\rho+\rho^{-1})/4 along the real axis and b(ρ−ρ−1)/4b(\rho-\rho^{-1})/4 along the imaginary axis. Two values of ρ\rho play different roles. First, choose ρΓ>1\rho_{\Gamma}>1 such that Γ\Gamma lies in EρΓ\mathcal{E}_{\rho_{\Gamma}}. Since ∣Tk(2z/b−1)∣≤ρΓk\lvert\mathcal{T}_k(2z/b-1)\rvert\le\rho_{\Gamma}^{k} for z∈Γz \in\Gamma, the Chebyshev basis satisfies MΦ≤ρΓm−1M_{\Phi}\le\rho_{\Gamma}^{m-1}, so ρΓ\rho_{\Gamma} controls how fast the estimation error of Theorem 2 grows with mm. Second, ρ∗\rho_* measures the smoothness of the filters we compare with, and it controls how fast the approximation error decays with mm.

For ρ∗>1\rho_*>1 and M∗>0M_*>0, let A(ρ∗,M∗)\mathcal{A}(\rho_*,M_*) be the class of filters that extend to analytic functions bounded by M∗M_* in the interior of Eρ∗\mathcal{E}_{\rho_*}. A larger ρ∗\rho_* means a smoother filter, which polynomials of degree less than mm approximate more accurately on [0,b][0,b] with error O(ρ∗−m)O(\rho_*^{-m}) (Trefethen, [58]). Lu et al. [42] consider a similar class of analytic filter functions with extra shape constraints, namely shrinkage factors in [0,1][0,1] that are non-decreasing and ridge-like, whereas A(ρ∗,M∗)\mathcal{A}(\rho_*,M_*) requires analyticity on an ellipse that does not change with nn. Let RA∗=inf⁡h∈AR(h(Sn)sn)R_{\mathcal{A}}^*=\inf_{h\in\mathcal{A}}R(h(S_n)s_n) be the risk of the best filter in this class given the data (Sn,sn)(S_n,s_n) at hand.

Theorem 3. Let β^m\hat{\beta}_m be risk-targeted Krylov fitting with the Chebyshev basis on [0,b][0,b] and coefficients constrained to ∥c∥≤2M∗(1−ρ∗−2)−1/2\lVert c\rVert\le2M_*(1-\rho_*^{-2})^{-1/2}, and let mn=⌊log⁡n/(2log⁡(ρ∗ρΓ2))⌋m_n=\lfloor\log n/(2\log(\rho_*\rho_{\Gamma}^{2}))\rfloor. Under Assumption 1,

R(β^mn)≤RA∗+Op(n−αlog⁡2n),α=log⁡ρ∗2log⁡ρ∗+4log⁡ρΓ∈(0,1/2).R(\hat{\beta}_{m_n})\le R_{\mathcal{A}}^*+O_p(n^{-\alpha}\log^2 n),\qquad\alpha=\frac{\log\rho_*}{2\log\rho_*+4\log\rho_{\Gamma}}\in(0,1/2).

The proof of Theorem 3 balances a Chebyshev approximation error against the estimation error of Theorem 2 and is given in § S4 of the Supplementary Material. Figure 2 shows this trade-off in a simulation. Ridge filters with levels bounded away from zero and rational filters with poles outside [0,b][0,b] belong to some A(ρ∗,M∗)\mathcal{A}(\rho_*,M_*). In particular, if the oracle filter h⋆h^\star of (2) belongs to A(ρ∗,M∗)\mathcal{A}(\rho_*,M_*), then RA∗≤R(h⋆(Sn)sn)R_{\mathcal{A}}^*\le R(h^\star(S_n)s_n), so the risk of RTK exceeds that of h⋆(Sn)snh^\star(S_n)s_n by at most Op(n−αlog⁡2n)O_p(n^{-\alpha}\log^2 n), and R(h⋆(Sn)sn)R(h^\star(S_n)s_n) converges to the oracle risk R∞(h⋆)R_\infty(h^\star).

Figure 2. Excess risk of risk-targeted Krylov fitting above that of the oracle filter h⋆h^\star, as a percentage of the excess risk of the oracle, in the latent-factor setting with γ=1.5\gamma= 1.5: against the Krylov dimension mm for nn from 250 to 4000 (left), and against nn for fixed mm (right). In the right panel the dashed line follows the best mm at each nn (printed below it), and the dash-dotted line is proportional to n−1n^{-1}. Means over 200 (n≤500n \le500), 100 (n=1000,2000n = 1000, 2000) and 50 (n=4000n = 4000) replicates. Bars in the right panel are ±1\pm1 standard error of the paired differences. Values for m=1m = 1, about 40% above the oracle, are not shown.

Remark 5. Theorem 3 requires the filter to be analytic around [0,b][0,b], but RTK also approaches the risk of filters that are only continuous on the spectrum, although without a rate. This covers the oracle for spiked covariance and other rational filters with poles in the gaps of the spectrum, and the filter 1{λ>τ}/λ1\{\lambda>\tau\}/\lambda of principal component regression with τ\tau in a gap. The reason is that a spectral estimator depends on its filter only through the values at the sample eigenvalues. Let ν^n=∑j(v^jTsn)2δλ^j\hat{\nu}_n=\sum_j(\hat{v}_j^\mathsf{T}s_n)^2\delta_{\hat{\lambda}_j}, so that ∥h(Sn)sn∥2=∫h2dν^n\lVert h(S_n)s_n\rVert^2=\int h^2\mathrm{d}\hat{\nu}_n. By (1) and the triangle inequality,

∣(R(β^h1)−σ2)1/2−(R(β^h2)−σ2)1/2∣≤∥Σ∥op1/2(∫(h1−h2)2dν^n)1/2.\left|(R(\hat{\beta}_{h_1})-\sigma^2)^{1/2}-(R(\hat{\beta}_{h_2})-\sigma^2)^{1/2}\right|\le\lVert\Sigma\rVert_{\mathrm{op}}^{1/2}\left(\int(h_1-h_2)^2\mathrm{d}\hat{\nu}_n\right)^{1/2}.

so the values of a filter where ν^n\hat{\nu}_n has no mass do not matter. Let N⊆[0,b]N\subseteq[0,b] be a closed set that contains the support of ν^n\hat{\nu}_n with probability tending to one. If hh is continuous on NN, the Weierstrass theorem gives for every ϵ>0\epsilon>0 a polynomial pϵp_\epsilon with ∣pϵ−h∣≤ϵ\lvert p_\epsilon-h\rvert\le\epsilon on NN. The measure ν^n\hat{\nu}_n has total mass ∥sn∥2\lVert s_n\rVert^2, so ∫(pϵ−h)2dν^n≤ϵ2∥sn∥2\int(p_\epsilon-h)^2\mathrm{d}\hat{\nu}_n\le\epsilon^2\lVert s_n\rVert^2. Since ∥sn∥=Op(1)\lVert s_n\rVert=O_p(1) and hh is bounded on the compact set NN, R(pϵ(Sn)sn)≤R(h(Sn)sn)+Op(ϵ)R(p_\epsilon(S_n)s_n)\le R(h(S_n)s_n)+O_p(\epsilon). With mm and the coefficient bound growing slowly in nn, Corollary 1(a) then shows that RTK attains R∞(h)R_\infty(h) up to op(1)o_p(1) for such h∈Fh\in\mathcal{F}, and the oracle risk if h⋆h^\star is of this form.

The rate of Theorem 3 degrades as ρ∗\rho_* approaches 1, which happens when the filter has a pole whose distance to [0,b][0,b] is small compared with the length of the interval. As discussed in § 3.3, a few outlying eigenvalues stretch [0,b][0,b], so even a pole at a moderate distance from the bulk falls into this case. The oracle filter may also have poles in the gaps of the spectrum. Such poles do not affect the risk (Remark 5), but they lie inside [0,b][0,b] and rule out the rate of Theorem 3. The truncated space fits the outlying directions separately and approximates the filter only on the much shorter bulk interval [0,b′][0,b'], which excludes these gaps. Compared with the length of this interval, the poles of the filter are typically far away. Let Eρ′\mathcal{E}'_{\rho} and A′(ρ,M)\mathcal{A}'(\rho,M) denote Eρ\mathcal{E}_{\rho} and A(ρ,M)\mathcal{A}(\rho,M) for this interval.

Proposition 2. Suppose that the restriction of hh to [0,b′][0,b'] belongs to A′(ρ′,M)\mathcal{A}'(\rho',M) for some ρ′>1\rho' > 1 and M>0M > 0, and Mout=max⁡j≤K∣h(λ^j)∣M_{\mathrm{out}} = \max_{j \le K} |h(\hat{\lambda}_j)| is finite.

(a) (Uniform approximation) There is a filter hmh_m of the form (13) with hm(λ^j)=h(λ^j)h_m(\hat{\lambda}_j) = h(\hat{\lambda}_j) (j≤Kj \le K) and sup⁡[0,b′]∣hm−h∣≤2Mρ′1−m/(ρ′−1)\sup_{[0,b']} |h_m - h| \le2M\rho'^{1-m}/(\rho' - 1).

(b) (Risk approximation) On Ωn\Omega_n, R(hm(Sn)sn)−R(h(Sn)sn)≤C(1+M+Mout)2ρ′−m(1+∥y∥2/n)R(h_m(S_n)s_n) - R(h(S_n)s_n) \le C(1 + M + M_{\mathrm{out}})^2\rho'^{-m}(1 + \lVert y\rVert^2/n), where CC depends also on ρ′\rho'.

(c) (Rational filters) The restriction to [0,b′][0,b'] of a rational filter ∑jwj/(λ+μj)\sum_j w_j/(\lambda+ \mu_j) with real poles at distance at least ε\varepsilon from [0,b′][0,b'] belongs to A′(ρ′,M)\mathcal{A}'(\rho',M), with ρ′=1+(ε/b′)1/2\rho' = 1 + (\varepsilon/b')^{1/2} and M=4∑j∣wj∣/(3ε)M = 4\sum_j |w_j|/(3\varepsilon), wherever the poles lie relative to λ^1,…,λ^K\hat{\lambda}_1,\ldots,\hat{\lambda}_K.

The proof of Proposition 2 is given in § S5 of the Supplementary Material. In part (b), the factor 1+∥y∥2/n=Op(1)1 + \lVert y\rVert^2/n = O_p(1) bounds the size of sns_n, since ∥sn∥2≤C1∥y∥2/n\lVert s_n\rVert^2 \le C_1\lVert y\rVert^2/n on Ωn\Omega_n. The positive poles of the oracle for spiked covariance all lie above the smallest outlying eigenvalue, so by part (c) the degree needed on the bulk is governed by the gap between the bulk and the outliers.

Remark 6. The results of §§ 4.1 and 4.2 extend to the truncated Krylov space with a fixed bulk interval under a gap condition (§ S5 of the Supplementary Material). The condition requires the spectrum of SnS_n to split with high probability into the bulk and KK eigenvalues in fixed windows away from it, also after one or two observations are removed. The fitted shrinkage factors λ^jd^j\hat{\lambda}_j\hat{d}_j are then within Op(n−1/2)O_p(n^{-1/2}) of the risk-optimal factors when the space is well conditioned, and Proposition 2 gives the analogue of Theorem 3 for the class A′(ρ′,M)\mathcal{A}'(\rho',M). The condition fails for near-critical spikes, whose outlying eigenvalues lie within the fluctuation scale of the bulk edge.

Simulations

Design

The simulations cover 3 parts. The first two examine the theory in § 4: § 5.2 follows PLS and RTK in the same Krylov space as mm grows, which isolates the gap of Corollary 2 and the estimation cost of Corollary 1(b), and § 5.3 follows the approach of RTK to the oracle filter as nn grows, which separates the approximation and estimation errors of Theorem 3. The third part, in § 5.4, is a systematic benchmark of RTK and RTK-C against 5 spectral estimators over 23 settings, chosen so that the oracle filter takes qualitatively different shapes.

Data are generated from the linear model (6) with x=Σ1/2zx = \Sigma^{1/2}z, z∼N(0,Ip)z \sim N(0,I_p), ϵ∼N(0,σ2)\epsilon\sim N(0,\sigma^2) independent of xx, σ2=1\sigma^2 = 1 and p=γnp = \gamma n. Without loss of generality, we take Σ\Sigma diagonal, so that its eigenvectors are the coordinate vectors eke_k. Two further settings in the Supplementary Material instead use the elliptical design x=rΣ1/2zx = r\Sigma^{1/2}z, with r2∈{0.25,1.75}r^2 \in\{0.25,1.75\} equally likely and independent of zz, whose coordinates are dependent although uncorrelated. The settings differ in the spectrum of Σ\Sigma and in how β⋆\beta^\star is distributed over its eigenspaces (Table 1). Ridge regression is the exact oracle in the isotropic setting. When one or two spikes carry the signal, the oracle amplifies the leading sample directions. When the largest of several spikes carries no signal, the oracle is non-monotone across the separated eigenvalues, and when the signal lies in one atom of a latent-factor or three-atom spectrum, it has a bump inside the sample spectrum. In the power-law settings the sample eigenvalues span several orders of magnitude.

We compare 7 estimators in the benchmark. Ridge regression (Ridge) chooses its regularization level by exact leave-one-out; principal component regression (PCR) chooses the number of components by tenfold cross-validation; PLS chooses m≤6m \le6 by approximate leave-one-out, which combines its normal equations (7) with the leave-one-out features of RTK; gradient descent (GD) chooses its stopping time by exact leave-one-out, computed from Theorem 1; and one-step selfλk\lambda_k, kkth eigenvalue of Σ\Sigma; aa, decay exponent of the signal. Components in an eigenspace, including the bulk, point in a uniformly random direction within it, scaled so that ∥β⋆∥2\lVert\beta^\star\rVert^2 is as given, and signs in the power-law settings are random. For the isotropic setting ∥β⋆∥2\lVert\beta^\star\rVert^2 is the expectation. In the three-atom setting the proportions are chosen so that the middle atom stays separated from the other two in the sample spectrum.

distillation (SD) [15] chooses its level and mixing weight by exact leave-one-out. Every tuning parameter thus targets the prediction risk, through its cross-validation estimate. RTK and RTK-C use m=5m=5 without further selection, and RTK-C chooses KK by the resolution rule of § 3.3. Sections 5.3 and 5.4 examine the choice of mm. Section 5.2 also includes the hybrid method of Chung et al. [11], whose regularization parameter is chosen at every step by weighted generalized cross-validation. As an infeasible benchmark, the oracle filter h⋆h^\star of (2) is approximated by the best linear combination of polynomials and resolvents, fitted to 50 independent draws of each setting at the same nn. For Gaussian designs, whose limiting risk R∞R_\infty is well defined [22], we directly computed h⋆h^\star by minimizing the explicit form of R∞(h)R_\infty(h) over the values of hh at the points of a fine grid on the limiting spectrum. The two filters nearly coincide, and their asymptotic excess risks differ by at most 0.6%, so the comparisons with the oracle below do not depend on how the oracle is computed (§ S7.2 of the Supplementary Material). Tuning grids and the construction of the oracle are described in § S7.1 of the Supplementary Material. We report the excess risk R(β^)−σ2R(\hat{\beta})-\sigma^2 of (1), computed exactly from Σ\Sigma and β⋆\beta^\star.

Stability in the Krylov dimension

As shown in Figure 1, the risk of PLS was smallest at 2–5 components and then rose toward that of the least squares solution. The risk of RTK rose by at most 20% up to m=20m=20, consistent with an estimation cost of order n−1n^{-1} per dimension (Corollary 1). At the best number of components of PLS the gap of Corollary 2 remained: RTK was 5 to 16% better. The largest gain was in the spike + bulk setting, in which PLS deteriorates little with mm but is worse at every mm. The hybrid method deteriorated almost as much as PLS, because its regularization parameter decreased with mm, so that its iterates drifted toward the unregularized conjugate gradient solution.

Figure 1. Excess risk against the Krylov dimension mm for estimators sharing the same Krylov space: partial least squares minimizing the empirical risk (PLS); risk-targeted Krylov fitting minimizing the exact leave-one-out risk (RTK); and the hybrid method (Hybrid) of Chung et al. [11], which applies Tikhonov regularization to the projected problem with its parameter chosen at every mm by weighted generalized cross-validation. Means over 20 replicates with n=400n = 400 and the same data for all methods. The settings are described in Table 1, and the values are listed in Table S2 of the Supplementary Material.

Settingγ\gammaSpectrum of Σ\SigmaSignal∥β⋆∥2\lVert\beta^\star\rVert^2
Isotropic1.5∗1.5^\astIpI_pN(0,2p−1Ip)N(0,2p^{-1}I_p)2
One spike1.5diag⁡(3,1,…,1)\operatorname{diag}(3,1,\ldots,1)e1e_11
Spike + bulk2∗2^\astdiag⁡(5,1,…,1)\operatorname{diag}(5,1,\ldots,1)1.7e1+bulk direction1.7e_1+\text{bulk direction}4
Two spikes1.5diag⁡(6,3,1,…,1)\operatorname{diag}(6,3,1,\ldots,1)0.7e1+0.8e2+bulk direction0.7e_1+0.8e_2+\text{bulk direction}1.38
Multiple spikes1.5diag⁡(32,16,8,4,1,…,1)\operatorname{diag}(32,16,8,4,1,\ldots,1)e2+e3e_2+e_32
Latent factor1.5∗1.5^\ast5% at 4, 95% at 1in the eigenvalue-4 space1.5
Three-atom1.55% at 12, 15% at 4, 80% at 1in the eigenvalue-4 space4
Mixed1.5half 1, half 2, one at 120.6e1+eigenvalue-2 space0.6e_1+\text{eigenvalue-2 space}1.86
Power law, a=0.6a=0.61.5∗1.5^\astλk∝k−0.7\lambda_k\propto k^{-0.7}, mean 1βk⋆∝±k−0.6\beta_k^\star\propto\pm k^{-0.6}2
Power law, a=1a=11.5λk∝k−0.7\lambda_k\propto k^{-0.7}, mean 1βk⋆∝±k−1\beta_k^\star\propto\pm k^{-1}2
Steep power law1.5λk∝k−0.9\lambda_k\propto k^{-0.9}, mean 1βk⋆∝±k−0.6\beta_k^\star\propto\pm k^{-0.6}2

Table 1. Simulation settings, with p=γnp=\gamma n

Approach to the oracle

In Figure 2, the gap between RTK and the oracle at fixed mm is the sum of an approximation error and an estimation error. The first is the excess risk of the best polynomial filter of degree less than mm over the oracle and does not depend on nn, and the second is of order n−1n^{-1} by Corollary 1(b). For each mm, we regressed the gap across the sample sizes of Figure 2 on n−1n^{-1} by weighted least squares, so that the intercept estimates the approximation error and the slope divided by nn estimates the estimation error. The residuals were within the Monte Carlo error (Table S3 of the Supplementary Material), so these two errors account for the gap. The approximation error decreased roughly

Ridge, ridge regression; PCR, principal component regression; PLS, partial least squares with m≤6m \le6 chosen by approximate leave-one-out; GD, gradient descent; SD, one-step self-distillation; RTK, risk-targeted Krylov fitting with m=5m = 5; RTK-C, risk-targeted Krylov fitting with truncation and m=5m = 5; Oracle, oracle filter h⋆h^\star, which is infeasible; –, not available (§ S7.1 of the Supplementary Material); aa, decay exponent of the signal. The smallest excess risk among the 7 estimators is in bold. Monte Carlo standard errors of the means are at most 0.038; differences between estimators, which are fitted to the same replicates, are estimated more precisely. Eleven of the 23 settings are shown. All are in Table S5 of the Supplementary Material.

geometrically in mm and was indistinguishable from zero for m≥9m \ge9, as expected for an oracle that is analytic near the spectrum, whereas each additional dimension added about 2σ2/n2\sigma^2/n to the excess risk, of the same order as the cost σ2/n\sigma^2/n of a regressor in least squares. In the right panel, the curve for m=2m = 2 therefore stays at its approximation error for every nn, whereas that for m=10m = 10 falls like n−1n^{-1}. As the curves cross, the best dimension grows with nn, from 2 for n≤500n \le500 to 6 for n≥2000n \ge2000. Along the best dimension (dashed line), the gap decreased like n−0.44n^{-0.44} between n=1000n = 1000 and 4000. This is slower than n−1n^{-1}, as the exponent α<1/2\alpha< 1/2 of Theorem 3 allows.

Because an unnecessary dimension costs only estimation error, overestimating the dimension is cheaper than underestimating it (§ 3.1), and the left panel shows the risk becoming flat in mm over a widening range as nn grows. The best dimension also exceeded the schedule mnm_n of Theorem 3, which stays at 2–3 over this range for typical constants because its bound allows the cost per dimension to grow exponentially in mm. In these simulations the cost did not grow. The fixed dimension m=5m = 5 used in § 5.4 was within 0.2 percentage points of the best one for n≥1000n \ge1000.

Comparison with other spectral estimators

RTK and RTK-C had lower excess risk than PLS in every setting, by up to 63%. No estimator dominated, and each was best where the oracle has a shape it can express: ridge regression in the isotropic settings and self-distillation in the settings in which a spike carries most of the signal. A competitor whose filter family contains the oracle has no approximation error and estimates one or two parameters instead of mm, so RTK cannot be expected to improve on it there. Its disadvantage in these settings is mainly an estimation cost of order n−1n^{-1} and shrank from n=400n = 400 to n=1000n = 1000 (Table S6 of the Supplementary Material). The truncated variant came closest to being uniformly good. It had the smallest excess risk in 13 of the 23 settings, and its excess risk was never more than about 1% above that of the best of the 7 estimators (Table S7 of the Supplementary Material).

Its largest gains came where the competing filters cannot follow the oracle: it was 20% better than self-distillation in the multiple-spike setting and up to 21% better in the power-law settings, and these gains persisted at n=400n=400. These are the only settings in which the resolution rule selected K>0K>0, and truncation lowered the excess risk in the power laws by up to 57%. In the other settings RTK and RTK-C coincide. Choosing mm by cross-validation instead of fixing m=5m=5 changed the excess risk only slightly (Table S8 of the Supplementary Material).

Figure 3 shows how these differences arise. In the one-spike and latent-factor settings the oracle shrinkage factors reach about 1.3 at the top of the spectrum, which ridge regression and principal component regression cannot attain. PLS departs from the oracle there, whereas RTK follows it closely. In the power-law setting the sample eigenvalues span 3 orders of magnitude. As anticipated in § 3.3, RTK then resolves the rise of the oracle on the bulk poorly, whereas free factors at the largest eigenvalues let the truncated variant follow it.

Figure 3. Shrinkage factors g(λ)=λh(λ)g(\lambda)=\lambda h(\lambda) at the sample eigenvalues for the first replicate of the one-spike, latent-factor and power-law (a=0.6a=0.6) settings of Table 2, against those of the oracle filter h⋆h^{\star} (dashed). The ticks at the bottom mark the sample eigenvalues, and the dotted line marks g=1g=1. In the one-spike and latent-factor settings the resolution rule selects K=0K=0, so RTK-C coincides with RTK and is omitted for clarity. Abbreviations as in Table 2.

Application to real data

We applied the estimators to single-cell sequencing data and large-scale neural population recordings, in both of which a response is predicted linearly from hundreds to thousands of correlated measurements. The single-cell data are 8 public data sets (Table S11 of the Supplementary Material): 4 from 10x Genomics and 4 Perturb-seq screens ([44, 50, 45]). Three of the 10x data sets are of peripheral blood mononuclear cells (PBMC) and the fourth is of embryonic mouse brain. One PBMC data set also includes 17 surface proteins measured by CITE-seq ([55]). After pretreatment as in Seurat ([53]) and Scanpy ([63]), each retains at most 2000 highly variable genes, and each task predicts a marker or perturbation-responsive gene from the other genes, or a surface protein from all genes. The neural data are from the visual cortex. In anesthetized macaques ([66]), the common fluctuation of the primary visual cortex (V1) population is first regressed out, and the mean activity of the recorded secondary visual cortex (V2) neurons is then predicted from about 100 V1 neurons, as in Semedo et al. [54]. In mice ([57]), the angle of a static grating is decoded from 2000 V1 neurons.

Data setTargetsPCRPLSGDSDRTKRTK-CW/T/L
PBMC 3k9 genes0.9540.9610.9470.9500.9390.9346/1/2
PBMC 10k13 genes0.9780.9910.9720.9711.0310.95610/3/0
Mouse brain 10k11 genes0.9700.9910.9730.9761.0020.9665/6/0
CITE-seq14 proteins0.9810.9870.9720.9701.0130.95011/3/0
Norman 2019, K56210 genes0.9940.9850.9730.9660.9630.9586/2/2
Replogle 2022, K56210 genes0.9871.0030.9750.9750.9700.9637/3/0
Replogle 2022, RPE110 genes0.9751.0030.9780.9820.9760.9638/2/0
Papalexi 2021, THP-110 genes0.9831.0020.9720.9730.9890.9619/1/0
Papalexi 2021, THP-14 proteins1.0031.0330.9920.9950.9931.0030/1/3

Table 3. Single-cell sequencing: test error relative to ridge regression (smaller is better)

Abbreviations as in Table 2; W/T/L, numbers of targets in which RTK-C was better than, indistinguishable from or worse than the best of the 5 competing estimators for that target, judged by a paired tt-statistic over the splits beyond ±2\pm2; pp, number of predictors; ntrainn_{\mathrm{train}}, number of training cells. Entries are medians over the targets of the ratio of the test mean squared error to that of ridge regression, averaged over 12 random splits with ntrain=p/1.5n_{\mathrm{train}} = p/1.5, and RTK and RTK-C use m=3m = 3. Medians are reported because the targets differ widely in how well they can be predicted. The smallest median among the 7 estimators is in bold.

Settingγ\gammaRidgePCRPLSGDSDRTKRTK-COracle
Isotropic1.51.2651.5581.3811.2881.2661.2741.2741.258
One spike1.50.7660.7340.6590.6390.5440.5510.5510.543
Spike + bulk22.1732.2112.0712.0291.6871.6821.6821.668
Two spikes1.50.8720.8740.7190.7440.6640.6430.6430.633
Multiple spikes1.50.7470.5800.4910.5070.3770.2990.3020.293
Latent factor1.50.9700.9240.7850.8140.7220.7010.7010.691
Three-atom1.52.3162.3572.1152.1302.0141.9981.9981.945
Mixed1.51.5221.7301.5251.4771.4541.4581.4581.444
Power law, a=0.6a = 0.61.50.6280.5930.6630.5150.5020.5580.4750.471
Power law, a=1a = 11.50.3890.2350.2280.2210.2050.1740.1620.158
Steep power law1.50.4680.4410.9900.3870.3880.8600.370–

Table 2. Simulations: mean excess risk R(β^)−σ2R(\hat{\beta}) - \sigma^2 over 30 replicates, n=1000n = 1000

p/ntrainp/n_{\mathrm{train}}ntrainn_{\mathrm{train}}mmRidgePCRPLSGDSDRTKRTK-C
Macaque V1 to V2: prediction of the averaged V2 activity
1.559–10520.4640.4390.4510.4690.4480.4700.469
188–15820.4970.4800.4840.5050.4830.5060.503
0.5176–31620.5360.5190.5250.5430.5360.5430.538
0.28–0.4932020.5450.5280.5390.5500.5470.5500.548
Mouse V1: decoding of the grating angle
0.53–0.573490–375950.6190.6040.6160.6290.6280.6260.629
0.85–0.922181–234950.5900.5790.5890.6030.6030.6020.603

Table 4. Neural recordings: mean out-of-sample R2R^2 (larger is better)

Abbreviations as in Table 2; pp, number of neurons; ntrainn_{\mathrm{train}}, number of training trials; mm, Krylov dimension of RTK and RTK-C. The macaque data comprise 40 data sets with 88 to 158 V1 neurons and 400 trials, with 100 random splits each, and the mouse data 12 tasks with 2000 neurons and 4362 to 4699 trials, with 3 random splits each. Means are reported because each row predicts the same type of response in all data sets or tasks. The largest R2R^2 among the 7 estimators is in bold.

All methods use the same random splits into training and test sets and the tuning of § 5. The methods are compared by the test mean squared error or the out-of-sample R2R^2. Following § 5.3, the Krylov dimension was fixed in advance and increased with the training size: m=2m = 2 for the macaque data (at most 320 training trials), m=3m = 3 for the single-cell data (about 1000 training cells) and m=5m = 5 for the mouse data (2000–4000 training trials). Details are given in §§ S8.1–S8.3 of the Supplementary Material.

In the single-cell data the truncated variant was most accurate in all groups of targets but one, and it was better than the best competing estimator in most tasks (Table 3). The exception is the surface proteins of the THP-1 screen, which all methods predict poorly. Without truncation, RTK lost mainly in the 10x data sets with the widest spectra, where the leading eigenvalues stretch the interval on which the polynomial needs to be accurate, as the argument of § 3.3 predicts. In the neural data the methods were closer to one another (Table 4). RTK or RTK-C had the largest or nearly the largest out-of-sample R2R^2 at every training size. RTK was best in the macaque data, in which only 2–3 eigenvalues were separated from the bulk, and early-stopped gradient descent and self-distillation came close at the larger training sizes. The leading eigenvalues of the mouse data lie far outside the bulk, and there RTK-C, early-stopped gradient descent and self-distillation had mean R2R^2 within 0.001 of one another. Ridge regression, principal component regression and PLS were less accurate than RTK-C in most groups of single-cell targets and than both RTK and RTK-C at every training size in the neural data.

Discussion

We proposed risk-targeted Krylov fitting, which targets the oracle risk directly instead of estimating the oracle filter. The oracle risk, previously attained only by filters tailored to special covariance structures, can thus be approached adaptively, without prior knowledge of the structure. More broadly, RTK follows two principles: nested spaces of spectral estimators whose smallest risk tends to the oracle one, and a criterion that estimates the risk uniformly over these spaces. This view explains why the Krylov space of PLS is a good starting point, even though the empirical risk that PLS minimizes is not. First, the shrinkage factors of PLS oscillate and can exceed one ([20, 9, 35] (Lingjærde & Christophersen 2000)). These long-recognized peculiarities show that the Krylov space contains filters of the shapes that the oracle filter may require, whereas the more common spectral estimators shrink monotonically and never amplify. Second, the leave-one-out features of the Krylov space follow from one eigendecomposition through the recursion of Theorem 1, so that the exact leave-one-out risk can be minimized without refitting.

This view also suggests directions for future work, mainly in the choice of the space. Truncation is one such choice, and it helps only when a few eigenvalues lie far above the bulk. On spectra spanning a wide range of scales, rational approximation with geometrically spaced poles typically outperforms polynomials ([23]), which suggests rational Krylov spaces ([51]) spanned by the ridge estimators (Sn+μkI)−1Sn(S_n+\mu_k I)^{-1}S_n at fixed μk>0\mu_k>0. Their exact leave-one-out features follow from Lemma A1 with z=−μkz=-\mu_k, and the proof of Theorem 2 carries over because these filters are holomorphic near the spectrum. What remains is the choice of the poles and an analogue of Theorem 3. Beyond linear regression, the leave-one-out features of Theorem 1 are exact for kernel regression in any regime, and the theory of § 4 may extend to inner-product kernels in the polynomial regime n≍pζn\asymp p^\zeta with ζ>0\zeta>0 ([29, 42]. Block Krylov spaces suggest a further extension to multivariate responses ([13]). Finally, any estimate of the risk that is uniformly consistent over the spaces could replace the exact leave-one-out risk, and one with smaller fluctuation may reduce the estimation error that each dimension adds to (15).

Several questions remain open. The practical choices of mm and KK have no guarantees yet. The schedule of Theorem 3 is the only data-independent choice we analyze, and its rate is likely improvable by choosing Chebyshev polynomials on the real spectrum rather than on a complex contour. In the simulations of § 5.3 the estimation cost per dimension did not grow with mm, and the best dimension exceeded the schedule. Theorem 2 requires a polynomial tail bound on ∥Sn∥op\lVert S_n\rVert_{\mathrm{op}}, which excludes elliptical designs with heavy-tailed radius. Exact leave-one-out costs one n×nn\times n eigendecomposition, and this cost is no longer negligible for very large nn. Theorem 1 needs only the local response moments (Tnjy)i(T_n^jy)_i, which cost mm matrix-vector products, and the diagonals (Tnj)ii(T_n^j)_{ii}. Replacing these diagonals by their average, which for ridge regression gives generalized cross-validation, fails under elliptical designs (Remark 3), so combining Theorem 1 with randomized estimation of the diagonals is a natural direction.

Declaration of the use of generative AI and AI-assisted technologies

During the preparation of this work the authors used Claude and Claude Code (Anthropic) in order to condense the manuscript, edit its structure and wording, check the theorems and their proofs, and organize the code. After using these tools the authors reviewed and edited the content as necessary and take full responsibility for the content of the publication.

Supplementary material

The Supplementary Material includes the proofs of all results not proved in the main text or the Appendix, implementation details, additional simulation results and details of the real-data applications. The implementation details cover the computation of the features of the separated directions and of leave-one-out predictions along gradient descent paths, and the Chebyshev form of Algorithm 1 used in our computations. The additional simulation results include a comparison of rules for the truncation. Python code that reproduces the simulations of § 5 is available at https://doi.org/10.5281/zenodo.23755357.

Appendix 1

Proofs of Theorem 1 and Proposition 1

Lemma A1. Let A∈Rn×nA \in\mathbb{R}^{n \times n} be symmetric, let A(i)A^{(i)} be AA without its ii-th row and column and αi=A−i,i∈Rn−1\alpha_i = A_{-i,i} \in\mathbb{R}^{n-1} its ii-th column without the diagonal entry, and let z∈Cz \in\mathbb{C} with z∉spec⁡(A)∪spec⁡(A(i))z \notin\operatorname{spec}(A) \cup\operatorname{spec}(A^{(i)}). Write D=zI−A(i)D = zI - A^{(i)} and ωi(z)=yi+αiTD−1y(i)\omega_i(z) = y_i + \alpha_i^{T}D^{-1}y^{(i)}. Then ((zI−A)−1)ii=(z−Aii−αiTD−1αi)−1≠0\left((zI-A)^{-1}\right)_{ii} = (z-A_{ii}-\alpha_i^{T}D^{-1}\alpha_i)^{-1} \ne0 and

((zI−A)−1y)i=((zI−A)−1)iiωi(z).\left((zI-A)^{-1}y\right)_i = \left((zI-A)^{-1}\right)_{ii}\omega_i(z).

Proof. Order the coordinate ii first, so that zI−AzI-A has blocks z−Aiiz-A_{ii}, −αiT-\alpha_i^{T}, −αi-\alpha_i and DD, and let τ=z−Aii−αiTD−1αi\tau= z-A_{ii}-\alpha_i^{T}D^{-1}\alpha_i. Since det⁡(zI−A)=det⁡(D)τ\det(zI-A)=\det(D)\tau and zI−AzI-A is invertible, τ≠0\tau\ne0. Block inversion gives

(zI−A)−1=(τ−1τ−1αiTD−1τ−1D−1αiD−1+τ−1D−1αiαiTD−1).(zI-A)^{-1} = \begin{pmatrix} \tau^{-1} & \tau^{-1}\alpha_i^{T}D^{-1}\\ \tau^{-1}D^{-1}\alpha_i & D^{-1}+\tau^{-1}D^{-1}\alpha_i\alpha_i^{T}D^{-1} \end{pmatrix}.

The first row applied to yy gives ((zI−A)−1y)i=τ−1ωi(z)\left((zI-A)^{-1}y\right)_i=\tau^{-1}\omega_i(z).

Proof of Theorem 1. We prove (12) for a general symmetric AA in place of TnT_n, with vi,a=(Aay)iv_{i,a}=(A^a y)_i and ui,a=αiT(A(i))a−1y(i)u_{i,a}=\alpha_i^{T}(A^{(i)})^{a-1}y^{(i)} for a≥1a \ge1 and ui,0=vi,0=yiu_{i,0}=v_{i,0}=y_i. For ∣z∣>∥A∥op|z|>\lVert A\rVert_{\mathrm{op}}, which also exceeds ∥A(i)∥op\lVert A^{(i)}\rVert_{\mathrm{op}} by interlacing, the Neumann series converge absolutely and give

((zI−A)−1)ii=∑j≥0(Aj)iizj+1,((zI−A)−1y)i=∑a≥0vi,aza+1,ωi(z)=∑a≥0ui,aza.\left((zI-A)^{-1}\right)_{ii}=\sum_{j\ge0}\frac{(A^j)_{ii}}{z^{j+1}},\qquad \left((zI-A)^{-1}y\right)_i=\sum_{a\ge0}\frac{v_{i,a}}{z^{a+1}},\qquad \omega_i(z)=\sum_{a\ge0}\frac{u_{i,a}}{z^a}.

by the definition of ui,au_{i,a}. By Lemma A1, the second series is the product of the first and the third. Comparing the coefficients of z−a−1z^{-a-1} gives vi,a=∑j=0a(Aj)iiui,a−jv_{i,a}=\sum_{j=0}^{a}(A^j)_{ii}u_{i,a-j}, which is (12) because (A0)ii=1(A^0)_{ii}=1.

For A=TnA=T_n we have αi=ti=X(i)Txi/n\alpha_i=t_i=X^{(i)T}x_i/n, where X(i)X^{(i)} is XX without its ii-th row. Since Sn(i)T=X(i)TTn(i)X(i)S_n^{(i)T}=X^{(i)T}T_n^{(i)}X^{(i)} induction gives (Sn(i))aX(i)T=X(i)T(Tn(i))a(S_n^{(i)})^aX^{(i)T}=X^{(i)T}(T_n^{(i)})^a, and therefore xiT(Sn(i))axi/n=xi(i)T(Tn(i))ay(i)/n=tiT(Tn(i))ay(i)x_i^{T}(S_n^{(i)})^a x_i/n=x_i^{(i)T}(T_n^{(i)})^a y^{(i)}/n=t_i^{T}(T_n^{(i)})^a y^{(i)}. The leave-one-out moments of Theorem 1 are thus the ui,au_{i,a} above with A=TnA=T_n. □

Proof of Proposition 1. Let X(i)=∑rσrarbrTX^{(i)}=\sum_r \sigma_r a_r b_r^T be a singular value decomposition with σr>0\sigma_r>0. Then Sn(i)br=(σr2/n)brS_n^{(i)}b_r=(\sigma_r^2/n)b_r, Tn(i)ar=(σr2/n)arT_n^{(i)}a_r=(\sigma_r^2/n)a_r, Sn(i)=n−1∑rσrbr(arTy(i))S_n^{(i)}=n^{-1}\sum_r\sigma_r b_r(a_r^Ty^{(i)}), and ti=X(i)Txi/nt_i=X^{(i)T}x_i/n is orthogonal to the null space of Tn(i)T_n^{(i)}. Hence, for every function ϕ\phi on the spectrum, xiTϕ(Sn(i))si(i)=tiTϕ(Tn(i))y(i)x_i^T\phi(S_n^{(i)})s_i^{(i)}=t_i^T\phi(T_n^{(i)})y^{(i)}. Let μ1>μ2>⋯\mu_1>\mu_2>\cdots be the distinct eigenvalues of Tn(i)T_n^{(i)}, Πr\Pi_r the corresponding spectral projectors and kr=tiTΠry(i)k_r=t_i^T\Pi_r y^{(i)}, so that tiTϕ(Tn(i))y(i)=∑rϕ(μr)krt_i^T\phi(T_n^{(i)})y^{(i)}=\sum_r\phi(\mu_r)k_r. By Lemma A1 with A=TnA=T_n and the eigendecomposition of TnT_n, for zz outside both spectra,

Ni(z)Di(z)−yi=∑rκrz−μr,Ni(z)=∑lQily~lz−λ^l,Di(z)=∑lQil2z−λ^l=−ψi(z).(16)\frac{N_i(z)}{D_i(z)}-y_i=\sum_r\frac{\kappa_r}{z-\mu_r},\qquad N_i(z)=\sum_l\frac{Q_{il}\widetilde y_l}{z-\widehat\lambda_l},\qquad D_i(z)=\sum_l\frac{Q_{il}^2}{z-\widehat\lambda_l}=-\psi_i(z). \tag*{(16)}

On (λ^j+1,λ^j)(\widehat\lambda_{j+1},\widehat\lambda_j), ψi′(θ)=∑lQil2/(λ^l−θ)2>0\psi_i'(\theta)=\sum_l Q_{il}^2/(\widehat\lambda_l-\theta)^2>0, and ψi(θ)→+∞\psi_i(\theta)\to+\infty as θ↑λ^j+1\theta\uparrow\widehat\lambda_{j+1} and ψi(θ)→−∞\psi_i(\theta)\to-\infty as θ↓λ^j+1\theta\downarrow\widehat\lambda_{j+1}, because QijQ_{ij} and Qi,j+1Q_{i,j+1} are nonzero. Hence ψi\psi_i has exactly one root λ^j(i)\widehat\lambda_j^{(i)} there. With eie_i the ii-th standard basis vector of Rn\mathbb{R}^n, the vector q~=(Tn−λ^j(i)I)−1ei\widetilde q=(T_n-\widehat\lambda_j^{(i)}I)^{-1}e_i has ii-th coordinate ψi(λ^j(i))=0\psi_i(\widehat\lambda_j^{(i)})=0, so the rows k≠ik\ne i of (Tn−λ^j(i)I)q~=ei(T_n-\widehat\lambda_j^{(i)}I)\widetilde q=e_i give (Tn−λ^j(i)I)q~(i)=0(T_n-\widehat\lambda_j^{(i)}I)\widetilde q^{(i)}=0 with q~(i)≠0\widetilde q^{(i)}\ne0, and λ^j(i)\widehat\lambda_j^{(i)} is an eigenvalue of Tn(i)T_n^{(i)}. Cauchy interlacing places the jj-th largest eigenvalue of Tn(i)T_n^{(i)}, counted with multiplicity, in [λ^j+1,λ^j][\widehat\lambda_{j+1},\widehat\lambda_j] and the neighboring ones in [λ^j,λ^j−1][\widehat\lambda_j,\widehat\lambda_{j-1}] and [λ^j+2,λ^j+1][\widehat\lambda_{j+2},\widehat\lambda_{j+1}], with λ^0=∞\widehat\lambda_0=\infty. Since the top K+1K+1 eigenvalues of TnT_n are simple, λ^j(i)\widehat\lambda_j^{(i)} is the jj-th largest eigenvalue μj\mu_j of Tn(i)T_n^{(i)} and is simple. As λ^j(i)\widehat\lambda_j^{(i)} is a simple zero of DiD_i, with Di′(λ^j(i))=−∑lQil2/(λ^l−λ^j(i))2<0D_i'(\widehat\lambda_j^{(i)})=-\sum_l Q_{il}^2/(\widehat\lambda_l-\widehat\lambda_j^{(i)})^2<0, and not a pole of NiN_i, the residue of the left-hand side of (A1) at λ^j(i)\widehat\lambda_j^{(i)} is Ni(λ^j(i))/Di′(λ^j(i))=oijN_i(\widehat\lambda_j^{(i)})/D_i'(\widehat\lambda_j^{(i)})=o_{ij}, and that of the right-hand side is κj\kappa_j. The jj-th separated direction corresponds to ϕ=1{λ=μj}\phi=1\{\lambda=\mu_j\}, whose feature is κj=oij\kappa_j=o_{ij}, and the kk-th bulk basis vector to ϕ(λ)=φ~k(λ)1{λ∉{μ1,…,μK}}\phi(\lambda)=\widetilde\varphi_k(\lambda)1\{\lambda\notin\{\mu_1,\ldots,\mu_K\}\}, whose feature is ∑rφ~k(μr)κr−∑j≤Kφ~k(μj)κj=titφ~k(Tn(i))y(i)−∑j≤Kφ~k(λ^j(i))oij\sum_r\widetilde\varphi_k(\mu_r)\kappa_r-\sum_{j\le K}\widetilde\varphi_k(\mu_j)\kappa_j=t_i^t\widetilde\varphi_k(T_n^{(i)})y^{(i)}-\sum_{j\le K}\widetilde\varphi_k(\widehat\lambda_j^{(i)})o_{ij}. □

References

  1. [1]Allen, D. M. (1974). The relationship between variable selection and data augmentation and a method for prediction. Technometrics 16, 125–127.DOI
  2. [2]Bai, Z. & Silverstein, J. W. (2010). Spectral Analysis of Large Dimensional Random Matrices. Springer Series in Statistics. New York: Springer, 2nd ed.DOI
  3. [3]Bates, S., Hastie, T. & Tibshirani, R. (2024). Cross-validation: What does it estimate and how well does it do it? Journal of the American Statistical Association 119, 1434–1445.
  4. [4]Bauer, F., Pereverzev, S. & Rosasco, L. (2007). On regularization algorithms in learning theory. Journal of complexity 23, 52–72.
  5. [5]Bellec, P. C., Du, J.-H., Koriyama, T., Patil, P. & Tan, K. (2025). Corrected generalized cross-validation for finite ensembles of penalized estimators. Journal of the Royal Statistical Society Series B: Statistical Methodology 87, 289–318.arxiv.org/abs/2310.01374
  6. [6]Bellec, P. C. & Tan, K. (2026). Uncertainty quantification for iterative algorithms in linear models with application to early stopping. The Annals of Statistics 54, 1315–1344.arxiv.org/abs/2404.17856
  7. [7]Boulesteix, A. L. & Strimmer, K. (2007). Partial least squares: a versatile tool for the analysis of high-dimensional genomic data. Briefings in Bioinformatics 8, 32–44.
  8. [8]Breiman, L. (1996). Stacked regressions. Machine learning 24, 49–64.DOI
  9. [9]Butler, N. A. & Denham, M. C. (2000). The peculiar shrinkage properties of partial least squares regression. Journal of the Royal Statistical Society Series B-Statistical Methodology 62, 585–593.DOI
  10. [10]Chun, H. & Keles, S. (2010). Spare partial least squares regression for simultaneous dimension reduction and variable selection. Journal of the Royal Statistical Society Series B-Statistical Methodology 72, 3–25.pubmed.ncbi.nlm.nih.gov/20107611
  11. [11]Chung, J., Nagy, J. G. & O’Leary, D. P. (2008). A weighted-GCV method for Lanczos-hybrid regularization. Electronic Transactions on Numerical Analysis 28, 149–167.
  12. [12]Cook, R. D. & Forzani, L. (2019). Partial least squares prediction in high-dimensional regression. Annals of Statistics 47, 884–908.DOI
  13. [13]Cook, R. D., Helland, I. S. & Su, Z. (2013). Envelopes and partial least squares regression. Journal of the Royal Statistical Society Series B: Statistical Methodology 75, 851–877.DOI
  14. [14]Craven, P. & Wahba, G. (1978). Smoothing noisy data with spline functions. Numerische Mathematik 31, 377–403.DOI
  15. [15]Dang, H., Patil, P. & Rinaldo, A. (2026). Optimal unconstrained self-distillation in ridge regression: strict improvements, precise asymptotics, and one-shot tuning. In Proc. 43rd Int. Conf. Mach. Learn., vol. 306. arXiv: 2602.17565.arxiv.org/abs/2602.17565
  16. [16]Ding, X. & Trogdon, T. (2022). The conjugate gradient algorithm on a general class of spiked covariance matrices. Quart. Appl. Math. 80, 99–155.arxiv.org/abs/2106.13902
  17. [17]Dorriban, E. & Wager, S. (2018). High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics 46, 247–279.
  18. [18]EBRAHIMI, S., LECOQ, J., RUMYANTSEV, O., TASCI, T., ZHANG, Y., IRIMIA, C., LI, J., GANGULI, S. & SCHNITZER, M. J. (2022). Emergent reliability in sensory cortical coding and inter-area communication. Nature 605, 713–721.DOI
  19. [19]EL KAROUI, N. (2008). Spectrum estimation for large dimensional covariance matrices using random matrix theory. Annals of Statistics 36, 2757–2790.arxiv.org/abs/math/0609418
  20. [20]FRANK, I. E. & FRIEDMAN, J. H. (1993). A statistical view of some chemometrics regression tools. Technometrics 35, 109–135.
  21. [21]GOLUB, G. H., HEATH, M. & WAHBA, G. (1979). Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215–223.DOI
  22. [22]GREEN, A. & ROMANOV, E. (2025). The high-dimensional asymptotics of principal component regression. The Annals of Statistics 53, 1697–1727, 31.DOI
  23. [23]GÜTTEL, S. (2013). Rational krylov approximation of matrix functions: Numerical methods and optimal pole selection. GAMM-Mitteilungen 36, 8–31.DOI
  24. [24]HANSEN, B. E. & RACINE, J. S. (2012). Jackknife model averaging. Journal of Econometrics 167, 38–46.DOI
  25. [25]HANSEN, P. C. (2010). Discrete inverse problems: insight and algorithms. SIAM.
  26. [26]HASTIE, T., MONTANARI, A., ROSSET, S. & TIBSHIRANI, R. J. (2022). Surprises in high-dimensional ridgeless least squares interpolation. Annals of Statistics 50, 949–986.DOI
  27. [27]HELLAND, I. S. (1988). On the structure of partial least squares regression. Communications in Statistics - Simulation and Computation 17, 581–607.DOI
  28. [28]HELMER, M., WARRINGTON, S., MOHAMMADI-NEJAD, A. R., JI, J. L., HOWELL, A., ROSAND, B., ANTICEVIC, A., SOTIROPOULOS, S. N. & MURRAY, J. D. (2024). On the stability of canonical correlation analysis and partial least squares with application to brain-behavior associations. Communications Biology 7.
  29. [29]HU, H., LU, Y. M. & MISIAKIEWICZ, T. (2024). Asymptotics of random feature regression beyond the linear scaling regime. arXiv:2403.08160.arxiv.org/abs/2403.08160
  30. [30]HUBER, P. J. (1967). The behavior of maximum likelihood estimates under nonstandard conditions. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, vol. 1. Berkeley, CA.
  31. [31]HÖSKULDSSON, A. (1988). PLS regression methods. Journal of Chemometrics 2, 211–228.DOI
  32. [33]KONG, W. H. & VALLIANT, G. (2017). Spectrum estimation from samples. Annals of Statistics 45, 2218–2247.arxiv.org/abs/1602.00061
  33. [34]KRISHNAN, A., WILLIAMS, L. J., MCINTOSH, A. R. & ABDI, H. (2011). Partial least squares (PLS) methods for neuroimaging: A tutorial and review. Neuroimage 56, 455–475.DOI
  34. [35]KRÄMER, N. (2007). An overview on the shrinkage properties of partial least squares regression. Computational Statistics 22, 249–273.DOI
  35. [36]KRÄMER, N. & SUGIYAMA, M. (2011). The degrees of freedom of partial least squares regression. Journal of the American Statistical Association 106, 697–705.arxiv.org/abs/1002.4112
  36. [37]KURNIA, A., SARTONO, B., RAMADHAN, M. A., RAHARDIANTORO, S. & YANTI, Y. (2021). Stacking method for determining weights in partial least squares model averaging. Journal of Mathematical and Computational Science 11, 2193–2203.DOI
  37. [39]LEDOIT, O. & WOLF, M. (2017). Numerical implementation of the quest function. Computational Statistics & Data Analysis 115, 199–223.
  38. [41]LO GERFO, L., ROSASCO, L., ODONE, F., DE VITO, E. & VERRI, A. (2008). Spectral algorithms for supervised learning. Neural Computation 20, 1873–1897.DOI
  39. [42]LU, W., LIN, Q., XIA, Y. & HUANG, D. (2026). Learning curves and benign overfitting of spectral algorithms in large dimensions. arXiv preprint arXiv:2604.23212 .
  40. [43]MOU, Y., CHEN, W. Z. & LIU, J. G. (2025). Total partial least square regression and its application in infrared spectra quantitative analysis. Measurement 247.DOI
  41. [44]NORMAN, T. M., HORLBECK, M. A., REPLOGLE, J. M., GE, A. Y., XU, A., JOST, M., GILBERT, L. A. & WEISSMAN, J. S. (2019). Exploring genetic interaction manifolds constructed from rich single-cell phenotypes. Science 365, 786–+.DOI
  42. [45]PAPALEXI, E., MIMITOU, E. P., BUTLER, A. W., FOSTER, S., BRACKEN, B., MAUCK, W. M., WESSELS, H. H., HAO, Y. H., YEUNG, B. Z., SMIBERT, P. & SATIJA, R. (2021). Characterizing the molecular regulation of inhibitory immune checkpoints with multimodal single-cell screens. Nature Genetics 53, 322–331.DOI
  43. [46]PATIL, P., WEI, Y., RINALDO, A. & TIBSHIRANI, R. (2021). Uniform consistency of cross-validation estimators for high-dimensional ridge regression. In International conference on artificial intelligence and statistics. PMLR.
  44. [47]PATIL, P., WU, Y. & TIBSHIRANI, R. (2024). Failures and successes of cross-validation for early-stopped gradient descent. In International Conference on Artificial Intelligence and Statistics. PMLR.arxiv.org/abs/2402.16793
  45. [48]PHATAK, A. & DE HOOG, F. (2002). Exploiting the connection between PLS, Lanczos methods and conjugate gradients: alternative proofs of some properties of PLS. Journal of Chemometrics 16, 361–367.DOI
  46. [49]Rad, K. R. & Maleki, A. (2020). A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation. Journal of the Royal Statistical Society Series B: Statistical Methodology 82, 965–996.
  47. [50]Replogle, J. M., Saunders, R. A., Pogson, A. N., Hussmann, J. A., Lenail, A., Guna, A., Mascibroda, L., Wagner, E. J., Ader, J. J., Aldana, K., Lithwick-Yangi, G., Iremadze, N., Oberstrass, F., Lipson, D., Bonnar, J. L., Jost, M., Norman, T. M. & Weissman, J. S. (2022). Mapping information-rich genotype-phenotype landscapes with genome-scale perturb-seq. Cell 185, 2559–+.DOI
  48. [51]Ruhe, A. (1998). Rational krylov: A practical algorithm for large sparse nonsymmetric matrix pencils. Siam Journal on Scientific Computing 19, 1535–1551.
  49. [52]Rumyantsev, O. I., Lecoq, J. A., Hernandez, O., Zhang, Y., Savall, J., Chrapkiewicz, R., Li, J., Zeng, H., Ganguli, S. & Schnitzer, M. J. (2020). Fundamental bounds on the fidelity of sensory cortical coding. Nature 580, 100–105.
  50. [53]Satija, R., Farrell, J. A., Gennert, D., Schier, A. F. & Regev, A. (2015). Spatial reconstruction of single-cell gene expression data. Nature Biotechnology 33, 495–U206.
  51. [54]Semedo, J. D., Zandvakili, A., Machens, C. K., Yu, B. M. & Kohn, A. (2019). Cortical areas interact through a communication subspace. Neuron 102, 249–259.
  52. [55]Stoeckius, M., Hafemeister, C., Stephenson, W., Houck-Loomis, B., Chattopadhyay, P. K., Swerdlow, H., Satija, R. & Smibert, P. (2017). Simultaneous epitope and transcriptome measurement in single cells. Nature Methods 14, 865–+.
  53. [56]Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society Series B-Statistical Methodology 36, 111–147.
  54. [57]Stringer, C., Michaelos, M., Tsyboulski, D., Lindo, S. E. & Pachitariu, M. (2021). High-precision coding in visual cortex. Cell 184, 2767–2778 e15.
  55. [58]Trefethen, L. N. (2013). Approximation Theory and Approximation Practice. Philadelphia: SIAM.
  56. [59]Van der Laan, M. J., Polley, E. C. & Hubbard, A. E. (2007). Super learner. U.C. Berkeley Division of Biostatistics Working Paper Series .
  57. [60]Wold, H. (1966). Estimation of principal components and related models by iterative least squares. Multivariate analysis , 391–420.
  58. [61]Wold, S., Ruhe, A., Wold, H. & Dunn, III, W. J. (1984). The collinearity problem in linear regression. The partial least squares (PLS) approach to generalized inverses. SIAM Journal on Scientific and Statistical Computing 5, 735–743.
  59. [62]Wold, S., Sjöström, M. & Eriksson, L. (2001). PLS-regression: a basic tool of chemometrics. Chemometrics and intelligent laboratory systems 58, 109–130.
  60. [63]Wolf, F. A., Angerer, P. & Theis, F. J. (2018). Scanpy: large-scale single-cell gene expression data analysis. Genome Biology 19.
  61. [64]Wolpert, D. H. (1992). Stacked generalization. Neural networks 5, 241–259.DOI
  62. [66]Zandvakili, A. & Kohn, A. (2015). Coordinated neuronal activity enhances corticocortical communication. Neuron 87, 827–839.

Paper details

vlnc:W_htmvnk9h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, Claude Code

View statement
Looking for related papers…
Contents