Abstract: Optimal transport (OT) theory is the branch of mathematics that aims at studying and generalizing the fundamental problem of matching optimally two groups of observations, covered in all CS 101 courses (remember the Hungarian algorithm). Following a short introduction to that theory, I present use cases in ML when optimal matchings pop up in various applied areas in ML, where matchings are used to resolve labelling ambiguities. I will then show why a direct resolution of OT problems (using e.g. the Hungarian algorithm or more general network flows/linear programs) runs into several issues: computational complexity, sample complexity, poor parallelization and lack of a meaningful notion of differentiability (e.g. how an optimal matching varies with changes in inputs). I will then detail how regularization can help solve this issues, and present the implementation of these approaches in the ott-jax toolbox.
References:
[1][2]
References:
[1][2]