Order Constraints in Optimal Transport
  Optimal transport is a framework for comparing measures whereby a cost is
incurred for transporting one measure to another. Recent works have aimed to
improve optimal transport plans through the introduction of various forms of
structure. We introduce novel order constraints into the optimal transport
formulation to allow for the incorporation of structure. While there will are
now quadratically many constraints as before, we prove a $\delta-$approximate
solution to the order-constrained optimal transport problem can be obtained in
$\mathcal{O}(L^2\delta^{-2} \kappa(\delta(2cL_\infty (1+(mn)^{1/2}))^{-1})
\cdot mn\log mn)$ time. We derive computationally efficient lower bounds that
allow for an explainable approach to adding structure to the optimal transport
plan through order constraints. We demonstrate experimentally that order
constraints improve explainability using the e-SNLI (Stanford Natural Language
Inference) dataset that includes human-annotated rationales for each
assignment.
