Search

We study gradient drift-diffusion processes on a probability simplex set with finite state Wasserstein metrics, namely the Wasserstein common noise. A fact is that the Kolmogorov transition equation of finite reversible Markov jump processes forms the gradient flow of entropy in finite state Wasserstein space. This paper proposes to perturb finite state Markov jump processes with Wasserstein common noises and formulate stochastic reversible Markov jumping processes. We also define a Wasserstein Q-matrix for this stochastic Markov jumping process. We then derive the functional Fokker-Planck equation in probability simplex, whose stationary distribution is a Gibbs distribution of entropy functional in a simplex set. Finally, we present several examples of Wasserstein drift-diffusion processes on a two-point state space., Correct some typos

We propose an easy-to-implement iterative method for resolving the implicit (or semi-implicit) schemes arising in solving reaction-diffusion (RD) type equations. We formulate the nonlinear time implicit scheme as a min-max saddle point problem and then apply the primal-dual hybrid gradient (PDHG) method. Suitable precondition matrices are applied to the PDHG method to accelerate the convergence of algorithms under different circumstances. Furthermore, our method is applicable to various discrete numerical schemes with high flexibility. From various numerical examples tested in this paper, the proposed method converges properly and can efficiently produce numerical solutions with sufficient accuracy., Any feedbacks or comments are welcome

Mean-field games (MFGs) have shown strong modeling capabilities for large systems in various fields, driving growth in computational methods for mean-field game problems. However, high order methods have not been thoroughly investigated. In this work, we explore applying general high-order numerical schemes with finite element methods in the space-time domain for computing the optimal transport (OT), mean-field planning (MFP), and MFG problems. We conduct several experiments to validate the convergence rate of the high order method numerically. Those numerical experiments also demonstrate the efficiency and effectiveness of our approach.

We formulate a free probabilistic analog of the Wasserstein manifold on $\mathbb{R}^d$ (the formal Riemannian manifold of smooth probability densities on $\mathbb{R}^d$), and we use it to study smooth non-commutative transport of measure. The points of the free Wasserstein manifold $\mathscr{W}(\mathbb{R}^{*d})$ are smooth tracial non-commutative functions $V$ with quadratic growth at $\infty$, which correspond to minus the log-density in the classical setting. The space of smooth tracial non-commutative functions used here is a new one whose definition and basic properties we develop in the paper; they are scalar-valued functions of self-adjoint $d$-tuples from arbitrary tracial von Neumann algebras that can be approximated by trace polynomials. The space of non-commutative diffeomorphisms $\mathscr{D}(\mathbb{R}^{*d})$ acts on $\mathscr{W}(\mathbb{R}^{*d})$ by transport, and the basic relationship between tangent vectors for $\mathscr{D}(\mathbb{R}^{*d})$ and tangent vectors for $\mathscr{W}(\mathbb{R}^{*d})$ is described using the Laplacian $L_V$ associated to $V$ and its pseudo-inverse $\Psi_V$ (when defined). Following similar arguments to arXiv:1204.2182, arXiv:1701.00132, and arXiv:1906.10051 in the new setting, we give a rigorous proof for the existence of smooth transport along any path $t \mapsto V_t$ when $V$ is sufficiently close $(1/2) \sum_j \operatorname{tr}(x_j^2)$, as well as smooth triangular transport., Comment: 134 pages, revised

We study a class of regularized proximal operators in Wasserstein-2 space. We derive their solutions by kernel integration formulas. We obtain the Wasserstein proximal operator using a pair of forward-backward partial differential equations consisting of a continuity equation and a Hamilton-Jacobi equation with a terminal time potential function and an initial time density function. We regularize the PDE pair by adding forward and backward Laplacian operators. We apply Hopf-Cole type transformations to rewrite these regularized PDE pairs into forward-backward heat equations. We then use the fundamental solution of the heat equation to represent the regularized Wasserstein proximal with kernel integral formulas. Numerical examples show the effectiveness of kernel formulas in approximating the Wasserstein proximal operator.

We design and compute a class of optimal control problems for reaction-diffusion systems. They form mean field control problems related to multi-density reaction-diffusion systems. To solve proposed optimal control problems numerically, we first apply high-order finite element methods to discretize the space-time domain and then solve the optimal control problem using augmented Lagrangian methods (ALG2). Numerical examples, including generalized optimal transport and mean field control problems between Gaussian distributions and image densities, demonstrate the effectiveness of the proposed modeling and computational methods for mean field control problems involving reaction-diffusion equations/systems., Comment: 40 pages, 12 figures

