Generalized Kernel Thinning

The evolution of probabilistic inference methods has seen a shift from simple Monte Carlo sampling to sophisticated kernel-based approaches. Kernel methods, especially kernel herding and Stein variational techniques, have provided improved convergence guarantees in low to moderate dimensions. Dwivedi & Mackey’s (2021) kernel thinning (KT) algorithm further advanced this by optimizing coresets in RKHS, achieving better-than-i.i.d. error bounds. Nonetheless, these methods rely heavily on kernel smoothness and suffer from exponential dimension dependence, limiting their effectiveness in high-dimensional applications such as Bayesian posterior approximation, spatial statistics, and scientific modeling. As data complexity and dimensionality increase, there is a pressing need for scalable algorithms with dimension-free guarantees that can handle diverse kernels and heavy-tailed distributions, motivating the current research.

Existing kernel thinning algorithms exhibit dimension-dependent error bounds, which grow exponentially with the ambient space dimension, severely restricting their scalability. Non-smooth kernels like Laplace and Matérn, common in spatial and physical models, lack the smoothness properties required for prior guarantees. Moreover, many methods depend on kernel smoothness and decay properties, making them unsuitable for complex, high-dimensional distributions with heavy tails or irregular structures. The core challenge is to develop a universal, scalable kernel thinning method that provides tight, dimension-free guarantees across various kernels and distributions, including non-analytic and non-smooth types, while maintaining computational feasibility.

The paper proposes TARGET KT, a novel kernel thinning algorithm that directly applies the target kernel, achieving dimension-free error bounds regardless of kernel smoothness or distribution tail behavior. It introduces KT+—a multi-kernel approach combining the target kernel with a fractional power kernel (kα)—to improve performance on non-smooth kernels like Laplace and Matérn. Theoretical analysis confirms that these methods attain near-optimal error bounds, matching lower bounds in high dimensions. The approach maintains O(n²) complexity, suitable for large datasets, and extends the applicability of kernel methods to complex, high-dimensional inference tasks. This work fundamentally shifts the paradigm by removing the reliance on kernel smoothness and dimension, broadening the scope of kernel-based distribution approximation.

• �� Extend the original KT framework with TARGET KT, which applies the target kernel directly, avoiding the need for kernel square roots. • Develop KT-SPLIT and KT-SWAP steps—non-uniform random partitioning and iterative point exchanges—to optimize MMD. • Introduce multi-kernel combination (KT+) by summing the target kernel with a scaled fractional power kernel (kα), leveraging interpolation properties. • Theoretical analysis involves deriving tight error bounds using covering numbers of RKHS unit balls, ensuring dimension-free guarantees. • Complexity analysis confirms O(n²) evaluations, with practical implementation considerations for large datasets. • Experimental validation includes high-dimensional Bayesian posteriors and differential equation models, comparing MMD and integration errors across methods.

Experiments use synthetic and real-world datasets, including high-dimensional Gaussian mixtures, Bayesian posteriors from ODE models, and spatial data. Baselines include i.i.d. sampling, Dwivedi & Mackey’s ROOT KT, and other coreset methods. Metrics focus on MMD and single-function integration errors. Hyperparameters such as kernel bandwidths are tuned for each setting. Multiple replicates ensure statistical robustness. Results demonstrate TARGET KT’s superior performance in high dimensions, with error reductions up to 50% compared to i.i.d. and prior methods. KT+ further improves non-smooth kernel performance, validating theoretical guarantees. Ablation studies confirm the benefits of multi-kernel approaches and fractional power kernels.

TARGET KT achieves near dimension-free MMD bounds, with errors in d=100 reduced to below 0.05 at n=1024 samples, outperforming i.i.d. errors (~0.15). For non-smooth kernels, KT+ attains o(n−1/4) errors, significantly better than prior bounds. In Bayesian posterior compression, the method reduces sample sizes by over 50% while maintaining accuracy. Theoretical bounds closely match empirical results, confirming the tightness and universality of the guarantees. Multi-kernel approaches demonstrate robustness across diverse kernel types and distribution tail behaviors, establishing a new standard in high-dimensional kernel methods.

The algorithms are directly applicable to Bayesian inference, scientific computing, and spatial modeling, where high-dimensional distributions are common. They enable efficient posterior approximation, model compression, and uncertainty quantification with provable error bounds. The flexibility to handle various kernels and distributions makes them suitable for large-scale machine learning, physics simulations, and data-driven scientific discovery, especially in scenarios where traditional sampling is computationally prohibitive.

Despite theoretical advances, computational costs remain O(n²), limiting scalability for extremely large datasets. Practical implementation requires efficient approximations, such as low-rank kernel methods. The guarantees depend on assumptions about distribution tail behavior; performance on heavy-tailed or highly skewed data may vary. Further validation is needed for non-stationary or oscillatory kernels, and real-world deployment may encounter unforeseen challenges. Future work should focus on scalable algorithms, adaptive kernel selection, and extending guarantees to broader classes of distributions.