PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting Thinning Methods for Kernel Learning Problems

Blanca Cano-Camarero, Yago R. Aguado-Carrillo-de-Albornoz, Ángela Fernández-Pascual, José R. Dorronsoro

arXiv:2609.07432v1cs.LGcs.AI

TL;DR

Kernel methods can be computationally expensive, while kernel subset methods also face restrictions such as Kernel Thinning's fixed coreset sizes. This paper introduces backward subset removal, flexible-size thinning, and supervised extensions; its experiments find competitive efficiency for Backward Kernel Herding and frequent predictive-performance gains for Flexible Kernel Thinning, with no single method leading in every setting.

  • Problem

    Kernel methods can require O(n^2) memory and up to O(n^3) training and inference time, and standard Kernel Thinning restricts coreset size to fixed power-of-two compression ratios.

    Source: §1 · p. 1, §3.1 · p. 7

  • Method

    The paper introduces Backward Kernel Herding, which removes points from the full dataset, and Flexible Kernel Thinning, which supports arbitrary coreset sizes while retaining Kernel Thinning's guarantees and computational cost.

    Source: §1 · p. 2, §5 · p. 19

  • Results

    Backward Kernel Herding matches state-of-the-art reduction methods while often offering favorable training-time efficiency, whereas Flexible Kernel Thinning frequently achieves the best predictive performance, especially at moderate compression ratios.

    Source: §5 · p. 19

  • Takeaways & Limitations

    The methods offer different trade-offs in predictive performance, training time, and memory, so no single reduction strategy dominates across all scenarios.

    Source: §5 · p. 19

    In GP regression, all methods obtain statistically equivalent results at every reduction size, with no clear winner.

    Source: §4 · p. 17

Abstract

from arXiv · show

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.

1 Introduction

Kernel subsampling addresses the high costs of kernel methods by using representative subsets, but existing approaches have limitations in how they construct or size those subsets. The paper introduces backward selection, flexible-size Kernel Thinning, supervised extensions, and a comparative evaluation.

1 Introduction

  • Kernel methods can require O(n^2) memory and up to O(n^3) training and inference time, limiting their use on large datasets.Representative subsets seek to preserve full-data properties in the RKHS, typically using MMD.Source: §1 · pp. 1–2
  • Forward Kernel Herding may severely harm predictive performance when the desired subset is smaller than half the dataset, while direct removal may require fewer iterations when retaining most points.The proposed backward strategy directly optimizes the points to remove.Source: §1 · p. 2
  • Kernel Thinning restricts coreset sizes to successive halvings, and the proposed modification enables subsets of arbitrary size.The paper also states that the extension retains Kernel Thinning's convergence guarantees and computational cost.Source: §1 · p. 2
  • Backward Kernel Herding starts from the full dataset and iteratively removes points, providing a backward alternative to forward subset construction.The paper also extends backward subset selection to supervised kernel learning settings such as KSVMs and GPs.Source: §1 · p. 2
  • The paper addresses supervised dataset selection and compares Backward Kernel Herding, Kernel Herding, and Kernel Thinning amid a lack of standardized Kernel Thinning evaluations.Its experimental comparison is presented as showing the proposal to be competitive with state-of-the-art techniques.Source: §1 · p. 2

2 Kernel subsampling methods

This section reviews Kernel Herding and Kernel Thinning, then describes supervised kernels and several kernel constructions used to incorporate labels. The methods use RKHS representations and MMD to guide subset selection or kernel design.

2.1 Kernel Herding

  • Kernel Herding greedily selects super-samples to approximate a target distribution by minimizing MMD in the RKHS.In practice, the search can be restricted to the observed sample set.Source: §2.1 · p. 3

2.2 Kernel Thinning

  • Kernel Thinning uses randomized online halving with a square-root kernel, then selects and refines a candidate coreset using MMD and the target kernel.Its computational cost is O(n^2), and its output size is n/2^m for a prefixed integer m.Source: §2.2 · pp. 3–4

