Finite-Sample Unbiased Variance of MMD under Unbalanced Sampling: Exact Estimation and Quasi-Linear Computation

Existing two-sample testing techniques, particularly those based on choosing a kernel for the Maximum Mean Discrepancy (MMD), often assume equal sample sizes from the two distributions. Applying these methods in practice can require discarding valuable data, unnecessarily reducing test power. We address this long-standing limitation by extending the theory of generalized U-statistics and applying it to the usual MMD estimator, resulting in new characterization of the asymptotic distributions of the MMD estimator with unequal sample sizes (particularly outside the proportional regimes required by previous partial results). This generalization also provides a new criterion for optimizing the power of an MMD test with unequal sample sizes. Our approach preserves all available data, enhancing test accuracy and applicability in realistic settings. Along the way, we give much cleaner characterizations of the variance of MMD estimators, revealing something that might be surprising to those in the area: while zero MMD implies a degenerate estimator, it is sometimes possible to have a degenerate estimator with nonzero MMD as well; we give a construction and a proof that it does not happen in common situations.

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.

We propose Sobolev-regularized Maximum Mean Discrepancy (SrMMD) gradient flow, a regularized variant of maximum mean discrepancy (MMD) gradient flow based on a gradient penalty on the witness function. The proposed regularization mitigates the non-convexity of the MMD objective and yields provable \emph{global} convergence guarantees in MMD in both continuous and discrete time. A more surprising appeal is that our convergence analysis does not rely on isoperimetric assumptions on the target distribution. Instead, it is based on a regularity condition on the difference between kernel mean embeddings. A key highlight of the proposed flow is that it is applicable in both sampling (from an unnormalized target distribution) -- using Stein kernels -- and generative modeling settings, unlike previous works, where a gradient flow is suitable for only generative modeling or sampling but not both. The effectiveness of the proposed flow is empirically verified on a broad range of tasks in both generative modelling and sampling.