Task-Calibrated Random Features via Influence-Based Error Cancellation

Shinto Eguchi

stat.MLNov 4, 2026

Task-Calibrated Random Features via Influence-Based Error Cancellation

Authors: Shinto Eguchi

Abstract

Random features approximate kernel integrals by Monte Carlo, yet only selected frequency-sampling errors affect a downstream task. We propose Task-Calibrated Random Features (TCRF), which balance frequency moments constructed from task-specific influence using weights shared across kernel entries. Closed-form weights coincide with classical minimum-distance calibration; the contribution is a reusable, task-derived calibration space. We show that first-order variance equals the residual variance after projection onto this space. For kernel ridge regression, complete cancellation yields a non-Gaussian second-order limit. For kernel Stein discrepancy, a subset identity and disjoint-block variance decomposition eliminate the linear component of pilot noise. Positive exponential-tilting weights preserve the positive-semidefinite feature representation and support higher feasible calibration ranks. Paired experiments show improved approximation to exact kernel ridge regression at larger frequency budgets and to the exact empirical Stein discrepancy under a fixed alternative, even after accounting for a frequency-equivalent pilot budget. Gains are smaller with cross-validated ridge, landmark pilots require conservative rank selection, and near the Stein null allocating the pilot budget to additional ordinary frequencies is preferable.

Figures & tables

$\lambda=0.02$
$m$	RFF RMSE	MM	TCRF	MM–TCRF	TCRF-ET	MM–TCRF-ET
50	0.1054	0.782	0.965 [3.5]	0.739 [7.3]	0.886 [10.9]	0.691 [13.6]
100	0.0768	0.767	0.894 [6.5]	0.673 [11.4]	0.615 [23.8]	0.529 [25.8]
200	0.0558	0.755	0.777 [10.8]	0.574 [16.7]	0.440 [44.6]	0.388 [49.0]
400	0.0388	0.771	0.605 [18.4]	0.479 [23.8]	0.329 [63.5]	0.311 [63.8]
800	0.0273	0.775	0.476 [27.5]	0.406 [33.5]	0.298 [64.0]	0.287 [64.0]

Table 1: Kernel ridge regression approximation error over 200 replications. The RFF column gives the mean RMSE with respect to exact KRR; the remaining columns give the ratio of the mean RMSE to RFF, with the mean selected rank in square brackets. TCRF and MM–TCRF use the closed-form weights with rank rule ( 6 ); TCRF-ET and MM–TCRF-ET use exponential-tilting weights with the pilot-proxy rank rule ( 15 ). Lower is better.

Figure 1: KRR approximation RMSE relative to RFF under the fixed and cross-validated ridge parameters, comparing closed-form and ET calibration; bars are paired-bootstrap 95% intervals. The candidate-rank grid ends at

64

; ET often selects this boundary for the larger frequency budgets.

$\lambda=0.02$ ; exact KRR 0.6791
$m$	RFF	MM	MM–TCRF	MM–TCRF-ET
50	0.7016	0.6895	0.6954	0.6924
100	0.6912	0.6855	0.6860	0.6821
200	0.6855	0.6820	0.6819	0.6780
400	0.6824	0.6802	0.6797	0.6780
800	0.6814	0.6799	0.6791	0.6784

Table 2: Statistical error: mean RMSE against the true regression function. The block headings give the error of exact KRR; the entries include the additional frequency-approximation error.

$\lambda=0.02$
	$n_{L}=30$		$n_{L}=50$		$n_{L}=100$
$m$	CF	ET	CF	ET	CF	ET
100	0.964	1.011	0.943	0.905	0.923	0.807
200	0.935	0.909	0.885	0.811	0.838	0.698
400	0.863	0.825	0.820	0.749	0.752	0.655
800	0.834	0.802	0.776	0.733	0.679	0.637

Table 3: Landmark hybrid relative to moment matching over 150 paired replications: ratio of the mean RMSE of MM–Landmark-TCRF to that of MM, with closed-form weights (CF) and exponential-tilting weights (ET). Lower is better.

