PaperlayerView exact revision on arXiv

Source-linked AI summary

Fastfood: Approximate Kernel Expansions in Loglinear Time

Quoc Viet Le, Tamas Sarlos, Alexander Johannes Smola

arXiv:1408.3060v1cs.LGstat.ML

TL;DR

Large-scale kernel methods are hindered by expensive decision-function storage and computation. Fastfood uses structured Hadamard and diagonal Gaussian matrices to accelerate Random Kitchen Sinks, achieving comparable accuracy with substantially lower computational cost and memory.

  • Problem

    Kernel methods become expensive on large datasets because storing and evaluating their decision-function expansions, especially at prediction time, scales poorly.

  • Method

    Fastfood replaces dense Gaussian random matrices in Random Kitchen Sinks with Gaussian-scaled Hadamard matrices that are inexpensive to store and multiply.

  • Results

    Fastfood achieves similar accuracy to full kernel expansions and Random Kitchen Sinks while being 100x faster and using 1000x less memory.

  • Takeaways & Limitations

    Fastfood makes kernel methods practical for applications with large training sets or real-time prediction, including embedded applications.

  • Takeaways & Limitations

    Random Kitchen Sinks remains limited by storing the random matrix and computing Zx at O(n · d) cost for each observation.

Abstract

from arXiv · show

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.

1 Introduction

Kernel methods represent nonlinear functions through implicit high-dimensional feature spaces, but their dual expansions become costly as datasets and support-vector counts grow.

  • Kernel methods: Kernel methods compute inner products in high-dimensional, potentially infinite-dimensional feature spaces implicitly through a kernel function.The feature map transports observations into a feature space while avoiding explicit coordinates.
  • Kernel methods: The kernel trick evaluates the decision function through a finite expansion of kernel evaluations.The Representer Theorem guarantees such finite expansions under fairly benign conditions.
  • Scaling challenge: Support-vector counts can grow linearly with training-set size, increasing the cost of evaluating the decision function.This becomes especially problematic when datasets contain billions of instances.
  • Scaling challenge: Large-scale primal solvers avoid this expansion cost but limit themselves to linear kernels.That restriction reduces the available function class compared with nonlinear kernel methods.

2 Related Work

Prior scalable kernel approximations trade computational cost, memory, dimensionality, or flexibility in different ways; Fastfood replaces dense random matrices with structured matrices to reduce both time and storage.

  • Existing approximations: Reduced-set and low-rank expansions reduce kernel complexity but can require costly optimization, basis selection, or temporary O(n^2) training storage.Reduced-set prediction costs O(nρd), while covariance inversion costs O(n^3).
  • Existing approximations: Multipole methods are efficient in modest dimensions but become intractable in high dimensions and are typically tuned to Gaussian RBF kernels.Their space-partitioning requirements are limited by the curse of dimensionality.
  • Existing approximations: Random subset kernels require evaluating membership across all partitions and incur O(knm) computation for n partitions, k sets, and m observations.The estimate is optimistic because it assumes partition computation is independent of data dimensionality.
  • Random Kitchen Sinks: Random Kitchen Sinks explicitly generate features by multiplying observations by a Gaussian random matrix and applying a coordinatewise nonlinearity.This approach requires O(n × d) storage and O(nρd) prediction computation.
  • Fastfood: Fastfood replaces Gaussian random matrices with Gaussian-scaled Hadamard matrices, enabling FFT-like multiplication without storing the matrix.The resulting approximation reduces Random Kitchen Sinks from O(nd) to O(n log d) time and from O(nd) to O(n) storage.
  • Fastfood: Fastfood is theoretically unbiased, has low variance, and concentrates nearly as fast as Random Kitchen Sinks.The method extends beyond radial basis functions to kernels expressible as dot products.
  • Optimization: Explicit feature expansions support optimization methods that require gradients in the feature space to be computed directly.This includes recent online and batch subgradient algorithms.
  • Computational comparison: Table 1 summarizes computational costs for reduced-rank expansion algorithms under β = 1 and typical sparsity ρ = 0.01.The caption provides the assumptions but not the individual algorithm values.

3 Kernels and Regularization

This section develops kernel expansions through feature spaces, Mercer decompositions, and symmetry-group eigensystems. It then connects these representations to sampled Fourier and spherical constructions while identifying computational and locality trade-offs.

  • Regularization links feature maps and RKHS norms, with kernels recoverable as inner products or Green’s functions of regularization operators.
  • Mercer’s theorem expresses suitable kernels as inner products in a Hilbert space, enabling feature-space representations.
  • Sampling spectral components approximates the kernel expansion and converges to the true kernel as n →∞.
  • Kernels via Symmetry Groups: Symmetry-group invariance decomposes kernel eigenfunctions into irreducible representations, whose eigenvalues are identical within each representation.
  • Kernels via Symmetry Groups: Translation-invariant kernels admit Fourier expansions, with spectral functions obtained from the Fourier transform of k(x, 0); Gaussian kernels retain Gaussian spectra.
  • Explicit Templates: Dot-product kernels can use spherical sampling and Legendre polynomials, while explicit polynomial expansions trade exact common forms for faster evaluation.
  • Explicit Templates: Group-based expansions can create nonlocal effects, so local changes in observations may affect distant covariates through global basis functions.

