# Order Constraints in Optimal Transport

arXiv: https://arxiv.org/abs/2110.07275 · HTML: https://mlsanity.com/paper/2110.07275/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 59 references that are in the map.
- First posted on arXiv 14 Oct 2021.

## Builds on (most cited first, 30 of 32)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [LSUN: Construction of a Large-scale Image Dataset using Deep Learning with Humans in the Loop](https://mlsanity.com/paper/1506.03365/) (2015)
- [e-SNLI: Natural Language Inference with Natural Language Explanations](https://mlsanity.com/paper/1812.01193/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques](https://mlsanity.com/paper/1909.03012/) (2019)
- [Optimal Feature Transport for Cross-View Image Geo-Localization](https://mlsanity.com/paper/1907.05021/) (2019)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Hierarchical Optimal Transport for Document Representation](https://mlsanity.com/paper/1906.10827/) (2019)
- [Multi-marginal optimal transport: theory and applications](https://mlsanity.com/paper/1406.0026/) (2014)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [All of the Fairness for Edge Prediction with Optimal Transport](https://mlsanity.com/paper/2010.16326/) (2020)
- [On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification](https://mlsanity.com/paper/2006.12301/) (2020)
- [Towards Optimal Transport with Global Invariances](https://mlsanity.com/paper/1806.09277/) (2018)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [Word Mover's Embedding: From Word2Vec to Document Embedding](https://mlsanity.com/paper/1811.01713/) (2018)
- [Rationalizing Text Matching: Learning Sparse Alignments via Optimal Transport](https://mlsanity.com/paper/2005.13111/) (2020)
- [Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport](https://mlsanity.com/paper/1905.10812/) (2019)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [Optimal Transport on Discrete Domains](https://mlsanity.com/paper/1801.07745/) (2018)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces](https://mlsanity.com/paper/1911.02536/) (2019)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Context Mover's Distance & Barycenters: Optimal Transport of Contexts for Building Representations](https://mlsanity.com/paper/1808.09663/) (2018)

## Built on by (most cited first, 4 of 4)

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Timestamp-supervised Wearable-based Activity Segmentation and Recognition with Contrastive Learning and Order-Preserving Optimal Transport](https://mlsanity.com/paper/2310.09114/) (2023)
- [Many-to-Many Matching via Sparsity Controlled Optimal Transport](https://mlsanity.com/paper/2503.24204/) (2025)
- [From Cone Geometry to Monge Structure: Local Defects and Global Regret in High-Dimensional Optimal Transport](https://mlsanity.com/paper/2606.04695/) (2026)

## Abstract (arXiv)

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. We define an efficient method for obtaining explainable solutions to the new formulation that scales far better than standard approaches. The theoretical properties of the method are provided. We demonstrate experimentally that order constraints improve explainability using the e-SNLI (Stanford Natural Language Inference) dataset that includes human-annotated rationales as well as on several image color transfer examples.