Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes

Gromov-Wasserstein problems (Mémoli, 2011; Solomon et al., 2016)) and for computing euclidean projection on the Optimal transport is an important tool in machine Birkhoff polytope (Li et al., 2020). It appears in statistical learning, allowing to capture geometric properties inference on random permutations (Birdal & Simsekli, of the data through a linear program on transport 2019). Inference on random permutations can be obtained polytopes. We present a single-loop optimization by minimizing various other convex functions (Linderman algorithm for minimizing general convex objectives et al., 2018). Optimisation on this polytope also arises when on these domains, utilizing the principles trying to both compute and minimize a Wasserstein distance of Sinkhorn matrix scaling and mirror descent.