mlsanityData to 14 Oct 2026

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

arXiv 2606.11255 ↗First posted 8 Jun 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Bernstein--Schur kernels are products of a finite-feature kernel and a completely monotone shift-invariant kernel: nonstationary kernels falling between the shift-invariant and dot-product templates random features exploit, so neither Bochner sampling nor polynomial sketching applies to the full kernel directly. We give one random-feature construction for the whole class that randomizes both factors: it sketches the finite modulation and samples the radial factor's one-dimensional Bernstein--Widder scale before applying Gaussian random Fourier features, giving feature dimension Dm, free of the O(d2) size of the exact modulation feature. With the modulation kept exact (the m→∞ limit), we prove unbiasedness, an exact variance, and a matrix-Bernstein operator-norm bound controlled by the top kernel and modulation eigenvalues and an intrinsic dimension rather than the crude Nmaxij route. Whitening this argument at the ridge makes the effective dimension deff(λ) the exact intrinsic dimension of the matrix variance, so O((1+|P|op/λ)log(deff/δ)) radial draws preserve the kernel-ridge solution; tilting the draw by a closed-form whitened leverage improves this to the effective-dimension count O((1+deff)log(deff/δ)). Conditioning on the sketch carries every guarantee to the deployed doubly-randomized estimator up to one additive sketch term, and all hold for the whole class with the modulation Gram in place of the polynomial one. The flagship instance is the biased yat-kernel kyat,b(w,x)=(w^top x+b)2/(|w-x|2+varepsilon), whose family span contains the inverse-multiquadric kernel by finite differences in b.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 43 references that are in the map. First posted on arXiv 8 Jun 2026.

Builds on

23 of 43 references.

References · 23

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  2. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  3. 2020Rethinking Attention with Performerscited by 1,601
  4. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  5. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  6. 2016Generalization Properties of Learning with Random Featurescited by 164
  7. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  8. 2013Gaussian Process Kernels for Pattern Discovery and Extrapolationcited by 132
  9. 2016Orthogonal Random Featurescited by 91
  10. 2013Structure Discovery in Nonparametric Regression through Compositional Kernel Searchcited by 88
  11. 2014Fastfood: Approximate Kernel Expansions in Loglinear Timecited by 74
  12. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
11 more
  1. 2014Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernelscited by 42
  2. 2017Non-Stationary Spectral Kernelscited by 38
  3. 2017Spatial Mapping with Gaussian Processes and Nonstationary Fourier Featurescited by 16
  4. 2019Implicit Kernel Learningcited by 13
  5. 2022Improved Random Features for Dot Product Kernelscited by 12
  6. 2018Harmonizable mixture kernels with variational Fourier featurescited by 8
  7. 2022Random Gegenbauer Features for Scalable Kernel Methodscited by 6
  8. 2017Random Features for Compositional Kernelscited by 5
  9. 2024A spectral mixture representation of isotropic kernels with application to random Fourier featurescited by 5
  10. 2026SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernelcited by 1
  11. 2026A Universal Reproducing Kernel Hilbert Space from Polynomial Alignment and IMQ Distancecited by 1

Built on by

Not cited yet.