Kantorovich Initiative: KI-Retreat in Spring

Thursday, March 12

9:30 am: Start

9:30 am - 10:30 am: Nassif Ghoussoub (University of British Columbia)

Title: Skew-linear entropies, Kantorovich operators and their ergodic theory

Abstract: Kantorovich operators are non-linear extensions of Markov operators and are as omnipresent in potential theory, probability theory, ergodic theory, control theory, and Hamiltonian dynamics. They are closely related to various notions of non-linear analysis: Choquet functional capacities, pressure operators, monetary risk measures and maximal gains in gambling houses. They are in duality with skew-linear entropies which appear whenever we have a scheme that relate, compare, or transport a probability distribution to  another: Balayage, optimal stopping, mass transport, and stochastic control. Repeated iterations (resp., convolutions) of Kantorovich operators (resp., skew-linear entropies) lead to generalized versions of weak KAM (resp., Mather) theory, which originate in Hamiltonian mechanics. This talk consists of an overview of these notions, which can be considered as the building blocks of contemporary non-linear analysis.  

10:30 am - 10:50 am: Discussion

10:50 am - 11:40 am: Ja Kwang KIM (Chinese University of Hong Kong)

Title:  Extension of coupling via the Projection of Optimal Transport

Abstract: We study the extension of coupling via the projection of optimal transport. In reality, for several practical reasons, coupled data is usually more expansive to collect than decoupled marginal ones. However, it is valid that decoupled marginal data also contain meaningful information. We propose the fully nonparametric estimator to recover the coupling among the large amount of decoupled marginal data using the small amount of given coupled data. The estimator is a solution for the optimal transport projection over the space of probability measures. Not only is its stability established, but its sample complexity is also derived using recent advances in statistical optimal transport. In addition to this, we present the explicit formula of it based on shadow. Furthermore, introducing entropic shadow, the estimator can be approximated in almost linear time and in parallel, which verifies the practical strength of our method. We also present experiments with real and synthetic data to justify the performance of our method.

11:40 am - 11:50 am: Break

11:50 am - 12:25 pm: Garret Mulcahy (University of Washington)

Title: Diffusion Approximation to Schrödinger Bridges

Abstract: We present a collection of explicit diffusion approximations to small temperature Schrödinger bridges on manifolds. Our most precise results are when both marginals are the same and the Schrödinger bridge is on a manifold with a reference process given by a reversible diffusion. In the special case that the reference process is the manifold Brownian motion, we show that the gradient of the corresponding Schrödinger potential converges, as the temperature vanishes, to a manifold analogue of the score function of the marginal. Joint work with Soumik Pal.

12:25 pm - 2:00 pm: Lunch

2:00 pm - 2:35 pm: Rentian Yao (University of British Columbia)

Title: From Snapshots to Dynamics: An Optimal Transport Approach

Abstract: Many modern datasets capture populations only at isolated time points, leaving us with snapshots rather than continuous trajectories. How can we reconstruct the underlying dynamics from such partial views? In this talk, I will present a series of projects that use entropic optimal transport (EOT) as a framework for connecting snapshots into dynamic flows. EOT provides a principled way to interpolate between distributions, supporting both the study of density evolution and the design of trajectory inference methods. These results highlight new possibilities for dynamic data analysis and suggest broad directions at the interface of statistics, computation, and scientific machine learning.

2:35 pm - 3:00 pm: Discussion

3:00 pm - 3:35 pm: Michele Martino (University of Washington)

Title: Error Analysis of Triangular Optimal Transport Maps for Filtering

Abstract: We present a systematic analysis of estimation errors for a class of optimal transport based algorithms for filtering and data assimilation. Along the way, we extend previous error analyses of Brenier maps to the case of conditional Brenier maps that arise in the context of simulation based inference. We then apply these results in a filtering scenario to analyze the optimal transport filtering (OTF) algorithm. An extension of that algorithm along with numerical benchmarks on various non-Gaussian and high-dimensional examples are provided to demonstrate its effectiveness and practical potential.

3:35 pm - 4:00 pm: Discussion

