A Deterministic Sampling Method via Maximum Mean Discrepancy Flow with Adaptive Kernel
Authors: Yindong Chen, Yiwei Wang, Lulu Kang, Chun Liu
Abstract
We propose a novel deterministic sampling method, EVI-MMD, to approximate a target distribution ρ∗ by minimizing the kernel discrepancy, also known as the Maximum Mean Discrepancy (MMD). Leveraging the energetic variational inference framework (Wang et al., 2021), we transform the MMD minimization problem into solving a dynamic system of Ordinary Differential Equations (ODEs) for particles. The implicit Euler scheme is employed to solve the ODE system, leading to a proximal minimization problem at each iteration, which is efficiently addressed using optimization algorithms such as L-BFGS. A key innovation of our method is a dynamic bandwidth selection strategy for the Gaussian kernel, which, although heuristic at this stage, represents a meaningful step toward addressing a long-standing challenge in kernel-based methods. Comprehensive numerical experiments demonstrate that this adaptive bandwidth significantly enhances the performance of EVI-MMD. We apply the EVI-MMD algorithm to two types of sampling problems: (1) when the target distribution is fully specified by a density function, and (2) the ``two-sample problem,'' where only training data are available. In the latter case, EVI-MMD serves as a generative model, producing new samples that faithfully replicate the distribution of the training data. With carefully tuned parameters, EVI-MMD outperforms several existing methods in both scenarios.
Integration against a probability distribution given its unnormalized density is a central task in Bayesian inference and other fields. We introduce new methods for approximating such expectations with a small set of weighted samples -- i.e., a quadrature rule -- constructed via an interacting particle system that minimizes maximum mean discrepancy (MMD) to the target distribution. These methods extend the classical mean shift algorithm, as well as recent algorithms for optimal quantization of empirical distributions, to the case of continuous distributions. Crucially, our approach creates dynamics for MMD minimization that are invariant to the unknown normalizing constant; they also admit both gradient-free and gradient-informed implementations. The resulting mean shift interacting particle systems converge quickly, capture anisotropy and multi-modality, avoid mode collapse, and scale to high dimensions. We demonstrate their performance on a wide range of benchmark sampling problems, including multi-modal mixtures, Bayesian hierarchical models, PDE-constrained inverse problems, and beyond.
Accurately and efficiently estimating the variance of the Maximum Mean Discrepancy (MMD) remains challenging, particularly for unbalanced sample sizes. In this paper, we derive a finite-sample unbiased estimator of the MMD variance. To overcome the traditional O(N2) computational bottleneck, we develop a recursive prefix-suffix accumulation scheme for the Laplace kernel, reducing the computational complexity to O(NlogN) while requiring O(N) memory. Experimental results verify the theoretical exactness and numerical stability of the proposed estimator and demonstrate its scalability on large datasets. Furthermore, the method proves effective for monitoring distributional convergence during the training of Time-series Generative Adversarial Networks (TimeGAN).
Sampling from constrained distributions has a wide range of applications, including in Bayesian optimization and robotics. Prior work establishes convergence and feasibility guarantees for constrained sampling, but assumes that the feasible set is connected. However, in practice, the feasible set often decomposes into multiple disconnected components, which makes efficient sampling under constraints challenging. In this paper, we propose MAnifold Sampling via Entropy Maximization (MASEM) for sampling on a manifold with an unknown number of disconnected components, implicitly defined by smooth equality and inequality constraints. The presented method uses a resampling scheme to maximize the entropy of the empirical distribution based on k-nearest neighbor density estimation. We show that, in the mean field, MASEM decreases the KL-divergence between the empirical distribution and the maximum-entropy target exponentially in the number of resampling steps. We instantiate MASEM with multiple local samplers and demonstrate its versatility and efficiency on synthetic and robotics-based benchmarks. MASEM enables fast and scalable mixing across a range of constrained sampling problems, improving over alternatives by an order of magnitude in Sinkhorn distance with competitive runtime.
Cornelius V. Braun, Tilman Burghoff, Marc Toussaint