Covariate Shift in High-Dimensional Random Feature Regression

1.2 Related work

• Prior empirical work reports linear trends between shifted and unshifted performance, while theoretical accounts of distribution-shift behavior remain comparatively limited.The introduction also surveys theoretical work on domain adaptation, distribution shift, and high-dimensional generalization.Source: §1 · p. 1, §1.2 · p. 4

1.1 Summary of contributions

• The analysis gives asymptotically exact test error, bias, and variance for random-feature regression under covariate shift, extending results to anisotropic Gaussian covariates.The paper also gives asymptotically exact results for covariate shift in linear regression.Source: §1.1 · p. 2, §1 · p. 2
• When covariate scale is unchanged, a model-independent partial order gives sufficient conditions for determining whether a shift increases or decreases bias and test error.When scale changes, model-dependent conditions are needed.Source: §1.1 · pp. 2–3
• Overparameterization enhances robustness to covariate shift, with error, bias, and variance nonincreasing in the number of excess parameters.The paper describes this behavior as persisting in simpler settings and potentially arising from high-dimensionality.Source: §1.1 · p. 3
• In the ridgeless limit, in-distribution and out-of-distribution generalization performance have an exact linear relationship parameterized by overparameterization.The linearity approximately persists with nonzero regularization but is violated in the underparameterized regime.Source: §1.1 · p. 3

2.1 Problem setup and notation

• The analysis takes the proportional limit with sample size, input dimension, and hidden-layer size growing at the same rate; φ/ψ is the limiting ratio of features to samples.The target is a random isotropic linear signal with additive training-label noise, and the covariates are Gaussian.Source: §2.1 · p. 5
• Kernel ridge regression uses a single-layer random neural feature map with Gaussian weights, an elementwise activation, and ridge regularization.The test error, bias, and variance average over the data, weights, and label noise; the standard analysis assumes γ ≥ 0, although optimal γ can sometimes be negative in low-noise settings.Source: §2.1 · pp. 5–6

2.2 Assumptions

• The limiting description uses the joint spectral distribution of training and test covariances, including their eigendirection overlap, rather than considering their spectra separately.The empirical joint spectral distribution is assumed to converge, with bounded covariance operator norms and finite expectations under the stated regularity conditions.Source: §2.2 · pp. 6–7

2.3 A simple family of diatomic distributions

• A diatomic limiting distribution provides an interpretable family with two covariance eigenscales and a parameter θ that controls their relative emphasis under shift.θ = 1 represents no shift; θ < 1 suppresses large training eigendirections in the test distribution, while θ > 1 further emphasizes them.Source: §2.3 · p. 8

3. Motivating example: linear regression

• For linear regression, the shift's effect on test error can be decomposed across covariance eigendirections, motivating conditions that compare their overlap coefficients.The section presents a finite-dimensional test-error expression and an illustrative diatomic example.Source: §3 · pp. 8–9
• If one test covariance has at least as large a trace and the ratios of its overlap coefficients to the other's are nondecreasing, its linear-regression test error is ordered accordingly.For the diatomic example, a larger θ corresponds to a lower test error and satisfies the eigendirection ordering condition.Source: §3 · p. 9
• Linear-regression test error scales linearly with the overall scale of the test covariance, a property that does not generalize to nonlinear random-feature regression.Source: §3 · p. 9

4. Definition of shift strength

• A shift is defined as easier or harder by comparing conditional expected overlap ratios across training eigenvalues and the overall expected overlap.The ordering compares distributions with the same training-spectrum marginal; relative to no shift, the resulting order labels shifts easy or hard.Source: §4 · p. 9
• When scales differ, shift effects remain coupled to the model; generic shifts can combine scale changes with covariance restructuring.The paper distinguishes no shift, pure-scale shift, scale-preserving restructuring, and generic shifts that change both structure and scale.Source: §4 · p. 10
• With equal training and test covariance scales, the shift ordering gives an essentially model-independent account of how random-feature models respond to shift strength.This motivates the equal-scale assumption used in the analysis.Source: §4 · p. 10

5.1 Main results

• Theorem 5.1 characterizes the high-dimensional limits of test error as bias plus variance, and its asymptotic predictions agree well with finite-size simulations.The theorem applies as n0, n1, and m tend to infinity.Source: §5.1 · pp. 11–12

5.2 Harder shifts increase the bias and test error