4:00 pm - 5:00 pm: Benjamin Bloem-Reddy (University of British Columbia)

Title: Measure transport in causal modelling and inference: an overview and some open problems

Abstract: Many problems in causal modelling may be framed in terms of measure transport, and there is an ongoing effort to understand how known families of transports behave as causal models, as well as the statistical properties of estimating them from data. I will give an overview of some of those problems, and highlight recent and ongoing work in my research group, in which we have begun to develop a framework for transport-based causal modelling and inference. In the process of developing that framework and corresponding statistical methods, we have uncovered a number of interesting connections between the causal inference literature and the theory of measure transport, as well as some challenging problems.  

5:00 pm - 5:10 pm: Break

5:10 pm - 5:45 pm: Forest Kobayashi (University of Utah)

Title: Topology of Average Distance Minimizers

Abstract: Suppose one has been tasked with designing a network Σ of water pipes for a city in which demand is distributed according to a probability measure μ and the cost of construction is proportional to the total length 𝓗¹(Σ). Then, given a fixed budget ℓ (and a functional quantifying Σ's "approximation performance" via the average p-th power distance from μ to Σ), what can one say about the optimal network shape Σ*?

Naturally, many of the precise geometric properties of Σ* will depend on those of μ. However, for coarser information (e.g. topological properties), one might expect to obtain general results. Indeed, this is the case. In 2003, Buttazzo and Stepanov showed that in ℝ², with certain regularity hypotheses on μ, Σ* must be a finite, binary tree. Subsequent works by Paolini and Stepanov in 2004 and 2006 showed (under weaker regularity hypotheses and in ℝⁿ rather than ℝ²) that Σ* must be a tree. However, the questions of finiteness and binariness remained open thereafter.

In this talk we discuss our resolution to this problem via variational tools developed by two of the authors in a previous work on principal curves. In particular, our result shows that under the same regularity hypotheses as Stepanov's 2006 work, for most values of p ≥ 2, Σ* must be a finite, binary tree.

Joint work with Lucas O'Brien (MIT) and Young-Heon Kim (UBC).

6:30 pm - 9:00 pm: Retreat dinner on campus 

Browns Crafthouse UBC (6111 University Blvd #101)

Friday, March 13

9:30 am: Start

9:30 am - 10:05 am: Andrew Warren  (University of British Columbia)

Title: Finite-sample analysis for principal curves and surfaces

Abstract: Principal curves and surfaces offer a definition of the "middle" of a data distribution and can be interpreted as providing the continuum limit for certain manifold learning algorithms. They also carry an interpretation as "free target" OT problems. In this talk, I will discuss work in progress regarding quantitative rates of convergence when one only has a finite number of iid data from the distribution, rather than the whole distribution itself.

10:05 am - 10:15 am: Break

10:15 am - 10:50 am: Danir Omarov (University of Alberta)

Title: Optimal Trajectories for Optimal Transport Problem in Nonuniform Environments

Abstract: We address discrete optimal transport problem in spatially nonuniform media.Our method constructs the transport cost matrix by computing optimal point-to-point paths via Euler–Lagrange equations, then applies classical discrete OT solvers. We provide verifiable sufficient conditions for optimality and new a-posteriori algorithms to certify the computed costs. Results and performance are demonstrated on 2D and 3D examples.

10:50 am - 11:00 am: Break

11:00 am - 11:35 am: Alex Kokot (University of Washington)

Title: Coreset Selection for the Sinkhorn Divergence and Generic Smooth Divergences

Abstract: We introduce CO2, an efficient algorithm to produce convexly-weighted coresets with respect to generic smooth divergences. By utilizing a functional Taylor expansion, we show a local equivalence between sufficiently regular losses and their second order approximations, reducing the coreset selection problem to maximum mean discrepancy minimization. We apply CO2 to the Sinkhorn divergence, providing a novel sampling procedure that requires poly-logarithmically many data points to match the approximation guarantees of random sampling. To show this, we additionally verify several new regularity properties for entropically regularized optimal transport of independent interest. Our approach leads to a new perspective linking coreset selection and kernel quadrature to classical statistical methods such as moment and score matching. We showcase this method with a practical application of subsampling image data, and highlight key directions to explore for improved algorithmic efficiency and theoretical guarantees.

11:35 am - 11:50 am: Break

11:50 am - 12:25 pm: Omar Abdul Halim (University of Alberta)

Title: Multi-to -one dimensional and semi-discrete screening

Abstract: We study the monopolist's screening problem with a multi-dimensional distribution of consumers and a one-dimensional space of goods.  We establish general conditions under which solutions satisfy a structural condition known as nestedness, which greatly simplifies their analysis and characterization.  Under these assumptions, we go on to develop a general method to solve the problem, either in closed form or with relatively simple numerical computations, and illustrate it with examples.  These results are established both when the monopolist has access to only a discrete subset of the one-dimensional space of products, as well as when the entire continuum is available.

12:25 pm - 2:00 pm: Lunch

2:00 pm - 2:35 pm: William Dudarov (University of Washington)

Title: TBA

Abstract: TBA

2:35 pm - 3:00 pm: Discussion

3:00 pm - 3:35 pm: Sharvaj Kubal  (University of British Columbia)

Title: Average-case thresholds for exact regularization of linear programs

Abstract: Sometimes, regularization of a small enough strength does not change the solution of an optimization problem. This phenomenon, known as exact regularization, is particularly useful when one desires the computational benefits of regularization while still solving the original problem. We characterize the average-case behaviour of exact regularization in linear programming with probabilistic tools; given a linear program with a standard Gaussian cost vector and a convex regularizer, we provide bounds on the probability that exact regularization succeeds, in terms of the regularization strength.

Our bounds uncover dependence on the ambient dimension explicitly in certain problems, including (discrete) quadratically regularized optimal transport, and this is corroborated by numerical experiments. A key technical contribution which underlies these results is the quantification of the Gaussian measure of shifted cones.

3:35 pm - 3:40 pm: Break

3:40 pm - 4:10 pm: Clement Soubrier  (University of British Columbia)

Title: The multilinear Gromov-Wasserstein distance and its application to chiral shape comparison.

Abstract: In this talk we introduce a class of optimization problems generalizing the Gromov-Wasserstein distance to multilinear objectives. Under mild assumptions on the multilinear form chosen as cost, we obtain a distance on $\mathcal{P}_2(X)/G$, with $G$ a matrix Lie group. In particular for $G=SO(d)$, we introduce the Chiral Gromov Wasserstein distance. This distance has practical applications for shape comparison, e.g. in biology where the orientation of proteins and molecules  can affect their function. We also show that multilinear Gromov-Wasserstein optimization problems have a low dimensional structure, that we can leverage to compute local solutions and approximate global solutions. We finally state the convergence rate of our global optimization algorithm and go over numerical examples and applications. This is a joint work with Geoffrey Woollard, Andrew Warren and Khanh Dao Duc.

4:10 pm - 4:20 pm: Break

4:20 pm - 4:55 pm: Natalia Kravtsova  (University of British Columbia)

Title: Whole organism lineage tracing from bulk RNA-sequencing using Wasserstein barycenters

Abstract: Whole-organism lineage tracing in cell biology aims to infer how a complex living organism develops from a single parental cell. The main tool for this inference is the construction of a graph - a lineage tree - reflecting the relationships between cells in the organism of interest. While lineage trees for several smaller organisms have been documented in the literature, constructing a lineage tree for a mammal (even one as small as a mouse) remains out of reach due to the prohibitive cost of sequencing an entire organism at the single-cell level. In this work we propose an alternative approach that leverages an affordable experimental setup: bulk measurements on the whole organism combined with single-cell measurements on a small subset. We describe a method based on Wasserstein barycenters that combines information from these two types of experiments with the goal of constructing a lineage tree at a very large scale, and discuss the associated mathematical challenges. This is a joint work in progress with Elias Ventre, Rentian Yao, Nozomu Yachie, and Geoffrey Schiebinger.