Sparsistency guarantees for inverse optimal transport

Title

Sparsistency guarantees for inverse optimal transport

Speaker

Clarice Poon - University of Warwick

Abstract

Optimal Transport is a useful metric to compare probability distributions and to compute a pairing given a ground cost. Its entropic regularization variant (eOT) is crucial to have fast algorithms and reflect fuzzy/noisy matchings. This work focuses on Inverse Optimal Transport (iOT), the problem of inferring the ground cost from samples drawn from a coupling that solves an eOT problem. It is a relevant problem that can be used to infer unobserved/missing links, and to obtain meaningful information about the structure of the ground cost yielding the pairing. This work presents an in-depth theoretical study of the l1 regularization to model for instance Euclidean costs with sparse interactions between features. Specifically, we derive a sufficient condition for the robust recovery of the sparsity of the ground cost that can be seen as a far reaching generalization of the Lasso’s celebrated "Irrepresentability Condition". To provide additional insight into this condition, we consider the Gaussian case and show that as the entropic penalty varies, the iOT problem interpolates between a graphical Lasso and a classical Lasso, thereby establishing a connection between iOT and graph estimation, an important problem in ML. This is joint work with Francisco Andrade and Gabriel Peyre.

Bio

Clarice Poon is an associate professor in the Mathematical Institute at the University of Warwick. She received her PhD in applied mathematics from the University of Cambridge and her undergraduate degree in Mathematics and Computer Science from the University of Oxford. Her research interests include compressed sensing, inverse problems on measures and optimisation for imaging problems.

When

Monday October 9th, 16:00

Where

Room 705, DIMA, Via Dodecaneso 35