Gonzalo Mena (University of Oxford)

“On the unreasonable effectiveness of Sinkhorn algorithm for learning permutations and entropic optimal transport”

Abstract: Sinkhorn’s algorithm realizes the solution of entropy-regularized linear programs on certain matrix polytopes. In the past years, the interest in this algorithm has grown considerably because of its usefulness as a tool for the modeling of permutations, and because of its fundamental role in the solution of an entropic optimal transport problem, also called the Schrödinger bridge. In this talk, I will give an overview of my work in relation to these two areas.
First, regarding entropic optimal transport, I will argue that this tool is valuable for deriving sensible statistical procedures. Indeed, we show that it enjoys a substantially better sample complexity compared to optimal transport, which suffers from the curse of dimensionality. Also, in the more applied setup of model-based clustering we show that it can be used as an alternative to the log-likelihood, since it has fewer bad local optima. Based on this observation, we develop a new algorithm, Sinkhorn-EM, in which we only modify the E-step to solve an Entropic Optimal Transport problem. Our algorithm is shown to attain better practical performance.
Second, regarding permutations, I will describe some successful applications in Deep Learning, and in neuroscience, for the inference of neural identities in C.elegans worms.

Links
https://arxiv.org/abs/1802.08665
https://arxiv.org/abs/1905.11882
https://arxiv.org/abs/2006.16548