Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees
This work addresses the problem of scalable and expressive kernel methods for non-stationary data, which is critical for real-world applications, representing a novel extension rather than an incremental improvement.
The paper tackled the challenge of modeling non-stationary processes in machine learning by introducing Random Wavelet Features (RWF), a scalable framework that approximates non-stationary kernels using wavelet families, and demonstrated empirically that RWF outperforms stationary random features on synthetic and real-world datasets.
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.