First Finite-Particle Guarantee for the Optimization Landscape of Overparameterized Weighted MMD

From Kernel Methods to Particle Optimization: The Optimization Challenge of MMD

Maximum Mean Discrepancy (MMD) is a classic measure in machine learning for quantifying the difference between two distributions, widely used in generative models, domain adaptation, and kernel two-sample testing. In practice, MMD is typically computed by approximating the target distribution with a set of weighted particles (weighted atomic measures), whose positions and weights are jointly optimized via gradient descent.

The problem is that this optimization problem is non-convex. When the number of particles is insufficient, gradient flow easily gets trapped in "spurious" local minima—the loss cannot decrease, and the generated distribution deviates significantly from the target. For a long time, there has been a lack of quantitative finite-particle guarantees regarding "how many particles are enough" and "whether bad stationary points exist in the non-convex landscape."

Maximum Mean Discrepancy (MMD): Given a reproducing kernel Hilbert space (RKHS) $\mathcal{H}$ with kernel function $k$, for two distributions $P$ and $Q$, MMD is defined as

$$\mathrm{MMD}^2(P,Q)=\big|\mathbb{E}{X\sim P}[k(X,\cdot)]-\mathbb{E}{Y\sim Q}[k(Y,\cdot)]\big|_{\mathcal{H}}^2.$$

Intuitively, it measures the distance between the mean embeddings of two distributions after kernel mapping, so if and only if the kernel is characteristic (e.g., Gaussian kernel), $\mathrm{MMD}(P,Q)=0 \iff P=Q$. In practice, a set of weighted particles (atomic measures) $\sum_i w_i \delta_{x_i}$ is commonly used to approximate the target distribution $Q$, jointly optimizing particle positions ${x_i}$ and weights ${w_i}$ by minimizing $\mathrm{MMD}^2$. The exponential form of the Gaussian kernel makes this objective highly non-convex with respect to positions, and understanding its optimization landscape (stationary point structure, number of local minima) is precisely the core problem of this paper.

Core Result: With Enough Particles, Bad Local Minima Disappear

This study provides the first known finite-particle overparameterization guarantee for weighted MMD optimization with a one-dimensional Gaussian kernel. Specifically, for any compactly supported target distribution, as long as the number of particles is sufficiently large, the MMD at every local minimum can be arbitrarily small—in other words, the "poor basins" in the non-convex landscape are flattened.

More critically, the stability result states: any stationary point with MMD value far from zero is unstable under weightless gradient flow on particle positions. This means gradient flow will not stably remain at these bad stationary points but will continue to descend. This conclusion covers both common parameterization schemes: weights constrained to the simplex (simplex-constrained), and weights unconstrained but optimized to optimality at each step.

Overparameterisation and Benign Landscape: In deep learning, when the number of model parameters exceeds the number of training samples, despite the loss function remaining non-convex, optimization often becomes easier. The core question in theoretical research is: does there exist a threshold on the number of particles/parameters beyond which every local minimum of the loss function achieves a value close to the global minimum (i.e., no spurious local minima), and all saddle points are strict saddle points (unstable)? Such conclusions are typically called "overparameterization guarantees." The contribution of this paper is precisely to extend this paradigm from neural networks to weighted MMD optimization: the number of particles corresponds to adjustable parameters, and the "threshold" in the conclusion is the minimum number of particles required for overparameterization.

Weightless Gradient Flow: Since each particle has both position and weight variables, directly performing gradient descent on both would couple the gradient in the weight dimension with the position gradient, complicating stability analysis. The paper adopts "weightless gradient flow"—fixing the current optimal weights and performing continuous-time gradient flow only on particle positions—to characterize stationary point stability. This simplification captures the essential dynamics of position parameters: if a stationary point has a negative eigenvalue in the Hessian along the position direction, then even with optimal weights, that stationary point cannot be stable, and gradient flow will escape along the negative curvature direction. This analytical approach is equivalent to gradient descent with infinitesimal step size in the continuous-time limit.

