Source-linked AI summary
Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
Haim Avron, Vikas Sindhwani, Jiyan Yang, Michael Mahoney
TL;DR
The paper addresses the large feature counts and scalability costs associated with randomized Fourier feature maps for shift-invariant kernels. It replaces Monte Carlo sampling with classical and adaptive QMC sequences, derives discrepancy-based analyses, and reports empirical evidence supporting their effectiveness, while noting limits for some downstream classification settings and non-factorized densities.
Problem
Randomized feature maps can require very large numbers of random features to reach state-of-the-art accuracy, limiting efficient scaling of kernel methods.
Method
The paper replaces Monte Carlo feature sampling with low-discrepancy QMC sequences, analyzes integration error, and learns adaptive sequences by optimizing a box-discrepancy objective.
Results
Empirical results demonstrate the effectiveness of classical and adaptive QMC techniques and support the paper’s theoretical analyses.
Takeaways & Limitations
QMC feature maps provide a promising approach for improving the efficiency of large-scale kernel methods.
Takeaways & Limitations
QMC sequences do not improve classification accuracy as consistently as regression accuracy for moderate feature counts, and the multivariate-t density of the Matérn kernel does not factorize into univariate densities.
Abstract
from arXiv · showhide
We consider the problem of improving the efficiency of randomized Fourier feature maps to accelerate training and testing speed of kernel methods on large datasets. These approximate feature maps arise as Monte Carlo approximations to integral representations of shift-invariant kernel functions (e.g., Gaussian kernel). In this paper, we propose to use Quasi-Monte Carlo (QMC) approximations instead, where the relevant integrands are evaluated on a low-discrepancy sequence of points as opposed to random point sets as in the Monte Carlo approach. We derive a new discrepancy measure called box discrepancy based on theoretical characterizations of the integration error with respect to a given sequence. We then propose to learn QMC sequences adapted to our setting based on explicit box discrepancy minimization. Our theoretical analyses are complemented with empirical results that demonstrate the effectiveness of classical and adaptive QMC techniques for this problem.
1 Introduction
Kernel methods provide powerful non-parametric models, but their scalability limits become severe for large datasets. The paper revisits randomized Fourier features and replaces Monte Carlo sampling with Quasi-Monte Carlo sequences to improve kernel approximation efficiency.
- Motivation: Kernel methods support many nonlinear learning tasks through embeddings into potentially infinite-dimensional Hilbert spaces.Their broad applicability includes classification, regression, clustering, time-series analysis, and hypothesis testing.
- Motivation: Kernel training can require O(n^3 + n^2d) computation and O(n^2) memory, with O(nd) prediction time for one test point.These costs arise from solving systems involving the n × n Gram matrix.
- Randomized Feature Maps: Randomized feature maps reduce regression costs to O(ns^2) training, O(ns) memory, and O(sd) prediction when s is sufficiently smaller than n.They approximate the kernel with a low-dimensional representation and then apply a linear method.
- Motivation: Very large numbers of random features may be needed for state-of-the-art accuracy, motivating methods that achieve comparable approximation quality with smaller s.The paper identifies this convergence-efficiency problem as its central motivation.
- Contributions: The paper interprets random Fourier features as Monte Carlo approximations and proposes low-discrepancy QMC sequences to reduce integration error.It additionally derives an average-case error analysis and uses the resulting bound to optimize sequences adapted to the kernels.
- Contributions: Empirical results demonstrate QMC superiority over MC feature maps and indicate potential value for adaptive QMC in large-scale kernel methods.The experiments also support the paper’s theoretical analysis.
2 Preliminaries
The preliminaries frame kernel approximation as numerical integration. Monte Carlo uses independent random points with O(s^-1/2) convergence, whereas QMC uses designed low-discrepancy sequences to reduce clustering and improve convergence.
- Kernel Approximation: The Gram matrix is defined by K_ij = k(x_i, x_j), and scalable kernel methods approximate it using low-rank feature maps or sampling methods.Randomized feature maps construct Ψ̂: X → C^s so that k(x, z) is approximated by an inner product in C^s.
- Monte Carlo: Monte Carlo approximates an integral by independently drawing a random point set S and averaging function evaluations over those points.Its integration error is defined relative to the exact integral and the empirical estimate.
- Monte Carlo: O(s^-1/2) is the Monte Carlo convergence rate, as implied by the central-limit-theorem approximation to integration error.The scale depends on the integrand variance and a standard normal random variable.
- Quasi-Monte Carlo: QMC constructs S from deterministic low-discrepancy points rather than independent random samples to improve convergence.Designed correlations reduce clustering and empty regions that leave parts of the integrand poorly sampled.
- Quasi-Monte Carlo: QMC error bounds separate integrand variation from a sequence-dependent discrepancy term measuring deviation from uniformity.The Koksma-Hlawka framework uses Hardy-Krause variation and sequence discrepancy.
3 QMC Feature Maps: Our Algorithm
The algorithm converts kernel integrals into unit-cube integrals, transforms low-discrepancy points through inverse marginal CDFs, and plugs the resulting frequencies into the QMC feature map.
- Density Transformation: The method assumes the spectral density factorizes as p(x) = ∏_j p_j(x_j), including densities associated with Gaussian, Laplacian, and Cauchy kernels.This product structure enables coordinatewise transformation from the unit cube.
- Density Transformation: QMC first generates a low-discrepancy sequence t_1, …, t_s in [0,1]^d instead of sampling frequencies directly from p.The sequence is then transformed into points in R^d.
- Density Transformation: A change of variables converts the spectral integral into an integral over the unit cube.The coordinate transformation uses the marginal cumulative distribution functions Φ_j.
- Feature Map Construction: The algorithm sets w_i = Φ^-1(t_i) and substitutes these transformed points into the feature-map approximation.This produces the QMC feature map summarized in Algorithm 1.
4 Theoretical Analysis and Average Case Error Bounds
The paper develops a theoretical framework for QMC feature-map approximation because classical Koksma–Hlawka analysis does not apply to the relevant integrands. It introduces box discrepancy and relates it to average-case integration error, including Gaussian-kernel formulas and Monte Carlo baselines.
- Motivation: Classical Koksma–Hlawka analysis cannot be applied to the integrands arising in the QMC feature-map setting.This motivates a separate framework for analyzing approximation quality.
- Framework: The framework defines integration error over functions induced by differences in the data domain and analyzes it through a related RKHS.The construction uses a Paley–Wiener RKHS and damped approximations to connect the target function class with RKHS error bounds.
- Box discrepancy: Box discrepancy is introduced as a sequence-dependent measure derived from the explicit discrepancy formula for the Paley–Wiener space.The measure is defined with respect to the sampling density and the relevant box domain.
- Average-case error: The expected square error for an integrand uniformly drawn from the target function class is proportional to the squared box discrepancy.This provides an average-case interpretation of the proposed discrepancy measure.
- Gaussian case: For Gaussian-kernel sampling densities, the box discrepancy balances separation among frequency points against matching the Gaussian sampling distribution.The Gaussian case is treated explicitly because its density is the one relevant to the Gaussian kernel.
- Monte Carlo comparison: Monte Carlo sequences have expected discrepancy decay O(s^-1/2), providing a reference rate for the QMC analysis.The result also implies the existence of point sets with this order of discrepancy.
5 Learning Adaptive QMC Sequences
The paper learns adaptive QMC sequences by directly minimizing the smooth, closed-form box discrepancy. It considers global and greedy optimization, extensions to lattice rules and weights, and connections to herding and Bayesian Monte Carlo.
- Optimization framework: Box discrepancy is smooth and has a closed-form formula, enabling direct evaluation and optimization of QMC sequences.The paper uses this property instead of prescribing sequences solely through classical discrepancy theory.
- Global adaptation: Global adaptive sequences are obtained by minimizing box discrepancy over sequences of s vectors in R^d.The gradient is available for first-order numerical optimization.
- Extensions: The framework extends to rank-one lattice rules, whose generating vector can be learned by local box-discrepancy minimization.This provides another adaptive QMC construction beyond the sequence procedures developed directly in the paper.
- Greedy adaptation: Greedy adaptive sequences add each new point by solving a sequential box-discrepancy optimization problem.The procedure starts from the empty set and repeatedly appends the optimized point.
- Relation to herding: The greedy procedure is closely related to herding, although the O(1/t) discrepancy guarantee for herding is not established for the Paley–Wiener setting.The cited restrictions may fail for infinite-dimensional RKHSs, while their applicability here remains unclear.
- Weighted features: With fixed points, nonnegative weights can be learned through a convex optimization problem, and weighted sequences can also be optimized adaptively.The construction allows unnormalized weights, while the feature-map hypothesis space remains unchanged when all weights are positive.
6 Experiments
Experiments compare classical and adaptive QMC feature sequences with Monte Carlo features using kernel-approximation, discrepancy, integration-error, and downstream regression metrics. Classical QMC generally improves Gram-matrix approximation and regression performance, while adaptive methods can further reduce discrepancy and sometimes improve test error, especially when optimized on the central bounding-box region.
- Classical QMC sequences: Classical low-discrepancy sequences generally approximate the Gram matrix better than MC features, except for Sobol’ sequences.Digital Nets, Lattice Rules, and Halton produce lower error, with similar results observed on other datasets.
- Classical QMC sequences: Scrambled QMC sequences usually yield more accurate Gram-matrix approximations than their non-scrambled counterparts, especially for larger s.The study therefore uses scrambled sequences in later experiments.
- Classical QMC sequences: QMC sequences outperform MC sequences on the regression datasets overall, with Halton reducing census generalization error by almost 20%.On cpu, all sequences behave similarly, although Halton has the lowest test error; MC also shows higher variance across sampling sizes.
- Classical QMC sequences: QMC sequences do not consistently improve classification accuracy over MC features for moderate s below 2000.The paper leaves the connection between kernel approximation and downstream performance outside its scope.
- Adaptive QMC sequences: Optimizing box discrepancy can improve Gram-matrix approximation, but optimizing over the full bounding box may overfit regions where integrands are sparse.On housing, optimizing the central box improved mean and norm errors, motivating central-region discrepancy measures.
- Adaptive QMC sequences: Adaptive sequences reduce discrepancy by orders of magnitude and can lower test error, but greedy methods may require more than 500 points and optimized sequences can sometimes worsen error.Central-box adaptive sequences usually outperform full-box versions, while different adaptive schemes are best at different sampling sizes and datasets.
7 Conclusion and Future Work
Kernel methods can achieve strong accuracy on very large datasets, but random-feature approximations may require many features. This paper introduces QMC-based feature maps, supported by theory and promising empirical results.
- Random features have enabled kernel methods to scale to very large datasets and sometimes match DNN accuracy.
- Over 200,000 random features were needed on TIMIT to match DNN performance.
- The paper exploits high-dimensional QMC integration techniques for kernel feature maps, combining theoretical analyses with promising empirical results.
A Technical Details
This section provides detailed proofs for the assertions developed in Sections 4 and 5.
- The appendix supplies detailed proofs for the theoretical assertions in Sections 4 and 5.
A.1 Proof of Proposition 5
The proof develops a transformed-integrand representation using coordinatewise CDFs and establishes that the relevant Hardy–Krause variation is unbounded.
- The proof maps coordinates through the marginal CDFs Φj and their inverses when transforming the integrand.
- The proof concludes that VHK[fu(t)] is unbounded because it appears as a term in equation (6).
A.2 Proof of Proposition 6
The proof establishes boundedness and representability properties for expectation functionals in an RKHS, under a bounded diagonal-kernel assumption.
- The appendix introduces shared notation and lemmas used to prove Proposition 6.
- Assuming κ = supx∈Rd h(x, x) < ∞, the integral of any RKHS function against p is finite.
- The expectation operator T(f) = E[f(X)] is treated as a bounded linear functional, with X distributed according to p.
- The proof shows that the function x ↦ ∫Rd h(u, x)p(x)dx belongs to the RKHS and uses the reproducing property to derive the result.
- The proof of Proposition 6 follows from the preceding existence lemmas and additional intermediate steps.
A.3 Proof of Theorem 9
The proof specializes the preceding result to sinc_b and uses integrability and Hermitian properties to justify its transformations.
- The argument applies equation (9) to the specific choice h = sinc_b.
- Each coordinate can be treated separately in the resulting analysis.
- Interchanging terms is justified by the integrability of p_j(x).
- The proof introduces h_j(x, y) = sin(b_j(x − y))/π(x − y) after fixing w ∈ R.
- The final algebra uses the shifted characteristic function and the Hermitian property of ϕ_j.
A.4 Proof of Theorem 12
The proof derives error expressions through Fourier analysis, integral changes of variables, and term-by-term differentiation, with auxiliary lemmas supporting the derivative calculations.
- The function r_S is square-integrable, and the approximation error is identified with the magnitude of its Fourier transform at u.
- Plancherel’s formula connects the relevant equality to the L2 norm, while r_S matches the expression used to derive D□.
- A change of variables maps φ to t through t_l = (Φ_1(φ_1), …, Φ_d(φ_d)), enabling the integral manipulations.
- The derivative calculation is organized around two auxiliary lemmas and applies Lemma 20 to the term associated with w_lj.
- Proposition 16 follows by combining derivative contributions from sinc_b terms, including diagonal terms handled directly by symmetry and the definition.