  Many problems in machine learning involve calculating correspondences between
sets of objects, such as point clouds or images. Discrete optimal transport
provides a natural and successful approach to such tasks whenever the two sets
of objects can be represented in the same space, or at least distances between
them can be directly evaluated. Unfortunately neither requirement is likely to
hold when object representations are learned from data. Indeed, automatically
derived representations such as word embeddings are typically fixed only up to
some global transformations, for example, reflection or rotation. As a result,
pairwise distances across two such instances are ill-defined without specifying
their relative transformation. In this work, we propose a general framework for
optimal transport in the presence of latent global transformations. We cast the
problem as a joint optimization over transport couplings and transformations
chosen from a flexible class of invariances, propose algorithms to solve it,
and show promising results in various tasks, including a popular unsupervised
word translation benchmark.
