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 -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 times. Under general distributions and covariance structures, RTK attains the optimal prediction risk in the Krylov space up to . Furthermore, its risk approaches that of the optimal analytic filter with of order . In simulations over a wide range of covariance structures, RTK and a truncated variant were robust to the choice of 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 and the number of observations are of the same order. The data are independent observations from the linear model , written in the design matrix and the response vector . Here is the true regression coefficient and the noise has mean zero given and variance .
The performance of an estimator is measured by its prediction risk, the expected squared error at a new observation independent of ,
where is the population covariance matrix.
An important class of estimators, known as spectral estimators, takes the form , where and . The spectral filter is a scalar function applied to the eigenvalues of . Along a sample eigendirection with eigenvalue , such an estimator multiplies the least squares coefficient by the shrinkage factor [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 , 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 with , the risk is asymptotically deterministic for ridge regression and many other spectral estimators [17, 26, 22]. Let be the class of fixed filters for which converges in probability to a deterministic limit. The oracle filter is the filter in with the smallest limiting risk,
and is therefore a fixed function that does not depend on the realization of the data. Since depends linearly on and the prediction risk (1) is quadratic in , the risk depends quadratically on , and so does its limit. Finding therefore amounts to minimizing a quadratic functional of determined by , , the spectral distribution of and the distribution of the signal over the eigenvalues of , as shown by the limits derived for principal component regression [22] and spiked covariance (Lecoiu et al., 2026). Because involves the unknown population quantities , and , the oracle estimator is generally unavailable. Moreover, closed forms of 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 are difficult to estimate accurately. For example, the spectral distribution of can be estimated from that of the sample covariance matrix [19, 33, 39], but this inverse problem can be ill-posed when the dimension is comparable to the sample size.
Instead of computing from estimates of unknown population quantities such as and , we ask whether a data-driven spectral estimator can attain the oracle risk without explicitly estimating these quantities. We construct such an estimator from (2) by replacing the limiting risk by a risk estimate and the class by a space of filters ,
Within this framework, we seek and that satisfy two conditions:
the minimum risk over approaches ;
is consistent for uniformly over .
Together, the two conditions ensure that attains the oracle risk asymptotically. In general, condition (i) requires to grow with , 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 must be flexible enough to reproduce the shape of the oracle filter, whose shrinkage factor 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 to be the space of polynomials of degree less than , where may grow with , so that the corresponding estimators form the Krylov space
which we abbreviate to . The best estimator in this space attains the smallest risk
which approaches the oracle risk as grows whenever the oracle filter is continuous on the spectrum (Remark 5). For condition (ii), we take to be the leave-one-out risk. On , the leave-one-out predictions are linear in the polynomial coefficients and follow from a single eigendecomposition of the matrix , allowing RTK to minimize the leave-one-out risk directly over . 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 -component PLS regression minimizes the empirical risk (the training error) over the same Krylov space as RTK,
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 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 grows (Remark 1).
Since RTK minimizes the leave-one-out risk over rather than evaluating it at a fixed estimator, it needs to be consistent uniformly over 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 uniformly over bounded subsets of (Theorem 2). If the basis vectors of are not nearly collinear, RTK therefore attains the risk of the best estimator in up to a term of order , whereas PLS does not in general (Corollaries 1 and 2). With of order , 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 (Theorem 3). The only tuning parameter in RTK is . Unlike the level of ridge regression, it does not select a filter but only sets the dimension of , within which the leave-one-out risk determines the filter (Remark 1). Each unnecessary dimension costs only (Corollary 1(b)), so 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 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 grew, also where a competing filter family contains the closed-form oracle. At 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 () are independent copies of following the linear model
where the rows of are , the entries of are , and and are the sample counterparts of and .
With the eigendecomposition and , a spectral estimator is
For , its coefficient along is the least squares coefficient multiplied by the shrinkage factor . Ridge regression with level , principal component regression with threshold and steps of gradient descent with step size have the filters
Their shrinkage factors are non-decreasing in and at most one, for gradient descent when . PLS uses a polynomial filter of degree less than 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 , which we abbreviate to . For a univariate response, this characterization and the equivalence of PLS with the -th iterate of conjugate gradients for started at zero are classical ([61, 27, 48]).
To parametrize , we pick a basis of the polynomials of degree less than , for instance the monomials or the Chebyshev polynomials on an interval 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 and . Every is then for a coefficient vector . With the in-sample features , that is, (; ), the empirical risk in (5) is the least squares criterion
so that , where solves its normal equations
However, our goal is to attain the smallest risk (4) in . By (1), the risk of is also a quadratic function of ,
with . The empirical risk minimized by PLS has the form of (8) with in place of , that is, with and replaced by their sample counterparts and . PLS thus minimizes a plug-in estimate of the risk built from the same and that span . The plug-in is accurate in low-dimensional regimes.
In the proportional regime, and do not estimate and 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 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 -th iterate of conjugate gradients, the non-monotone dependence of its risk on 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 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 that minimizes the prediction risk in (8), which is equivalent to minimizing the risk over polynomial filters in (4). Since depends on the unknown and , it cannot be computed directly, and we estimate it from the observations () by the leave-one-out risk
where and are and computed without observation , with the normalization kept. The leave-one-out fit keeps the coefficients and rebuilds only the basis without observation , so is the cross-validation error of the fixed filter . Since is a function of the observations other than , the conditional expectation of the -th term given these observations is by (1), so that for fixed . The leave-one-out risk is thus unbiased for the expected risk of computed from observations.
Risk-targeted Krylov fitting (RTK) chooses the coefficients by minimizing the leave-one-out risk ,
The minimization in (9) is again a least squares problem over . Indeed, the leave-one-out prediction is linear in , where the leave-one-out features
are the predictions at of the basis of . Hence is the least squares criterion
with , which has the form of (8) with in place of . Thus, the minimizer in (9) solves the normal equations
Compared with the normal equations (7) of PLS, (11) replaces the in-sample features by the leave-one-out features , while the Krylov basis is unchanged.
Note that unbiasedness of holds only for fixed , whereas depends on the data. Minimizing therefore requires it to be consistent for 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 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 rather than a drift toward interpolation as in PLS, so need not be tuned and can be fixed in advance, as long as it is small compared with .
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 are the leave-one-out predictions of and thus form the level-one data of stacking (Wolpert [64]; Breiman [8]). Like stacking, RTK regresses 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 are not good estimators but a basis of , 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 sets the size of the nested Krylov space without specifying the form of any candidate filter, which allows to grow with . With a slowly growing , 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 . Computing by refitting would require fits, and we instead obtain it exactly and efficiently from full-sample quantities. Writing , each feature is a fixed linear combination of the leave-one-out moments . Their full-sample counterparts are the local response moments with . The following theorem recovers the leave-one-out moments from two full-sample quantities, the local response moments and the local spectral moments .
Theorem 1. Let and for , with . Then for and all ,
The proof of Theorem 1 is purely algebraic and is given in the Appendix. By Theorem 1, the leave-one-out moments require only and , and both follow from one eigendecomposition as and . All leave-one-out features therefore cost operations, the cost of one singular value decomposition of .
Write and for and without the -th row and column or entry, and for the -th column of without its diagonal entry. Then , and the proof uses only this form and the symmetry of . The recursion (12) therefore holds for any symmetric matrix in place of , which covers kernel regression with replaced by for a kernel matrix and leave-one-out predictions along gradient descent paths with in place of (§ S2 of the Supplementary Material).
The same form gives an algorithm that requires only matrix-vector products. Deleting observation amounts to setting the -th entry of a vector to zero before each multiplication by , and keeping one column per observation carries out all deletions at once.
Algorithm 1 (Masked recursion). The input is , the response and the dimension .
Step 1. Set , so that column of is a copy of .
Step 2. For , set the diagonal of to zero and replace by . Record for .
By induction, the -th column of after iteration is with , so its -th entry is the moment of Theorem 1. Setting the diagonal to zero thus removes the self-feedback of observation 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 operations, compared with 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 and the dimension .
Step 1. Form and its eigendecomposition , and set .
Step 2. Compute the features of by Theorem 1.
Step 3. Compute for and solve .
Step 4. Output .
The output equals because .
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 , 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 . For ridge regression with level , the exact leave-one-out residual is , and the local spectral moments enter only through the denominator. Replacing it by its average gives the residual of generalized cross-validation [14, 21]. Such averaging is accurate only when the concentrate, which fails for high-order moments and under elliptical designs, where varies with the radius (Table S10 of the Supplementary Material). Both cases matter for RTK, whose features involve moments up to order and whose theory covers bounded elliptical designs (Assumption 1). Under an elliptical design, the error of the averaged-diagonal approximation of did not decrease with in our simulations, whereas that of exact leave-one-out decreased at rate (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 in RTK depends on how well polynomials of degree less than 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 that covers them places the bulk near its endpoint , where the approximation is poor. In particular, a filter that is singular within distance of an endpoint has polynomial approximation error no smaller than (Lemma S4 of the Supplementary Material; see Trefethen, [58], Ch. 8), and is small when 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 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 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 grows, with a slightly larger dimension (§ S7.9 of the Supplementary Material).
Suppose that , let and , and let be the Chebyshev polynomials on the bulk interval . The truncated Krylov space of dimension consists of the spectral estimators
whose filter is a polynomial of degree less than on the bulk eigenvalues () and takes a free value at each of the separated eigenvalues. The coefficient sets the shrinkage factor of the -th direction. The leave-one-out version of (13) keeps fixed and uses the top eigenvectors of , so its leave-one-out risk is again a least squares criterion in with exact leave-one-out features. We call the method risk-targeted Krylov fitting with truncation (RTK-C), which reduces to RTK for . Let be the -th eigenvector of and . The leave-one-out features of the two kinds of terms form the matrices and with entries
RTK-C minimizes , so its coefficients in (13) solve the normal equations
The bulk features differ from because they are deflated by the top leave-one-out eigenvectors, and the features 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 separated directions, which the following proposition obtains from the same full-sample eigendecomposition through Lemma A1 in the Appendix.
Proposition 1. Let and , suppose , and suppose that for , that is, observation has a nonzero loading on each of the top eigenvectors of . For , the function has exactly one root in , which is the -th largest eigenvalue of and is simple. The feature of the -th separated direction is
and the bulk features are , 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 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 increases between consecutive full-sample eigenvalues, bisection finds the roots at cost 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 to the number of eigenvalues of 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 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 is fixed in advance as for RTK in § 3.1.
Theory
This section shows that RTK nearly attains the smallest prediction risk in the -dimensional Krylov space and approaches the oracle risk as grows with . 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 . It arises because RTK minimizes a data-driven risk estimate instead of the unknown prediction risk , and it grows with . The approximation error is the gap between the smallest risk in and the oracle risk , and it decreases as grows. If is close to uniformly over bounded coefficients, then minimizing nearly minimizes . 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 and to compare RTK with PLS. Section 4.3 shows that the approximation error decays geometrically in when the oracle filter is analytic near the spectrum. Balancing the two errors then leads to of order 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 is close to the unknown prediction risk uniformly over estimators in with bounded coefficients.
Assumption 1. The observations follow the linear model (6), and with . In addition, (i) is bounded; (ii) and are bounded; (iii) there are constants and such that for all .
Conditions (ii) and (iii) of Assumption 1 hold for Gaussian and sub-Gaussian designs and for elliptical designs with a bounded radius . For the former, is
even exponentially small in . Elliptical designs with unbounded radius can violate (iii), because then grows with .
The bounds below hold for any basis of the polynomials of degree less than (§ 2.2) and depend on it only through the largest value of on a fixed contour around the spectrum of . We work on the event of a bounded sample spectrum, , whose probability tends to one by Assumption 1(iii). Fix and let be the positively oriented boundary of the -neighborhood of in . On , encloses the spectrum of at distance at least , so that with on . We therefore measure the basis by . Below, denotes a constant that depends only on , and the constants in Assumption 1, not on or the basis, so that can grow with in § 4.3.
Theorem 2. Let , and be the coefficients of the leave-one-out risk (10), and let , and be those of the population risk (8). Under Assumption 1, for all ,
Consequently, for every ,
The proof of Theorem 2 is given in § S3 of the Supplementary Material. The errors of and matter since they determine the estimation error of RTK. The leave-one-out risk is the quadratic with estimated coefficients, so a minimizer of over a bounded set satisfies
where the constant terms cancel since they do not depend on . Since depends on the data, needs to be close to uniformly over , not only at a fixed . The right-hand side of (14) depends only on and , which Theorem 2 bounds.
To bound these errors, the proof uses that each feature is a function of the leave-one-out quantities and evaluated at the held-out . By the contour representation above, is an integral of the resolvent over , 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 with independent coordinates of , under which the quadratic forms concentrate around . 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 , , so the theorem covers paths with of order at most .
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 is invertible, the risk (8) is minimized over by , and every other in has excess risk over
Corollary 1. Let . Under Assumption 1, the following hold.
(a) A minimizer of over satisfies .
(b) If the Krylov space is well conditioned, i.e. with probability tending to one and , then the coefficients of § 3.1 satisfy and .
The proof of Corollary 1 is given in § S4 of the Supplementary Material. Part (a) holds without conditions on and is the form used in § 4.3, where grows. The ball only makes the uniform bound of Theorem 2 applicable, and RTK itself is unconstrained. Part (b) is the analogue of least squares on well-conditioned regressors, which has excess risk of order .
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 and , this fluctuation is of order , whereas the bias from fitting on rather than observations is of order , so the fluctuation determines the rate 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 , a fluctuation of order moves the minimizer by but raises the risk by only (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),
The proof of Corollary 2 is given in § S4 of the Supplementary Material. By (15), the excess risk of PLS over is exactly , and that of RTK is by Corollary 1(b). Since and do not estimate and consistently, does not converge to in general. The gap therefore persists as grows, while the excess risk of RTK decays like (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 . A larger lowers the approximation error but raises the estimation error, and we quantify both by Bernstein ellipses around an interval that contains the spectrum. Let be fixed, so that contains the spectrum of on . For , let be the closed Bernstein ellipse of centered at with semi-axes along the real axis and along the imaginary axis. Two values of play different roles. First, choose such that lies in . Since for , the Chebyshev basis satisfies , so controls how fast the estimation error of Theorem 2 grows with . Second, measures the smoothness of the filters we compare with, and it controls how fast the approximation error decays with .
For and , let be the class of filters that extend to analytic functions bounded by in the interior of . A larger means a smoother filter, which polynomials of degree less than approximate more accurately on with error (Trefethen, [58]). Lu et al. [42] consider a similar class of analytic filter functions with extra shape constraints, namely shrinkage factors in that are non-decreasing and ridge-like, whereas requires analyticity on an ellipse that does not change with . Let be the risk of the best filter in this class given the data at hand.
Theorem 3. Let be risk-targeted Krylov fitting with the Chebyshev basis on and coefficients constrained to , and let . Under Assumption 1,
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 belong to some . In particular, if the oracle filter of (2) belongs to , then , so the risk of RTK exceeds that of by at most , and converges to the oracle risk .
Figure 2. Excess risk of risk-targeted Krylov fitting above that of the oracle filter , as a percentage of the excess risk of the oracle, in the latent-factor setting with : against the Krylov dimension for from 250 to 4000 (left), and against for fixed (right). In the right panel the dashed line follows the best at each (printed below it), and the dash-dotted line is proportional to . Means over 200 (), 100 () and 50 () replicates. Bars in the right panel are standard error of the paired differences. Values for , about 40% above the oracle, are not shown.
Remark 5. Theorem 3 requires the filter to be analytic around , 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 of principal component regression with in a gap. The reason is that a spectral estimator depends on its filter only through the values at the sample eigenvalues. Let , so that . By (1) and the triangle inequality,
so the values of a filter where has no mass do not matter. Let be a closed set that contains the support of with probability tending to one. If is continuous on , the Weierstrass theorem gives for every a polynomial with on . The measure has total mass , so . Since and is bounded on the compact set , . With and the coefficient bound growing slowly in , Corollary 1(a) then shows that RTK attains up to for such , and the oracle risk if is of this form.
The rate of Theorem 3 degrades as approaches 1, which happens when the filter has a pole whose distance to is small compared with the length of the interval. As discussed in § 3.3, a few outlying eigenvalues stretch , 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 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 , which excludes these gaps. Compared with the length of this interval, the poles of the filter are typically far away. Let and denote and for this interval.
Proposition 2. Suppose that the restriction of to belongs to for some and , and is finite.
(a) (Uniform approximation) There is a filter of the form (13) with () and .
(b) (Risk approximation) On , , where depends also on .
(c) (Rational filters) The restriction to of a rational filter with real poles at distance at least from belongs to , with and , wherever the poles lie relative to .
The proof of Proposition 2 is given in § S5 of the Supplementary Material. In part (b), the factor bounds the size of , since on . 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 to split with high probability into the bulk and eigenvalues in fixed windows away from it, also after one or two observations are removed. The fitted shrinkage factors are then within of the risk-optimal factors when the space is well conditioned, and Proposition 2 gives the analogue of Theorem 3 for the class . 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 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 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 , , independent of , and . Without loss of generality, we take diagonal, so that its eigenvectors are the coordinate vectors . Two further settings in the Supplementary Material instead use the elliptical design , with equally likely and independent of , whose coordinates are dependent although uncorrelated. The settings differ in the spectrum of and in how 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 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, th eigenvalue of ; , decay exponent of the signal. Components in an eigenspace, including the bulk, point in a uniformly random direction within it, scaled so that is as given, and signs in the power-law settings are random. For the isotropic setting 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 without further selection, and RTK-C chooses by the resolution rule of § 3.3. Sections 5.3 and 5.4 examine the choice of . 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 of (2) is approximated by the best linear combination of polynomials and resolvents, fitted to 50 independent draws of each setting at the same . For Gaussian designs, whose limiting risk is well defined [22], we directly computed by minimizing the explicit form of over the values of 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 of (1), computed exactly from and .
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 , consistent with an estimation cost of order 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 but is worse at every . The hybrid method deteriorated almost as much as PLS, because its regularization parameter decreased with , so that its iterates drifted toward the unregularized conjugate gradient solution.
Figure 1. Excess risk against the Krylov dimension 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 by weighted generalized cross-validation. Means over 20 replicates with 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 | Spectrum of | Signal | ||
| Isotropic | 2 | |||
| One spike | 1.5 | 1 | ||
| Spike + bulk | 4 | |||
| Two spikes | 1.5 | 1.38 | ||
| Multiple spikes | 1.5 | 2 | ||
| Latent factor | 5% at 4, 95% at 1 | in the eigenvalue-4 space | 1.5 | |
| Three-atom | 1.5 | 5% at 12, 15% at 4, 80% at 1 | in the eigenvalue-4 space | 4 |
| Mixed | 1.5 | half 1, half 2, one at 12 | 1.86 | |
| Power law, | , mean 1 | 2 | ||
| Power law, | 1.5 | , mean 1 | 2 | |
| Steep power law | 1.5 | , mean 1 | 2 |
Table 1. Simulation settings, with
Approach to the oracle
In Figure 2, the gap between RTK and the oracle at fixed 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 over the oracle and does not depend on , and the second is of order by Corollary 1(b). For each , we regressed the gap across the sample sizes of Figure 2 on by weighted least squares, so that the intercept estimates the approximation error and the slope divided by 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 chosen by approximate leave-one-out; GD, gradient descent; SD, one-step self-distillation; RTK, risk-targeted Krylov fitting with ; RTK-C, risk-targeted Krylov fitting with truncation and ; Oracle, oracle filter , which is infeasible; –, not available (§ S7.1 of the Supplementary Material); , 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 and was indistinguishable from zero for , as expected for an oracle that is analytic near the spectrum, whereas each additional dimension added about to the excess risk, of the same order as the cost of a regressor in least squares. In the right panel, the curve for therefore stays at its approximation error for every , whereas that for falls like . As the curves cross, the best dimension grows with , from 2 for to 6 for . Along the best dimension (dashed line), the gap decreased like between and 4000. This is slower than , as the exponent 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 over a widening range as grows. The best dimension also exceeded the schedule 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 . In these simulations the cost did not grow. The fixed dimension used in § 5.4 was within 0.2 percentage points of the best one for .
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 , so RTK cannot be expected to improve on it there. Its disadvantage in these settings is mainly an estimation cost of order and shrank from to (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 . These are the only settings in which the resolution rule selected , and truncation lowered the excess risk in the power laws by up to 57%. In the other settings RTK and RTK-C coincide. Choosing by cross-validation instead of fixing 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 at the sample eigenvalues for the first replicate of the one-spike, latent-factor and power-law () settings of Table 2, against those of the oracle filter (dashed). The ticks at the bottom mark the sample eigenvalues, and the dotted line marks . In the one-spike and latent-factor settings the resolution rule selects , 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 set | Targets | PCR | PLS | GD | SD | RTK | RTK-C | W/T/L |
| PBMC 3k | 9 genes | 0.954 | 0.961 | 0.947 | 0.950 | 0.939 | 0.934 | 6/1/2 |
| PBMC 10k | 13 genes | 0.978 | 0.991 | 0.972 | 0.971 | 1.031 | 0.956 | 10/3/0 |
| Mouse brain 10k | 11 genes | 0.970 | 0.991 | 0.973 | 0.976 | 1.002 | 0.966 | 5/6/0 |
| CITE-seq | 14 proteins | 0.981 | 0.987 | 0.972 | 0.970 | 1.013 | 0.950 | 11/3/0 |
| Norman 2019, K562 | 10 genes | 0.994 | 0.985 | 0.973 | 0.966 | 0.963 | 0.958 | 6/2/2 |
| Replogle 2022, K562 | 10 genes | 0.987 | 1.003 | 0.975 | 0.975 | 0.970 | 0.963 | 7/3/0 |
| Replogle 2022, RPE1 | 10 genes | 0.975 | 1.003 | 0.978 | 0.982 | 0.976 | 0.963 | 8/2/0 |
| Papalexi 2021, THP-1 | 10 genes | 0.983 | 1.002 | 0.972 | 0.973 | 0.989 | 0.961 | 9/1/0 |
| Papalexi 2021, THP-1 | 4 proteins | 1.003 | 1.033 | 0.992 | 0.995 | 0.993 | 1.003 | 0/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 -statistic over the splits beyond ; , number of predictors; , 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 , and RTK and RTK-C use . 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 | Ridge | PCR | PLS | GD | SD | RTK | RTK-C | Oracle | |
| Isotropic | 1.5 | 1.265 | 1.558 | 1.381 | 1.288 | 1.266 | 1.274 | 1.274 | 1.258 |
| One spike | 1.5 | 0.766 | 0.734 | 0.659 | 0.639 | 0.544 | 0.551 | 0.551 | 0.543 |
| Spike + bulk | 2 | 2.173 | 2.211 | 2.071 | 2.029 | 1.687 | 1.682 | 1.682 | 1.668 |
| Two spikes | 1.5 | 0.872 | 0.874 | 0.719 | 0.744 | 0.664 | 0.643 | 0.643 | 0.633 |
| Multiple spikes | 1.5 | 0.747 | 0.580 | 0.491 | 0.507 | 0.377 | 0.299 | 0.302 | 0.293 |
| Latent factor | 1.5 | 0.970 | 0.924 | 0.785 | 0.814 | 0.722 | 0.701 | 0.701 | 0.691 |
| Three-atom | 1.5 | 2.316 | 2.357 | 2.115 | 2.130 | 2.014 | 1.998 | 1.998 | 1.945 |
| Mixed | 1.5 | 1.522 | 1.730 | 1.525 | 1.477 | 1.454 | 1.458 | 1.458 | 1.444 |
| Power law, | 1.5 | 0.628 | 0.593 | 0.663 | 0.515 | 0.502 | 0.558 | 0.475 | 0.471 |
| Power law, | 1.5 | 0.389 | 0.235 | 0.228 | 0.221 | 0.205 | 0.174 | 0.162 | 0.158 |
| Steep power law | 1.5 | 0.468 | 0.441 | 0.990 | 0.387 | 0.388 | 0.860 | 0.370 | – |
Table 2. Simulations: mean excess risk over 30 replicates,
| Ridge | PCR | PLS | GD | SD | RTK | RTK-C | |||
| Macaque V1 to V2: prediction of the averaged V2 activity | |||||||||
| 1.5 | 59–105 | 2 | 0.464 | 0.439 | 0.451 | 0.469 | 0.448 | 0.470 | 0.469 |
| 1 | 88–158 | 2 | 0.497 | 0.480 | 0.484 | 0.505 | 0.483 | 0.506 | 0.503 |
| 0.5 | 176–316 | 2 | 0.536 | 0.519 | 0.525 | 0.543 | 0.536 | 0.543 | 0.538 |
| 0.28–0.49 | 320 | 2 | 0.545 | 0.528 | 0.539 | 0.550 | 0.547 | 0.550 | 0.548 |
| Mouse V1: decoding of the grating angle | |||||||||
| 0.53–0.57 | 3490–3759 | 5 | 0.619 | 0.604 | 0.616 | 0.629 | 0.628 | 0.626 | 0.629 |
| 0.85–0.92 | 2181–2349 | 5 | 0.590 | 0.579 | 0.589 | 0.603 | 0.603 | 0.602 | 0.603 |
Table 4. Neural recordings: mean out-of-sample (larger is better)
Abbreviations as in Table 2; , number of neurons; , number of training trials; , 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 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 . Following § 5.3, the Krylov dimension was fixed in advance and increased with the training size: for the macaque data (at most 320 training trials), for the single-cell data (about 1000 training cells) and 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 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 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 at fixed . Their exact leave-one-out features follow from Lemma A1 with , 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 with ([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 and 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 , and the best dimension exceeded the schedule. Theorem 2 requires a polynomial tail bound on , which excludes elliptical designs with heavy-tailed radius. Exact leave-one-out costs one eigendecomposition, and this cost is no longer negligible for very large . Theorem 1 needs only the local response moments , which cost matrix-vector products, and the diagonals . 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 be symmetric, let be without its -th row and column and its -th column without the diagonal entry, and let with . Write and . Then and
Proof. Order the coordinate first, so that has blocks , , and , and let . Since and is invertible, . Block inversion gives
The first row applied to gives .
Proof of Theorem 1. We prove (12) for a general symmetric in place of , with and for and . For , which also exceeds by interlacing, the Neumann series converge absolutely and give
by the definition of . By Lemma A1, the second series is the product of the first and the third. Comparing the coefficients of gives , which is (12) because .
For we have , where is without its -th row. Since induction gives , and therefore . The leave-one-out moments of Theorem 1 are thus the above with . □
Proof of Proposition 1. Let be a singular value decomposition with . Then , , , and is orthogonal to the null space of . Hence, for every function on the spectrum, . Let be the distinct eigenvalues of , the corresponding spectral projectors and , so that . By Lemma A1 with and the eigendecomposition of , for outside both spectra,
On , , and as and as , because and are nonzero. Hence has exactly one root there. With the -th standard basis vector of , the vector has -th coordinate , so the rows of give with , and is an eigenvalue of . Cauchy interlacing places the -th largest eigenvalue of , counted with multiplicity, in and the neighboring ones in and , with . Since the top eigenvalues of are simple, is the -th largest eigenvalue of and is simple. As is a simple zero of , with , and not a pole of , the residue of the left-hand side of (A1) at is , and that of the right-hand side is . The -th separated direction corresponds to , whose feature is , and the -th bulk basis vector to , whose feature is . □
References
- [1]Allen, D. M. (1974). The relationship between variable selection and data augmentation and a method for prediction. Technometrics 16, 125–127.DOI
- [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]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]Bauer, F., Pereverzev, S. & Rosasco, L. (2007). On regularization algorithms in learning theory. Journal of complexity 23, 52–72.
- [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]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]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]Breiman, L. (1996). Stacked regressions. Machine learning 24, 49–64.DOI
- [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]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]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]Cook, R. D. & Forzani, L. (2019). Partial least squares prediction in high-dimensional regression. Annals of Statistics 47, 884–908.DOI
- [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]Craven, P. & Wahba, G. (1978). Smoothing noisy data with spline functions. Numerische Mathematik 31, 377–403.DOI
- [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]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]Dorriban, E. & Wager, S. (2018). High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics 46, 247–279.
- [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]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]FRANK, I. E. & FRIEDMAN, J. H. (1993). A statistical view of some chemometrics regression tools. Technometrics 35, 109–135.
- [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]GREEN, A. & ROMANOV, E. (2025). The high-dimensional asymptotics of principal component regression. The Annals of Statistics 53, 1697–1727, 31.DOI
- [23]GÜTTEL, S. (2013). Rational krylov approximation of matrix functions: Numerical methods and optimal pole selection. GAMM-Mitteilungen 36, 8–31.DOI
- [24]HANSEN, B. E. & RACINE, J. S. (2012). Jackknife model averaging. Journal of Econometrics 167, 38–46.DOI
- [25]HANSEN, P. C. (2010). Discrete inverse problems: insight and algorithms. SIAM.
- [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]HELLAND, I. S. (1988). On the structure of partial least squares regression. Communications in Statistics - Simulation and Computation 17, 581–607.DOI
- [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]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]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]HÖSKULDSSON, A. (1988). PLS regression methods. Journal of Chemometrics 2, 211–228.DOI
- [33]KONG, W. H. & VALLIANT, G. (2017). Spectrum estimation from samples. Annals of Statistics 45, 2218–2247.arxiv.org/abs/1602.00061
- [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
- [35]KRÄMER, N. (2007). An overview on the shrinkage properties of partial least squares regression. Computational Statistics 22, 249–273.DOI
- [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
- [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
- [39]LEDOIT, O. & WOLF, M. (2017). Numerical implementation of the quest function. Computational Statistics & Data Analysis 115, 199–223.
- [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
- [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 .
- [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
- [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
- [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
- [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.
- [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
- [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
- [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.
- [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
- [51]Ruhe, A. (1998). Rational krylov: A practical algorithm for large sparse nonsymmetric matrix pencils. Siam Journal on Scientific Computing 19, 1535–1551.
- [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.
- [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.
- [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.
- [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–+.
- [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.
- [57]Stringer, C., Michaelos, M., Tsyboulski, D., Lindo, S. E. & Pachitariu, M. (2021). High-precision coding in visual cortex. Cell 184, 2767–2778 e15.
- [58]Trefethen, L. N. (2013). Approximation Theory and Approximation Practice. Philadelphia: SIAM.
- [59]Van der Laan, M. J., Polley, E. C. & Hubbard, A. E. (2007). Super learner. U.C. Berkeley Division of Biostatistics Working Paper Series .
- [60]Wold, H. (1966). Estimation of principal components and related models by iterative least squares. Multivariate analysis , 391–420.
- [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.
- [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.
- [63]Wolf, F. A., Angerer, P. & Theis, F. J. (2018). Scanpy: large-scale single-cell gene expression data analysis. Genome Biology 19.
- [64]Wolpert, D. H. (1992). Stacked generalization. Neural networks 5, 241–259.DOI
- [66]Zandvakili, A. & Kohn, A. (2015). Coordinated neuronal activity enhances corticocortical communication. Neuron 87, 827–839.


