Research map / Learning theory and algorithms / Kernels and regression theory

Manifold Random Features

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Random feature approximation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Manifold Random Features (MRFs), which train a neural network on discrete graph random feature signatures over a manifold discretization to yield positive, bounded random features approximating heat/diffusion kernels on manifolds.

Problem

Approximating bi-variate kernel functions (e.g., heat kernels) defined on general Riemannian manifolds with random features is hard, since analytic feature maps are unavailable and spectral computations scale cubically with the number of points.

Approach

Use Graph Random Features on a discretized manifold graph as teachers to train a neural network g_theta(x,omega) that acts as a continuous positive feature field; kernel values are then approximated by summing products of these learned fields over sampled points, and the Gaussian kernel's positive RF is recovered from grid-graph GRFs.</:parameter>

Key results

• On surfaces, MRF kernel relative Frobenius error is 0.067 (sphere), 0.047 (ellipsoid), 0.035 (Mobius strip), 0.062 (torus), versus 0.101-0.489 for best ambient RF baselines.
• Kernel evaluation for 512 points is 37x-61x faster than spectral decomposition on the four surfaces.
• On vertex normal prediction with m=256, MRF achieves cosine similarity 0.85 versus 0.71-0.72 for RFF/ORF; on Brodatz, MRF group accuracy is 55.7% versus 43.5% for RFF.

Surprising findings

• Gaussian-kernel positive random features are recovered as a by-product by applying GRFs on grid graphs with wrap-around, without analytic derivation.

Limitations

• Method is developed for compact manifolds; non-compact extension is only a preliminary local-on-compacts experiment on H^3.
• Requires offline preprocessing (graph construction, random walks, network training) that may not pay off for small one-off problems.
• Relies on clamping and neural regression accuracy; Mobius strip is sensitive to discretization.

Experimental setup

Datasets: Thingi10k flag_simple Brodatz (log-SPD descriptors)

Benchmarks: sphere, ellipsoid, Mobius strip, torus heat kernel reconstruction Thingi10k vertex normal interpolation flag_simple velocity interpolation Brodatz group accuracy Mobius-strip masked reconstruction

Metrics: R^2 relative Frobenius error MSE cosine similarity interpolation time growth exponent group accuracy speed-up

Baselines: RFF ORF PRF PORF spectral heat kernel decomposition ambient RBF kernel

Builds on: Graph Random Features Random Fourier Features Positive Random Features Orthogonal Random Features

Closest papers by meaning

• Taming graph kernels with random features (ICML 2023 · similarity 0.90)
• General Graph Random Features (ICLR 2024 · similarity 0.90)
• Computationally-efficient Graph Modeling with Refined Graph Random Features (ICML 2026 · similarity 0.88)
• Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.87)
• Variance-Reducing Couplings for Random Features (ICLR 2025 · similarity 0.86)
• Manifold Diffusion Fields (ICLR 2024 · similarity 0.85)