Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Bahar Taskesen, Soroosh Shafieezadeh-Abadeh, Daniel KuhnMath. Program 2021 · DOI · OpenReview

TL;DR

This paper tackles the computational hardness of semi-discrete optimal transport (SDOT) problems, proving it's #P-hard. To overcome this, they introduce a novel regularization framework based on distributionally robust optimization and discrete choice models, leading to new and existing regularization schemes. They also develop an improved stochastic gradient descent algorithm for solving these regularized problems efficiently.

What Problem Does This Paper Address?

Optimal transport (OT) is a powerful mathematical framework for comparing probability distributions, finding applications across statistics, machine learning, and computer vision. A key variant is semi-discrete optimal transport (SDOT), where one distribution is discrete and the other is continuous. While SDOT problems are widely used, they are generally considered computationally challenging. This paper aims to formally establish the theoretical basis for this perceived hardness and to develop practical methods for solving these problems. Specifically, they address the lack of a theoretical justification for the computational difficulty of SDOT and propose a unified approach to regularize and solve these problems efficiently.

Methods

The paper introduces a novel regularization framework for SDOT problems by leveraging ideas from distributionally robust optimization (DRO) and discrete choice theory. The core idea is to perturb the transportation cost with an additive disturbance governed by an uncertain probability distribution within a specified ambiguity set. Solving the dual SDOT problem under the "least favorable" disturbance distribution effectively smooths the dual objective and regularizes the primal objective.

They demonstrate that this DRO-based smoothing is equivalent to various regularization schemes, including known ones and new ones derived from different ambiguity sets (e.g., generalized extreme value distributions, Chebyshev ambiguity sets, and marginal ambiguity sets).

For solving the resulting regularized SDOT problems, they propose an averaged stochastic gradient descent (SGD) algorithm that can handle biased stochastic gradient oracles. They provide new convergence guarantees for this algorithm, showing it achieves rates of $O(1/\sqrt{T})$ for Lipschitz continuous objectives and $O(1/T)$ for generalized self-concordant objectives, where $T$ is the number of iterations. Crucially, they show this algorithm improves upon existing convergence guarantees for entropic regularizers in SDOT.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development, with numerical experiments conducted on synthetic data generated from specific distributions.

Key Insights and Ideas

  • #P-Hardness of SDOT: The paper provides the first theoretical proof that computing the Wasserstein distance in a semi-discrete setting is #P-hard, even for simplified cases (two-point discrete distribution against Lebesgue measure). This formally justifies the perceived computational difficulty.
  • Unified Regularization Framework: The connection between DRO and discrete choice models offers a principled way to derive and understand various regularization schemes for SDOT. This framework unifies existing methods and opens doors to new ones by exploring different ambiguity sets.
  • Discrete Choice Models as Regularizers: The interpretation of the dual SDOT objective as a best-case expected utility in a discrete choice model provides a powerful intuition and a rich theoretical toolkit for developing new regularization techniques.
  • Improved SGD for Biased Oracles: The development of an averaged SGD algorithm with new convergence guarantees for biased oracles is a significant algorithmic contribution, enabling more efficient solutions for regularized SDOT.
  • Algorithmic Acceleration: The improved convergence rates for the proposed SGD algorithm, particularly for generalized self-concordant objectives and for entropic regularizers, represent a practical advancement in solving these problems.

Key Results

  • Theoretical Hardness: The paper proves that computing the Wasserstein distance between a discrete measure on two points and the Lebesgue measure on the hypercube is #P-hard.
  • Regularization Framework: A unifying framework for regularizing SDOT problems is proposed, connecting DRO with discrete choice models. This framework yields known and new regularization schemes.
  • Algorithmic Convergence: An averaged SGD algorithm with biased gradient oracles is analyzed, achieving convergence rates of $O(1/\sqrt{T})$ and $O(1/T)$ for different classes of objective functions.
  • Improved Entropic Regularization: The proposed algorithm improves the state-of-the-art convergence guarantee for entropic regularized SDOT from $O(1/\sqrt{T})$ to $O(1/T)$ in certain cases.
  • Numerical Validation: Experiments demonstrate that the proposed regularization and algorithms lead to faster convergence and better performance compared to standard methods.

Limitations and Future Work

  • Approximation Bounds: While the paper derives approximation bounds for regularized SDOT problems, these bounds are not always tight.
  • Generalization to Non-Diagonal Matrices: Proposition 3.5, concerning Chebyshev ambiguity sets, is generalized to arbitrary diagonal matrices but not to non-diagonal matrices.
  • Computational Complexity of Choice Probabilities: While the paper shows that choice probabilities can be computed efficiently in many cases, their computation can still be a bottleneck for certain ambiguity sets.
  • Future Directions: The authors suggest exploring more general ambiguity sets and investigating the computational properties of different regularization schemes. The connection to discrete choice models also opens avenues for further research in interdisciplinary applications.

Summary updated

Abstract

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.
BibTeX
@article{taskesen2021semi,
  author = {Bahar Taskesen and Soroosh Shafieezadeh-Abadeh and Daniel Kuhn},
  title = {{Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution}},
  journal = {Math. Program},
  year = {2021},
  doi = {10.1007/s10107-022-01856-x},
}
Figure