Kernel methods get faster and use less memory for big data
Revisiting Thinning Methods for Kernel Learning Problems
Machine LearningArtificial Intelligence
Summary
Kernel methods are powerful tools for analyzing data but can be slow and use lots of memory with large datasets. The authors introduce Backward Kernel Herding, a way to speed up this process by carefully removing data points while still keeping the important information. They also improve another method, Flexible Kernel Thinning, which lets you pick any size for your reduced dataset rather than just cutting it in half repeatedly. Their experiments show that choosing the right method depends on whether you want the best accuracy, the fastest training, or the least memory use. No one method works best for everything, so different tools suit different needs.
Kernel methodsMaximum Mean DiscrepancyReproducing Kernel Hilbert SpaceSubsamplingBackward Kernel HerdingKernel ThinningGaussian ProcessesSupport Vector MachinesCompression ratioSupervised learning
Authors
Blanca Cano-Camarero, Yago R. Aguado-Carrillo-de-Albornoz, Ángela Fernández-Pascual, José R. Dorronsoro
Abstract
Kernel methods are widely used because of their strong theoretical guarantees and empirical performance. However, their high computational cost limits their applicability to large-scale datasets. To address this shortcoming, several approaches use Maximum Mean Discrepancy to construct representative subsets that preserve the properties of the full dataset in a Reproducing Kernel Hilbert Space. We introduce Backward Kernel Herding, an algorithm that addresses this problem by iteratively removing points from the dataset, achieving results comparable to current state-of-the-art approaches while accelerating the subsampling process in realistic scenarios where the reduced size is less than half of the dataset. Moreover, we overcome a limitation of Kernel Thinning by proposing an extension that enables the construction of subsets of arbitrary size rather that restricting to successive halvings. Finally, we conduct an extensive experimental comparison focusing on the most relevant kernel learning procedures: Gaussian Processes and Kernel Support Vector Machines. The results show that Backward Kernel Herding consistently achieves competitive performance with the most favorable training-time efficiency, while the proposed Flexible Kernel Thinning frequently achieves the best predictive performance. These gains become especially pronounced for moderate compression ratios, highlighting the benefits of incorporating supervised information into the thinning process. In terms of memory consumption, Flexible Kernel Thinning is also competitive, whereas Backward Kernel Herding remains an alternative when computational efficiency is the primary objective. Overall, no single method dominates across all scenarios, underscoring the importance of selecting the reduction strategy according to the desired trade-off between predictive performance, training cost, and memory requirements.