Bernstein-Schur Kernels: New random features slash dimension from O(d²) to Dm

Kernel methods remain powerful but suffer from cubic scaling in data size — random feature approximations reduce this, but existing techniques (Bochner sampling, polynomial sketching) fail on nonstationary kernels like those mixing shift-invariance and dot-products. Taha Bouhsine's new paper introduces Bernstein-Schur Kernels, a unified class where the kernel is a product of a finite-feature kernel and a completely monotone shift-invariant kernel. The core contribution is a random-feature construction that simultaneously sketches the finite modulation and randomizes the radial component, drawing from the one-dimensional Bernstein-Widder scale then applying Gaussian random Fourier features. This produces a feature dimension of D×m, where m is the sketch size and D the number of radial draws — crucially avoiding the O(d²) cost of exact modulation features.

The paper provides rigorous theoretical guarantees: in the limit where the modulation is exact (m→∞), the estimator is unbiased with an exact variance formula for the recommended flat estimator, plus an expected matrix-Bernstein operator-norm bound controlled by the top eigenvalues of the kernel and modulation Gram matrices. This bound depends on an intrinsic dimension rather than crude entrywise maxima, and a deterministic relative-spectral kernel-ridge stability result is proven. When the sketch is conditioned, the doubly-randomized estimator inherits the same intrinsic-dimension operator-norm guarantee plus an additive sketch term tunable independently of D. The motivating instance is the biased yat-kernel (w·x+b)²/(||w-x||²+ε), whose family spans the inverse-multiquadric kernel — for it the radial mixture becomes the IMQ spectral sampler, and one frequency per scale is variance-optimal at a fixed radial-feature budget. This work opens the door to efficient, provably accurate kernel approximations in high-dimensional settings where traditional random features fail.