• Under stated noise and model-constant conditions, harder shifts increase bias and total test error, but variance need not be ordered in general.For pure-scale shifts, additional conditions can guarantee ordered variance.Source: §5.2 · pp. 13–14

5.3 The benefit of overparameterization

• When ξ ≤ 1, bias is nonincreasing with overparameterization; in ridgeless regression, variance is also nonincreasing once φ > ψ.Without ξ ≤ 1, bias can be nonmonotonic; the variance result is stated for the ridgeless setting.Source: §5.3 · p. 14
• Under the proposition’s shift-ordering conditions, the shifted–unshifted generalization gap is nonincreasing with φ/ψ when φ > ψ.This is the formal robustness result for overparameterized models.Source: §5.3 · p. 15

5.4 Linear trends between in-distribution and out-of-distribution generalization

• In the ridgeless overparameterized regime, shifted error is linear in unshifted error as φ/ψ varies; under Assumption 4, hard shifts have slope at least one and easy shifts at most one.The figure reports slopes greater than one for the hard shift and less than one for the easy shift.Source: §5.4 · pp. 15–16, Figure 2 · p. 16

6. Optimal regularization

• Negative optimal regularization is possible, but it does not arise in the reported simulations, which use low signal-to-noise ratios.The authors connect this possibility to the implicit regularization effect of nonlinear feature maps.Source: §6 · pp. 17–18
• Tuning regularization on the shifted distribution makes test error nonincreasing with overparameterization, while unshifted-distribution tuning can leave a residual peak away from the interpolation threshold.The remaining peak suggests a different origin from the interpolation-threshold peak.Source: §6 · p. 17
• In the infinite-overparameterization limit, the optimal regularization coefficient is independent of covariate shift, and the shifted- and unshifted-tuned values approach one another.The paper attributes this extension to random feature regression to the implicit regularization effect of nonlinear feature maps.Source: §6 · pp. 17–19
• For hard shifts, the optimal regularization values differ substantially in the underparameterized regime but approach equality as overparameterization grows.The figure description also highlights an intermediate overparameterization ratio around φ/ψ ≈ 2 where the values are equal across shift strengths.Source: §6 · pp. 17–18

7.1 Monotonicity condition in partial order of shifts

• Incomparable shifts are common because the partial order requires all eigendirections to act in concert, making aggregate effects difficult to predict; deviation measures provide model-independent error bounds.For small finite-size violations caused by o(1) overlap coefficients, the nonmonotonicity vanishes in the high-dimensional limit; persistent violations can be bounded using monotone envelopes, which loosen as the envelope widens.Source: §7 · p. 19, §7.1 · p. 20, §7.1.2 · pp. 21, 23

7.1.1 MONOTONICITY IS NECESSARY TO GUARANTEE ORDERING OF THE TOTAL ERROR

• When overlap-ratio monotonicity fails, total-error ordering can reverse across model sizes and activation functions; pairs satisfying the partial order retain their predicted ordering.The ordering of incomparable shifts can change with the overparameterization ratio or activation function.Source: §7.1.1 · p. 20, §7.1.2 · p. 21, Figure 4 · p. 21

7.2 Label noise

• Large label noise can make variance rise enough to reverse the total-error ordering of easy and hard shifts, whereas optimal regularization preserves decreasing error with easier shifts.The small-noise condition σ2 ε ≤ω is needed for the stated ordering without this remedy; optimal regularization maintains it even with large noise in the analyzed settings.Source: §7.2 · pp. 23–24

7.3 Discrepancies in scale between the training and test distributions

• Training-test scale mismatch separates the constants governing bias and variance: bias depends on the linear component, while variance also depends on the noise component.Unequal scales create separate sets of model-dependent constants and require more intricate conditions for some results.Source: §7.3 · pp. 24–25

7.3.1 UNEQUAL SCALES AND NONMONOTONICITY OF THE BIAS

• When the test-to-training linear-scale ratio ξ exceeds 1, bias can be nonmonotonic because eigendirections switch from underestimation to overestimation at different values of x.For ξ ≤1, bias decreases with x; for ξ >1, each eigendirection has a distinct unbiased value of x, preventing simultaneous optimization.Source: §7.3.1 · pp. 26–27

7.3.2 SCALE-INDUCED MODEL DEPENDENCE