We design and compute first-order implicit-in-time variational schemes with high-order spatial discretization for initial value gradient flows in generalized optimal transport metric spaces. We first review some examples of gradient flows in generalized optimal transport spaces from the Onsager principle. We then use a one-step time relaxation optimization problem for time-implicit schemes, namely generalized Jordan-Kinderlehrer-Otto schemes. Their minimizing systems satisfy implicit-in-time schemes for initial value gradient flows with first-order time accuracy. We adopt the first-order optimization scheme ALG2 (Augmented Lagrangian method) and high-order finite element methods in spatial discretization to compute the one-step optimization problem. This allows us to derive the implicit-in-time update of initial value gradient flows iteratively. We remark that the iteration in ALG2 has a simple-to-implement point-wise update based on optimal transport and Onsager's activation functions. The proposed method is unconditionally stable for convex cases. Numerical examples are presented to demonstrate the effectiveness of the methods in two-dimensional PDEs, including Wasserstein gradient flows, Fisher--Kolmogorov-Petrovskii-Piskunov equation, and two and four species reversible reaction-diffusion systems.

We construct a new Markov chain Monte Carlo method on finite states with optimal choices of acceptance-rejection ratio functions. We prove that the constructed continuous time Markov jumping process has a global in-time convergence rate in $L^1$ distance. The convergence rate is no less than one-half and is independent of the target distribution. For example, our method recovers the Metropolis-Hastings algorithm on a two-point state. And it forms a new algorithm for sampling general target distributions. Numerical examples are presented to demonstrate the effectiveness of the proposed algorithm.

In finite-dimensions, minimal surfaces that fill in the space delineated by closed curves and have minimal area arose naturally in classical physics in several contexts. No such concept seems readily available in infinite dimensions. The present work is motivated by the need for precisely such a concept that would allow natural coordinates for a surface with a boundary of a closed curve in the Wasserstein space of probability distributions (space of distributions with finite second moments). The need for such a concept arose recently in stochastic thermodynamics, where the Wasserstein length in the space of thermodynamic states quantifies dissipation while area integrals (albeit, presented in a special finite-dimensional parameter setting) relate to useful work being extracted. Our goal in this work is to introduce the concept of a minimal surface and explore options for a suitable construction. To this end, we introduce the basic mathematical problem and develop two alternative formulations. Specifically, we cast the problem as a two-parameter Benamou-Breiner type minimization problem and derive a minimal surface equation in the form of a set of two-parameter partial differential equations. Several explicit solutions for minimal surface equations in Wasserstein spaces are presented. These are cast in terms of covariance matrices in Gaussian distributions.

The computation of Wasserstein gradient direction is essential for posterior sampling problems and scientific computing. The approximation of the Wasserstein gradient with finite samples requires solving a variational problem. We study the variational problem in the family of two-layer networks with squared-ReLU activations, towards which we derive a semi-definite programming (SDP) relaxation. This SDP can be viewed as an approximation of the Wasserstein gradient in a broader function family including two-layer networks. By solving the convex SDP, we obtain the optimal approximation of the Wasserstein gradient direction in this class of functions. Numerical experiments including PDE-constrained Bayesian inference and parameter estimation in COVID-19 modeling demonstrate the effectiveness of the proposed method.

One of a classical synchronization model is the Kuramoto model. We propose both first and second order Kuramoto dynamical models on graphs using discrete optimal transport dynamics. We analyze the synchronization behaviors for some examples of Kuramoto models on graphs. We also provide a generalized Hopf-Cole transformation for discrete optimal transport systems. Focus on the two points graph, we derive analytical formulas of the Kuramoto dynamics with various potential induced from entropy functionals. Several numerical examples for the Kuramoto model on general graphs are presented.

We formulate a class of mean field games on a finite state space with variational principles resembling continuous state mean field games. We construct a controlled continuity equation with a nonlinear activation function on graphs induced by finite reversible Markov chains. With this controlled dynamics on graph and the dynamic programming principle for value function, we derive the mean field game systems, the functional Hamilton-Jacobi equations and the master equations on the finite probability space for potential mean field games. We also give a variational derivation for the master equations of non-potential games and mixed games on a finite state space. Finally, several concrete examples of discrete mean field game dynamics on a two-point space are presented with closed formula solutions, including discrete Wasserstein distances, mean field planning, and potential mean field games., Comment: 39 pages

