Manifold Random Features

• URL: http://arxiv.org/abs/2602.03797v1
• Date: Tue, 03 Feb 2026 18:00:01 GMT
• Title: Manifold Random Features
• Authors: Ananya Parashar, Derek Long, Dwaipayan Saha, Krzysztof Choromanski,
• Abstract summary: We create Manifold Random Features (MRFs) to approximate kernels on general manifold.<n>MRFs leverage discretization of the manifold and the recently introduced technique of Graph Random Features (GRFs)<n>We show deep connection between GRFs, defined on discrete graph objects, and continuous random features used for regular kernels.
• Score: 4.067075813886517
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a new paradigm for creating random features to approximate bi-variate functions (in particular, kernels) defined on general manifolds. This new mechanism of Manifold Random Features (MRFs) leverages discretization of the manifold and the recently introduced technique of Graph Random Features (GRFs) to learn continuous fields on manifolds. Those fields are used to find continuous approximation mechanisms that otherwise, in general scenarios, cannot be derived analytically. MRFs provide positive and bounded features, a key property for accurate, low-variance approximation. We show deep asymptotic connection between GRFs, defined on discrete graph objects, and continuous random features used for regular kernels. As a by-product of our method, we re-discover recently introduced mechanism of Gaussian kernel approximation applied in particular to improve linear-attention Transformers, considering simple random walks on graphs and by-passing original complex mathematical computations. We complement our algorithm with a rigorous theoretical analysis and verify in thorough experimental studies.

Related papers

• Deep Gaussian Processes for Functional Maps [15.327037938888154]
  Learning incorporations between functional spaces, also known as function-on-function regression, play a crucial role in functional data analysis.<n>Existing approaches either fall short of capturing complex nonlinearities or lack reliable uncertainty under noisy, sparse, and irregularly sampled data.<n>We propose Deep Gaussian Processes for Functional Maps (DGPFM) to address these issues.<n>Our method designs a sequence of GP-based linear and nonlinear transformations, leveraging integral transforms of kernels, GP, and nonlinear activations sampled from GPs.
  arXiv  Detail & Related papers  (2025-10-24T23:05:48Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  We present a novel mechanism to improve the accuracy of graph random features (GRFs) Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs.
  arXiv  Detail & Related papers  (2023-05-21T14:12:02Z)
• 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)
• A mixed-categorical correlation kernel for Gaussian process [0.0]
  We present a kernel-based approach that extends continuous exponential kernels to handle mixed-categorical variables. The proposed kernel leads to a new GP surrogate that generalizes both the continuous relaxation and the Gower distance based GP models.
  arXiv  Detail & Related papers  (2022-11-15T16:13:04Z)
• Vector-valued Gaussian Processes on Riemannian Manifolds via Gauge Equivariant Projected Kernels [108.60991563944351]
  We present a recipe for constructing gauge equivariant kernels, which induce vector-valued Gaussian processes coherent with geometry. We extend standard Gaussian process training methods, such as variational inference, to this setting.
  arXiv  Detail & Related papers  (2021-10-27T13:31:10Z)
• Non-Gaussian Gaussian Processes for Few-Shot Regression [71.33730039795921]
  We propose an invertible ODE-based mapping that operates on each component of the random variable vectors and shares the parameters across all of them. NGGPs outperform the competing state-of-the-art approaches on a diversified set of benchmarks and applications.
  arXiv  Detail & Related papers  (2021-10-26T10:45:25Z)
• 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)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

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.