2.3 Supervised methods

  • In supervised learning, ignoring labels when constructing kernels may miss class structure or input-output dependencies, motivating kernels over the joint space X × Y.The paper notes these risks for classification and regression tasks.Source: §2.3 · p. 4

2.3.1 Joint Kernel Construction

  • The joint kernel's feature map is the tensor product of the input and label feature maps.The paper states that the product of positive-definite input and label kernels is also positive definite.Source: §2.3.1 · p. 6

2.3.2 Radial Basis Function (RBF) Kernel

  • For the Gaussian RBF kernel, Random Fourier Features approximate its infinite-dimensional RKHS feature map using sampled frequencies and phases.The frequency distribution is N(0, 2γI), and the phases are sampled uniformly on [0, 2π).Source: §2.3.2 · p. 6

2.3.3 Triangular Kernel

  • The triangular kernel's feature map can be approximated in finite dimensions by discretizing its integral representation.The discretization uses a uniform grid and scales the inner product to ensure consistency with the L2 inner product.Source: §2.3.3 · pp. 6–7

2.3.4 Kronecker Delta Kernel

  • For discrete labels, the Kronecker delta kernel corresponds to a one-hot label feature map.Its value is 1 for matching labels and 0 otherwise.Source: §2.3.4 · p. 7

3 New coreset selection techniques

Flexible Kernel Thinning (FKT) extends Kernel Thinning to target arbitrary retention fractions, while Backward Kernel Herding (BKH) reaches a target subset size by iteratively removing points. FKT uses tree pruning and joint refinement; BKH removes points to limit distortion of the dataset’s mean embedding.

3.1 Flexible Kernel Thinning (FKT)

  • FKT applies one KT-SWAP refinement to the union of its selected blocks, allowing swaps across levels to address cross-block redundancy.KT-SWAP can refine any candidate set, and the combined refinement can only improve the candidate’s MMD.Source: §3.1 · p. 8, §3.1.1 · p. 8
  • FKT supports any prescribed coreset size ≈pn by using a truncated binary expansion of the retention fraction and selecting corresponding subsets from a KT-SPLIT tree.The expansion is truncated at tolerance τ; each nonzero bit contributes a block of approximately n/2^i points.Source: §3.1 · p. 7, §3.1.1 · p. 10

3.1.1 Theoretical guarantees

  • FKT preserves standard Kernel Thinning’s worst-case cost and better-than-i.i.d. MMD guarantees, with an approximation-bound factor depending logarithmically on the binary expansion length of p.Its tree-pruning selections use the same balanced random walk at each level, with sub-Gaussian tail control.Source: §3.1.1 · pp. 8, 10

3.2 Backward Kernel Herding via Mean Embedding Minimization

  • BKH iteratively removes points until the target size, choosing removals to minimize distortion of the remaining dataset’s mean embedding.The kernelized formulation avoids relying on an explicit feature-map representation.Source: §3.2 · pp. 10–11

12 end

BKH removes feature-space points near the full dataset’s mean embedding, complementing SVMs’ retention of extreme support-vector points. Its computational advantage over Kernel Herding depends on the retention fraction and whether an exact kernel is required.

3.2.1 Observations

  • BKH removes points near the feature-space mean embedding, whereas SVMs retain extreme support-vector points; the paper identifies removed points as least informative to an SVM.The authors connect this contrast to discarding non-support-like points first for dataset compression.Source: §3.2.1 · p. 12
  • Although Kernel Herding methods optimize the same objective, their greedy path dependence means they can produce different coresets at the same final size.The passage states that both methods have the same MMD error guarantees for T = ⌊np⌋.Source: §3.3 · p. 13, §3.2.1 · p. 13

