Semi-discrete optimal transport: hardness, regularization and numerical solution
From MaRDI portal
(Redirected from Publication:6038666)
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.
Recommendations
- Semidual regularized optimal transport
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Asymptotics for semidiscrete entropic optimal transport
- Discrete optimal transport: complexity, geometry and applications
Cites work
- A comment on ``Computational complexity of stochastic programming problems
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A Convex Optimization Approach for Computing Correlated Choice Probabilities With Many Alternatives
- A formula for the time derivative of the entropic cost and applications
- A method for globally minimizing concave functions over convex sets
- A new algorithm for the assignment problem
- A note on scenario reduction for two-stage stochastic programs
- A numerical algorithm for \(L_2\) semi-discrete optimal transport in 3D
- A polynomial time primal network simplex algorithm for minimum cost flows
- A Representative Consumer Theory of the Logit Model
- A sparse multiscale algorithm for dense optimal transport
- A Stochastic Approximation Method
- A transportation \(L^p\) distance for signal analysis
- Acceleration of Stochastic Approximation by Averaging
- Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
- An Econometric Analysis of Residential Electric Appliance Holdings and Consumption
- An optimal method for stochastic composite optimization
- An unconstrained convex programming view of linear programming
- Asymptotic analysis of the exponential penalty trajectory in linear programming
- Asymptotics for semidiscrete entropic optimal transport
- Auction algorithms for network flow problems: A tutorial introduction
- Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
- Choice Prediction With Semidefinite Optimization When Utilities are Correlated
- Concentration inequalities. A nonasymptotic theory of independence
- Confidence level solutions for stochastic programming
- Convergence of latent mixing measures in finite and infinite mixture models
- Convergence rate of incremental subgradient algorithms
- Convex histogram-based joint image segmentation with regularized optimal transport cost
- Convex optimization: algorithms and complexity
- Convolutional Wasserstein distances: efficient optimal transportation on geometric domains
- Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
- Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
- Discrete Choice Methods with Simulation
- Discretization of the 3D Monge-Ampere operator, between wide stencils and power diagrams
- Distributionally robust stochastic programming
- Earth mover's distances on discrete surfaces
- Efficient online and batch learning using forward backward splitting
- Entropic approximation of Wasserstein gradient flows
- Entropic optimal transport is maximum-likelihood deconvolution
- Entropic regularization of continuous optimal transport problems
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Financial scenario generation for stochastic multi-stage decision processes as facility location problems
- From Knothe's Rearrangement to Brenier's Optimal Transport Map
- From large deviations to Wasserstein gradient flows in multiple dimensions
- Generalized self-concordant functions: a recipe for Newton-type methods
- Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
- Geodesic PCA versus Log-PCA of Histograms in the Wasserstein Space
- High-dimensional integration: The quasi-Monte Carlo way
- scientific article; zbMATH DE number 3965301 (Why is no real title available?)
- scientific article; zbMATH DE number 3748284 (Why is no real title available?)
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 3465097 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- scientific article; zbMATH DE number 1444745 (Why is no real title available?)
- scientific article; zbMATH DE number 7415088 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3238721 (Why is no real title available?)
- Hybrid deterministic-stochastic methods for data fitting
- Introduction to algorithms.
- Iterative Bregman projections for regularized transportation problems
- Learning Theory and Kernel Machines
- Mathematical Methods and Models for Economists
- Minkowski-type theorems and least-squares clustering
- On the Complexity of Computing the Volume of a Polyhedron
- Optimal distributed online prediction using mini-batches
- Optimal Transport
- Optimal transport with proximal splitting
- Optimum bounds for the distributions of martingales in Banach spaces
- Pegasos: primal estimated sub-gradient solver for SVM
- Persistency model and its applications in choice modeling
- Polar factorization and monotone rearrangement of vector‐valued functions
- Power particles: an incompressible fluid solver based on power diagrams
- Quadratically regularized optimal transport on graphs
- Regularization via mass transportation
- Regularized discrete optimal transport
- Regularized optimal transport and the rot mover's distance
- Robust Stochastic Approximation Approach to Stochastic Programming
- Scaling algorithms for unbalanced optimal transport problems
- Scenario reduction revisited: fundamental limits and guarantees
- Scenario tree generation for multiperiod financial optimization of optimal discretization
- Self-concordant analysis for logistic regression
- Smooth Optimization with Approximate Gradient
- Stochastic finance. An introduction in discrete time
- Technical note: On the relation between several discrete choice models
- The earth mover's distance as a metric for image retrieval
- Variational Analysis
- Wasserstein discriminant analysis
- Wasserstein loss for image synthesis and restoration
Cited in
(15)- Computational semi-discrete optimal transport with general storage fees
- Semi-discrete optimization through semi-discrete optimal transport: a framework for neural architecture search
- Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Semidual regularized optimal transport
- Asymptotics for semidiscrete entropic optimal transport
- A stochastic Gauss–Newton algorithm for regularized semi-discrete optimal transport
- Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- Dynamic programming in probability spaces via optimal transport
- Stability and sample complexity of divergence regularized optimal transport
- Generalized logit dynamics based on rational logit functions
- An inexact Halpern iteration with application to distributionally robust optimization
- Distributionally robust optimization
- Robust probabilistic inference via a constrained transport metric (with discussion)
This page was built for publication: Semi-discrete optimal transport: hardness, regularization and numerical solution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038666)
