We study the optimisation landscape of the maximum mean discrepancy (MMD) over weighted atomic measures. For the one-dimensional Gaussian kernel, we show that, for any compactly supported target distribution, sufficiently many particles ensure that every local minimum has arbitrarily small MMD. Moreover, any stationary point whose MMD remains bounded away from zero is unstable under an unweighted gradient flow over the particle locations. These results hold both when the weights are constrained to the simplex, and when they are unconstrained but optimised at each step. When the target is itself finitely supported, we further strengthen this result: beyond an explicit particle threshold, there are no spurious local minima, and every spurious stationary point is unstable. To our knowledge, these are the first finite-particle overparameterisation guarantees of their kind for weighted MMD optimisation.
Figures & tables
Setting and result
Particle threshold
Guarantees
Relaxed weights K -atom target, ETP kernel (Theorem 4 )
N≥K
No spurious local minima. Every spurious stationary point is unstable.
Relaxed weights Target with compact support of diameter at most D , Gaussian kernel (Theorem 5 )
N>Nε(D)=OD(loglog(1/ε)log(1/ε))
Every local minimum has \MMD<ε . Stationary points with \MMD≥ε are unstable.
Simplex weights Target with compact support of diameter at most D , Gaussian kernel (Theorem 6 )
N>Nε(D)=OD(ε−4log(1/ε))
Every local minimum has \MMD<ε . Stationary points with \MMD≥ε are unstable.
No spurious local minima. Every spurious stationary point is unstable.
Table 1: Summary of the one-dimensional landscape and instability guarantees. Instability refers to the unweighted particle flow θ˙i=−Δ′(θi) . Relaxed weights are unrestricted and optimised at each particle configuration; the simplex results concern the joint objective in the weights and positions. The rates are asymptotic as ε→0 , with D and the Gaussian bandwidth fixed.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 1: A numerical illustration of the finite-particle landscapes. (a) Largest MMD among the retained local minima, for each of the 30 well-specified three-atom targets. Dots correspond to individual targets, while boxes show medians and quartiles with 1.5 -IQR whiskers. For N≥3 , the target can be represented exactly; hence a plotted value of zero means that the numerical search retained no positive-error local minimum. (b) MMD of the retained local minima for the continuous target P∗=Unif[0,12] , shown on a logarithmic scale. The N=1 solutions are obtained analytically.
Minimum maximum mean discrepancy (MMD) estimation has emerged as a robust and likelihood-free alternative to maximum likelihood estimation for parameter estimation. Yet, despite its practical success, the associated optimization problem remains poorly understood, with theoretical guarantees for existing algorithms hinging on convexity assumptions that rarely hold in practice. We address this gap by proposing a preconditioned gradient descent (PGD) scheme, establishing its asymptotic global convergence under explicit gradient-dominance and projection-residual conditions. Our approach is inspired by recent progress on MMD gradient flows, a nonparametric descent scheme on the space of probability measures. We provide extensive empirical evidence that our PGD scheme outperforms standard gradient descent across a range of challenging parameter estimation and composite hypothesis testing problems.
Sophia Seulkee Kang, Louis Sharrock, Xiaoyuan Cheng +2
Independent Researcher · University College London
Optimizing functionals over the space of probability measures is now ubiquitous in machine learning. A widely used approach is to perform the optimization directly over the Wasserstein space, but many objective functionals of practical interest are non-convex along Wasserstein geodesics, making the analysis of standard first-order methods challenging. In this work, we study a class of objectives over the Wasserstein space that admit a difference-of-convex (DC) decomposition and we lift the classical convex-concave procedure (CCCP) to this setting. Under smoothness and strong convexity assumptions on the convex components of the decomposition, we prove almost stationarity along the iterates of the resulting algorithm. Our main focus is on the Maximum Mean Discrepancy (MMD) and the Energy Distance (ED) functionals, for which we develop explicit Wasserstein DC decompositions, and establish local convergence of the scheme under mild assumptions. Empirically, we show that well-chosen DC decompositions yield faster and more stable convergence than Wasserstein gradient descent on these MMD objectives.
We study the problem of learning Gaussian mixture models under overparameterization. Prior work has shown that while overparameterization is essential for avoiding spurious local optima and enables global recovery of the ground-truth model using the gradient-EM (expectation-maximization) algorithm, it can dramatically slow down the local rate of convergence. Under certain assumptions on the mixture weights, we show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically, and design a gradient-based method that converges to minimizers at a locally linear rate. Additionally, we show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights. At a high level, the method alternates between several "short" gradient descent steps that approach the manifold and "long" Polyak steps that contract the distance to minimizers. Our results suggest that slow convergence is not an intrinsic challenge of overparameterization, but can be overcome by exploiting the favorable structure of the loss landscape.
Electrical & Computer Engineering, University of Washington, Seattle, WA · National Institute for Theory and Mathematics in Biology, Chicago, IL · Amazon, Inc.