2024 Summer PIMS-CM2LA Kantorovich Initiative Retreat Meeting

Speaker list 

Titles and Abstracts

August 21st @9:00 am Beomjun Choi (POSTECH AI center)

Title: Łojasiewicz's theorem, gradient conjecture and Wasserstein gradient flow

Abstract: In the 1960s, Łojasiewicz established the celebrated theorem on the convergence of gradient flows of analytic potential functions. Since then, the key component of this theorem, the Łojasiewicz gradient inequality, has become fundamentally important in analyzing the global convergence of gradient descents and PDEs with gradient structure. In this talk, we will first review the theory and R. Thom’s gradient conjecture on the next-order asymptotics of convergence, which was later proven by Kurdyka-Mostowski-Parusinski.

We will then discuss its generalization to PDEs and Wasserstein gradient flows of non-convex functionals. This is based on joint work with P.-K. Hung and ongoing joint work with G. Seo.

August 21st @10:00 am Soumik Pal (U. Washington)

Title: Iterated Schroedinger bridge approximations to Wasserstein gradient flows

Abstract: The theory of Monge-Kantorovich optimal transport has become widely popular in various areas of mathematics and its applications. Part of this popularity is due to a regularized version of the problem with the entropy serving as a penalty function. The solution of this problem, called the Schrödinger bridge, is itself a mathematically interesting object. In this talk we will talk about some recent results on approximations of Wasserstein gradient flows with iterated entropy regularized optimal transport between the same marginal.  

August 21st @11:00 am Luca Nenna (Paris-Saclay Univerity)

Title: Sticky-Schrödinger problem: from Large Deviation principle to JKO scheme

Abstract: In this talk we consider the Sticky-Schrödinger problem, namely the minimisation of a relative entropy with respect to the sticky Brownian motion under marginal constraints. Roughly speaking the sticky brownian process is a stochastic process which behaves as a standard diffusions in the interior of the prescribed domain and when it hints the boundary it sticks following an intrinsic tangential diffusion. We carefully derive a large variation principle and identify the limit functional which turns out to be an Optimal Transport problem (OT) with a given cost $d_\nu$ , where $\nu$ is the tangential viscosity. Moreover this OT problem defines a distance between probability measures and in the special case of $d_{\infty}$ we study the associated JKO scheme. This talk is based on joint works with Jean-Baptiste Casteras and Léonard Monsaigeon.

August 21st @12:00 pm  Namkyeong Cho (POSTECH AI center)

Title: Neural Network Approximations for Solving Fractional Schrödinger Equations

Abstract: Recently, various approaches have been proposed to solve partial differential equations using machine learning. In this work, we consider Schrödinger equations in the whole space driven by fractional operators. The fractional operator is the infinitesimal generator of a (rotationally) symmetric 2s-stable Lévy process, which is gaining significant attention due to its unique non-local properties in pure mathematics and its applications in describing nonlocal phenomena in physics. In particular, Schrödinger equations have recently seen advancements in computational material science and quantum chemistry. We provide theoretical evidence that the solution to nonlocal Schrödinger equations does not suffer from the curse of dimensionality by demonstrating regularity estimates in Barron space.

August 21st @1:40 pm Khanh Dao Duc (UBC)

Title: Mathematics of 3D reconstruction and model building in Cryo-EM: Challenges and opportunities for OT and machine learning

Abstract: Cryogenic Electron Microscopy is a powerful technique for imaging biomolecules, unlocking promising applications for drug discovery. Upon introducing the various mathematical aspects of the workflow for reconstructing 3D atomic structures, I will then focus on our recent efforts to improve and automate the process of building atomic models from 3D density maps. This work more specifically leverages OT metrics and algorithms to register and align 3D maps, as well as generative AI models to improve simulations of 3D density maps and fit atomic models, suggesting potential applications of OT and machine learning for improving Cryo-EM pipelines.

August 21st @3:00 pm Daniyar Omarov (UAlberta)

Title: Solving Semi-Discrete Optimal Transport Problems: Star-shapedeness and Newton's method

Abstract: In my presentation, I will propose a novel implementation of Newton's method for solving semi-discrete optimal transport (OT) problems for cost functions which are a positive combination of $p$-norms, $1<p<\infty$. It is well understood that the solution of a semi-discrete OT problem is equivalent to finding a partition of a bounded region in Laguerre cells, and I will show that the Laguerre cells are star-shaped with respect to the target points. By exploiting the geometry of the Laguerre cells, I will obtain an efficient and reliable implementation of Newton's method to find the sought network structure. I will provide implementation details and extensive results in support of the technique in 2-d problems, as well as comparison with other approaches used in the literature.

August 21st @3:40 pm Andrew Warren (UBC)

Title: Nonlocal limits of heat flows on graphs

