Harnessing Multilevel Circulant Matrices for Generalizable Spectral Kernel Learning

Kernel methods, which embed data distributions into a reproducing kernel hilbert space (RKHS) via positive-definite similarity measures, continue to play an important role. However, learning a good, generalizable kernel for high-dimensional and heterogeneous data under temporal or regional distribution shift remains challenging. To address these issues, we propose SpectraMancer, which learns kernels directly in the Fourier spectral domain induced by multilevel circulant matrices, thereby enabling generalizable kernel learning for complex data. SpectraMancer embeds all shift-invariant candidates into a common multilevel order via randomized multilevel circulant matrices, which yields a fixed Fourier diagonalization and turns inverses, products, and gradients into elementwise fast Fourier transform (FFT) operations. To the best of our knowledge, this is the first kernel-learning approach that exploits randomized multilevel circulant matrices for joint diagonalization across kernels. SpectraMancer further enforces scale invariance via kernel double centering and Frobenius normalization, reduces spectral variance through antithetic phase pairing with quasi-Monte Carlo draws, and optimizes a solver-free spectral risk proxy (SRP) for bandwidth weighting without repeated inner solves. Experimental results show that SpectraMancer improves spectrum-aware kernel selection and predictive performance across diverse benchmarks.