TL;DR
McKernel is a high-performance C++ library that brings the power of kernel methods to large-scale datasets by approximating kernel expansions in log-linear time. By combining a lightning-fast Walsh-Hadamard implementation with mini-batch SGD, it offers a theoretically grounded, parameter-efficient alternative to traditional deep learning.
What Problem Does This Paper Address?
Kernel methods, such as Support Vector Machines with RBF kernels, are prized for their flexibility and theoretical elegance. However, they traditionally scale poorly—often quadratically—with the number of data points, making them impractical for "big data" applications.
While deep learning has become the de facto standard for large-scale non-linear learning, the authors argue that deep networks are essentially performing a brute-force search for a good kernel in a massive, over-parameterized space. McKernel aims to bridge this gap by providing a fast, scalable way to use non-linear kernel expansions within the familiar mini-batch Stochastic Gradient Descent (SGD) framework, drastically reducing the number of parameters that need to be learned.
Methods
The library implements an optimized version of the Fastfood algorithm, which approximates the feature mapping of a kernel (like RBF or Matérn) using a series of structured matrices.
Key technical contributions include:
- Fast Walsh-Hadamard Transform (FWHT): The authors developed a custom, cache-friendly FWHT implementation. By utilizing SIMD (SSE2) intrinsics and loop unrolling, it significantly outperforms existing state-of-the-art libraries like Spiral.
- Memory Efficiency via Hashing: Instead of storing massive random matrices, McKernel uses hashing (Murmurhash) to generate pseudo-random components—such as permutations and binary flips—on-the-fly. This makes models incredibly compact and ensures deterministic behavior across training and testing without the need for large storage.
- Compositionality: The framework allows for "highly compositional networks" by increasing the number of kernel expansions ($E$), effectively stacking non-linearities in a way that mimics the depth of neural networks.
Datasets
The authors evaluated McKernel on two standard computer vision benchmarks:
- MNIST: The classic dataset of handwritten digits.
- FASHION MNIST: A more challenging drop-in replacement for MNIST featuring 10 classes of clothing items (e.g., T-shirts, coats, sneakers).
Key Insights and Ideas
- Deep Learning as Kernel Search: The paper proposes a unifying view where many deep learning breakthroughs—such as Batch Normalization, Dropout, and multi-branch architectures—have direct mathematical counterparts in the world of approximate kernel expansions.
- Log-Linear Scaling: By reducing the computational bottleneck of kernel expansions from $O(n^2)$ to $O(n \log n)$, McKernel enables kernel-based learning on millions of samples that were previously inaccessible.
- Parameter Efficiency: Most of the "intelligence" in McKernel comes from the fixed (but randomly initialized) kernel expansion. This allows the model to achieve high accuracy by learning only a final linear classifier, requiring far fewer learned parameters than a typical deep neural network.
Key Results
- Speedup: The custom FWHT implementation is roughly 2x faster than the Spiral library. For a matrix of size $2^{20}$, McKernel completes the transform in ~16ms compared to Spiral's ~36ms.
- Competitive Accuracy: On MNIST, McKernel reaches ~98% accuracy with 9 kernel expansions, matching state-of-the-art deep learning performance and significantly outperforming standard logistic regression (~92%).
- Fashion MNIST Performance: The library achieved ~89% accuracy on Fashion MNIST, a notable improvement over the ~84% baseline provided by logistic regression.

Limitations and Future Work
While the kernel expansions in this framework are largely fixed, the authors acknowledge that certain data types may benefit from specific kernels. They suggest that future work could involve learning the "calibration" parameters (the $C$ and $G$ matrices) via backpropagation. This would effectively create a hybrid model that combines the speed of fixed kernel expansions with the data-driven flexibility of deep learning. The ultimate goal is to establish these building blocks as part of a unifying theory of learning.
Summary updated