Abstract: The heat equation on graphs has been identified as the gradient flow of the relative entropy with respect to a "graph Wasserstein distance". Furthermore, for certain classes of graphs that converge in the Gromov-Hausdorff sense to a Euclidean domain, it is known (thanks to results of Gigli-Maas and Garcia Trillos) that the associated heat equations on these graphs converge, in the evolutionary Gamma-convergence sense, to the heat equation on a Euclidean domain. Conversely, in this work, we identify a class of sequences of graphs which converge in Gromov-Hausdorff sense to Borel graphs embedded in Euclidean space, and for which the evolutionary Gamma-limit of the associated heat equations is instead a certain nonlocal diffusion equation.

August 22nd @9:20 am Jakwang Kim (UBC)

Title: Optimal allocation in single-cell RNA sequencing: balancing between deep and shallow sequencing

Abstract: In this work, we investigate optimal allocation rule of reads of single-cell RNA sequencing experiments. Thanks to the advance of single-cell RNA sequencing machinery, people have understood variety aspects of cell populations. In particular, to understand the distribution of gene expressions of cell population under the restricted budget of reads, it has been an important consideration for biologists both theoretically and practically to decide whether to inspect a few cells in detail or to explore many cells roughly. Often described as deep sequencing versus shallow sequencing, many researchers have tried to resolve this controversy and provide an optimal allocation rule of the measurements to achieve the best approximation of the true distribution of gene expression in population level under certain assumptions. Here, we establish the theory of the optimal allocation rule with full generality, which guarantees that a proposed empirical distribution is close to the true one in Wasserstein distance with high probability. Furthermore, we propose an empirical analysis of real data set which strongly supports our theoretical results.

August 22nd @10:00 am Rentian Yao (UBC)

Title: Fast Trajectory Inference via Coordinate KL Divergence Gradient Descent

Abstract: This paper concerns the trajectory inference problem, which aims to reconstruct the path measure of a drift-diffusion process from temporal marginal snapshots. Building on the consistent M-estimator based on the min-entropy principle proposed by Lavenant et al.(2021), we provide a non-asymptotic rate of convergence analysis. While Chizat et al.(2022) proposed a grid-free algorithm using mean-field Langevin dynamics requiring exponential iterations, we introduce a novel grid-free algorithm based on coordinate KL-divergence gradient descent. Our method achieves comparable accuracy with only polynomial iterations, significantly improving computational efficiency. This work enhances both the theoretical understanding and practical implementation of trajectory inference for recovering continuous-time dynamics from discrete observations.

August 22nd @11:00 am Forest Kobayashi (UBC)

Title: Monge-Kantorovich Fitting Under a Sobolev Budget

Abstract: Given a measure rho with n-dimensional support, how can we best “approximate” rho via an m-dimensional set (m < n)? When m=1 this is essentially the (Euclidean) “principal curve” problem; there, the approximating set is defined as the image of a curve f : [0,1] -> R^n. In order to ensure we don’t “cheat” by taking f to be space-filling it is necessary to add some method of controlling the complexity of f; a straightforward approach is to bound the arc length ||f’||_{L^1} above by a constant L.

We introduce a similar problem for general m < n in which the arc length ||f’||_{L^1} is replaced by a Sobolev norm ||f||_{W^{k,q}}. This allows us to add control over the higher-order derivatives of f, which is desirable in some real-world applications such as routing problems. However, the severe parametrization-dependence of ||f||_{W^{k,q}} also adds many theoretical challenges that are not present in the arc length case. We discuss some of these challenges and the approaches we take to work around them; in particular we discuss a ``gradient'' of the objective that (on the theory side) can be used to obtain smooth local improvements, and (in numerical contexts) admits a highly-efficient discrete approximation when the target measure is uniform.

Joint work with Young-Heon Kim (University of British Columbia) and Jonathan Hayase (University of Washington)

August 22nd @11:40 am Jiajin Li (UBC)

Title: Trade-off among Infeasibility, Efficiency and Accuracy for Gromov-Wasserstein Computation 

Abstract: In this talk, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition, two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) enjoy the convergence guarantees. Upon task-specific properties, our analysis further provides novel theoretical insights to guide how to select the best-fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.

August 22nd @1:40 pm Jinwoo Jang (POSTECH AI center)

Title: Asymptotic Stability of Vacuum for the 3D Vlasov-Maxwell system in $\mathbb{T}^2\times \mathbb{R}_+$

Abstract: In this talk, I will introduce a recent proof of the asymptotic stability of the vacuum state for the 3-dimensional Vlasov-Maxwell system in $\mathbb{T}^2 \times \mathbb{R}_+$. The self-consistent electromagnetic fields follow the Maxwell equations, which are equivalent to the 3D inhomogeneous wave equations in $\mathbb{T}^2 \times \mathbb{R}_+$ given the continuity equations for the inhomogeneity terms. The main difficulties arise from the lack of dimensions for the dispersion of waves in $\mathbb{T}^2 \times \mathbb{R}_+$ compared to those in $\mathbb{R}^3$. We assume inflow boundary conditions at $x_3 = 0$ and prove the global-in-time well-posedness of classical solutions and the asymptotic stability of the vacuum. The initial velocity distribution profile does not need to be small in $L^\infty$; we only assume that its energy density is exponentially decaying in $x_3$. This is a joint work with Chanwoo Kim at the University of Wisconsin-Madison.