We derive mean-field information Hessian matrices on finite graphs. The "information" refers to entropy functions on the probability simplex. And the "mean-field" means nonlinear weight functions of probabilities supported on graphs. These two concepts define a mean-field optimal transport type metric. In this metric space, we first derive Hessian matrices of energies on graphs, including linear, interaction energies, entropies. We name their smallest eigenvalues as mean-field Ricci curvature bounds on graphs. We next provide examples on two-point spaces and graph products. We last present several applications of the proposed matrices. E.g., we prove discrete Costa's entropy power inequalities on a two-point space.

We formulate closed-form Hessian distances of information entropies in one-dimensional probability density space embedded with the L2-Wasserstein metric.

We study the Lyapunov convergence analysis for degenerate and non-reversible stochastic differential equations (SDEs). We apply the Lyapunov method to the Fokker-Planck equation, in which the Lyapunov functional is chosen as a weighted relative Fisher information functional. We derive a structure condition and formulate the Lypapunov constant explicitly. Given the positive Lypapunov constant, we prove the exponential convergence result for the probability density function towards its invariant distribution in the $L_1$ norm. Two examples are presented: underdamped Langevin dynamics with variable diffusion matrices and three oscillator chain models with nearest-neighbor couplings., Comment: Examples added. Typos corrected. 46 pages, 4 figures

In this paper, we propose an efficient and flexible algorithm to solve dynamic mean-field planning problems based on an accelerated proximal gradient method. Besides an easy-to-implement gradient descent step in this algorithm, a crucial projection step becomes solving an elliptic equation whose solution can be obtained by conventional methods efficiently. By induction on iterations used in the algorithm, we theoretically show that the proposed discrete solution converges to the underlying continuous solution as the grid size increases. Furthermore, we generalize our algorithm to mean-field game problems and accelerate it using multilevel and multigrid strategies. We conduct comprehensive numerical experiments to confirm the convergence analysis of the proposed algorithm, to show its efficiency and mass preservation property by comparing it with state-of-the-art methods, and to illustrates its flexibility for handling various mean-field variational problems., Comment: 38 pages, 9 figures

We introduce a framework for Newton's flows in probability space with information metrics, named information Newton's flows. Here two information metrics are considered, including both the Fisher-Rao metric and the Wasserstein-2 metric. A known fact is that overdamped Langevin dynamics correspond to Wasserstein gradient flows of Kullback-Leibler (KL) divergence. Extending this fact to Wasserstein Newton's flows, we derive Newton's Langevin dynamics. We provide examples of Newton's Langevin dynamics in both one-dimensional space and Gaussian families. For the numerical implementation, we design sampling efficient variational methods in affine models and reproducing kernel Hilbert space (RKHS) to approximate Wasserstein Newton's directions. We also establish convergence results of the proposed information Newton's method with approximated directions. Several numerical examples from Bayesian sampling problems are shown to demonstrate the effectiveness of the proposed method., 62 pages