• With ξ > 1, bias can rise as overparameterization increases, overcoming nonincreasing variance and raising total error; optimal regularization removes this nonmonotonicity.The comparison conditions for different shifts are sufficient but not necessarily optimal; loosening them requires additional spectral information.Source: §7.3.2 · p. 27
• When ξ > 1, bias and total error can increase as shifts become easier, and optimal regularization does not guarantee monotonicity with shift strength.With fixed regularization, bias and total error also need not be nonincreasing in overparameterization ratio or shift power; under optimal regularization, they remain nonmonotonic in shift power.Source: §7.3.2 · pp. 27–28, Figure 8 · p. 28

7.3.3 PURE-SCALE SHIFTS

• For pure-scale shifts, total error is nondecreasing when s ≤ s* ≤ 1/4; with s=1, it decreases for 1/4 < s* < s.When s=1/250, bias and variance are both nondecreasing in the stated interval, so total error is as well.Source: Figure 9 · p. 29, §7.3.3 · p. 29
• Bias is nondecreasing for s* ≥ s, while variance is nondecreasing only through s*=1/4; either quantity may be nonmonotonic outside these conditions.The conditions follow from scale-dependent bounds; bias and variance need not both be nondecreasing for total error to increase.Source: §7.3.3 · pp. 28–29

7.4 Nonlinear trends with nonzero ridge constant or underparameterization

• The shifted-versus-unshifted error relationship is exactly linear only for ridgeless overparameterized models; it is markedly nonlinear underparameterized and deviates slightly with nonzero ridge.The small deviations for nonzero ridge suggest approximate linearity may hold beyond the exact conditions.Source: §7.4 · pp. 29–30, Figure 10 · p. 30

8. Conclusion

• Exact high-dimensional results characterize test error, bias, and variance under covariate shift; the partial order predicts help or harm when covariate scale is unchanged.With scale changes, performance depends on model-specific constants, and bias can be nonmonotonic in feature count or ridge regularization.Source: §8 · pp. 30–31

A.1 Basic properties of the self-consistent equation for x

• A unique nonnegative solution to the self-consistent equation for x is established, alongside nonnegativity properties used in the analysis.The proof uses the equation's root behavior and concavity to establish uniqueness.Source: §A.1 · p. 33

A.2 I and I∗ inequalities

• The I and I* functionals admit raising and lowering identities and inequalities that also bound shifts incomparable with the null shift.The extension uses monotone bounds on shift strength.Source: §A.2 · pp. 34–35

Appendix B. Hardness is a partial order

• The hardness relation defined from overlap coefficients and mean overlap forms a partial order over covariate shifts.The appendix establishes the relation's reflexivity, antisymmetry, and transitivity.Source: Appendix B · pp. 35–36

Appendix C. Repeated eigenvalues of Σ

• Repeated covariance eigenvalues make individual overlap coefficients basis-dependent, but the conditional expected overlap and downstream shift definitions remain invariant.Different eigendecompositions yield shifts in the same equivalence class when their conditional expected overlaps agree.Source: Appendix C · pp. 36–37

D.1 Asymptotic and nonasymptotic results for m > n0 + 1

• For m > n0 + 1, the Gaussian sample covariance is almost surely invertible, and the result does not require a generative assumption on β.The proof uses the expected inverse sample covariance of a Gaussian matrix.Source: §D.1 · p. 37
• When test-covariance trace is ordered and overlap-coefficient ratios are nondecreasing, the linear-regression test errors are ordered.The overlap-ratio condition handles repeated eigenvalues through non-repeated eigenvalues and corresponding overlap coefficients.Source: §D.1 · p. 38

D.2 Linear regression limit of random feature regression

• In the ridgeless limit with φ < 1, taking the activation toward linear and ψ toward zero recovers the linear-regression result.The appendix analyzes the self-consistent solution for x in this limit.Source: §D.2 · p. 39
• For φ > 1 with equal training and test covariances, the limiting error matches Hastie et al. (2019, Cor. 2).The comparison uses the minimum-norm limit and the isotropic β setting described in the appendix.Source: §D.2 · pp. 40–41
• With nonzero regularization and equal training and test covariances, the random-feature error matches linear ridge regression using an effective regularizer.The appendix identifies the effective regularizer as γeff.Source: §D.2 · pp. 41–43

Appendix E. Harder shifts increase the bias and the total error

• For ordered shifts, the appendix restates conditions under which the harder shift increases bias and total error.The general setting allows distinct training and test scales, so additional parameter constraints are needed for the ordering.Source: Appendix E · p. 43

E.1 Pure-scale shifts

