More Like this

1. Nonlocal-Interaction Equation on Graphs: Gradient Flow Structure and Continuum Limit

   https://doi.org/10.1007/s00205-021-01631-w  

   Esposito, Antonio; Patacchini, Francesco S.; Schlichting, André; Slepčev, Dejan (May 2021, Archive for Rational Mechanics and Analysis)

   null (Ed.)

   Abstract We consider dynamics driven by interaction energies on graphs. We introduce graph analogues of the continuum nonlocal-interaction equation and interpret them as gradient flows with respect to a graph Wasserstein distance. The particular Wasserstein distance we consider arises from the graph analogue of the Benamou–Brenier formulation where the graph continuity equation uses an upwind interpolation to define the density along the edges. While this approach has both theoretical and computational advantages, the resulting distance is only a quasi-metric. We investigate this quasi-metric both on graphs and on more general structures where the set of “vertices” is an arbitrary positive measure. We call the resulting gradient flow of the nonlocal-interaction energy the nonlocal nonlocal-interaction equation (NL $$^2$$ 2 IE). We develop the existence theory for the solutions of the NL $$^2$$ 2 IE as curves of maximal slope with respect to the upwind Wasserstein quasi-metric. Furthermore, we show that the solutions of the NL $$^2$$ 2 IE on graphs converge as the empirical measures of the set of vertices converge weakly, which establishes a valuable discrete-to-continuum convergence result. 

   more » « less
2. Regularized Stein Variational Gradient Flow

   https://doi.org/10.1007/s10208-024-09663-w  

   He, Ye; Balasubramanian, Krishnakumar; Sriperumbudur, Bharath K; Lu, Jianfeng (July 2024, Foundations of Computational Mathematics)

   Abstract The stein variational gradient descent (SVGD) algorithm is a deterministic particle method for sampling. However, a mean-field analysis reveals that the gradient flow corresponding to the SVGD algorithm (i.e., the Stein Variational Gradient Flow) only provides a constant-order approximation to the Wasserstein gradient flow corresponding to the KL-divergence minimization. In this work, we propose the Regularized Stein Variational Gradient Flow, which interpolates between the Stein Variational Gradient Flow and the Wasserstein gradient flow. We establish various theoretical properties of the Regularized Stein Variational Gradient Flow (and its time-discretization) including convergence to equilibrium, existence and uniqueness of weak solutions, and stability of the solutions. We provide preliminary numerical evidence of the improved performance offered by the regularization. 

   more » « less
3. A mean-field analysis of two-player zero-sum games

   Domingo-Enrich, Carles; Jelassi, S; Mensch, A; Rotskoff, G; Bruna, J (December 2020, Advances in neural information processing systems)

   null (Ed.)

   Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs. 

   more » « less
4. Numerical analysis of the LDG method for large deformations of prestrained plates

   https://doi.org/10.1093/imanum/drab103  

   Bonito, Andrea; Guignard, Diane; Nochetto, Ricardo H.; Yang, Shuo (January 2022, IMA Journal of Numerical Analysis)

   Abstract A local discontinuous Galerkin (LDG) method for approximating large deformations of prestrained plates is introduced and tested on several insightful numerical examples in Bonito et al. (2022, LDG approximation of large deformations of prestrained plates. J. Comput. Phys., 448, 110719). This paper presents a numerical analysis of this LDG method, focusing on the free boundary case. The problem consists of minimizing a fourth-order bending energy subject to a nonlinear and nonconvex metric constraint. The energy is discretized using LDG and a discrete gradient flow is used for computing discrete minimizers. We first show $$\varGamma $$-convergence of the discrete energy to the continuous one. Then we prove that the discrete gradient flow decreases the energy at each step and computes discrete minimizers with control of the metric constraint defect. We also present a numerical scheme for initialization of the gradient flow and discuss the conditional stability of it. 

   more » « less
5. Gradient descent algorithms for Bures-Wasserstein barycenters

   Chewi, Sinh; Maunu, Tyler; Rigollet, Philipp; Stromme, Austin J. (January 2020, Proceedings of Machine Learning Research)

   Abernethy, Jacob; Agarwal, Shivani (Ed.)

   We study first order methods to compute the barycenter of a probability distribution $$P$$ over the space of probability measures with finite second moment. We develop a framework to derive global rates of convergence for both gradient descent and stochastic gradient descent despite the fact that the barycenter functional is not geodesically convex. Our analysis overcomes this technical hurdle by employing a Polyak-Ł{}ojasiewicz (PL) inequality and relies on tools from optimal transport and metric geometry. In turn, we establish a PL inequality when $$P$$ is supported on the Bures-Wasserstein manifold of Gaussian probability measures. It leads to the first global rates of convergence for first order methods in this context. 

   more » « less