# Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 1 Feb 2026.

## Builds on (most cited first, 22 of 22)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Gaussian Process Kernels for Pattern Discovery and Extrapolation](https://mlsanity.com/paper/1302.4245/) (2013)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Non-Stationary Spectral Kernels](https://mlsanity.com/paper/1705.08736/) (2017)
- [Random Feature Expansions for Deep Gaussian Processes](https://mlsanity.com/paper/1610.04386/) (2016)
- [Deep Gaussian Processes with Importance-Weighted Variational Inference](https://mlsanity.com/paper/1905.05435/) (2019)
- [Learning to Learn Kernels with Variational Random Features](https://mlsanity.com/paper/2006.06707/) (2020)
- [Inter-domain Deep Gaussian Processes](https://mlsanity.com/paper/2011.00415/) (2020)
- [Compositional Modeling of Nonlinear Dynamical Systems with ODE-based Random Features](https://mlsanity.com/paper/2106.05960/) (2021)
- [Deep Random Features for Scalable Interpolation of Spatiotemporal Data](https://mlsanity.com/paper/2412.11350/) (2024)
- [A spectral mixture representation of isotropic kernels with application to random Fourier features](https://mlsanity.com/paper/2411.02770/) (2024)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [Sparse Spectrum Warped Input Measures for Nonstationary Kernel Learning](https://mlsanity.com/paper/2010.04315/) (2020)
- [Integrated Variational Fourier Features for Fast Spatial Modelling with Gaussian Processes](https://mlsanity.com/paper/2308.14142/) (2023)
- [Adaptive RKHS Fourier Features for Compositional Gaussian Process Models](https://mlsanity.com/paper/2407.01856/) (2024)

## Built on by (most cited first, 2 of 2)

- [Downscaling land surface temperature data using edge detection and block-diagonal Gaussian process regression](https://mlsanity.com/paper/2602.02813/) (2026)
- [Random Feature Pruning for Multi-Class Classification](https://mlsanity.com/paper/2610.15101/) (2026)

## Abstract (arXiv)

Modeling non-stationary processes, where statistical properties vary across the input domain, is a critical challenge in machine learning; yet most scalable methods rely on a simplifying assumption of stationarity. This forces a difficult trade-off: use expressive but computationally demanding models like Deep Gaussian Processes, or scalable but limited methods like Random Fourier Features (RFF). We close this gap by introducing Random Wavelet Features (RWF), a framework that constructs scalable, non-stationary kernel approximations by sampling from wavelet families. By harnessing the inherent localization and multi-resolution structure of wavelets, RWF generates an explicit feature map that captures complex, input-dependent patterns. Our framework provides a principled way to generalize RFF to the non-stationary setting and comes with a comprehensive theoretical analysis, including positive definiteness, unbiasedness, and uniform convergence guarantees. We demonstrate empirically on a range of challenging synthetic and real-world datasets that RWF outperforms stationary random features and offers a compelling accuracy-efficiency trade-off against more complex models, unlocking scalable and expressive kernel methods for a broad class of real-world non-stationary problems.