A blob method for inhomogeneous diffusion with applications to multi-agent control and sampling
HTML articles powered by AMS MathViewer
- by Katy Craig, Karthik Elamvazhuthi, Matt Haberland and Olga Turanova
- Math. Comp. 92 (2023), 2575-2654
- DOI: https://doi.org/10.1090/mcom/3841
- Published electronically: June 14, 2023
- HTML | PDF | Request permission
Abstract:
As a counterpoint to classical stochastic particle methods for linear diffusion equations, such as Langevin dynamics for the Fokker-Planck equation, we develop a deterministic particle method for the weighted porous medium equation 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.
The fact that our method succeeds in capturing the long time behavior of the weighted porous medium equation 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 {\rho }$ by evolving an empirical measure $\rho ^N(t) = \frac {1}{N} \sum _{i=1}^N \delta _{X^i(t)}$ according to stochastic Langevin dynamics so that $\rho ^N(t)$ flows toward $\bar {\rho }$, our particle method provides a way to quantize $\bar {\rho }$ according to deterministic particle dynamics approximating the weighted porous medium equation. In this way, our method has natural applications to multi-agent coverage algorithms and sampling probability measures.
A specific case of our method corresponds to confined mean-field dynamics of training a two-layer neural network for a radial basis 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 the weighted porous medium equation. 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.
References
- Luca Alasio, Maria Bruna, and José Antonio Carrillo, The role of a strong confining potential in a nonlinear Fokker-Planck equation, Nonlinear Anal. 193 (2020), 111480, 28. MR 4062975, DOI 10.1016/j.na.2019.03.003
- Luigi Ambrosio, Elia Brué, and Daniele Semola, Lectures on optimal transport, Unitext, vol. 130, Springer, Cham, [2021] ©2021. La Matematica per il 3+2. MR 4294651, DOI 10.1007/978-3-030-72162-6
- Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré, Gradient flows in metric spaces and in the space of probability measures, 2nd ed., Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2008. MR 2401600
- B. Anderson, E. Loeser, M. Gee, F. Ren, S. Biswas, O. Turanova, M. Haberland, and A. L. Bertozzi, Quantitative assessment of robotic swarm coverage, Proceedings of the 15th International Conference on Informatics in Control, Automation, and Robotics, vol. 2, 2018, pp. 91–101.
- Brendon G. Anderson, Eva Loeser, Marissa Gee, Fei Ren, Swagata Biswas, Olga Turanova, Matt Haberland, and Andrea L. Bertozzi, Quantifying robotic swarm coverage, Informatics in control, automation and robotics, Lect. Notes Electr. Eng., vol. 613, Springer, Cham, [2020] ©2020, pp. 276–301. MR 4328240, DOI 10.1007/978-3-030-31993-9_{1}3
- Jean-David Benamou, Guillaume Carlier, Quentin Mérigot, and Édouard Oudet, Discretization of functionals involving the Monge-Ampère operator, Numer. Math. 134 (2016), no. 3, 611–636. MR 3555350, DOI 10.1007/s00211-015-0781-y
- Marianne Bessemoulin-Chatard and Francis Filbet, A finite volume scheme for nonlinear degenerate parabolic equations, SIAM J. Sci. Comput. 34 (2012), no. 5, B559–B583. MR 3023729, DOI 10.1137/110853807
- V. I. Bogachev, Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655, DOI 10.1007/978-3-540-34514-5
- N. Bou-Rabee and A. Eberle, Markov chain Monte Carlo methods, Lecture notes, 2020 https://uni-bonn.sciebo.de/s/kzTUFff5FrWGAay.
- David P. Bourne and Riccardo Cristoferi, Asymptotic optimality of the triangular lattice for a class of optimal location problems, Comm. Math. Phys. 387 (2021), no. 3, 1549–1602. MR 4324385, DOI 10.1007/s00220-021-04216-6
- D. P. Bourne and S. M. Roper, Centroidal power diagrams, Lloyd’s algorithm, and applications to optimal location problems, SIAM J. Numer. Anal. 53 (2015), no. 6, 2545–2569. MR 3419889, DOI 10.1137/141000993
- Francesco Bullo, Jorge Cortés, and Sonia Martínez, Distributed control of robotic networks, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2009. A mathematical approach to motion coordination algorithms. MR 2524493, DOI 10.1515/9781400831470
- Martin Burger, José A. Carrillo, and Marie-Therese Wolfram, A mixed finite element method for nonlinear diffusion equations, Kinet. Relat. Models 3 (2010), no. 1, 59–83. MR 2580954, DOI 10.3934/krm.2010.3.59
- M. Burger and A. Esposito, Porous medium equation as limit of nonlocal interaction, Preprint, arXiv:2202.05030, 2022.
- Giuseppe Buttazzo, Semicontinuity, relaxation and integral representation in the calculus of variations, Pitman Research Notes in Mathematics Series, vol. 207, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989. MR 1020296
- Emanuele Caglioti, François Golse, and Mikaela Iacobelli, A gradient flow approach to quantization of measures, Math. Models Methods Appl. Sci. 25 (2015), no. 10, 1845–1885. MR 3358447, DOI 10.1142/S0218202515500475
- José Antonio Carrillo, Yanghong Huang, Francesco Saverio Patacchini, and Gershon Wolansky, Numerical study of a particle method for gradient flows, Kinet. Relat. Models 10 (2017), no. 3, 613–641. MR 3591126, DOI 10.3934/krm.2017025
- José A. Carrillo, Alina Chertock, and Yanghong Huang, A finite-volume method for nonlinear nonlocal equations with a gradient flow structure, Commun. Comput. Phys. 17 (2015), no. 1, 233–258. MR 3372289, DOI 10.4208/cicp.160214.010814a
- José Antonio Carrillo, Katy Craig, and Francesco S. Patacchini, A blob method for diffusion, Calc. Var. Partial Differential Equations 58 (2019), no. 2, Paper No. 53, 53. MR 3913840, DOI 10.1007/s00526-019-1486-3
- José A. Carrillo, Katy Craig, Li Wang, and Chaozhen Wei, Primal dual methods for Wasserstein gradient flows, Found. Comput. Math. 22 (2022), no. 2, 389–443. MR 4407747, DOI 10.1007/s10208-021-09503-1
- José A. Carrillo, Katy Craig, and Yao Yao, Aggregation-diffusion equations: dynamics, asymptotics, and singular limits, Active particles. Vol. 2. Advances in theory, models, and applications, Model. Simul. Sci. Eng. Technol., Birkhäuser/Springer, Cham, 2019, pp. 65–108. MR 3932458
- J. A. Carrillo and J. S. Moll, Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms, SIAM J. Sci. Comput. 31 (2009/10), no. 6, 4305–4329. MR 2566595, DOI 10.1137/080739574
- J. A. Carrillo, F. S. Patacchini, P. Sternberg, and G. Wolansky, Convergence of a particle method for diffusive gradient flows in one dimension, SIAM J. Math. Anal. 48 (2016), no. 6, 3708–3741. MR 3566905, DOI 10.1137/16M1077210
- José A. Carrillo, Helene Ranetbauer, and Marie-Therese Wolfram, Numerical simulation of nonlinear continuity equations by evolving diffeomorphisms, J. Comput. Phys. 327 (2016), 186–202. MR 3564334, DOI 10.1016/j.jcp.2016.09.040
- S. Chewi, T. L. Gouic, C. Lu, T. Maunu, and P. Rigollet, SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence, Preprint, arXiv:2006.02509, 2020.
- L. Chizat and F. Bach, On the global convergence of gradient descent for over-parameterized models using optimal transport, Preprint, arXiv:1805.09545, 2018.
- J. Cortes, S. Martinez, T. Karatas, and F. Bullo, Coverage control for mobile sensing networks, IEEE Trans. Robot. Autom. 20 (2004), no. 2, 243–255.
- Katy Craig, Nonconvex gradient flow in the Wasserstein metric and applications to constrained nonlocal interactions, Proc. Lond. Math. Soc. (3) 114 (2017), no. 1, 60–102. MR 3653077, DOI 10.1112/plms.12005
- Katy Craig and Andrea L. Bertozzi, A blob method for the aggregation equation, Math. Comp. 85 (2016), no. 300, 1681–1717. MR 3471104, DOI 10.1090/mcom3033
- Sara Daneri, Emanuela Radici, and Eris Runa, Deterministic particle approximation of aggregation-diffusion equations on unbounded domains, J. Differential Equations 312 (2022), 474–517. MR 4361838, DOI 10.1016/j.jde.2021.12.019
- M. Di Francesco and M. D. Rosini, Rigorous derivation of nonlinear scalar conservation laws from follow-the-leader type models via many particle limit, Arch. Ration. Mech. Anal. 217 (2015), no. 3, 831–871. MR 3356989, DOI 10.1007/s00205-015-0843-4
- V. Dobrić and J. E. Yukich, Asymptotics for transportation cost in high dimensions, J. Theoret. Probab. 8 (1995), no. 1, 97–118. MR 1308672, DOI 10.1007/BF02213456
- Jean Dolbeault, Ivan Gentil, Arnaud Guillin, and Feng-Yu Wang, $L^q$-functional inequalities and weighted porous media equations, Potential Anal. 28 (2008), no. 1, 35–59. MR 2366398, DOI 10.1007/s11118-007-9066-0
- R. M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 40 (1968), 40–50. MR 236977, DOI 10.1214/aoms/1177697802
- K. Elamvazhuthi, C. Adams, and S. Berman, Coverage and field estimation on bounded domains by diffusive swarms, 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE, 2016, pp. 2867–2874.
- K. Elamvazhuthi and S. Berman, Nonlinear generalizations of diffusion-based coverage by robotic swarms, 2018 IEEE Conference on Decision and Control (CDC), IEEE, 2018, pp. 1341–1346.
- U. Eren and B. Açıkmeşe, Velocity field generation for density control of swarms using heat equation and smoothing kernels, IFAC-PapersOnLine 50 (2017), no. 1, 9405–9411.
- L. C. Evans, O. Savin, and W. Gangbo, Diffeomorphisms and nonlinear heat flows, SIAM J. Math. Anal. 37 (2005), no. 3, 737–751. MR 2191774, DOI 10.1137/04061386X
- Alessio Figalli and Federico Glaudo, An invitation to optimal transport, Wasserstein distances, and gradient flows, EMS Textbooks in Mathematics, EMS Press, Berlin, [2021] ©2021. MR 4331435, DOI 10.4171/ETB/22
- Thomas O. Gallouët, Quentin Mérigot, and Andrea Natale, Convergence of a Lagrangian discretization for barotropic fluids and porous media flow, SIAM J. Math. Anal. 54 (2022), no. 3, 2990–3018. MR 4421481, DOI 10.1137/21M1422756
- Siegfried Graf and Harald Luschgy, Foundations of quantization for probability distributions, Lecture Notes in Mathematics, vol. 1730, Springer-Verlag, Berlin, 2000. MR 1764176, DOI 10.1007/BFb0103945
- Gabriele Grillo, Matteo Muratori, and Maria Michaela Porzio, Porous media equations with two weights: smoothing and decay properties of energy solutions via Poincaré inequalities, Discrete Contin. Dyn. Syst. 33 (2013), no. 8, 3599–3640. MR 3021373, DOI 10.3934/dcds.2013.33.3599
- J. D. Hunter, Matplotlib: a 2D graphics environment, Comput. Sci. Eng. 9 (2007), no. 3, 90–95.
- Mikaela Iacobelli, A gradient flow perspective on the quantization problem, PDE models for multi-agent phenomena, Springer INdAM Ser., vol. 28, Springer, Cham, 2018, pp. 145–165. MR 3888971
- Mikaela Iacobelli, Asymptotic analysis for a very fast diffusion equation arising from the 1D quantization problem, Discrete Contin. Dyn. Syst. 39 (2019), no. 9, 4929–4943. MR 3986316, DOI 10.3934/dcds.2019201
- Adel Javanmard, Marco Mondelli, and Andrea Montanari, Analysis of a two-layer neural network via displacement convexity, Ann. Statist. 48 (2020), no. 6, 3619–3642. MR 4185822, DOI 10.1214/20-AOS1945
- Richard Jordan, David Kinderlehrer, and Felix Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Anal. 29 (1998), no. 1, 1–17. MR 1617171, DOI 10.1137/S0036141096303359
- A. Korba, A. Salim, M. Arbel, G. Luise, and A. Gretton, A non-asymptotic analysis for Stein variational gradient descent, Adv. Neural Inf. Process. Syst. 33 (2020), 4672–4682.
- V. Krishnan and S. Martínez, Distributed optimal transport for the deployment of swarms, 2018 IEEE Conference on Decision and Control (CDC), IEEE, 2018, pp. 4583–4588.
- Pierre-Louis Lions and Sylvie Mas-Gallic, Une méthode particulaire déterministe pour des équations diffusives non linéaires, C. R. Acad. Sci. Paris Sér. I Math. 332 (2001), no. 4, 369–376 (French, with English and French summaries). MR 1821479, DOI 10.1016/S0764-4442(00)01795-X
- Q. Liu, Stein variational gradient descent as gradient flow, Adv. Neural Inf. Process. Syst. 30 (2017).
- Q. Liu and D. Wang, Stein variational gradient descent: a general purpose Bayesian inference algorithm, Adv. Neural Inf. Process. Syst. 29 (2016).
- Jianfeng Lu, Yulong Lu, and James Nolen, Scaling limit of the Stein variational gradient descent: the mean field regime, SIAM J. Math. Anal. 51 (2019), no. 2, 648–671. MR 3919409, DOI 10.1137/18M1187611
- Daniel Matthes, Robert J. McCann, and Giuseppe Savaré, A family of nonlinear fourth order equations of gradient flow type, Comm. Partial Differential Equations 34 (2009), no. 10-12, 1352–1397. MR 2581977, DOI 10.1080/03605300903296256
- Daniel Matthes and Horst Osberger, Convergence of a variational Lagrangian scheme for a nonlinear drift diffusion equation, ESAIM Math. Model. Numer. Anal. 48 (2014), no. 3, 697–726. MR 3177862, DOI 10.1051/m2an/2013126
- Daniel Matthes and Benjamin Söllner, Convergent Lagrangian discretization for drift-diffusion with nonlocal aggregation, Innovative algorithms and analysis, Springer INdAM Ser., vol. 16, Springer, Cham, 2017, pp. 313–351. MR 3644286
- Song Mei, Andrea Montanari, and Phan-Minh Nguyen, A mean field view of the landscape of two-layer neural networks, Proc. Natl. Acad. Sci. USA 115 (2018), no. 33, E7665–E7671. MR 3845070, DOI 10.1073/pnas.1806579115
- Q. Mérigot, A multiscale approach to optimal transport, Comput. Graph. Forum 30 (2011), 1583–1592. Wiley Online Library.
- Alexandre R. Mesquita, João P. Hespanha, and Karl Åström, Optimotaxis: a stochastic multi-agent optimization procedure with point measurements, Hybrid systems: computation and control, Lecture Notes in Comput. Sci., vol. 4981, Springer, Berlin, 2008, pp. 358–371. MR 2728891, DOI 10.1007/978-3-540-78929-1_{2}6
- Karl Oelschläger, Large systems of interacting particles and the porous medium equation, J. Differential Equations 88 (1990), no. 2, 294–346. MR 1081251, DOI 10.1016/0022-0396(90)90101-T
- R. Okuta, Y. Unno, D. Nishino, S. Hido, and C. Loomis, CuPy: a NumPy-Compatible Library for NVIDIA GPU Calculations, 31st Conference on Neural Information Processing Systems, 2017.
- Felix Otto, The geometry of dissipative evolution equations: the porous medium equation, Comm. Partial Differential Equations 26 (2001), no. 1-2, 101–174. MR 1842429, DOI 10.1081/PDE-100002243
- Francesco S. Patacchini and Dejan Slepčev, The nonlocal-interaction equation near attracting manifolds, Discrete Contin. Dyn. Syst. 42 (2022), no. 2, 903–929. MR 4369035, DOI 10.3934/dcds.2021142
- G. M. Rotskoff and E. Vanden-Eijnden, Trainability and accuracy of artificial neural networks: an interacting particle system approach, Comm. Pure Appl. Math. 75 (2022), no. 9, 1889–1935. MR 4465905, DOI 10.1002/cpa.22074
- H. L. Royden, Real analysis, The Macmillan Company, New York; Collier Macmillan Ltd., London, 1963. MR 151555
- Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
- Sylvia Serfaty, Gamma-convergence of gradient flows on Hilbert and metric spaces and applications, Discrete Contin. Dyn. Syst. 31 (2011), no. 4, 1427–1451. MR 2836361, DOI 10.3934/dcds.2011.31.1427
- Justin Sirignano and Konstantinos Spiliopoulos, Mean field analysis of neural networks: a law of large numbers, SIAM J. Appl. Math. 80 (2020), no. 2, 725–752. MR 4074020, DOI 10.1137/18M1192184
- Zheng Sun, José A. Carrillo, and Chi-Wang Shu, A discontinuous Galerkin method for nonlinear parabolic equations and gradient flow problems with interaction potentials, J. Comput. Phys. 352 (2018), 76–104. MR 3717129, DOI 10.1016/j.jcp.2017.09.050
- Alexandre B. Tsybakov, Introduction to nonparametric estimation, Springer Series in Statistics, Springer, New York, 2009. Revised and extended from the 2004 French original; Translated by Vladimir Zaiats. MR 2724359, DOI 10.1007/b13794
- S. Van Der Walt, S. C. Colbert, and G. Varoquaux, The NumPy array: a structure for efficient numerical computation, Comput. Sci. Eng. 13 (2011), no. 2, 22–30.
- Juan Luis Vázquez, The mathematical theories of diffusion: nonlinear and fractional diffusion, Nonlocal and nonlinear diffusions and interactions: new methods and directions, Lecture Notes in Math., vol. 2186, Springer, Cham, 2017, pp. 205–278. MR 3588125
- Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
- P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, et al., SciPy 1.0: fundamental algorithms for scientific computing in Python, Nat. Methods 17 (2020), no. 3, 261–272.
- N. K. Vishnoi, An introduction to Hamiltonian Monte Carlo method for sampling, Preprint, arXiv:2108.12107, 2021.
- Jonathan Weed and Francis Bach, Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, Bernoulli 25 (2019), no. 4A, 2620–2648. MR 4003560, DOI 10.3150/18-BEJ1065
- Weinan E, Chao Ma, and Lei Wu, Machine learning from a continuous viewpoint, I, Sci. China Math. 63 (2020), no. 11, 2233–2266. MR 4170870, DOI 10.1007/s11425-020-1773-8
- Michael Westdickenberg and Jon Wilkening, Variational particle schemes for the porous medium equation and for the system of isentropic Euler equations, M2AN Math. Model. Numer. Anal. 44 (2010), no. 1, 133–166. MR 2647756, DOI 10.1051/m2an/2009043
- S. Wojtowytsch, On the convergence of gradient descent training for two-layer ReLU-networks in the mean field regime, Preprint, arXiv:2005.13530, 2020.
Bibliographic Information
- Katy Craig
- Affiliation: Department of Mathematics, South Hall, Room 6607, University of California, Santa Barbara, California 93106-3080
- ORCID: 0000-0001-6085-4022
- Email: kcraig@math.ucsb.edu
- Karthik Elamvazhuthi
- Affiliation: Department of Mechanical Engineering, Bourns Hall A342, 900 University Ave., Riverside, California 92521
- ORCID: 0000-0003-0849-5178
- Email: kelamvazhuthi@engr.ucr.edu
- Matt Haberland
- Affiliation: BioResource and Agricultural Engineering Dept., Agricultural Engineering Bldg. (08), Room 101, San Luis Obispo, California 93407
- MR Author ID: 1436816
- ORCID: 0000-0003-4806-3601
- Email: mhaberla@calpoly.edu
- Olga Turanova
- Affiliation: Department of Mathematics, Michigan State University, 619 Red Cedar Road, C212 Wells Hall, East Lansing, MI 48824
- ORCID: 0000-0002-3129-6989
- Email: turanova@msu.edu
- Received by editor(s): March 9, 2022
- Received by editor(s) in revised form: February 7, 2023, and February 14, 2023
- Published electronically: June 14, 2023
- Additional Notes: The work of the first author was supported by NSF DMS grants 1811012 and 2145900, as well as a Hellman Faculty Fellowship. The first and fourth authors were supported by the Simons Center for Theory of Computing, at which part of this work was completed. The work of the second author was supported by AFOSR grants FA9550-18-1-0502 and FA9550-18-1-0502. The work of the fourth author was supported by NSF DMS grant 1907221 and NSF DMS grant 2204722.
- © Copyright 2023 American Mathematical Society
- Journal: Math. Comp. 92 (2023), 2575-2654
- MSC (2020): Primary 35Q35, 35Q62, 35Q68, 35Q82, 65M12, 82C22, 93A16
- DOI: https://doi.org/10.1090/mcom/3841