• For pure-scale shifts, the appendix separately states the bias, variance, and total-error ordering result.The proof section derives the variance comparison while the bias and total-error result follows from the earlier proposition.Source: §E.1 · p. 45

E.2 Incomparable shifts of equal scale

• For incomparable shifts with equal scale, the appendix bounds bias and total error relative to the in-distribution quantities.The setting assumes equal training and test scales.Source: §E.2 · p. 46

F.1 The bias is nonincreasing

• When ξ ≤ 1, bias is nonincreasing in the overparameterization ratio φ/ψ.The appendix notes that monotonicity is not guaranteed when ξ > 1.Source: §F.1 · p. 47

F.2 The variance is nonincreasing

• The variance result focuses on the ridgeless limit; analysis for nonzero ridge is deferred, although figures show the result may hold there.Source: §F.2 · p. 48
• In the overparameterized regime, variance is nonincreasing in φ/ψ, regardless of the overall covariance scales s and s∗.The proposition is proved in the ridgeless limit.Source: §F.2 · pp. 47–48

F.3 The generalization gap is nonincreasing

• For two LJSDs with µ1 ≤ µ2 and 1 ≤ ζ2/ζ1 ≤ η2/η1, the generalization gap Eµ2 − Eµ1 is nonincreasing in φ/ψ when ψ < φ.Source: §F.3 · p. 48

• In the ridgeless, overparameterized regime, Eµ2 is linear in Eµ1, parametrically in φ/ψ.Source: Appendix G · p. 49
• When µ1 ≤ µ2 and 1 ≤ ζ2/ζ1 ≤ η2/η1, the linear relationship has slope SLOPE ≥ 1.The intercept E0 and slope SLOPE are constants independent of φ/ψ.Source: Appendix G · p. 49
• The proof derives the linear relationship by eliminating a term in φ/ψ from the two test-error expressions, whose other quantities are independent of that ratio.Source: Appendix G · pp. 49–50

Appendix H. Optimal regularization

• As φ/ψ tends to infinity, the optimal regularization γopt is independent of µ under Assump. 4.Source: Appendix H · p. 50

Appendix I. Proof of Thm. 5.1

• The proof develops calculations for the high-dimensional test-error limit and its decomposition into bias and variance for random feature kernel ridge regression.The setup uses a ridge regularization constant γ and linear labels.Source: Appendix I · pp. 51–52

I.1 Reducing to the mean-zero case

• For the mean-zero reduction, the appendix gives an alternative proof approach and shows that replacing the feature matrices by centered versions does not alter the limiting test error.The alternative is motivated by the infeasibility of the cited Gegenbauer-polynomial approach for iid Gaussian matrices.Source: §I.1 · p. 52

I.1.1 PREREQUISITES FOR CONCENTRATION AND LINEARIZATION

• The squared expected operator norm of Υ is bounded by an n0-independent constant.The section also truncates activations at a threshold proportional to √log M to control large entries with high probability.Source: §I.1.1 · pp. 54, 57
• As a consequence of the Taylor expansion and Assump. 3, each entry of ˜∆ is bounded in absolute value by C n_c^-1.Source: §I.1.1 · p. 56

I.1.2 CONTROLLING THE ATYPICAL BEHAVIOR

• The atypical-event argument reduces its contribution to bounded second moments, using Cauchy–Schwarz and P[E^c]→0.The proof then bounds the needed fourth moments by constants.Source: §I.1.2 · pp. 60–61

I.1.3 SCHUR COMPLEMENT FORMULA FOR BOUNDING ∆

• Because centering changes F and f by rank one, the analysis uses a Schur complement to express its effect.The resulting expression is given in Equation (S235).Source: §I.1.3 · pp. 61–62

I.1.4 CONCENTRATION WITH HIGH-PROBABILITY

• The conditional mean δ is at most C n0^-1/2 and its variance is at most C/n0 on Edata.The variance bound follows by Taylor expansion and the law of total variance.Source: §I.1.4 · p. 63
• The concentration argument conditions on suitable events, bounds conditional variance, and applies Chebyshev’s inequality to control random terms.The passages describe conditioning on Edata or EW and using the law of total variance before applying Chebyshev’s inequality.Source: §I.1.4 · pp. 64–66

I.1.5 COMPLETING THE ARGUMENT FOR THE TYPICAL BEHAVIOR

• The typical-behavior argument bounds the deviation ∆ by Cn^-2c conditional on E, for n0-independent constants c and C.The proof decomposes ∆ into two terms and bounds them using the preceding concentration estimates.Source: §I.1.5 · p. 67

