# Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution arXiv: https://arxiv.org/abs/2103.06263 ยท HTML: https://mlsanity.com/paper/2103.06263/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 54 of its 175 references that are in the map. - First posted on arXiv 10 Mar 2021. ## Builds on (most cited first, 30 of 54) - [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013) - [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017) - [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015) - [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016) - [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017) - [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015) - [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017) - [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016) - [Image to Image Translation for Domain Adaptation](https://mlsanity.com/paper/1712.00479/) (2017) - [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015) - [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017) - [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018) - [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013) - [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017) - [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017) - [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019) - [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019) - [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013) - [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017) - [A Distributionally Robust Approach to Fair Classification](https://mlsanity.com/paper/2007.09530/) (2020) - [Optimal Transport for Diffeomorphic Registration](https://mlsanity.com/paper/1706.05218/) (2017) - [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017) - [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013) - [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019) - [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014) - [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017) - [Wasserstein Discriminant Analysis](https://mlsanity.com/paper/1608.08063/) (2016) - [A Statistical Test for Probabilistic Fairness](https://mlsanity.com/paper/2012.04800/) (2020) ## Built on by (most cited first, 13 of 13) - [Unifying Distributionally Robust Optimization via Optimal Transport Theory](https://mlsanity.com/paper/2308.05414/) (2023) - [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023) - [Trust Region Policy Optimization with Optimal Transport Discrepancies: Duality and Algorithm for Continuous Actions](https://mlsanity.com/paper/2210.11137/) (2022) - [Nash Equilibria, Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization](https://mlsanity.com/paper/2303.03900/) (2023) - [AlignFlow: Improving Flow-based Generative Models with Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.15038/) (2025) - [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022) - [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022) - [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024) - [A Nonparametric Approach with Marginals for Modeling Consumer Choice](https://mlsanity.com/paper/2208.06115/) (2022) - [An Inexact Halpern Iteration with Application to Distributionally Robust Optimization](https://mlsanity.com/paper/2402.06033/) (2024) - [Going from a Representative Agent to Counterfactuals in Combinatorial Choice](https://mlsanity.com/paper/2505.23546/) (2025) - [On optimal solutions of classical and sliced Wasserstein GANs with non-Gaussian data](https://mlsanity.com/paper/2509.06505/) (2025) - [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025) ## Abstract (arXiv) Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification. To fill this gap, we prove that computing the Wasserstein distance between a discrete probability measure supported on two points and the Lebesgue measure on the standard hypercube is already #P-hard. This insight prompts us to seek approximate solutions for semi-discrete optimal transport problems. We thus perturb the underlying transportation cost with an additive disturbance governed by an ambiguous probability distribution, and we introduce a distributionally robust dual optimal transport problem whose objective function is smoothed with the most adverse disturbance distributions from within a given ambiguity set. We further show that smoothing the dual objective function is equivalent to regularizing the primal objective function, and we identify several ambiguity sets that give rise to several known and new regularization schemes. As a byproduct, we discover an intimate relation between semi-discrete optimal transport problems and discrete choice models traditionally studied in psychology and economics. To solve the regularized optimal transport problems efficiently, we use a stochastic gradient descent algorithm with imprecise stochastic gradient oracles. A new convergence analysis reveals that this algorithm improves the best known convergence guarantee for semi-discrete optimal transport problems with entropic regularizers.