Revisiting Thinning Methods for Kernel Learning Problems
Blanca Cano-Camarero, Yago R. Aguado-Carrillo-de-Albornoz, Ángela Fernández-Pascual, José R. Dorronsoro
cs.LG · cs.AI
Quick verdict
Adds backward herding and flexible kernel thinning for arbitrary-size supervised coresets; FKT most accurate, but random-subset and SKT baselines missing.
Summary
The paper tackles the quadratic-to-cubic cost of kernel methods by coreset selection in the RKHS via MMD. It contributes three things: (1) Backward Kernel Herding (BKH), which starts from the full dataset and iteratively removes the point whose feature map lies closest to the kernel mean embedding, with an exact identity linking the removed mass to the remaining MMD; (2) Flexible Kernel Thinning (FKT), which lifts Kernel Thinning's power-of-two size restriction by pruning the KT-SPLIT tree according to the binary expansion of the target retention fraction, at a claimed √L cost in the MMD bound; and (3) supervised joint kernels kX·kY (delta for classification, RBF/triangular for regression) for label-aware selection. Experiments on 72 OpenML classification and 35 CTR23 regression datasets, with KSVM and GP at 25/50/75% retention, use Wilcoxon+Holm and Friedman+Nemenyi tests. FKT attains the best predictive ranks, decisively at 50–75% retention (all methods tie at 25%); GP regression shows no significant differences. BKH is fastest or near-fastest while KH leads time at low retention; FKT is slowest (rank 3.00) but best in KSVM memory. Main limitations: no random-subset or Supervised Kernel Thinning baseline, no supervised-vs-unsupervised kernel ablation, and informal FKT theory resting on an unproven independence assumption.
Review complete
Assessment at a glance
6
risk flags identified
● high 1
● medium 2
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Backward Kernel Herding removes the point closest to the kernel mean embedding at each step and matches Kernel Herding's predictive performance at lower subsampling cost when retention p > 0.27.
- Flexible Kernel Thinning produces coresets of arbitrary size ≈pn by pruning the KT-SPLIT tree according to the binary expansion of p, retaining KT's MMD guarantees up to a √L factor.
- Supervised joint kernels kX·kY enable label-aware thinning, and FKT achieves the best predictive ranks across KSVM/GP tasks, especially at 50-75% retention.
- No single method dominates: FKT trades the slowest training time (rank 3.00) for accuracy, BKH offers the best speed/accuracy compromise, and the memory winner is task-dependent.
Strengths
FKT removes a real usability blocker of Kernel Thinning
Section 3.1 and Algorithm 5 give a concrete dyadic tree-pruning scheme (Eqs. 6-7) that produces coresets of any size ≈pn from the binary expansion of p, with the overhead honestly quantified as a √L factor in the MMD bound (Eq. 11).
BKH is simple, well-derived, and memory-light
Section 3.2 reduces the greedy removal to a nearest-to-mean-embedding criterion (Eq. 13); Algorithm 7 needs only 2n scalars (no kernel matrix), and §3.2.1 derives the exact identity MMD²(X⁽ᵐ⁾, μn) = ‖εm‖²/(n−m)².
Unusually broad, statistically grounded benchmark
Honest cost accounting with actionable rule of thumb
Code and public data released
Weaknesses
Missing the two most informative baselines
Supervised-kernel benefit is claimed, not tested
FKT theory is informal and rests on an unproven independence claim
Internal cost contradiction
Experimental bookkeeping inconsistencies
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper revisits MMD-based coreset selection for scaling kernel methods, with three contributions: (1) **Backward Kernel Herding** (BKH, §3.2, Algorithms 6-7): starting from the full dataset, iteratively remove the point whose feature map is closest to the kernel mean embedding (Eq. 13), with the exact identity MMD²(X⁽ᵐ⁾, μn) = ‖εm‖²/(n−m)² derived in §3.2.1; (2) **Flexible Kernel Thinning** (FKT, §3.1, Algorithm 5): decompose any retention fraction p into its binary expansion (Eqs. 6-7), prune the KT-SPLIT tree accordingly, and union the selected subtrees into a ≈pn coreset, claiming KT's MMD guarantee up to a √L factor (Eq. 11); (3) **supervised joint kernels** kX·kY with Kronecker-delta (classification) and RBF/triangular (regression) label components (§2.3). Headline empirical claims: FKT gives the best predictive ranks, BKH the best time/accuracy trade-off, no universal winner (Tables 2-4).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 6 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Backward Kernel Herding and when should I use it?
Backward Kernel Herding (BKH) is a coreset selection algorithm that starts from the full dataset and iteratively removes the point whose feature-map image lies closest to the kernel mean embedding, until the target size is reached. It is the mirror image of Kernel Herding (which builds the subset up from empty). It is most useful when you want to keep most of the data: per the paper, its cost beats Kernel Herding once the retention fraction exceeds about 27%, and it avoids the many greedy additions forward herding would need at high retention.
What problem does Flexible Kernel Thinning solve?
Standard Kernel Thinning can only output coresets whose size is n/2^m for an integer m (successive halvings). Flexible Kernel Thinning (FKT) decomposes any target retention fraction p into its binary expansion, prunes the halving tree accordingly, and unions the selected blocks into a coreset of size ≈p·n. The claimed price is a √L factor (L = binary expansion depth) in the MMD guarantee, plus the cost of the swap refinement step.
Which thinning method should I use to shrink data for KSVM or GP training?
According to the paper's benchmark (72 classification and 35 regression OpenML datasets): use FKT when predictive accuracy matters most (and for memory efficiency in KSVM tasks); use BKH or Kernel Herding when training time matters, with BKH best at high retention (≥75%). No method dominates: at 25% retention all methods were statistically tied, and for GP regression no significant differences were found at any size.
Is code and data available for this paper?
Yes. The authors release their code at github.com/BlancaCC/backward-thinning, and the experiments use public benchmarks: the OpenML classification suites and the OpenML-CTR23 regression suite, with scikit-learn-style KSVM and GP models on CPU-scale tabular data.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Nested mathematical subscripts (e.g., Eq. 17, Table 1 FLOP polynomials, Algorithm 4/5 notation) may be PDF-extraction artifacts, so I avoided asserting specific notation-level typos and flagged only plain-text inconsistencies.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.