mlsanityData to 14 Oct 2026

Kernel Thinning

arXiv 2105.05842 ↗First posted 12 May 2021stat.ML cs.LG math.STcited by 47

Not on the map. Why?

Abstract (arXiv)

We introduce kernel thinning, a new procedure for compressing a distribution mathbbP more effectively than i.i.d. sampling or standard thinning. Given a suitable reproducing kernel kstar and O(n2) time, kernel thinning compresses an n-point approximation to mathbbP into a √n-point approximation with comparable worst-case integration error across the associated reproducing kernel Hilbert space. The maximum discrepancy in integration error is Od(n-1/2√log n) in probability for compactly supported mathbbP and Od(n^-frac12 (log n)(d+1)/2√loglog n) for sub-exponential mathbbP on ℝd. In contrast, an equal-sized i.i.d. sample from mathbbP suffers Omega(n-1/4) integration error. Our sub-exponential guarantees resemble the classical quasi-Monte Carlo error rates for uniform mathbbP on [0,1]d but apply to general distributions on ℝd and a wide range of common kernels. Moreover, the same construction delivers near-optimal L^∞ coresets in O(n2) time. We use our results to derive explicit non-asymptotic maximum mean discrepancy bounds for Gaussian, Mat'ern, and B-spline kernels and present two vignettes illustrating the practical benefits of kernel thinning over i.i.d. sampling and standard Markov chain Monte Carlo thinning, in dimensions d=2 through 100.

Key facts. Cited by 47 papers in the map (data through 14 Oct 2026). Builds on 22 of its 104 references that are in the map. First posted on arXiv 12 May 2021.

Builds on

22 of 104 references.

References · 22

  1. 2014Control functionals for Monte Carlo integrationcited by 59
  2. 2017Automated Scalable Bayesian Inference via Hilbert Coresetscited by 55
  3. 2018Stein Pointscited by 43
  4. 2016Support pointscited by 39
  5. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  6. 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
  7. 2019Stein Point Markov Chain Monte Carlocited by 29
  8. 2019Kernel quadrature with DPPscited by 27
  9. 2020Optimal Thinning of MCMC Outputcited by 26
  10. 2018Random Feature Stein Discrepanciescited by 23
  11. 2015Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filteringcited by 22
  12. 2016Monte Carlo with Determinantal Point Processescited by 22
10 more
  1. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
  2. 2020Kernel interpolation with continuous volume samplingcited by 21
  3. 2015Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guaranteescited by 20
  4. 2016Black-box Importance Samplingcited by 13
  5. 2017The Gram-Schmidt Walk: A Cure for the Banaszczyk Bluescited by 10
  6. 2018A Bayes-Sard Cubature Methodcited by 10
  7. 2015Statistically efficient thinning of a Markov chain samplercited by 8
  8. 2017Improved Coresets for Kernel Density Estimatescited by 8
  9. 2020A Statistical Perspective on Coreset Density Estimationcited by 6
  10. 2016The power of online thinning in reducing discrepancycited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 13; 2024: 6; 2025: 11; 2026: 10.

47 papers.

Sort:

By area:

  1. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  2. 2021Generalized Kernel Thinningcited by 29
  3. 2021Positively Weighted Kernel Quadrature via Subsamplingcited by 25
  4. 2025SonicMoE: Accelerating MoE with IO and Tile-aware Optimizationscited by 21
  5. 2021Distribution Compression in Near-linear Timecited by 19
  6. 2023Sampling-based Nystr"om Approximation and Kernel Quadraturecited by 17
  7. 2023Compress Then Test: Powerful Kernel Testing in Near-linear Timecited by 14
  8. 2022Counterfactual inference in sequential experimentscited by 13
  9. 2023Optimally-Weighted Estimators of the Maximum Mean Discrepancy for Likelihood-Free Inferencecited by 13
  10. 2025Weighted quantization using MMD: From mean field to mean shift via gradient flowscited by 12
  11. 2023Kernel quadrature with randomly pivoted Choleskycited by 11
  12. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
35 more
  1. 2025A Dictionary of Closed-Form Kernel Mean Embeddingscited by 9
  2. 2022Online Kernel CUSUM for Change-Point Detectioncited by 7
  3. 2023SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spacescited by 7
  4. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7
  5. 2024Distributional Dataset Distillation with Subtask Decompositioncited by 7
  6. 2025Low-Rank Thinningcited by 7
  7. 2023Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approachcited by 6
  8. 2026WildCat: Near-Linear Attention in Theory and Practicecited by 6
  9. 2025A Unified View of Optimal Kernel Hypothesis Testingcited by 5
  10. 2023When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimalitycited by 4
  11. 2024Efficient and Accurate Explanation Estimation with Distribution Compressioncited by 4
  12. 2026A Critical Look at Targeted Instruction Selection: Disentangling What Matters (and What Doesn't)cited by 4
  13. 2022Online, Informative MCMC Thinning with Kernelized Stein Discrepancycited by 3
  14. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  15. 2024Supervised Kernel Thinningcited by 3
  16. 2024Differentially Private Synthetic Data with Private Density Estimationcited by 2
  17. 2024Learning Counterfactual Distributions via Kernel Nearest Neighborscited by 2
  18. 2025Stationary MMD Pointscited by 2
  19. 2023Bayes Hilbert Spaces for Posterior Approximationcited by 1
  20. 2023Policy Gradient with Kernel Quadraturecited by 1
  21. 2025Solving the Cold Start Problem on One's Own as an End User via Preference Transfercited by 1
  22. 2025Neural Low-Discrepancy Sequencescited by 1
  23. 2026New Bounds for Kernel Sums via Fast Spherical Embeddingscited by 1
  24. 2026Thinned Mean Field Langevin Dynamicscited by 1
  25. 2022Optimal Sub-sampling to Boost Power of Kernel Sequential Change-point Detectioncited by 0
  26. 2023GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorchcited by 0
  27. 2025Quenched large deviations for Monte Carlo integration with Coulomb gasescited by 0
  28. 2025Bilateral Distribution Compression: Reducing Both Data Size and Dimensionalitycited by 0
  29. 2025BayesSum: Bayesian Quadrature in Discrete Spacescited by 0
  30. 2026Convex-Geometric Error Bounds for Positive-Weight Kernel Quadraturecited by 0
  31. 2026Stein Kernelized Molecular Dynamics for Active Learning of Interatomic Potentialscited by 0
  32. 2026Express Language Modelingcited by 0
  33. 2026Amortized quadrature for posterior expectations in inverse problemscited by 0
  34. 2026DS@GT ARC at ImageCLEFmed GANs 2026: Geometric Filtering for Privacy-Preserving CT Slice Generationcited by 0
  35. 2026Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructionscited by 0