Research map / Learning theory and algorithms / Kernels and regression theory
Quasi-Monte Carlo Features for Kernel Approximation
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.
Shows that quasi-Monte Carlo (Halton) features give O(log^a M / M) kernel approximation error for shift-invariant (e.g., Gaussian, Cauchy) and some non-shift-invariant kernels, and that kernel ridge regression with QMC features needs fewer features than random features for the same excess risk rate.
Problem
Random Fourier/random features approximate kernels with O_P(1/sqrt(M)) error, making kernel methods costly; it is unclear whether deterministic low-discrepancy sequences can give faster, deterministic kernel approximation with guarantees for learning.
Approach
Replace i.i.d. Monte Carlo sampling of random features with the first M points of a Halton QMC sequence; under a mild boundary-singularity condition (Gaussian/Cauchy kernels) or bounded Hardy-Krause variation, the Koksma-Hlawka inequality yields deterministic error O(log^a M / M), which translates into fewer features needed for kernel ridge regression.
Key results
- QMC features give deterministic kernel approximation error O(log^a M / M) versus O_P(1/sqrt(M)) for MC random features, with M=25 Halton features visibly approximating the Gaussian kernel while MC does not.
- For kernel ridge regression with r=1, QMCF-KRR needs M ~ n^{1/(2r+1)} features versus n^{2r/(2r+1)} for RF-KRR, matching exact KRR excess risk.
- Simulations on d=1 to 4 show QMC features reach exact-KRR test MSE with far fewer features than MC features.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace i.i.d. MC features with Halton-sequence QMC features | Kernel approximation under QMC Condition 1 · Kernel approximation | approximation error: OP (1/√M) -> O(loga M/M) | Helped |
| Use QMC features satisfying QMC Condition 2 | Kernel approximation · Kernel approximation | approximation error: OP (1/√M) -> CH(p) · (log M)p/M | Helped |
| Replace MC random features with QMC features | Kernel ridge regression · Kernel ridge regression | number of features for the same excess-risk rate: n2r/(2r+1) -> n1/(2r+1) | Helped |
| Use QMCF-KRR instead of RF-KRR | Kernel ridge regression · Gaussian kernel and min kernel; d ∈ [1, 4] | test MSE | Helped |
| Apply QMC features in high dimensions (d > 10) | Kernel approximation and kernel ridge regression · High-dimensional settings | performance | Hurt |
Surprising findings
- QMC features perform well for low dimensions but the paper observes no ideal performance for d>10.
Limitations
- Laplacian kernel does not satisfy the QMC boundary condition
- Performance advantage is not observed in high dimensions (d>10)
- Requires kernel-specific conditions (shift-invariance with mild singularity, or bounded Hardy-Krause variation)
Experimental setup
Datasets: synthetic regression data (Unif[0,1]^d, Gaussian noise) real-world datasets in Appendix D
Benchmarks: synthetic kernel ridge regression with min and Gaussian kernels
Metrics: test MSE kernel approximation error
Baselines: Monte Carlo random features (RF-KRR) exact kernel ridge regression
Builds on: random features (Rahimi & Recht 2007) Koksma-Hlawka inequality Rudi & Rosasco 2017 RF-KRR
Closest papers by meaning
- Quadrature-based features for kernel approximation (NeurIPS 2018 · similarity 0.88)
- Quasi-Monte Carlo Variational Inference (ICML 2018 · similarity 0.87)
- Quasi-Monte Carlo Graph Random Features (NeurIPS 2023 · similarity 0.86)
- Fast Summation of Radial Kernels via QMC Slicing (ICLR 2025 · similarity 0.85)
- Optimal Kernel Quantile Learning with Random Features (ICML 2024 · similarity 0.85)
- Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need (ICML 2024 · similarity 0.84)
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.