McKernel: A Library for Approximate Kernel Expansions in Log-linear Time

J. de Curtò, I. de Zarzà, Fei Yang, Alex Smola, Fernando De la Torre, Chong‐Wah Ngo, Luc Van Gool

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.

The McKernel pipeline illustrating the transformation of input data into approximate kernel expansions.

As shown in Figure 1, the McKernel pipeline processes an input vector $x$ through several stages:

  1. Preprocessing: The input vector is padded to the nearest power of 2.
  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$.
  3. 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})$.
  4. 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.

Comparison of execution time between McKernel and the state-of-the-art Spiral library.

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

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].
BibTeX
@misc{curto2017mckernel,
  author = {J. de Curtò and I. de Zarzà and Fei Yang and Alex Smola and Fernando De la Torre and Chong‐Wah Ngo and Luc Van Gool},
  title = {{McKernel: A Library for Approximate Kernel Expansions in Log-linear Time}},
  year = {2017},
  eprint = {1702.08159},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1702.08159},
}
Figure