Revisiting Thinning Methods for Kernel Learning Problems

• URL: http://arxiv.org/abs/2609.07432v1
• Date: Mon, 07 Sep 2026 12:34:50 GMT
• Title: Revisiting Thinning Methods for Kernel Learning Problems
• Abstract summary: Kernel methods are widely used because of their strong theoretical guarantees and empirical performance.<n>High computational cost limits their applicability to large-scale datasets.<n>We introduce Backward Kernel Herding, an algorithm that achieves results comparable to current state-of-the-art approaches.<n>We also overcome a limitation of Kernel Thinning by proposing an extension that enables the construction of subsets of arbitrary size.
• Score: 0.38498574327875934
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Evolution of Optimization Methods: Algorithms, Scenarios, and Evaluations [98.44542103979735]
  First-order gradient descent methods, epitomized by gradient descent (SGD) and Adam, serve as the cornerstone of modern training pipelines.<n>Large-scale model training, stringent privacy requirements, and distributed learning paradigms expose critical limitations in these conventional approaches regarding privacy protection and memory efficiency.<n>We retrospectively analyze the evolutionary trajectory of deep learning optimization algorithms and present a comprehensive empirical evaluation of mainstreams across diverse model architectures and training scenarios.<n>We distill key emerging trends and fundamental design trade-offs, pinpointing promising directions for future research.
  arXiv  Detail & Related papers  (2026-04-14T17:01:36Z)
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel [55.82768375605861]
  We establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity for kernel methods.<n>Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics.
  arXiv  Detail & Related papers  (2025-06-12T23:17:09Z)
• Scalable Gaussian Processes with Low-Rank Deep Kernel Decomposition [7.532273334759435]
  Kernels are key to encoding prior beliefs and data structures in Gaussian process (GP) models.<n>Deep kernel learning enhances kernel flexibility by feeding inputs through a neural network before applying a standard parametric form.<n>We introduce a fully data-driven, scalable deep kernel representation where a neural network directly represents a low-rank kernel.
  arXiv  Detail & Related papers  (2025-05-24T05:42:11Z)
• Center-Sensitive Kernel Optimization for Efficient On-Device Incremental Learning [88.78080749909665]
  Current on-device training methods just focus on efficient training without considering the catastrophic forgetting.<n>This paper proposes a simple but effective edge-friendly incremental learning framework.<n>Our method achieves average accuracy boost of 38.08% with even less memory and approximate computation.
  arXiv  Detail & Related papers  (2024-06-13T05:49:29Z)
• Fast Asymmetric Factorization for Large Scale Multiple Kernel Clustering [5.21777096853979]
  Multiple Kernel Clustering (MKC) has emerged as a solution, allowing the fusion of information from multiple base kernels for clustering. We propose Efficient Multiple Kernel Concept Factorization (EMKCF), which constructs a new sparse kernel matrix inspired by local regression to achieve memory efficiency.
  arXiv  Detail & Related papers  (2024-05-26T06:29:12Z)
• Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints [69.27190330994635]
  Coreset selection is powerful in reducing computational costs and accelerating data processing for deep learning algorithms. We propose an innovative method, which maintains optimization priority order over the model performance and coreset size. Empirically, extensive experiments confirm its superiority, often yielding better model performance with smaller coreset sizes.
  arXiv  Detail & Related papers  (2023-11-15T03:43:04Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence [0.18416014644193063]
  We consider the broad class of Nystr"om-type methods to construct preconditioners. All considered methods aim to identify a representative subset of inducing ( Kernel) columns to approximate the dominant kernel spectrum.
  arXiv  Detail & Related papers  (2022-12-24T13:45:50Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified Sketches [3.3379026542599934]
  Kernel methods are learning algorithms that enjoy solid theoretical foundations while suffering from important computational limitations. We show that sparsified Gaussian (and Rademacher) sketches still produce theoretically-valid approximations. We derive excess risk bounds for both single and multiple output kernel problems, with generic Lipschitz losses.
  arXiv  Detail & Related papers  (2022-06-08T11:50:23Z)
• Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
  Kernel $k$ clustering is a powerful tool for unsupervised learning of non-linear data. In this paper, we generalize results leveraging a general family of means to combat sub-optimal local solutions. Our algorithm makes use of majorization-minimization (MM) to better solve this non-linear separation problem.
  arXiv  Detail & Related papers  (2020-11-12T16:07:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.