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

arXiv: https://arxiv.org/abs/2606.11255 · HTML: https://mlsanity.com/paper/2606.11255/

## 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 (most cited first, 23 of 23)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Gaussian Process Kernels for Pattern Discovery and Extrapolation](https://mlsanity.com/paper/1302.4245/) (2013)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels](https://mlsanity.com/paper/1412.8293/) (2014)
- [Non-Stationary Spectral Kernels](https://mlsanity.com/paper/1705.08736/) (2017)
- [Spatial Mapping with Gaussian Processes and Nonstationary Fourier Features](https://mlsanity.com/paper/1711.05615/) (2017)
- [Implicit Kernel Learning](https://mlsanity.com/paper/1902.10214/) (2019)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Harmonizable mixture kernels with variational Fourier features](https://mlsanity.com/paper/1810.04416/) (2018)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Random Features for Compositional Kernels](https://mlsanity.com/paper/1703.07872/) (2017)
- [A spectral mixture representation of isotropic kernels with application to random Fourier features](https://mlsanity.com/paper/2411.02770/) (2024)
- [SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernel](https://mlsanity.com/paper/2602.04915/) (2026)
- [A Universal Reproducing Kernel Hilbert Space from Polynomial Alignment and IMQ Distance](https://mlsanity.com/paper/2605.03262/) (2026)

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