4 Sampling Basis Functions

Fastfood replaces dense Gaussian random matrices in Random Kitchen Sinks with structured Hadamard and diagonal matrices, preserving kernel-approximation properties while reducing computation and storage.

  • Random Kitchen Sinks: Random Kitchen Sinks approximate Gaussian RBF kernels with explicit features but require storing Z and computing Zx at O(n·d) cost per observation.The feature map converges in expectation to the Gaussian RBF kernel, but dense random-matrix multiplication remains expensive.
  • Random Kitchen Sinks: Hash-based regeneration reduces Random Kitchen Sinks storage to O(n) but is computationally more costly than the original method.The approach recomputes Gaussian entries from hashed uniform samples rather than storing the matrix.
  • Fastfood: Fastfood parameterizes the approximation with diagonal random matrices, a permutation, and the Walsh-Hadamard matrix instead of a dense Gaussian matrix.B has random ±1 diagonal entries, G has Gaussian diagonal entries, and S is a random scaling matrix.
  • Fastfood: The fast Hadamard transform applies the implicit Hadamard matrix in O(d log d) time without storing it explicitly.For n ≥ d, independent blocks are stacked to obtain enough feature dimensions.
  • Computational efficiency: O(n log d) computation and O(n) permanent storage suffice to compute n Fastfood features for n ≥ d.The bound follows from blockwise fast Hadamard transforms, diagonal operations, permutation lookup, and Fourier-basis computation.
  • Approximation properties: Fastfood preserves Gaussian-like behavior through scaling, sign randomization, permutation, and Hadamard transforms, yielding an unbiased RBF approximation with O(1/n) variance.Its variance has an additional dependence on the input magnitude, while the method also extends beyond Gaussian RBF kernels through spectral sampling.

5 Analysis

Fastfood matches Random Kitchen Sinks’ O(1/n) variance while using structured transforms, and its approximation concentrates almost as well with substantially cheaper computation.

  • Variance: O(1/n) variance matches Random Kitchen Sinks, with an additional dependence on the input magnitude.The paper states that this theoretical guarantee agrees with empirical parity between Fastfood and exact kernel expansions.
  • Feature construction: Fastfood constructs features through scaled Hadamard transforms, permutation, Gaussian scaling, and cosine evaluation.The feature computation decomposes Vv into w, u, and z, with ψ_j(v)=cos(z_j).
  • Concentration: The d×d Fastfood block has approximation error at most logarithmically larger than Random Kitchen Sinks for a fixed error probability.The authors characterize this bound as potentially pessimistic.
  • Limitations: The authors caution that kernel-matrix approximation guarantees are likely conservative for generalization performance.Experiments indicate the algorithm works better in practice than the theory predicts.
  • Concentration: Fastfood converges to the true kernel and offers almost sub-Gaussian convergence for fixed point pairs, with uniform convergence over compact bounded sets.The paper also states that small approximate-kernel error does not significantly perturb solutions or generalization error across a wide range of algorithms.
  • Concentration: The concentration analysis uses Gaussian concentration for Lipschitz functions, with Hadamard and binary diagonal transforms controlling the largest transformed coordinates.The construction is shown to have a small Lipschitz constant with high probability.

6 Experiments

Experiments find Fastfood’s approximation accuracy comparable to Random Kitchen Sinks and exact alternatives, while substantially reducing prediction time and memory requirements.

  • 6.1 Approximation quality: Fastfood and Random Kitchen Sinks converge quickly to exact kernel values as n increases, with indistinguishable performance in Figure 1.The comparison averages absolute approximation errors over 4000 sampled vectors.
  • 6.1 Approximation quality: Fastfood performs virtually as well as exact kernels, Nyström, and Random Kitchen Sinks while costing substantially less to compute.This comparison includes polynomial and other kernel experiments; Fourier features also perform well.
  • 6.2 Speed of kernel computations: CPU regression quality generally improves as the number of basis functions increases, and Fourier features perform well despite weaker Gaussian-RBF approximation.The results suggest direct spectral adjustment may be useful for learning kernels.
  • 6.2 Speed of kernel computations: 24x faster prediction reduces runtime from 0.07 seconds with Random Kitchen Sinks to 0.003 seconds for one d=1,024, n=16,384 input.The paper reports greater speed gains for larger problems.
  • 6.3 Random features for CIFAR-10: CIFAR-10 results show that nonlinear expansions improve accuracy while Fastfood remains practical for high-dimensional data.The dataset contains 50,000 training images, 10,000 test images, and 3072 features per image.

7 Summary

Fastfood computes nonlinear basis functions in O(n log d) time, making kernel methods more practical for large datasets and real-time prediction. Its analysis covers translation-invariant and inner-product kernels, while extensions to other symmetry groups remain future work.

  • 7 Summary: O(n log d) time computes n nonlinear basis functions, enabling more practical kernel methods for large datasets and real-time prediction.The paper also notes that Fastfood can run on cellphones because it is fast and uses little storage.
  • 7 Summary: Fastfood applies beyond translation-invariant kernels to inner-product formulations, but extending the method to other symmetry groups remains future research.The authors position this as broader scalability beyond simple subspace decomposition strategies.
Loading 1408.3060v1…