August 22nd @3:00 pm Yeoneung Kim (POSTECH AI center)

Title: Approximate Thompson Sampling for Learning Linear Quadratic Regulators with $O(\sqrt{T})$ Regret

Abstract: We propose an approximate Thompson sampling algorithm that learns linear quadratic regulators (LQR) with an improved Bayesian regret bound of $O(\sqrt{T})$. Our method leverages Langevin dynamics with a meticulously designed preconditioner as well as a simple excitation mechanism. We show that the excitation signal induces the minimum eigenvalue of the preconditioner to grow over time, thereby accelerating the approximate posterior sampling process. Moreover, we identify nontrivial concentration properties of the approximate posteriors generated by our algorithm. These properties enable us to bound the moments of the system state and attain an $O(\sqrt{T})$ regret bound without the unrealistic restrictive assumptions on parameter sets that are often used in the literature.

August 22nd @3:40 pm Wenjun Zhao (UBC)

Title: Wasserstein metric for pattern statistics and its application to bifurcation tracing

Abstract: Tracing the transition curves for reaction-diffusion systems is an interesting question that arises in various applications. In this talk, we will discuss a framework to quantify patterns via alpha-shape statistics, utilizing the Wasserstein metric to quantify the differences between such statistics corresponding to different parameter values. The framework is then incorporated within a continuation algorithm that can trace transitions in a 2D parameter space. Notably, the algorithm is completely data-driven and requires limited prior knowledge about the underlying system. Finally, we will demonstrate our algorithm on examples on Turing patterns. This talk is based on joint work with Bjorn Sandstede (Brown University) and Sam Maffa (Broad Institute of MIT and Harvard). 

August 22nd @4:20 pm Geuntaek Seo (POSTECH AI center)

Title: Geometry of minimizers of the free energy functional

Abstract: In this talk, I will discuss the geometry of the minimizers for certain free energy functional. Aggregation-diffusion equations have been extensively studied in biological and physical modeling to describe the repulsion and attraction of masses. From the gradient flow structure of these equations, there is a close relationship between the stationary solutions and the minimizers of the free energy functional.  

As shown by Lim and McCann [Arch Rational Mech Anal 241, (2021), pp. 553-576], the minimizers of the interaction energy with certain mildly repulsive potentials are equi-distributed on $\Delta^n$, the vertices of the $n$-simplex. We employ the technique of $\Gamma$-convergence to show that the minimizers of the free energy functional are compactly supported near $\Delta^n$ when the diffusion effect corresponds to the porous medium diffusion.

August 23rd @9:20 am Donghyun Lee (POSTECH AI center)

Title: Ill-posedness of Boltzmann-BGK model in exponential class 

Abstract: We prove that the solution map of the BGK model of the Boltzmann equation instantly blows up in the class of exponentially decaying functions. For this, we show that the relaxation operator of the BGK model is not a bounded operator between such exponential function class, by constructing an explicit sequence of functions which is bounded in the exponential class but the local Maxwellian constructed from it blows up in the same class. This poses a stark contrast with the Boltzmann equation for which the solution map is, at least for a finite time, stable. This is a joint work with Sung Bin Park and Seok-Bae Yun. 

August 23rd @10:00 am Kyeongsu Choi  (POSTECH AI center)

Title: Efficient escape from saddle points by gradient flow of surfaces

Abstract: Gradient descent can be trapped in saddle points and may take so long to escape. So, one needs to perturb initial data to bypass saddle points efficiently. As a gradient flow of hypersurfaces, the mean curvature flow can be trapped in saddle points as well. In particular, it is even possible to converge a saddle point, so called unstable self-similarly shrinking flow, where one can not see how the topology of the hypersurface changes. Hence, we need to perturb the initial hypersurface in order to let the flow only develop stable singularities, where its blow-ups are spheres and cylinders. In this talk, we discuss how to perturb the initial hypersurface of the mean curvature flow when it develops non-spherical or non-cylindrical singularity. 

August 23rd @11:00 am Brendan Pass (UAlberta )

Title: An ODE characterization of regularized optimal transport and variants with linear constraints.

Abstract: I will discuss various joint works with Luca Nenna and PhD student Joshua Hiew. We show that entropically regularized optimal transport with discrete marginals and general cost functions can be characterized by a well-posed ordinary differential equation.   The techniques adapt easily to a wide range of variants of optimal transport, with additional linear constraints, including multi-marginal optimal transport and martingale optimal transport.  For all of these problems, the ODE can be solved by standard schemes, yielding a new computational method.  This method has the advantage of simultaneously yielding the solution for all values of the regularization parameter.