Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels

By Haim Avron, Vikas Sindhwani, Jiyan Yang, Michael W. Mahoney. 2014

178 citations recorded by the source corpus.

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.

Subfields: Numerical Analysis, Radiation, Radiology, Nuclear Medicine and Imaging, Representation & Self-Supervised Learning, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Numerical Analysis

In Radiation

In Radiology, Nuclear Medicine and Imaging

In Representation & Self-Supervised Learning

In Probabilistic & Bayesian Methods

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “(3.53) This connection has been noted by several authors including Bach et al. (2012) and Yang et al. (2014).”
Convergence guarantees for kernel-based quadrature rules in misspecified settings (2016, background): “Because of this nice property, kernel quadratures have been studied extensively in recent years [7, 3, 5, 2, 17] and have started to find applications in machine learning and statistics [23, 14, 12, 6].”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “It is straightforward to replace the sampling strategy for random features with Fastfood [7] which enjoys the efficient computational cost, or Quasi-Monte Carlo sampling [43], data-dependent sampling [47] which enjoys faster convergence rate with fewer generated features.”
Orthogonal Random Features (2016, methodology): “t is well known that the convergence of MonteCarlo can be largely improved by carefully choosing a deterministic sequence instead of random samples [18]. Following this line of reasoning, Yang et al. [26] proposed to use low-displacement rank sequences in RFF. Yu et al. [29] studied optimizing the s”
Random Feature Attention (2021, methodology): “Using the well-established random feature maps (Rahimi & Recht, 2007; Avron et al., 2016; §2), R FA approximates the dot-then-exponentiate function with a kernel trick (Hofmann et al., 2008): exp( x · y ) ≈ φ ( x ) · φ ( y ) .”
Learning to Learn Kernels with Variational Random Features (2020, unknown): “This suggests that learning adaptive kernels with random features by data-driven sampling strategies (Sinha & Duchi, 2016) can improve the performance, even with a low sampling rate compared to using universal random features (Avron et al., 2016; Chang et al., 2017).”
Memory Efficient Kernel Approximation (2014, methodology): “Thus, we need totally different algorithms for clustering and approximating blocks to yield our memory-efficient scheme.”
Demystifying Orthogonal Monte Carlo and Beyond (2020, methodology): “The theory of MC is rich with various techniques improving the accuracy of base MC estimators such as: antithetic couplings and importance sampling [6], variance reduction via carefully designed control variate terms [28, 31] and ﬁnally: the vast ﬁeld of the so-called Quasi Monte Carlo (QMC) methods”
Local Group Invariant Representations via Orbit Embeddings (2016, methodology): “It is also possible to use quasi Monte Carlo approximation for the expectation over ω, which has been carefully studied for random Fourier features [46].”
Random Laplace Feature Maps for Semigroup Kernels on Histograms (2014, methodology): “The scalability of this approach can be further improved via design of specialized parallel solvers [12] to handle a larger number of random features, while replacing Monte Carlo approximations with more efficient numerical integration techniques [22].”
Generalization Properties of Learning with Random Features (2016, background): “Among others, one-hidden layer networks [3], or RBF networks [4], are examples of classical approaches considering these models.”
Kernel methods match Deep Neural Networks on TIMIT (2014, methodology): “Another promising direction is the use of Quasi-Monte Carlo techniques to improve the efficiency of explicit feature map approximations along the lines proposed in [15].”
Sampled Softmax with Random Fourier Features (2019, background): “Moreover, these features and their extensions are also theoretically better understood (see, e.g., [25, 26, 27]).”
Hybrid Random Features (2021, methodology): “, 2016) (regular variant ORF-reg as well as the one applying Hadamard matrices ORF-Had) and QMCs based on random Halton sequences (Halton-R)(Avron et al., 2016).”
Randomized Nonlinear Component Analysis (2014, methodology): “, 2014); the development of advanced sampling techniques using Quasi-Monte-Carlo methods (Yang et al., 2014) or their accelerated computation via fast Walsh-Hadamard transforms (Le et al.”
Visual Attention Methods in Deep Learning: An In-Depth Survey (2022, methodology): “Random Feature Attention (RFA) [92] uses a variant of softmax that is sampled from simple distribution-based Fourier random features [93], [94].”