On the Optimisation Landscape of Overparameterised Weighted MMD
This paper studies the nonconvex optimisation landscape of finite-particle maximum mean discrepancy (MMD) quantisation, where a target probability measure is approximated by a weighted atomic measure. For the one-dimensional Gaussian kernel, the authors prove that beyond explicit particle thresholds every local minimum has arbitrarily small MMD and every high-MMD stationary point is unstable under unweighted gradient flow. These are the first finite-particle overparameterisation guarantees for weighted MMD, though the analysis is currently limited to one dimension.
The paper delivers a rigorous landscape analysis for one-dimensional weighted MMD quantisation, establishing the first finite-particle overparameterisation guarantees of its kind. The results are sharp in the relaxed setting—where the exact threshold $N \geq K$ eliminates all spurious local minima—but are confined to the 1D Gaussian kernel and leave open higher-dimensional extensions and the tightness of simplex bounds.
The strongest parts are the structural results and the sharp relaxed guarantees. The authors show that every distinct particle location is active with positive total weight, that collisions are either globally optimal or unstable, and that in the relaxed well-specified case the landscape becomes exact once the number of particles $N$ reaches the number of target atoms $K$.
The principal limitation is the restriction to one dimension. The proofs rely on one-dimensional zero-counting and an ordering argument for particle signs, and the authors acknowledge that multidimensional analogues are an important open problem.
In addition, the simplex-constrained threshold scales as $O_D(\varepsilon^{-4} \log(1/\varepsilon))$, which the authors note is likely loose, especially when compared with the much milder relaxed rate $O_D(\log(1/\varepsilon)/\log\log(1/\varepsilon))$.
The evidence is internally consistent and the comparisons with related work are fair. The authors carefully distinguish their finite-particle landscape guarantees from population-level flow analyses, noting that those results do not describe the landscape at any fixed $N$. They also contrast their setting with prior parametric landscape work, emphasising that their guarantees cover arbitrary atomic targets with unequal weights and require only compact support for approximate results.
The paper is purely theoretical and no code or data repository is provided. Hyperparameters such as the Gaussian bandwidth normalisation $2\sigma^2 = 1$ and the simplex constraints are stated precisely, and full proofs are given in Appendices A and B. Reproducing the numerical illustrations in Appendix D would require independent implementation, while verifying the analytic results depends on carefully checking the constants in the zero-counting and interpolation arguments.
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.