Stationary MMD Points

Technical Summary: Stationary MMD Points

Problem Statement
The paper addresses the fundamental problem of approximating a target probability distribution $\mu$ on $\mathbb{R}^d$ using a finite set of $n$ points $\{x_i\}_{i=1}^n$ for the purpose of numerical integration (cubature). While selecting points to minimize the Maximum Mean Discrepancy (MMD) is a popular strategy, the MMD objective function is non-convex. Consequently, existing algorithms (e.g., sequential greedy methods, particle-based minimization) can only guarantee convergence to local minima, not the global minimum. This creates a gap between theoretical results—which often assume access to global minimizers—and practical algorithms that only find stationary points. The authors investigate whether these stationary points, despite not being global minimizers, still possess desirable properties for numerical integration.

Methodology
The paper proposes a two-pronged approach:

1. Theoretical Analysis of Stationary Points: The authors define "stationary MMD points" as point sets where the gradient of the squared MMD with respect to the particle locations is zero. They analyze the integration error of these points for functions $f$ in the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}$ associated with the kernel $k$.
2. Computational Strategy: To compute these stationary points, the authors utilize a noisy MMD particle descent scheme. This involves simulating a gradient flow on the MMD functional with injected noise. The update rule for particles $x_i^{(t)}$ at time $t$ is given by:
   $$x_i^{(t+1)} = x_i^{(t)} - \gamma \left( \frac{1}{n} \sum_{j=1}^n \nabla_1 k(x_i^{(t)} + \beta_t u_i^{(t)}, x_j^{(t)}) - \mathbb{E}_{Y \sim \mu}[\nabla_1 k(x_i^{(t)} + \beta_t u_i^{(t)}, Y)] \right)$$
   where $\gamma$ is the step size, $\beta_t$ is a noise scale, and $u_i^{(t)}$ are Gaussian noise vectors.

Key Contributions

1. Super-Convergence of Stationary Points:
   The paper proves that for integrands $f \in \mathcal{H}$, the numerical integration error of stationary MMD points vanishes faster than the MMD itself. Specifically, if $\mu_n$ is the empirical measure of stationary points, the integration error satisfies:
   $$\left| \frac{1}{n} \sum_{i=1}^n f(x_i) - \int f d\mu \right| = o(\text{MMD}(\mu, \mu_n))$$
   This "super-convergence" arises because stationary points exactly integrate a specific linear subspace of $\mathcal{H}$ (spanned by derivatives of the kernel) that expands as $n$ increases. This result explains why practical algorithms that find local minima often perform better than worst-case MMD bounds suggest.

2. Non-Asymptotic Convergence of Noisy Gradient Flow:
   The authors provide a refined convergence analysis for the time-discretized, finite-particle MMD gradient flow with noise injection. They establish a novel non-asymptotic finite-particle error bound (Theorem 4.1). Unlike previous works that often suffer from exponential error growth with time steps or require asymptotic limits, this analysis shows that the MMD converges to zero with a rate of $O_P(n^{-1/2})$ (up to logarithmic factors) as both the number of particles $n$ and iterations $T$ increase. This proves that the proposed noisy descent scheme can indeed compute stationary MMD points.

Results

• Theoretical: The paper establishes that stationary MMD points achieve exact integration for a growing subspace of $\mathcal{H}$, leading to super-convergence. It also proves that the noisy MMD particle descent converges to these stationary points under specific regularity assumptions on the kernel and noise injection levels.
• Empirical: Experiments on synthetic Gaussian mixtures and real-world OpenML datasets (House8L, Elevators) demonstrate that stationary MMD points consistently outperform baseline methods, including i.i.d. sampling, Kernel Herding, and Support Points, in terms of integration error.
  • In the mixture of Gaussians experiment, the integration error for a function in $\mathcal{H}$ decayed at a rate of $-1.39$, while the MMD error decayed at $-1.35$, empirically confirming the super-convergence prediction.
  • The method was shown to be computationally efficient compared to Kernel Thinning (KT), which requires a large candidate pool and significantly more time to compute.
  • The approach remains effective in higher dimensions ($d=10, 50$) and on datasets where the support does not strictly meet all theoretical assumptions (e.g., non-connected support).

Significance
The paper resolves a critical open issue in distribution quantification and numerical integration: reconciling the theoretical performance of global MMD minimizers with the practical reality that only stationary points are computable. By proving that stationary points exhibit super-convergence, the authors provide a theoretical justification for the strong empirical performance of existing MMD-based algorithms. Furthermore, the work extends the applicability of MMD gradient flows beyond generative modeling to the specific task of computing high-quality quadrature nodes, offering a method with strong theoretical guarantees that does not rely on a pre-specified candidate pool (unlike Kernel Thinning) and is applicable to general target distributions.