Fastfood: Approximate Kernel Expansions in Loglinear Time

By Quoc V. Le, Tamás Sarlós, Alex Smola. 2014

471 citations recorded by the source corpus.

Despite their successes, what makes kernel methods difficult to use in many large scale problems is the fact that storing and computing the decision function is typically expensive, especially at prediction time. In this paper, we overcome this difficulty by proposing Fastfood, an approximation that accelerates such computation significantly. Key to Fastfood is the observation that Hadamard matrices, when combined with diagonal Gaussian matrices, exhibit properties similar to dense Gaussian random matrices. Yet unlike the latter, Hadamard and diagonal matrices are inexpensive to multiply and store. These two matrices can be used in lieu of Gaussian matrices in Random Kitchen Sinks proposed by Rahimi and Recht (2009) and thereby speeding up the computation for a large range of kernel functions. Specifically, Fastfood requires O(n log d) time and O(n) storage to compute n non-linear basis functions in d dimensions, a significant improvement from O(nd) computation and storage, without sacrificing accuracy. Our method applies to any translation invariant and any dot-product kernel, such as the popular RBF kernels and polynomial kernels. We prove that the approximation is unbiased and has low variance. Experiments show that we achieve similar accuracy to full kernel expansions and Random Kitchen Sinks while being 100x faster and using 1000x less memory. These improvements, especially in terms of memory usage, make kernel methods more practical for applications that have large training sets and/or require real-time prediction.

Subfields: Artificial Intelligence, Computational Mathematics, Computer Vision and Pattern Recognition, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computational Mathematics

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Compacter: Efficient Low-Rank Hypercomplex Adapter Layers (2021, methodology): “Moreover, computing projections via FastFood transform, although theoretically possible in O(Dlogd′) [32], is slow in practice even with a CUDA implementation.”
Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning (2020, background): “Concretely Li et al. (2018) proposed 3 various actualizations of P ; a random linear dense projection ( θ d W ), random linear sparse projection( θ d W sparse ) and random linear projection via the Fastfood transform (Le et al., 2013).”
Measuring the Intrinsic Dimension of Objective Landscapes (2018, methodology): “S7, we describe and characterize scaling properties of three methods of projection: dense matrix projection, sparse matrix projection (Li et al., 2006), and the remarkable Fastfood transform (Le et al., 2013).”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “For kernels whose spectral distributions Λ(ω) are spherically invariant, i.e., Λ(ω) only depends on ‖ω‖2, the cost reduces further to O(n log d) by using the Fastfood technique (Le et al. 2013).”
Recent advances in convolutional neural networks (2015, methodology): “s multi-dimensional tensor and apply a Tensor-Train decomposition [164] to reduce the number of parameters of the fully-connected layers. Adaptive Fastfood transform is generalization of the Fastfood [165] transform for approximating matrix. It reparameterize the weight matrix C 2 R n n in fully-con”
Gradient-free Hamiltonian Monte Carlo with Efficient Kernel Exponential Families (2015, background): “Note that it is possible to achieve logarithmic computational costs in d exploiting properties of Hadamard matrices [29].”
Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages (2015, methodology): “To make the algorithm computationally tractable, we regress directly in the primal from random Fourier features of the data (Rahimi and Recht, 2007; Le et al., 2013; Yang et al., 2015).”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, background): “Finally, note that in terms of computation, there are extensions to avoid linear complexity in d (Le et al., 2013).”
FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test (2014, methodology): “For kernels that are spherically invariant, the Fastfood technique can be employed to further speedup ω sampling in step 2 and ωxu calculation in steps 4,5 of Algorithm 1 (Le et al., 2013).”
Deep Fried Convnets (2014, methodology): “To further reduce the amount of storage and computation required, Le et al. (2013) introduced a method named Fastfood which reduces computation and storage to O(n log d) and O(n) respectively.”
Calibrating Deep Convolutional Gaussian Processes (2018, methodology): “Structured random feature approximations: One of the advantages of the proposed model, compared to other GP approximations, is that it can exploit structured random feature expansions to accelerate computations and reduce the size of the approximate GP [20, 29].”
Unitary Evolution Recurrent Neural Networks (2015, background): “This combined with earlier work (Le et al., 2010) suggests that it is possible to create highly expressive matrices by composing simple matrices with few parameters.”
Improving Multi-Step Prediction of Learned Time Series Models (2015, background): “The pendulum and cart pole”
Flipout: Efficient Pseudo-Independent Weight Perturbations on Mini-Batches (2018, methodology): “We also note that the fastfood transform (Le et al., 2013) is based on similar mathematical techniques.”
Orthogonal Random Features (2016, methodology): “The order of time cost for a fixed D is SORF ' Other fast kernel approximations [13, 28] ⌧ ORF = QMC [25] = RFF [19].”
Large-scale Online Kernel Learning with Random Feature Reparameterization (2017, methodology): “Alternative ways are to use the random Fourier features [Rahimi and Recht, 2007], or to use Fastfood technique [Le et al., 2013] to approximate the original kernel function [Lu et al., 2015].”
Learning with SGD and Random Features (2018, background): “For diﬀerent input spaces and diﬀerent types of random features computational cost may diﬀer, see for example Orthogonal Random Features [16] or Fastfood [17] where the cost is reduced from O ( MD ) to O ( M log D ) .”
Functional Variational Bayesian Neural Networks (2019, methodology): “, 2016) still suffer for very large dataset, while random feature methods (Rahimi & Recht, 2008; Le et al., 2013) and KISS-GP (Wilson & Nickisch, 2015; Izmailov et al.”