Figure 2: Paired percentage reduction in landmark-hybrid approximation RMSE relative to MM over

150

replications, with 95% intervals; positive values favour the hybrid. The two ridge choices reveal that ET gains under the fixed

\lambda=0.02

setting need not carry over to the cross-validated full-sample prediction task.

Figure 3: Recovery of the KSD zero-variance direction with independent pilot subsets. The residual ratio

\rho_{D}

is shown against the number of pilot subsets

L

at fixed subset size

s=50

(left) and against subset size

s

at fixed

L=30

(right). Error bars are 95% Monte Carlo intervals over

100

replications.

Null
$m$	$n$	RFF ( $m+s$ )	Scale score	Indep. CF	Indep. ET	Disjoint CF	Disjoint ET
50	1000	0.574	0.996	0.959	0.961	0.962	0.957	[0.922, 0.994]
50	2000	0.578	0.977	0.961	0.949	0.978	0.971	[0.935, 1.005]
50	5000	0.608	0.989	0.999	0.994	0.974	0.967	[0.939, 0.997]
200	1000	0.810	0.981	0.924	0.923	0.938	0.938	[0.913, 0.963]
200	2000	0.806	0.976	0.951	0.950	0.941	0.939	[0.916, 0.964]

Table 4: Frequency-approximation RMSE relative to the exact empirical squared V-KSD (

s=100

): ratio to ordinary RFF with

m

frequencies over 100 datasets and eight frequency draws per dataset. RFF (

m+s

) spends the pilot budget of

ns

kernel evaluations on

s

additional frequencies. CF denotes the closed-form weights with rank rule ( 6 ); ET denotes exponential-tilting weights. Square brackets give paired-bootstrap 95% intervals for Disjoint ET over RFF.

Figure 4: Exact empirical squared V-KSD approximation error under the fixed mean shift: closed-form and ET calibration with independent and disjoint-block pilots (

s=100

). Error ratios are relative to uncalibrated RFF on paired datasets and frequencies; bars are paired-bootstrap 95% intervals. Null results are reported in Table 4 .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

$\lambda=0.02$
$m$	CF	ET-ESS 0.5	ET-ESS 0.9	ET-pMSE	ET-pMSE †
50	0.739 [7.3]	0.694 [15.6]	0.742 [5.7]	0.691 [13.6]	0.674 [13.6]
100	0.673 [11.4]	0.520 [28.2]	0.670 [11.0]	0.529 [25.8]	0.507 [25.8]
200	0.574 [16.7]	0.388 [48.2]	0.532 [20.1]	0.388 [49.0]	0.374 [49.6]
400	0.479 [23.8]	0.310 [63.9]	0.410 [34.0]	0.311 [63.8]	0.276 [85.4]
800	0.406 [33.5]	0.287 [64.0]	0.303 [58.0]	0.287 [64.0]	0.196 [111.8]

Appendix

Table D.1: Sensitivity of MM–TCRF to the weight family and the rank rule: ratio of the mean RMSE to RFF, with the mean selected rank in square brackets. CF is the closed-form rule ( 6 ); ET-ESS τ selects the largest rank whose exponential-tilting weights have effective sample size at least

\tau m

; ET-pMSE minimises the pilot proxy ( 15 ). † The candidate grid is extended by 80, 96 and 112, on an independent set of 100 replications. Lower is better.

Figure D.1: Sensitivity of the KRR ET approximation to increasing the candidate-rank limit from

64

112

. The extended grid uses an independent

100

-replication run rather than the primary

200

-replication sample.

		Full $\lambda$			Landmark CV
$n_{L}$	$m$	CF	ET-pMSE	ET-ESS 0.9	CF	ET-pMSE	ET-ESS 0.9
30	100	0.996	1.113	0.995	1.005	1.072	1.006
30	200	0.996	1.115	1.004	0.995	1.061	1.003
30	400	0.987	1.018	0.994	0.994	1.002	0.993
30	800	0.991	0.964	0.967	0.983	0.971	0.972
50	100	0.999	1.094	1.003	1.000	1.059	1.000

