CS Paper Radar

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

Caixing Wang, Yue Wang

cs.LG stat.ML ·submitted 2026-10-22 09:01 UTC · v1

Abstract

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., $s> α_0-1/β$, where $s,β$, and $α_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $α_0=1/β$, the optimality holds for all $s\in (0,2τ]$ with $τ$ and $γ$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.

Closest papers

Nearest neighbours by meaning across the whole index.

Kernel-Based Learning of Analytic Operators and Parametric PDEs

cs.LG stat.MLmath.ST ·2026-11-06 ·Giovanni S. Alberti, Markus Holzleitner, Lorenzo Rosasco, Matteo Santacesaria
similarity 0.72
Abstract · 43 pages, 4 figures

We study kernel-based learning of analytic operators from finite samples, with a focus on how the regularity of the target should determine the choice of the kernel. We establish embeddings of analytic operators into vector-valued reproducing kernel Hilbert spaces and derive finite-sample, high-probability guarantees that quantify the uncertainty due to random sampling: in the noiseless setting, suitable analytic kernels yield rates exponential in a fractional power of the sample size, while Sobolev-type kernels yield polynomial rates. We apply the theory to the solution operator of a parametric elliptic PDE, where the training data are themselves finite-element approximations, and obtain bounds that separate the sampling and discretization contributions to the error and prescribe how the mesh size should be coupled to the sample size. The results are illustrated numerically.

0.20

Unbounded Characteristic and Universal Kernels

cs.LG math.STstat.ML ·2026-10-07 ·Jose Cribeiro-Ramallo, Florian Kalinke, Zoltán Szabó
similarity 0.66
Abstract

Kernel methods are among the most powerful tools in machine learning and statistics, with a large number of successful applications. Their immense success stems from the flexible function class associated to each kernel---its reproducing kernel Hilbert space (RKHS)---which facilitates statistical analysis, as well as from their computational tractability and applicability to many domains. Multiple notions (such as characteristic, $L_p$-universal, and integrally strictly positive definite) capture the expressivity of kernels and their RKHSs and play a key role in understanding the statistical properties of kernel methods; these concepts and their relations are well-understood for bounded kernels. Even though unbounded kernels have received significant attention over the past decade (for instance, in the construction of kernel-based discrepancy and dependence measures such as the maximum mean discrepancy, the Hilbert-Schmidt independence criterion, and the kernel Stein discrepancy), surprisingly little is known about the relations of these notions in the unbounded case. In the present paper we tackle this severe bottleneck, establishing their relations under mild assumptions.

0.18

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.65
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

Learning under Target Shift: Optimal Density Ratio Estimation and Importance-Weighted Regression

cs.LG stat.ML ·2026-09-14 ·Ren-Rui Liu, Zheng-Chu Guo
similarity 0.64
Abstract

We study density ratio estimation and importance-weighted regression under target shift with continuous outputs. Under target shift, the conditional distribution of the inputs given the outputs remains invariant across the training and test distributions, while the output marginal distribution may change. Although this problem has been extensively studied for discrete outputs, the continuous setting is substantially less understood: the importance weights are determined by an unknown density ratio function, for which existing estimation methods lack explicit finite-sample convergence rates. We propose a spectral regularization method in a reproducing kernel Hilbert space (RKHS) for estimating the continuous density ratio from labeled training samples and unlabeled test inputs. Under a source condition with regularity parameter $ι>0$, we establish high-probability finite-sample guarantees and show that the estimator achieves the capacity-independent minimax-optimal RKHS-norm rate $O(n_η^{-ι/(2ι+2)})$. We then incorporate the estimated density ratio into importance-weighted regression and characterize the propagation of density-ratio estimation error to the final predictor. When sufficiently many samples are available for density ratio estimation, the resulting regression estimator attains the minimax-optimal rates of standard kernel regression. These results establish a finite-sample theory for continuous density ratio estimation and importance-weighted learning under target shift.

0.28

Revisiting Thinning Methods for Kernel Learning Problems

cs.LG cs.AI ·2026-09-07 ·Blanca Cano-Camarero, Yago R. Aguado-Carrillo-de-Albornoz, Ángela Fernández-Pascual, José R. Dorronsoro
similarity 0.63
Abstract

Kernel methods are widely used because of their strong theoretical guarantees and empirical performance. However, their high computational cost limits their applicability to large-scale datasets. To address this shortcoming, several approaches use Maximum Mean Discrepancy to construct representative subsets that preserve the properties of the full dataset in a Reproducing Kernel Hilbert Space. We introduce Backward Kernel Herding, an algorithm that addresses this problem by iteratively removing points from the dataset, achieving results comparable to current state-of-the-art approaches while accelerating the subsampling process in realistic scenarios where the reduced size is less than half of the dataset. Moreover, we overcome a limitation of Kernel Thinning by proposing an extension that enables the construction of subsets of arbitrary size rather that restricting to successive halvings. Finally, we conduct an extensive experimental comparison focusing on the most relevant kernel learning procedures: Gaussian Processes and Kernel Support Vector Machines. The results show that Backward Kernel Herding consistently achieves competitive performance with the most favorable training-time efficiency, while the proposed Flexible Kernel Thinning frequently achieves the best predictive performance. These gains become especially pronounced for moderate compression ratios, highlighting the benefits of incorporating supervised information into the thinning process. In terms of memory consumption, Flexible Kernel Thinning is also competitive, whereas Backward Kernel Herding remains an alternative when computational efficiency is the primary objective. Overall, no single method dominates across all scenarios, underscoring the importance of selecting the reduction strategy according to the desired trade-off between predictive performance, training cost, and memory requirements.

