A blob method for inhomogeneous diffusion with applications to multi-agent control and sampling

Katy Craig, Karthik Elamvazhuthi, Matt Haberland, О. А. ТурановаMath. Comput 2022

Abstract

This paper presents a deterministic particle method for the weighted porous medium equation (WPME), offering a robust alternative to classical stochastic particle methods for linear diffusion. By generalizing blob methods to inhomogeneous settings, we provide a meshfree approach that preserves the gradient flow structure of the underlying PDE. We prove the convergence of this method on bounded time intervals and demonstrate its utility in quantization tasks, such as multi-agent coverage and probability sampling. Furthermore, we establish a formal link between these particle dynamics and the training of overparametrized two-layer neural networks with radial basis function (RBF) activations, identifying conditions under which the continuum limit exhibits emergent convexity.

Introduction

The problem of quantization—approximating a continuous probability distribution with a finite set of discrete agents—is central to robotics, statistics, and machine learning. In multi-agent systems, robots must often distribute themselves to "cover" a target density. In statistics, sampling requires generating points that represent a target measure. Traditionally, these tasks are handled via stochastic methods like Langevin dynamics. While effective, stochasticity introduces noise that requires ensemble averaging and can be difficult to integrate into deterministic control frameworks.

This research introduces a deterministic "blob method" for the weighted porous medium equation (WPME). Unlike previous deterministic methods that struggle with inhomogeneous targets (where the desired density varies across space), our approach provides a rigorous, meshfree framework for evolving particles toward any target distribution.

The Deterministic Blob Method

The core of the method lies in treating discrete particles not as infinitely sharp points (Dirac deltas), but as smoothed "blobs." By applying a mollifier $\zeta_\epsilon$, we regularize the particle interactions, transforming the complex PDE into a system of manageable Ordinary Differential Equations (ODEs).

Gradient Flow Preservation

The method is designed to respect the Wasserstein gradient flow structure. This ensures that particles move along the path of steepest descent for a specific energy functional, naturally gravitating toward the target distribution $\bar{\rho}$. To handle spatial constraints without the need for complex boundary conditions, we incorporate a confining potential $V_k$. This potential penalizes particles for exiting the domain, allowing the system to remain entirely deterministic and autonomous.

Theoretical Convergence

A primary contribution of this work is the rigorous proof of convergence. Using the "flow interchange method," we demonstrate that as the number of particles $N$ increases and the blob size $\epsilon$ decreases, the discrete particle system recovers the weak solution of the WPME. This proof is significant because it holds in arbitrary dimensions and accounts for the inhomogeneous nature of the target density.

Connections to Neural Network Training

One of the most compelling applications of this framework is in the study of neural network optimization. We show that the training dynamics of an overparametrized two-layer neural network using Radial Basis Function (RBF) activations are mathematically equivalent to our blob method.

In the "mean-field" limit, where the number of neurons becomes very large, the evolution of the network's weights follows the WPME. This perspective allows us to identify conditions on the data distribution and target function that lead to "emergent convexity." Even if the discrete energy landscape of a finite network is non-convex and riddled with local minima, the continuous limit can be convex, explaining why gradient descent often finds global optima in high-dimensional neural architectures.

Numerical Results and Performance

The method was evaluated using several synthetic target distributions, including uniform, log-concave (Barenblatt profiles), and piecewise-constant densities.

  • Scaling and Efficiency: Numerical experiments in 1D suggest that the number of particles $N$ scales approximately as $\epsilon^{-1.01}$ to maintain accuracy. While the interaction cost is $O(N^2)$, the use of GPU acceleration (via the CuPy library) provided a two-order-of-magnitude speedup, making the method viable for large swarms.
  • Accuracy: The system captures the long-time behavior of the PDE accurately, with error (measured by Kullback-Leibler divergence) decaying exponentially as particles settle into the target distribution.
  • Convergence Order: Researchers observed approximately second-order convergence in unconfined settings, though this rate decreases slightly under strong confinement.

Discussion and Limitations

While the blob method provides a powerful deterministic alternative for sampling and control, several avenues for future work remain. Currently, the strongest stability results require the target distribution to be log-concave; extending this to multi-modal distributions is a priority. Additionally, while the $O(N^2)$ complexity is manageable with modern hardware, scaling to millions of particles will likely require the integration of fast multipole methods. Finally, while the theoretical proof is dimension-independent, further numerical validation in 3D and higher-dimensional spaces is needed to fully characterize the method's performance in complex environments.

Conclusion

By providing a deterministic bridge between particle dynamics and inhomogeneous diffusion, this work offers a new toolkit for quantization and a deeper understanding of neural network training. The blob method's ability to preserve gradient flow structure while remaining meshfree makes it a versatile solution for modern challenges in autonomous systems and computational statistics.

Summary updated

Abstract

As a counterpoint to classical stochastic particle methods for linear diffusion equations, we develop a deterministic particle method for the weighted porous medium equation (WPME) and prove its convergence on bounded time intervals. This generalizes related work on blob methods for unweighted porous medium equations. From a numerical analysis perspective, our method has several advantages: it is meshfree, preserves the gradient flow structure of the underlying PDE, converges in arbitrary dimension, and captures the correct asymptotic behavior in simulations. That our method succeeds in capturing the long time behavior of WPME is significant from the perspective of related problems in quantization. Just as the Fokker-Planck equation provides a way to quantize a probability measure $\barρ$ by evolving an empirical measure according to stochastic Langevin dynamics so that the empirical measure flows toward $\barρ$, our particle method provides a way to quantize $\barρ$ according to deterministic particle dynamics approximating WMPE. In this way, our method has natural applications to multi-agent coverage algorithms and sampling probability measures. A specific case of our method corresponds exactly to confined mean-field dynamics of training a two-layer neural network for a radial basis function activation function. From this perspective, our convergence result shows that, in the overparametrized regime and as the variance of the radial basis functions goes to zero, the continuum limit is given by WPME. This generalizes previous results, which considered the case of a uniform data distribution, to the more general inhomogeneous setting. As a consequence of our convergence result, we identify conditions on the target function and data distribution for which convexity of the energy landscape emerges in the continuum limit.
BibTeX
@article{craig2022blob,
  author = {Katy Craig and Karthik Elamvazhuthi and Matt Haberland and О. А. Туранова},
  title = {{A blob method for inhomogeneous diffusion with applications to multi-agent control and sampling}},
  journal = {Math. Comput},
  year = {2022},
}
Figure