Appendix

Table D.2: Landmark hybrid under cross-validated full-data ridge (100 paired replications): ratio of mean approximation RMSE to MM. Full

\lambda

uses the full-data cross-validated ridge in the landmark subproblem; landmark CV selects a separate subproblem ridge by five-fold cross-validation on landmarks. Lower is better.

$m$	Method	Mean RMSE	MCSE	/RFF	Mean rank	Rank-0 (%)	ESS
50	RFF	0.1083	0.0013	1.000	–	–	–
50	MM	0.0823	0.0010	0.760	–	–	–
50	TCRF	0.1040	0.0015	0.961	3.2	41.0	47.5
50	MM–TCRF	0.0774	0.0012	0.715	7.1	13.5	46.2
100	RFF	0.0774	0.0009	1.000	–	–	–
100	MM	0.0585	0.0006	0.756	–	–	–

Appendix

Table D.3: Detailed kernel ridge regression results. Rank-0 is the percentage of replications in which no positive task-calibration rank was admissible. ESS is the effective sample size of the frequency weights.

$m$	Method	Mean gain	MCSE	95% interval	Positive (%)
50	TCRF	$-0.02172$	0.00123	$[-0.02412,-0.01932]$	10.5
50	MM–TCRF	0.00490	0.00078	$[0.00336,0.00643]$	60.0
100	TCRF	$-0.01041$	0.00093	$[-0.01223,-0.00858]$	23.0
100	MM–TCRF	0.00863	0.00053	$[0.00760,0.00966]$	88.0
200	TCRF	$-0.00019$	0.00075	$[-0.00166,0.00127]$	52.5
200	MM–TCRF	0.01148	0.00038	$[0.01073,0.01223]$	99.5

Appendix

Table D.4: Paired kernel ridge regression gains relative to moment matching. The gain is the RMSE of MM minus that of the method, so positive values favour the method; the positive fraction is the percentage of replications in which the method has smaller approximation RMSE than MM.

$n_{L}$	$m$	Method	RMSE	MCSE	/RFF	Rank	Rank-0 (%)	Red. (%)
30	100	Landmark-TCRF	0.0708	0.0010	0.940	6.7	6.7	–
30	100	MM–Landmark-TCRF	0.0565	0.0007	0.750	11.1	0.7	1.6
30	200	Landmark-TCRF	0.0474	0.0008	0.885	10.8	2.0	–
30	200	MM–Landmark-TCRF	0.0383	0.0005	0.716	15.1	0.0	5.8
30	400	Landmark-TCRF	0.0308	0.0005	0.817	16.5	0.7	–
30	400	MM–Landmark-TCRF	0.0252	0.0004	0.668	21.1	0.0	10.7

Appendix

Table D.5: Detailed landmark results for the task-calibrated methods. RMSE is the mean RMSE with respect to exact KRR, and Rank-0 is the percentage of replications with no admissible positive rank. The final column is the paired percentage reduction in RMSE relative to MM for the hybrid; the standalone method is left blank in that column.

Scenario	Sweep	Setting	Mean $\rho_{D}$	MCSE	95% interval
Mixture	$L$	$L=1,\ s=50$	0.9287	0.0066	[0.9157,0.9416]
Mixture	$L$	$L=3,\ s=50$	0.9023	0.0072	[0.8881,0.9165]
Mixture	$L$	$L=10,\ s=50$	0.8484	0.0077	[0.8334,0.8634]
Mixture	$L$	$L=30,\ s=50$	0.7214	0.0095	[0.7029,0.7400]
Mixture	$L$	$L=100,\ s=50$	0.4667	0.0082	[0.4505,0.4829]
Mixture	$s$	$L=30,\ s=25$	0.8687	0.0076	[0.8538,0.8837]

Appendix

Table D.6: KSD subset-recovery diagnostics with independent pilot subsets. The two sweeps vary

L

at fixed

s=50

and vary

s

at fixed

L=30