Finite-Support Targets: Explicit Particle Threshold and No Spurious Minima

When the target distribution itself has finite support, the results are stronger. The paper provides an explicit particle count threshold, beyond which:

• No spurious local minima exist;
• Every spurious stationary point is unstable.

"Explicit threshold" means this particle count is not an abstract limiting statement but a concretely computable lower bound, providing direct guidance for particle count selection in practice.

According to the authors, this is the first such finite-particle overparameterization guarantee in the field of weighted MMD optimization. Previous results on overparameterized "benign landscapes" have mostly focused on neural networks or specific non-convex problems, and the corresponding theory for MMD particle optimization has been a blank.

Why This Result Matters

Overparameterization has been widely observed to improve optimization landscapes in deep learning, but theoretical explanations have long lagged behind. The value of this work lies in transforming the empirical intuition that "more particles make optimization easier" into a rigorous mathematical proposition for the specific and important objective of MMD.

The implications for practitioners are direct and clear:

• Particle count selection now has theoretical basis. In the one-dimensional Gaussian kernel setting, the required number of particles can be estimated based on the compact support range of the target distribution, rather than relying purely on tuning.
• Bad stationary points are not scary. Even if stationary points with large MMD exist, gradient flow will spontaneously escape, explaining why increasing the number of particles often stably improves results in practice.
• Weight constraint methods do not change the conclusions. The simplex-constrained and unconstrained stepwise optimization schemes have consistent landscape properties, leaving flexibility at the implementation level.

Of course, the conclusions are currently limited to one-dimensional Gaussian kernels and compactly supported targets. Finite-particle guarantees for high-dimensional kernels and other kernel functions remain open problems.

Limitations and Outlook

The one-dimensional assumption is the core limitation of this result. In high-dimensional spaces, the gradient flow dynamics of particle positions are more complex, and the compact support condition is harder to satisfy; whether the threshold can be generalized remains unclear. Additionally, the paper discusses the stability of continuous-time gradient flow, and the effect of step size in discrete gradient descent is not included in the analysis.

Nevertheless, as the first finite-particle guarantee in this direction, it provides a clear starting point for subsequent research: from one dimension to high dimensions, from Gaussian kernels to general kernels, from gradient flow to practical optimization algorithms, each step of generalization has a clear technical path to follow.

Continuous-time Gradient Flow vs. Discrete Gradient Descent: The stability conclusions in this paper are built on continuous-time gradient flow $\dot{x}(t) = -\nabla L(x(t))$. In reality, discrete gradient descent $x_{t+1}=x_t-\eta\nabla L(x_t)$ is used, and the two are equivalent only when the step size $\eta\to0$ and the number of iterations tends to infinity. For finite step sizes, even if a stationary point is unstable under continuous flow, if the step size is too large it may skip the escape direction leading to numerical divergence, and if the step size is too small the escape time may grow exponentially and appear stagnant. Therefore, extending from gradient flow to practical algorithms requires additional step size and complexity analysis, which is an important direction for future work.

One-line Summary

Weighted MMD optimization under one-dimensional Gaussian kernel: bad local minima disappear and bad stationary points are unstable when there are enough particles.

Paragraph Summary

This article introduces a study on the optimization landscape of weighted Maximum Mean Discrepancy (MMD), providing the first finite-particle overparameterization guarantee in this field. For one-dimensional Gaussian kernels and compactly supported target distributions, the authors prove that with enough particles, the MMD at every local minimum can be arbitrarily small—i.e., poor basins in the non-convex landscape are flattened. Moreover, any stationary point with MMD far from zero is unstable under weightless gradient flow, so gradient flow will not linger at bad stationary points. The conclusions cover both simplex-constrained weights and unconstrained stepwise optimization. When the target distribution has finite support, the results are stronger: an explicit particle count threshold exists beyond which no spurious local minima exist and all spurious stationary points are unstable. This provides theoretical guidance for particle count selection in practice, though currently limited to the one-dimensional Gaussian kernel setting.