We formulate explicit bounds to guarantee the exponential dissipation for some non-gradient stochastic differential equations towards their invariant distributions. Our method extends the connection between Gamma calculus and Hessian operators in $L^2$--Wasserstein space. In details, we apply Lyapunov methods in the space of probabilities, where the Lyapunov functional is chosen as the relative Fisher information. We derive the Fisher information induced Gamma calculus to handle non-gradient drift vector fields. We obtain the explicit dissipation bound in terms of $L_1$ distance and formulate the non-reversible Poincar{\'e} inequality. An analytical example is provided for a non-reversible Langevin dynamic.

We introduce a novel framework to model and solve mean-field game systems with nonlocal interactions. Our approach relies on kernel-based representations of mean-field interactions and feature-space expansions in the spirit of kernel methods in machine learning. We demonstrate the flexibility of our approach by modeling various interaction scenarios between agents. Additionally, our method yields a computationally efficient saddle-point reformulation of the original problem that is amenable to state-of-the-art convex optimization methods such as the primal-dual hybrid gradient method (PDHG). We also discuss potential applications of our methods to multi-agent trajectory planning problems.

We derive sub-Riemannian Ricci curvature tensor for sub-Riemannian manifolds. We provide examples including the Heisenberg group, displacement group, and Martinet sub-Riemannian structure with arbitrary weighted volumes, in which we establish analytical bounds for sub-Riemannian curvature dimension bounds and log-Sobolev inequalities. {These bounds can be used to establish the entropy dissipation results for sub-Riemannian drift diffusion processes on a compact spatial domain, in term of $L_1$ distance.} Our derivation of Ricci curvature is based on generalized Gamma $z$ calculus and $z$--Bochner's formula, where $z$ stands for extra directions introduced into the sub-Riemannian degenerate structure., Comment: Typos corrected. This version is combined to arXiv:1910.07480. arXiv admin note: substantial text overlap with arXiv:1910.07480

We derive the Fokker-Planck equation on the parametric space. It is the Wasserstein gradient flow of relative entropy on the statistical manifold. We pull back the PDE to a finite dimensional ODE on parameter space. Some analytical example and numerical examples are presented.

We propose dynamical optimal transport (OT) problems constrained in a parameterized probability subset. In application problems such as deep learning, the probability distribution is often generated by a parameterized mapping function. In this case, we derive a simple formulation for the constrained dynamical OT.

We formulate the Riemannian calculus of the probability set embedded with $L^2$-Wasserstein metric. This is an initial work of transport information geometry. Our investigation starts with the probability simplex (probability manifold) supported on vertices of a finite graph. The main idea is to embed the probability manifold as a submanifold of the positive measure space with a nonlinear metric tensor. Here the nonlinearity comes from the linear weighted Laplacian operator. By this viewpoint, we establish torsion-free Christoffel symbols, Levi-Civita connections, curvature tensors and volume forms in the probability manifold by Euclidean coordinates. As a consequence, the Jacobi equation, Laplace-Beltrami and Hessian operators on the probability manifold are derived. These geometric computations are also provided in the infinite-dimensional density space (density manifold) supported on a finite-dimensional manifold. In particular, an identity is given connecting the Baker-{\'E}mery $\Gamma_2$ operator (carr{\'e} du champ it{\'e}r{\'e}) by connecting Fisher-Rao information metric and optimal transport metric. Several examples are demonstrated., Comment: This draft is the revision of previous paper: "Geometry of probability simplex via optimal transport"

We design fast numerical methods for Hamilton-Jacobi equations in density space (HJD), which arises in optimal transport and mean field games. We overcome the curse-of-infinite-dimensionality nature of HJD by proposing a generalized Hopf formula in density space. The formula transfers optimal control problems in density space, which are constrained minimizations supported on both spatial and time variables, to optimization problems over only spatial variables. This transformation allows us to compute HJD efficiently via multi-level approaches and coordinate descent methods.

We endow the set of probability measures on a weighted graph with a Monge--Kantorovich metric, induced by a function defined on the set of vertices. The graph is assumed to have $n$ vertices and so, the boundary of the probability simplex is an affine $(n-2)$--chain. Characterizing the geodesics of minimal length which may intersect the boundary, is a challenge we overcome even when the endpoints of the geodesics don't share the same connected components. It is our hope that this work would be a preamble to the theory of Mean Field Games on graphs., 31 Pages

We propose a new semi-discretization scheme to approximate nonlinear Fokker-Planck equations, by exploiting the gradient flow structures with respect to the 2-Wasserstein metric. We discretize the underlying state by a finite graph and define a discrete 2-Wasserstein metric. Based on such metric, we introduce a dynamical system, which is a gradient flow of the discrete free energy. We prove that the new scheme maintains dissipativity of the free energy and converges to a discrete Gibbs measure at exponential (dissipation) rate. We exhibit these properties on several numerical examples.

We propose a new algorithm to approximate the Earth Mover's distance (EMD). Our main idea is motivated by the theory of optimal transport, in which EMD can be reformulated as a familiar $L_1$ type minimization. We use a regularization which gives us a unique solution for this $L_1$ type problem. The new regularized minimization is very similar to problems which have been solved in the fields of compressed sensing and image processing, where several fast methods are available. In this paper, we adopt a primal-dual algorithm designed there, which uses very simple updates at each iteration and is shown to converge very rapidly. Several numerical examples are provided.