CS Paper Radar

Task-Calibrated Random Features via Influence-Based Error Cancellation

Shinto Eguchi

cs.LG stat.ML ·submitted 2026-11-04 22:57 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Calibrated Functional Prediction from Overlapping Nonlinear Observations

cs.LG stat.ML ·2026-11-16 ·Peida Li
benchmark similarity 0.61
Abstract · 34 pages, 8 figures

We study prediction of nonlinear audit functionals from scalar observations of a shared hidden table state. For Schur-rational operators, local Gaussian projections yield a common sparse kernel for overlapping tasks, repeated row identities, and cross-row dependence. Shared-state residual samples extend this kernel through a positive-semidefinite feature representation. Positive matrix integration and sample-value enclosures connect the original inputs to the actual saved hybrid prediction. A sorted calibration-role perturbation bound then certifies its complete finite-pool pinball risk. Independent complete-loss selection chooses the ridge, score scale, and residual weight, while task-rank calibration supplies an upper endpoint. Evaluation uses twenty new reference contexts per dataset at two task sizes, giving 400 conditions across ten benchmark populations. The mean dataset complete-loss ratios are 0.9977 to the degree-two kernel, 0.9961 to matched complete-MC shrinkage, and 0.9911 to the retrospective minimum over 174 public configurations. The last ratio has a paired reference-bootstrap interval of [0.9898,0.9927]. On 40 profiles at coefficient tolerance $10^{-7}$, Gamma quadrature has a geometric mean cold-time ratio of .0646 to strengthened Arb/Petras integration.

0.30

Certified Approximation for Interpretable Representer Landmarks

cs.LG ·2026-09-30 ·Jayanta Mukherjee, Shourya Verma, Mengbo Wang, Jasorsi Ghosh, Ananth Grama
similarity 0.60
Abstract · 29 pages, 8 figures

Representer explanations rank the training landmarks that most influence a self-supervised representation. At scale, this ranking rests on up to four stacked approximations of the empirical neural tangent kernel (eNTK). These are random output heads, a parameter sketch, landmark sampling and a coefficient fit. Existing analyses bound each approximation separately, but none certifies the top-$K$ set against their combined error. We introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. We derive the exact variance of the sketched multi-head eNTK, which matches measurement within $4\%$ where Johnson-Lindenstrauss bounds err by up to $2.5\times$. This yields a high-probability top-$K$ certificate for a fixed coefficient fit, alongside exact residual-trace certificates for discarded spectral mass. An exact product-variance identity separates kernel error from fit variability and identifies when a larger kernel budget can still sharpen a ranking. Stochastic Lanczos Quadrature (SLQ) estimates the effective dimension within $0.72\%$ and guides the landmark budget without dense eigendecomposition. We show that residual mass does not control class coverage, and residual-greedy selection cuts the worst coverage excess of $k$-means++ from $8.5\times$ to $1.55\times$ ($4\times$ on the sketched eNTK). Cross-view initializers outperform principal-component initialization in five (AUI) to all six (CSI) settings. Against the KREPES Gauss-Newton solver, CAIRN converges $2.5$ to $11.3\times$ faster, trails by at most $0.31$ points and gains up to $3.14$ points on MNIST. Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.

0.22

Scalable and Adaptive Distribution Regression via Random Features

cs.LG stat.ML ·2026-10-17 ·Yinsong Wang, Xiao Liu, Yu Ding
theory similarity 0.60
Abstract

Distribution regression seeks to learn mappings from probability distributions to response variables and has emerged as a unifying framework for kernel methods, multi-instance learning, and set-valued learning. Despite its success, kernel-based distribution regression remains computationally expensive and sensitive to kernel choice, motivating scalable and adaptive representations. Building on random feature approximations, we develop a finite-sample analysis of Random Feature Distribution Regression (RaDR) under two-stage sampling. Our perturbation analysis separates the effects of distribution-level sampling, finite within-bag sampling, and random feature approximation. We establish sufficient feature-budget conditions under which RaDR preserves the order of our excess-risk upper bound for exact two-stage kernel distribution regression while maintaining computational efficiency. We further propose Adaptive Random Feature Distribution Regression (A-RaDR), a unified score-guided framework that adaptively allocates random features according to downstream learning objectives. Experiments on synthetic benchmarks and 41 real-world datasets demonstrate that RaDR delivers substantial computational savings while maintaining competitive predictive performance, whereas A-RaDR further improves learning accuracy in distribution regression while retaining the computational speed up. Together, these results establish a practical and theoretically grounded framework for adaptive, scalable distribution learning