I.2 Gaussian equivalents

• Centering activations across training and test distributions leaves limiting test error unchanged, and moment-matched Gaussian linearizations preserve the bulk error, bias, and variance statistics.The linearizations match mixed moments through second order.Source: §I.2 · pp. 69–70

I.3 Decomposition of the test loss

• The test-loss calculation uses kernel matrices K(X,X) and K(X,x), then evaluates the expectation over the test point using linearized representations.The derivation combines those expectation terms with the leading-order behavior in the teacher coefficients.Source: §I.3 · pp. 70–71

I.4 Decomposition of the bias and variance

• The bias is computed using a multivariate bias-variance decomposition, and total variance follows by subtracting bias from total test loss.The derivation introduces independent copies of the random variables to express the bias terms.Source: §I.4 · pp. 71–72

I.5 Summary of linearized trace terms

• The summary collects the trace terms needed for test error, bias, and variance, with the training covariance extracted explicitly from standard Gaussian matrices.Operator-valued free probability is then used to compute the limiting tracial expressions.Source: §I.5 · pp. 72–73

I.6 Calculation of error terms

• General training covariance Σ is handled with operator-valued free probability, reducing the transcendental calculations to one scalar fixed-point equation and algebraic equations given its solution.The method computes the kernel matrix’s operator-valued Stieltjes transform before evaluating the remaining error terms.Source: §I.6 · pp. 73–74
• Augmenting the matrices to self-adjoint form lets operator-valued Stieltjes transforms determine the asymptotic blockwise inverse traces.The Gaussian blocks yield a covariance map, and an iterated sparsity pattern makes the relevant matrix inverses explicit.Source: §I.6 · pp. 75, 76, 80, 81
• In the limit, normalized traces become expectations over the LJSD, leaving dependence on Σ and Σ* through training eigenvalues and overlap coefficients.The derivations use two-index functions of the LJSD to simplify the resulting expressions.Source: §I.6 · pp. 77, 82
• For both E21 and E31, repeated Schur-complement block-matrix inversion yields equations; straightforward algebra solves them for the undetermined entries of GE21 and GE31, obtaining the respective expressions.For E21, Σ* enters linearly in the numerator, simplifying dependence on Σ and Σ*.Source: §I.6 · pp. 79, 82, 83, 87
• Coupled equations for the undetermined entries of G_E32 are solved algebraically to obtain E32.The equations use the LJSD definition, stated relations, and results from App. I.6.1.Source: §I.6 · pp. 92, 94
• Block-matrix inversion and the operator-valued Stieltjes transform provide normalized inverse-block traces needed to compute limiting error terms.The derivation augments Q_E4 to a self-adjoint matrix before determining its asymptotic block-wise traces.Source: §I.6 · pp. 95–96
• The same coupled-equation approach solves for the undetermined entries of G_E4 and yields E4.The derivation simplifies expressions using the LJSD definition, stated relations, and results from App. I.6.1.Source: §I.6 · pp. 98–99

I.6.6 RESULTS FOR TOTAL ERROR, BIAS, AND VARIANCE

• Combining the appendix expressions and cited equations yields the bias and total error, with variance determined using Eµ = Bµ + Vµ.The expressions are in terms of E21, E31, E32, and E4.Source: §I.6.6 · p. 99
• The derivative ∂x/∂γ is specified by Eq. (S669) in terms of x and the asymptotic quantities shown there.Here x is the unique positive real root referenced in Eq. (S408).Source: §I.6.6 · p. 99
• The asymptotic trace objects τ and τ̄ are defined in Eqs. (S406) and (S407).Source: §I.6.6 · p. 100
• Together, these results prove Theorem 5.1.Source: §I.6.6 · p. 100

I.7 Proofs of Cor. 5.1 and Cor. 5.2

• Corollary 5.1 follows from Theorem 5.1 by taking γ → 0 after substituting expressions derived from Eqs. (S526) and (S670).Source: §I.7 · p. 100
• Corollary 5.2 follows from Theorem 5.1 by taking ψ → 0 after substituting expressions derived from Eqs. (S526) and (S670).Source: §I.7 · p. 100
• The Corollary 5.2 expressions use γ_eff = γ/ρ + ω and x as the unique positive real root of the specified equation.The supplied passage does not include that equation.Source: §I.7 · p. 100