3.3 Methods comparison

  • For p > 0.5, Kernelized BKH’s loop cost is at most 1/8n^2Ck versus KH’s more than 1/2n^2Ck, a reduction by more than a factor of four.The comparison concerns loop cost; BKH with RFF also avoids Kernelized BKH’s fixed O(n^2Ck) preprocessing.Source: §3.3 · p. 14
  • KH is preferred when p ≤0.27; for larger p, use Kernelized BKH when an exact kernel is required, otherwise BKH with RFF is preferable.The RFF option is especially preferable as p approaches 1 or when Ck ≫CΦ.Source: §3.3 · p. 14

4 Experiments

The experiments compare kernel reduction methods for supervised KSVM and GP tasks. FKT leads predictive performance in most scenarios, while BKH and KH remain attractive when training efficiency is the priority.

4 Experiments

  • Experiments use OpenML classification and regression suites; KSVMs and GPs are evaluated with task-appropriate predictive metrics, training time, and memory.Source: §4 · p. 15
  • FKT delivers the best predictive performance in most scenarios, especially classification and KSVM regression; BKH and KH remain alternatives when training efficiency matters.At 50% and 75% retained data, FKT improves performance in GP classification and KSVM regression; at 25%, methods are statistically indistinguishable, though FKT remains among the best.Source: Table 2 · p. 16, §4 · pp. 17–19
  • BKH and KH generally outperform FKT in training time; BKH ranks best for KSVM classification with 75% of the data retained.FKT’s supervised-kernel evaluation and iterative thinning add subset-construction overhead.Source: Table 3 · p. 17, §4 · pp. 17–18
  • For GP regression, all methods are statistically equivalent at every reduction size, so no clear predictive winner emerges.Source: §4 · p. 17
  • FKT uses the least memory for KSVM classification and regression; GP classification favors FKT at the strongest reduction, while BKH is competitive with larger subsets.For GP regression, FKT and BKH memory differences are not statistically significant.Source: Table 4 · p. 18, §4 · p. 18

5 Conclusions and further work

The authors report competitive performance for Backward Kernel Herding (BKH) and frequent best predictive performance for Flexible Kernel Thinning (FKT), with different accuracy–efficiency trade-offs. They also propose supervised and size-flexible methods and identify ensemble and multi-point strategies as future work.

5 Conclusions and further work

  • BKH starts with the full dataset and removes points to minimize mean-embedding distortion, reducing greedy iterations when the desired reduction is smaller than 27% of the dataset.The authors also justify its suitability for Support Vector Machines by noting that it discards less-informative interior points first, which may not be support vectors.Source: §5 · p. 19
  • FKT uses the target retention fraction's binary expansion to construct arbitrary-size coresets while preserving Kernel Thinning's computational cost and theoretical guarantees.The authors extend existing and proposed methods to supervised settings using joint and supervised kernels to retain label dependencies during compression.Source: §5 · p. 19
  • BKH matches state-of-the-art reduction performance, while FKT frequently achieves the best predictive performance and maintains competitive memory requirements.The authors report BKH's favorable computational properties, particularly training time, and FKT's advantage especially under moderate compression ratios.Source: §5 · p. 19
  • Future work could combine distinct BKH and Kernel Herding coresets into an ensemble, reusing computed kernel means and transformation values.The authors suggest this could improve performance and robustness.Source: §5 · p. 19
  • Future work could investigate selecting or removing multiple points per iteration, potentially improving approximation quality at additional computational cost.The authors give processing two points per iteration as an example.Source: §5 · p. 19

CRediT authorship contribution statement

The contribution statement assigns the authors' research and writing roles. The authors also disclose using ChatGPT to improve language style and state that they reviewed and edited the content and take responsibility for it.

CRediT authorship contribution statement

  • The contribution statement assigns conceptualization and supervision to all four authors, with methodology, software, validation, formal analysis, investigation, and data curation attributed to the first two.The first two authors also contributed original-draft writing; the latter two contributed review and editing, and José R. Dorronsoro is additionally credited with project administration and visualization is credited to Blanca Cano-Camarero.Source: CRediT authorship contribution statement · p. 20

Declaration of Generative AI and AI-assisted technologies in the writing process

Loading 2609.07432v1…