Optimal Transport for Stationary Markov Chains

• Activity Number: 215 - Contributed Poster Presentations: Section on Statistical Learning and Data Science
• Type: Contributed
• Date/Time: Tuesday, August 4, 2020 : 10:00 AM to 2:00 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Kevin O'Connor* and Andrew Nobel and Kevin McGoff
• Companies: University of North Carolina, Chapel Hill and University of North Carolina, Chapel Hill and University of North Carolina, Charlotte
• Keywords: optimal transport; markov chains; entropic regularization; policy iteration; joinings

Abstract

Optimal transport has become an increasingly useful tool in data science and machine learning. Recent work has successfully applied transport-based techniques to a variety of tasks including modeling the growth of cell populations and generative adversarial networks. However, the standard formulation of the optimal transport problem can give misleading results when the marginal probability measures evolve dynamically through time. In this presentation, I discuss an extension of optimal transport to stationary Markov chains via optimal transition coupling. In the case when the marginal measures correspond to stationary Markov chains, we argue for the consideration of a constrained form of optimal transport that accounts for stationarity, Markovity, and computational tractability. We propose an algorithm for obtaining global solutions as well as a regularized algorithm that yields approximate solutions more rapidly. Furthermore, we address the case when the marginal Markov chains are only known through a finite number of observations. Finally, we demonstrate the use of these algorithms on synthetic and real data.