Gradient Flows and Riemannian Structure in the Gromov-Wasserstein Geometry

• URL: http://arxiv.org/abs/2407.11800v1
• Date: Tue, 16 Jul 2024 14:53:23 GMT
• Title: Gradient Flows and Riemannian Structure in the Gromov-Wasserstein Geometry
• Authors: Zhengxin Zhang, Ziv Goldfeld, Kristjan Greenewald, Youssef Mroueh, Bharath K. Sriperumbudur,
• Abstract summary: We study gradient flows in the Gromov-Wasserstein (GW) geometry. We focus on the inner product GW (IGW) distance between distributions on $mathbbRd. We identify the intrinsic IGW geometry that gives rise to the intrinsic IGW geometry, using which we establish a Benamou-Brenier-like formula for IGW.
• Score: 29.650065650233223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Wasserstein space of probability measures is known for its intricate Riemannian structure, which underpins the Wasserstein geometry and enables gradient flow algorithms. However, the Wasserstein geometry may not be suitable for certain tasks or data modalities. Motivated by scenarios where the global structure of the data needs to be preserved, this work initiates the study of gradient flows and Riemannian structure in the Gromov-Wasserstein (GW) geometry, which is particularly suited for such purposes. We focus on the inner product GW (IGW) distance between distributions on $\mathbb{R}^d$. Given a functional $\mathsf{F}:\mathcal{P}_2(\mathbb{R}^d)\to\mathbb{R}$ to optimize, we present an implicit IGW minimizing movement scheme that generates a sequence of distributions $\{\rho_i\}_{i=0}^n$, which are close in IGW and aligned in the 2-Wasserstein sense. Taking the time step to zero, we prove that the discrete solution converges to an IGW generalized minimizing movement (GMM) $(\rho_t)_t$ that follows the continuity equation with a velocity field $v_t\in L^2(\rho_t;\mathbb{R}^d)$, specified by a global transformation of the Wasserstein gradient of $\mathsf{F}$. The transformation is given by a mobility operator that modifies the Wasserstein gradient to encode not only local information, but also global structure. Our gradient flow analysis leads us to identify the Riemannian structure that gives rise to the intrinsic IGW geometry, using which we establish a Benamou-Brenier-like formula for IGW. We conclude with a formal derivation, akin to the Otto calculus, of the IGW gradient as the inverse mobility acting on the Wasserstein gradient. Numerical experiments validating our theory and demonstrating the global nature of IGW interpolations are provided.

Related papers

• Neural Sampling from Boltzmann Densities: Fisher-Rao Curves in the Wasserstein Geometry [1.609940380983903]
  We deal with the task of sampling from an unnormalized Boltzmann density $rho_D$ by learning a Boltzmann curve given by $f_t$. Inspired by M'at'e and Fleuret, we propose an which parametrizes only $f_t$ and fixes an appropriate $v_t$. This corresponds to the Wasserstein flow of the Kullback-Leibler divergence related to Langevin dynamics.
  arXiv  Detail & Related papers  (2024-10-04T09:54:11Z)
• Global $\mathcal{L}^2$ minimization at uniform exponential rate via geometrically adapted gradient descent in Deep Learning [1.4050802766699084]
  We consider the scenario of supervised learning in Deep Learning (DL) networks. We choose the gradient flow with respect to the Euclidean metric in the output layer of the DL network.
  arXiv  Detail & Related papers  (2023-11-27T02:12:02Z)
• Bridging the Gap Between Variational Inference and Wasserstein Gradient Flows [6.452626686361619]
  We bridge the gap between variational inference and Wasserstein gradient flows. Under certain conditions, the Bures-Wasserstein gradient flow can be recast as the Euclidean gradient flow. We also offer an alternative perspective on the path-derivative gradient, framing it as a distillation procedure to the Wasserstein gradient flow.
  arXiv  Detail & Related papers  (2023-10-31T00:10:19Z)
• Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold [59.73080197971106]
  This paper presents a first-order conjugate optimization method that converges faster than the steepest descent method. It aims to achieve global convergence over the Stiefel manifold.
  arXiv  Detail & Related papers  (2023-08-21T08:02:16Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Variational Wasserstein gradient flow [9.901677207027806]
  We propose a scalable proximal gradient type algorithm for Wasserstein gradient flow. Our framework covers all the classical Wasserstein gradient flows including the heat equation and the porous medium equation.
  arXiv  Detail & Related papers  (2021-12-04T20:27:31Z)
• Large-Scale Wasserstein Gradient Flows [84.73670288608025]
  We introduce a scalable scheme to approximate Wasserstein gradient flows. Our approach relies on input neural networks (ICNNs) to discretize the JKO steps. As a result, we can sample from the measure at each step of the gradient diffusion and compute its density.
  arXiv  Detail & Related papers  (2021-06-01T19:21:48Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• On the Convergence of Gradient Descent in GANs: MMD GAN As a Gradient Flow [26.725412498545385]
  We show that a parametric kernelized gradient flow mimics the min-max game in gradient regularized $mathrmMMD$ GAN. We then derive an explicit condition which ensures that gradient descent on the space of the generator in regularized $mathrmMMD$ GAN is globally convergent to the target distribution.
  arXiv  Detail & Related papers  (2020-11-04T16:55:00Z)
• A diffusion approach to Stein's method on Riemannian manifolds [65.36007959755302]
  We exploit the relationship between the generator of a diffusion on $mathbf M$ with target invariant measure and its characterising Stein operator. We derive Stein factors, which bound the solution to the Stein equation and its derivatives. We imply that the bounds for $mathbb Rm$ remain valid when $mathbf M$ is a flat manifold.
  arXiv  Detail & Related papers  (2020-03-25T17:03:58Z)
• A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
  We propose a novel numerical scheme to optimize the gradient flows for learning energy-based models (EBMs) We derive a second-order Wasserstein gradient flow of the global relative entropy from Fokker-Planck equation. Compared with existing schemes, Wasserstein gradient flow is a smoother and near-optimal numerical scheme to approximate real data densities.
  arXiv  Detail & Related papers  (2019-10-31T02:26:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.