Fastfood - Computing Hilbert Space Expansions in loglinear time

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

165 citations recorded by the source corpus.

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

Fast Two-Sample Testing with Analytic Representations of Probability Measures (2015, background): “Our ﬁrst proposition is that d 2 ϕ,J ( P, Q ) can be a poor choice of distance between probability measures, as it fails to distinguish a large class of measures.”
Optimal Rates for Random Fourier Features (2015, neutral): “(i) Kernel derivatives: tighter guarantees, (ii) prediction using kernel (derivative) estimates, (iii) analysis of smart RFF approximations [5].”
Compressing Convolutional Neural Networks in the Frequency Domain (2015, methodology): “[62] adopt the fastfood transformation [32] for compressing the fully connected layers, and Kim et al.”
Deep Kernel Learning (2015, methodology): “(2014) combine convolutional networks, with parameters pre-trained on ImageNet, with a scalable Fastfood (Le et al., 2013) expansion for the RBF kernel applied to the final layer.”
Stochastic Variational Deep Kernel Learning (2016, background): “Many promising approaches to scalability have been explored, for example, involving randomized methods [20, 16, 31] , and low rank approximations [23, 19].”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “Random feature approximation is another popular approach for scaling up kernel methods [6, 7].”
Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP) (2015, methodology): “, 2010), a recent state of the art scalable GP method based on random projections with O(m(2)n) computations and O(m(2)) storage for m basis functions and n training points (see also Rahimi & Recht, 2007; Le et al., 2013; Lu et al., 2014; Yang et al., 2015).”
A la Carte - Learning Fast Kernels (2014, methodology): “A similar spectral decomposition holds for inner product kernels k ( x, x (cid:48) ) = κ ( (cid:104) x, x (cid:48) (cid:105) ) [Le et al., 2013, Schoenberg, 1942].”
Thoughts on Massively Scalable Gaussian Processes (2015, methodology): “…process model, including a full GP, inducing points methods such as FITC (Snel-son and Ghahramani, 2006), or the Big Data GP (Hensman et al., 2013), or ﬁnite basis models (e.g., Yang et al., 2015; L´azaro-Gredilla et al., 2010; Rahimi and Recht, 2007; Le et al., 2013; Williams and Seeger, 2001).”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, methodology): “Fast random projection and kernel approximation methods rely on the fast Hadamard transform (Le et al., 2013; Yu et al., 2016) and convolution (Yu et al., 2015), and convolution is a critical component of modern image processing architectures (Krizhevsky et al., 2012) as well as being useful in…”
Less is More: Nyström Computational Regularization (2015, background): “In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen.”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, methodology): “It has been applied to various kernel methods [11, 6, 12], among which most related to our work is RCA [12].”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “The growing body in deep learning [42], kernel methods [81], and decision trees [148] bears witness of this development.”
Random Feature Expansions for Deep Gaussian Processes (2016, background): “The results obtained on higher-dimensional datasets strongly suggest that approximations such as Fastfood (Le et al., 2013) could be instrumental in the interest of using more random features.”
Compact Random Feature Maps (2013, methodology): “Previous approaches to address this curse of support have mostly focused on embedding the non-linear feature space H into a low dimensional Euclidean space while incurring an arbitrarily small distortion in the inner product values (Rahimi & Recht, 2007) (Kar & Karnick, 2012) (Le et al., 2013) (Pham”
Parameter-Efficient Fine-Tuning Methods for Pretrained Language Models: A Critical Review and Assessment (2023, background): “…Intrinsic SAID fine-tunes the model by reparametrization the model in a lower-dimensional space, i.e., ∆ W = F ( W r ) , in which W r is the parameter to be optimized and F : R r → R d is a Fastfood transform 3 [87] that projects parameters from low-dimensional r to high-dimensional d .”
Randomness in neural networks: an overview (2017, methodology): “• In order to further speedup computations, Le et al.(65) presented the fastfood algorithm, which allows RFFs for the Gaussian kernel to be computed in O(B log(d)) time instead of O(Bd), by the use of specially designed matrices.”
A Survey of Multi-View Representation Learning (2016, unknown): “Consequently, a deep canonically correlated autoencoder (DCCAE) [20] is introduced through jointly optimizing the objectives of the deep CCA and the separate autoencoders from multiple views.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “Compared with using a Gaussian matrix product, FFT Fastfood gives a substantial reduction is arithmetic.”