, respectively.

Scenario	$n$	$s$	$m$	RFF ( $m+s$ )	Indep. CF	Indep. ET	Disj. CF	Disj. ET
Null	1000	50	50	0.698	0.972	0.974	0.992	0.999
Null	1000	50	100	0.822	0.952	0.951	0.971	0.966
Null	1000	50	200	0.891	0.961	0.960	0.959	0.959
Null	1000	100	50	0.574	0.959	0.961	0.962	0.957
Null	1000	100	100	0.717	0.941	0.936	0.956	0.955
Null	1000	100	200	0.810	0.924	0.923	0.938	0.938

Appendix

Table D.7: Exact empirical squared V-KSD benchmark for both subset sizes: ratio of frequency-approximation RMSE to ordinary RFF with

m

frequencies, over 100 datasets and eight frequency draws per dataset. RFF (

m+s

) spends the pilot budget of

ns

kernel evaluations on

s

additional frequencies; CF and ET denote closed-form and exponential-tilting weights with independent (Indep.) or disjoint-block (Disj.) pilots. The rows with

s=100

m\in\{50,200\}

repeat Table 4 .

Figure D.2: Absolute RMSE to the exact empirical squared V-KSD as a function of the number of frequencies

m

n=5000

and

s=100

. Left: Gaussian null; right: fixed mean-shift alternative.

$m$	ORF ( $m+200$ )	NY–MM–TCRF ( $J=20$ )	NY–MM–TCRF ( $J=80$ )	$J=80$ /ORF
700	0.03196	0.03229	0.03153	0.987 [0.956,1.019]
750	0.03184	0.03007	0.02966	0.931 [0.903,0.961]
800	0.03129	0.02948	0.02870	0.917 [0.887,0.950]

Appendix

Table E.1: Large-sample closed-form KRR approximation with the pilot-inclusive frequency budget (

n=10{,}000

M_{0}=200

100

paired replications). RMSE is measured against the 500-point Nyström KRR reference. The last column reports the ratio of mean RMSEs with a 95% paired-bootstrap interval.

$m$	ORF ( $m+200$ )	NY–MM–TCRF ( $J=20$ )	TCRF/ORF [95% CI]
400	0.03959	0.04272	1.079 [1.046,1.113]
500	0.03700	0.03685	0.996 [0.964,1.031]
600	0.03453	0.03428	0.993 [0.962,1.025]
700	0.03196	0.03229	1.011 [0.980,1.042]
750	0.03184	0.03007	0.945 [0.916,0.974]
800	0.03129	0.02948	0.942 [0.913,0.973]

Appendix

Table E.2: Complete pilot-inclusive frequency grid with

J=20

design points. Each entry is the mean RMSE over

100

paired replications relative to the independently fitted Nyström-500 reference. The last column is a ratio of mean RMSEs with a 95% paired-bootstrap interval.

Kernel Stein Discrepancy

See all 8 papers

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
Oct 13, 2026Caixing WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University, Nanjing, China
Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Aug 26, 2026Caixing Wang, Zhibo Chen, Yue WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China
Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding
May 25, 2026Rustem Takhanov, Zhenisbek AssylbekovKernel Ridge Regression Kernel Regression
Department of Mathematics, Nazarbayev University, Astana, Kazakhstan · Nazarbayev University Research Administration, Astana, Kazakhstan · Purdue University Fort Wayne, Indiana, USA.

Oct 13, 2026J/K move · Enter open · S save

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

Caixing Wang

School of Statistics and Data Science, Southeast University, Nanjing, China

Random Feature Methods Kernel Ridge Regression Statistical Learning Theory Model Misspecification

Open paper AskPDF arXiv

Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with

2r+γ>α_0

, where

(r,γ,α_0)

denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when

α_0=γ

, KRR-RF are minimax optimal for all

r \in (0,1]

. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.

Abstract

Kernel Stein Discrepancy

Explore similar work

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees

Conditional KRR: Injecting Unpenalized Features into Kernel Methods with Applications to Kernel Thresholding