Task-Calibrated Random Features via Influence-Based Error Cancellation

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.