0.19

Deep kernel hedging

cs.LG math.FAq-fin.CPq-fin.RM ·2026-09-28 ·Jean-Loup Dupret, Donatien Hainaut, Edouard Motte
theory similarity 0.63
Abstract

We introduce a deep kernel hedging framework that combines the flexibility of deep learning with the structural inductive bias of kernel methods. The hedging functional is restricted to a reproducing kernel Hilbert space whose kernel is parameterized through a neural network embedding of the input features. The framework minimizes a regularized empirical risk under convex loss functions and can accommodate path-dependent information through truncated time-augmented signature features. We derive a generalized representer theorem for the joint hedging problem, reducing the empirical optimization to a finite-dimensional problem. To further reduce the computational cost associated with large kernel matrices, we develop a scalable random Fourier feature approximation and establish convergence guarantees. The random Fourier parameters are sampled once and remain fixed throughout training, while the deep kernel adapts to market data through the learned neural representation. We evaluate the performance of the proposed deep kernel approach on both synthetic and real data and compare it with standard kernel methods and classical deep hedging architectures. Numerical results indicate competitive and robust hedging performance, particularly in low-data regimes, which highlights the benefits of combining expressive neural representations with the inductive bias of kernel methods.

0.31

Energy-Guided Learning for Heat Equation with Noisy Source: Optimal Estimation and Generalization Bounds

cs.LG math.STstat.MEstat.ML ·2026-10-10 ·Zixiang Zhou, Xiaohui Chen, Shanghua Teng
similarity 0.63
Abstract

Data and the governing partial differential equations (PDEs) of continuous-time dynamical systems provide rich structure for statistical learning. A central challenge is how to integrate data with PDE constraints in a principled way to improve generalization. In this paper, we characterize the statistical estimation and generalization properties of learning solutions to the heat equation with a noisy source function from finite, randomly sampled data. We first derive a novel variational formulation, which we characterize as the minimizer of loss function for an energy regularized and ellipticity debiased Sobolev regression. By formulating the learning task as a supervised problem over space-time domains under physically meaningful norms, our approach goes beyond the traditional supervised learning framework by effectively leveraging \emph{auxiliary data}---samples of the source function of the heat equation---to design a \emph{physics-informed energy regularization}. Our analysis reveals that learning in linear parabolic PDEs exhibits intrinsic anisotropy between spatial and temporal regularity, in sharp contrast to the static elliptic problems, leading to fundamentally different estimation and generalization behaviors. Specifically, we derive non-asymptotically rate-optimal estimation errors, as well as generalization error, which explicitly capture the interplay among temporal sampling, spatial resolution, and solution smoothness. Our numerical experiments demonstrate substantial orders of magnitude of reduction in testing errors against various physics-informed neural network methods on various parabolic and hyperbolic PDEs.

0.13

Gaussian Approximation of Besov Functions for Logistic Classification on Manifolds

cs.LG stat.MLmath.ST ·2026-10-19 ·Guanhang Lei, Lei Shi, Xiaoming Yuan
similarity 0.62
Abstract

We study Gaussian kernel approximation and regularized logistic classification on a connected compact smooth embedded manifold $X\subset\mathbb R^d$ without boundary and of intrinsic dimension $\varrho$. Two main challenges are to derive a fast oracle inequality without assuming a bounded Bayes function and to construct Gaussian approximants that exploit both the intrinsic dimension and the target's regularity without saturation. We address the first challenge through a Bernstein-type inequality whose constant depends linearly on the supremum norm of the predictor. Combined with localized complexity estimates, this yields an oracle inequality over separable normed function spaces. To address the second challenge, we establish a uniform Sobolev operator expansion and cancel its lower-order bias terms using a signed combination of Gaussian kernel integral operators at different bandwidths. Real interpolation then gives an $L_2(X)$ approximation error of order $γ^α$ for functions in $B^α_{2,\infty}(X)$, where $γ$ is the bandwidth. By constructing the approximants directly on the manifold without ambient extension, we obtain a squared Gaussian RKHS norm bound of order $γ^{-\varrho}$. This construction thus overcomes second-order saturation while retaining norm control governed by the intrinsic dimension. When the marginal distribution has a density $g\in L_p(X)$, these results yield the logistic excess-risk rate $\bigl((\log n)^{\varrho+1}/n\bigr)^{4α(1-1/p)/(4α(1-1/p)+3\varrho)}$. We further show that clipping predictions yields the faster clipped logistic excess-risk rate $\bigl((\log n)^{\varrho+2}/n\bigr)^{2α(1-1/p)/(2α(1-1/p)+\varrho)}$. For bounded densities, its polynomial exponent matches that of the minimax optimal rate for squared-loss regression, and its corresponding excess misclassification risk also matches the minimax optimal rate.

0.50