0.16

Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs

cs.LG stat.MLstat.CO ·2026-09-17 ·Zhenlin Yao, Wei Xiong
similarity 0.57
Abstract · 41 pages, 4 figures, 18 tables; includes core supplementary material

Accurate optimization of a supervised spectral objective need not produce an accurate population subspace or a better predictive representation. We investigate these distinctions for Online Kernel Supervised Principal Component Analysis (OKSPCA), which combines a centered cross-moment in finite random-feature coordinates with an Adam-style orthonormal basis update for an established objective. Fixed-map consistency, concentration and perturbation results describe the estimator and its exact subspace; same-target comparisons then assess the practical iterate separately. Across six predictive benchmarks, performance depends on the declared pipeline: replacing the tracker with the exact empirical target leaves the two regression deficits largely unchanged. Direct classification-rank models capture nearly all terminal objective energy on average, but a saved intermediate state exhibits substantial geometric deviation; a controlled sample-size study further separates empirical accuracy from population recovery. In distinct numerical-service workloads, exact on-request computation is faster in the tested classification settings, whereas Adam saves time relative to the tested full thin-SVD service for some dense wider-regression requests, alongside persistent geometric error. These diagnostics limit explanations based solely on terminal optimization accuracy and distinguish numerical cost from quality, rank coverage and freshness; they establish neither practical-tracker convergence nor predictive or deployment benefits from basis availability.

0.27

Trace-Norm Geometry of Composed Multitask Predictors

cs.LG ·2026-08-25 ·Mahdi Mohammadigohari
similarity 0.56
Abstract · Substantially revised and expanded. Added uniform guarantees for estimated feature Gram matrices, regularized fitting and generalization res…

Multitask predictors apply task-specific functions to a shared representation. Penalizing the representation and task functions separately can assign different costs to equivalent predictors and charge for directions the tasks do not use. We study the trace norm of the complete task predictors in a fixed input reproducing kernel Hilbert space, weighted by task sample sizes. For a finite-dimensional intermediate function space, this norm is the infimum of the product of the representation operator norm and task trace norm over invertible coordinate changes. Task inner products determine this norm; standard duality gives the exact empirical Rademacher complexity of its norm ball. We estimate the feature Gram matrix used in fitting. Under bounded leverage, one estimate controls the penalty for every task head and shared linear combination of fixed features, even when the Gram is singular and the coefficients are chosen after estimation. This yields comparisons of penalized empirical objectives and a generalization bound under an estimated norm constraint, with the stated loss and sampling assumptions. Controlled experiments show that signal alignment can favor either penalty. A SARCOS comparison finds close agreement between exact and estimated penalties on overlapping training and evaluation observations.

0.22

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

cs.LG stat.ML ·2026-10-13 ·Caixing Wang
similarity 0.56
Abstract · 61 pages, 10 figures, 2 tables

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.

0.24

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

cs.LG stat.ML ·2026-08-26 ·Caixing Wang, Zhibo Chen, Yue Wang
hot direction similarity 0.54
Abstract · 31 pages, 10 figures, 3 tables

Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.

0.33

Universal Distributed Feature Extraction Complementary to Side Information via H-Score

cs.IT cs.LGeess.SP ·2026-10-12 ·Yuan Xinjie, Dier Tang, Shao-Lun Huang
similarity 0.54
Abstract

This paper considers a distributed estimation system where edge nodes transmit averaged features to a center node for parameter estimation. A key challenge arises when the center node possesses auxiliary side information: how to design local extractors that are universally optimal for any downstream task, while avoiding redundancy with the side information. To tackle this problem, we orthogonally decompose the joint function space and demonstrate in the weak-dependence regime that the modal decomposition of the canonical dependence kernel's conditional-additive component yields optimal, task-independent features. We construct a distributed nested H-score to learn this decomposition and show that, under a limited feature budget, the mean-squared error (MSE) gap to the best task-specific features is determined solely by the task's alignment with the discarded, least informative modes, and vanishes to leading order for every square-integrable task once the budget is sufficient.

0.30