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

• URL: http://arxiv.org/abs/2602.00987v1
• Date: Sun, 01 Feb 2026 02:56:56 GMT
• Title: Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees
• Authors: Sawan Kumar, Souvik Chakraborty,
• Abstract summary: We introduce Random Wavelet Features (RWF), a framework that constructs scalable, non-stationary kernel approximations by sampling from wavelet families.<n>By harnessing the inherent localization and multi-resolution structure of wavelets, RWF generates an explicit feature map that captures complex, input-dependent patterns.<n>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.
• Score: 5.758073912084366
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Data-Aware Random Feature Kernel for Transformers [7.455696124254561]
  In pretrained models, queries and keys are typically anisotropic. This induces high Monte Carlo variance in isotropic sampling schemes.<n>We introduce DARKFormer, a Data-Aware Random-feature Kernel transformer that features a data-aligned kernel geometry.<n>By combining random-feature efficiency with data-aware kernels, DARKFormer advances kernel-based attention in resource-constrained settings.
  arXiv  Detail & Related papers  (2026-03-04T14:43:11Z)
• Random Controlled Differential Equations [1.2107297090229683]
  We introduce a training-efficient framework for time-series learning that combines random features with controlled differential equations (CDEs)<n>Only a linear readout layer is trained, resulting in fast, scalable models with strong inductive bias.<n>We evaluate both models across a range of time-series benchmarks, demonstrating competitive or state-of-the-art performance.
  arXiv  Detail & Related papers  (2025-12-29T18:25:10Z)
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning [53.17227599983122]
  Functional tensor decomposition can analyze multi-dimensional data with real-valued indices.<n>We propose a rank-revealing functional low-rank tensor completion (RR-F) method.<n>We establish the universal approximation property of the model for continuous multi-dimensional signals.
  arXiv  Detail & Related papers  (2025-12-25T03:15:52Z)
• On the Probabilistic Learnability of Compact Neural Network Preimage Bounds [71.59148070050212]
  In this work, we adopt a novel probabilistic perspective, aiming to deliver solutions with high-confidence guarantees and bounded error.<n>We introduce $textbfR$andom $textbfF$orest $textbfPro$perty $textbfVe$rifier ($texttRF-ProVe$), a method that exploits an ensemble of randomized decision trees to generate candidate input regions satisfying a desired output property.<n>Our theoretical derivations offer formal statistical guarantees on region purity and global coverage, providing a practical, scalable solution for computing
  arXiv  Detail & Related papers  (2025-11-10T16:56:51Z)
• Robust, Online, and Adaptive Decentralized Gaussian Processes [40.250871864353314]
  Decentralized random Fourier feature Gaussian processes (DRFGP) is an online and distributed algorithm that casts GPs in an information-filter form.<n>We extend DRFGP along two key directions: first, by introducing a robust-filtering update that downweights the impact of atypical observations; second, by incorporating a dynamic adaptation mechanism that adapts to time-varying functions.<n>We demonstrate its effectiveness on a large-scale Earth system application, underscoring its potential for in-situ modeling.
  arXiv  Detail & Related papers  (2025-09-22T16:49:49Z)
• Scale-Adaptive Generative Flows for Multiscale Scientific Data [20.583125441867434]
  Flow-based generative models can face challenges when modeling scientific data with multiscale Fourier spectra.<n>Key insight is that the noise should not be smoother than the target data, to ensure bounded drift fields near the initial time.<n>We show that spectrum-matched noise improves numerical efficiency compared to standard white-noise approaches.
  arXiv  Detail & Related papers  (2025-09-03T03:17:49Z)
• LVM-GP: Uncertainty-Aware PDE Solver via coupling latent variable model and Gaussian process [9.576396359649921]
  We propose a novel framework, termed LVM-GP, for uncertainty quantification in solving PDEs with noisy data.<n>The architecture consists of a confidence-aware encoder and a probabilistic decoder.
  arXiv  Detail & Related papers  (2025-07-30T09:00:39Z)
• Score-based Diffusion Models in Function Space [137.70916238028306]
  Diffusion models have recently emerged as a powerful framework for generative modeling.<n>This work introduces a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space.<n>We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Simplex Random Features [53.97976744884616]
  We present Simplex Random Features (SimRFs), a new random feature (RF) mechanism for unbiased approximation of the softmax and Gaussian kernels. We prove that SimRFs provide the smallest possible mean square error (MSE) on unbiased estimates of these kernels. We show consistent gains provided by SimRFs in settings including pointwise kernel estimation, nonparametric classification and scalable Transformers.
  arXiv  Detail & Related papers  (2023-01-31T18:53:39Z)
• Hybrid Random Features [60.116392415715275]
  We propose a new class of random feature methods for linearizing softmax and Gaussian kernels called hybrid random features (HRFs) HRFs automatically adapt the quality of kernel estimation to provide most accurate approximation in the defined regions of interest.
  arXiv  Detail & Related papers  (2021-10-08T20:22:59Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.