Research map / Learning theory and algorithms / Kernels and regression theory
Fast Summation of Radial Kernels via QMC Slicing
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 QMC slicing for fast radial kernel summation, using distance-minimizing spherical QMC designs to choose slicing directions, with error bounds and numerical gains over RFF and orthogonal features.
Problem
Fast computation of large radial kernel sums (O(MN) naively) that arise in kernel methods; existing fast Fourier methods scale poorly beyond about d=4, and random Fourier features converge only at O(1/sqrt(D)), are restricted to positive definite kernels.
Approach
Represent radial kernels as expectations of one-dimensional kernel sums over random projections (slicing), and replace i.i.d. directions with QMC designs on the sphere (distance-minimizing points, symmetrized) so that one-dimensional fast Fourier or sorting summations are applied along the projections, with improved slicing error rates.
Key results
- For the Gauss kernel in d=3, distance QMC designs achieve an estimated convergence rate of 2.10 versus 0.50 for iid slicing and 0.50 for RFF.
- Theory gives dimension-independent variance bounds for negative distance kernel and exact variance formulas for Laplace and Gauss kernels in d=3.
- QMC Fourier-slicing shows significantly smaller kernel summation error than RFF, ORF and non-QMC slicing on Letters, MNIST and FashionMNIST, with the smallest standard deviation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use distance QMC designs instead of iid random directions for slicing | Kernel approximation by slicing · Gauss, Matérn, and Laplace kernels; d=3, 10, and 50 | convergence rate r: Gauss: d=3 0.50 -> 2.10; d=10 0.50 -> 1.38; d=50 0.50 -> 0.78 | Helped |
| Use distance QMC designs instead of Sobol directions for slicing | Kernel approximation by slicing · Gauss, Matérn, and Laplace kernels; d=10 and d=50 | convergence rate r: Gauss d=10: 0.78 -> 1.38; Matérn ν=3+1/2 d=50: 0.67 -> 0.71; Laplace d=50: 0.59 -> 0.60 | Mixed |
| Use spherical designs instead of distance QMC designs | Kernel approximation by slicing · Matérn ν=3+1/2, d=3 | convergence rate r: 2.11 -> 4.01 | Helped |
| Use spherical designs instead of distance QMC designs | Kernel approximation by slicing · Matérn ν=1+1/2, d=3 | convergence rate r: 2.11 -> 2.24 | Helped |
| Use spherical designs instead of distance QMC designs | Kernel approximation by slicing · Laplace kernel, d=3 | convergence rate r: 1.26 -> 1.28 | Helped |
| Use distance QMC designs instead of spherical designs | Kernel approximation by slicing · Gauss kernel, d=3 | convergence rate r | No clear effect |
| Use QMC Fourier-slicing instead of the compared summation methods | Fast kernel summation · Letters, MNIST, and FashionMNIST | relative L1 approximation error | Helped |
| Use QMC Fourier-slicing instead of the compared summation methods | Fast kernel summation · Letters, MNIST, and FashionMNIST | standard deviation of error | Helped |
Surprising findings
- Empirical convergence rates of distance QMC designs often exceed the proven worst-case rate d/(2(d-1)).
- Iid slicing and RFF show the expected O(1/sqrt(P)) rate, while Sobol-based slicing is not a provable QMC design.
Limitations
- Observed convergence rates are significantly better than the proven error bounds.
- Computing QMC directions is costly and spherical designs are intractable in high dimensions.
- QMC advantage shrinks in higher dimensions.
Experimental setup
Datasets: Letters MNIST FashionMNIST
Benchmarks: Letters MNIST FashionMNIST
Metrics: approximation error of kernel function relative L1 kernel summation error estimated convergence rate computation time
Baselines: random Fourier features orthogonal random features QMC random Fourier features (Sobol) non-QMC slicing spherical designs
Builds on: random Fourier features orthogonal random features sliced Wasserstein distance non-equispaced fast Fourier transform
Closest papers by meaning
- Quasi-Monte Carlo Features for Kernel Approximation (ICML 2024 · similarity 0.85)
- Quadrature-based features for kernel approximation (NeurIPS 2018 · similarity 0.85)
- Quantization Algorithms for Random Fourier Features (ICML 2021 · similarity 0.85)
- Quasi-Monte Carlo for 3D Sliced Wasserstein (ICLR 2024 · similarity 0.83)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.82)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.