Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
arXiv:1412.8293
Abstract
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.
arXiv commentA short version of this paper has been presented in ICML 2014
References in corpus (7)
- Kernel-based Conditional Independence Test and Application in Causal Discovery
- Random Feature Maps for Dot Product Kernels
- Scalable Kernel Methods via Doubly Stochastic Gradients
- On the Equivalence between Herding and Conditional Gradient Algorithms
- Compact Random Feature Maps
- Fast Randomized Kernel Methods With Statistical Guarantees
- Optimally-Weighted Herding is Bayesian Quadrature
Cited by in corpus (20)
- Randomized Nonlinear Component Analysis
- Scalable Kernel Methods via Doubly Stochastic Gradients
- FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test
- Large-Scale Approximate Kernel Canonical Correlation Analysis
- Compact Nonlinear Maps and Circulant Extensions
- Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding
- Recycling Randomness with Structure for Sublinear time Kernel Expansions
- Convergence guarantees for kernel-based quadrature rules in misspecified settings
- Discrepancy Bounds for a Class of Negatively Dependent Random Points Including Latin Hypercube Samples
- Gaussian Quadrature for Kernel Features
- A Sharp Discrepancy Bound for Jittered Sampling
- Local Group Invariant Representations via Orbit Embeddings
- Tensor machines for learning target-specific polynomial features
- Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
- Data Dependent Kernel Approximation using Pseudo Random Fourier Features
- Deep Semi-Random Features for Nonlinear Function Approximation
- A General Framework for Constrained Bayesian Optimization using Information-based Search
- Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features
- Revisiting RIP guarantees for sketching operators on mixture models
- Intrinsic Exploration as Multi-Objective RL