Abstract
McKernel introduces a framework to use kernel approximates in the mini-batch setting with Stochastic Gradient Descent (SGD) as an alternative to Deep Learning. Based on Random Kitchen Sinks [Rahimi and Recht 2007], we provide a C++ library for Large-scale Machine Learning. It contains a CPU optimized implementation of the algorithm in [Le et al. 2013], that allows the computation of approximated kernel expansions in log-linear time. The algorithm requires to compute the product of matrices Walsh Hadamard. A cache friendly Fast Walsh Hadamard that achieves compelling speed and outperforms current state-of-the-art methods has been developed. McKernel establishes the foundation of a new architecture of learning that allows to obtain large-scale non-linear classification combining lightning kernel expansions and a linear classifier. It travails in the mini-batch setting working analogously to Neural Networks. We show the validity of our method through extensive experiments on MNIST and FASHION MNIST [Xiao et al. 2017].
Introduction
Kernel methods, such as Support Vector Machines (SVMs) with Radial Basis Function (RBF) kernels, have long been prized for their strong theoretical foundations and effectiveness on small-to-medium datasets. However, their scalability is a major hurdle; computational and storage requirements typically scale quadratically ($O(n^2)$) or cubically with the number of samples, making them impractical for modern "big data" applications.
While Deep Learning has become the dominant paradigm for large datasets, it is often viewed as a complex, "black-box" search for effective feature representations. McKernel proposes an alternative: using massive, approximate kernel expansions paired with simple linear classifiers. By leveraging highly optimized Fast Walsh Hadamard Transforms (FWHT), McKernel enables large-scale kernel learning in log-linear time, bridging the gap between the theoretical elegance of kernel methods and the scalability of deep networks.
Architecture and Methodology
The core of the McKernel library is a high-performance implementation of approximate kernel expansions based on Random Kitchen Sinks. The library is designed to work seamlessly with mini-batch Stochastic Gradient Descent (SGD), allowing it to be trained similarly to a neural network.
As shown in Figure 1, the McKernel pipeline processes an input vector $x$ through several stages:
- Preprocessing: The input vector is padded to the nearest power of 2.
- Transformation: The vector undergoes a series of in-place transformations defined by $\hat{Z} := \frac{1}{\sigma\sqrt{n}} CHG\Pi HB$. This sequence includes a binary matrix $B$ generated via hashing, the Walsh Hadamard matrix $H$, a random permutation $\Pi$, and Gaussian values $G$.
- Expansion: The resulting $\hat{Z}\hat{x}$ is passed through non-linear functions (sine and cosine) to form the final feature expansion $\phi(\hat{Z}\hat{x})$.
- Classification: A linear layer followed by a softmax function produces the final classification, optimized using SGD.
A key innovation is the custom FWHT, which utilizes SIMD intrinsics (SSE2 128-bit registers) and loop unrolling to achieve $O(n \log n)$ complexity with extremely low constants.
Experimental Evaluation
The authors evaluated McKernel on two standard benchmarks: MNIST (70,000 handwritten digits) and FASHION MNIST (70,000 clothing items). The experiments focused on comparing the computational efficiency of the McKernel library against existing state-of-the-art methods and assessing classification accuracy as a function of the number of kernel expansions.
Key Results
McKernel demonstrates significant improvements in both speed and scalability.
As illustrated in Figure 2, McKernel's optimized Hadamard transform consistently outperforms the "Spiral" library. For very large input matrices (dimension $2^{24}$), the library achieves up to an 18x speed improvement.
In terms of classification performance, the RBF Matérn kernel expansions consistently outperformed standard logistic regression. Accuracy improved steadily with more expansions ($E$), approaching the performance levels of sophisticated Deep Learning architectures but with significantly fewer learnable parameters. This suggests that increasing expansions builds a "hierarchical" structure that gains representational power similar to adding layers in a neural network.
Conclusion and Future Work
McKernel offers a compelling framework for large-scale machine learning by making massive kernel expansions computationally feasible. By viewing deep learning as a search for kernels, McKernel provides a more direct and theoretically grounded approach to building non-linear classifiers. Future work includes addressing the memory overhead associated with power-of-2 padding and porting these optimized transforms to GPUs to further enhance performance for massive datasets.
Summary updated