Semi-discrete optimal transport: hardness, regularization and numerical solution

DOI10.1007/s10107-022-01856-xzbMath1518.90049arXiv2103.06263OpenAlexW3135790023WikidataQ114228484 ScholiaQ114228484MaRDI QIDQ6038666

Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Bahar Taşkesen

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.06263

zbMATH Keywords

complexityWasserstein distancediscrete choice modelsoptimal transportdistributionally robust optimization\(\#P\)-hardnessstochastic gradient descent algorithms

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Robustness in mathematical programming (90C17)

Related Items

Discrete Optimal Transport with Independent Marginals is #P-Hard

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comment on ``Computational complexity of stochastic programming problems
• A sparse multiscale algorithm for dense optimal transport
• An optimal method for stochastic composite optimization
• Pegasos: primal estimated sub-gradient solver for SVM
• From large deviations to Wasserstein gradient flows in multiple dimensions
• Auction algorithms for network flow problems: A tutorial introduction
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Asymptotic analysis of the exponential penalty trajectory in linear programming
• A polynomial time primal network simplex algorithm for minimum cost flows
• Minkowski-type theorems and least-squares clustering
• Entropic optimal transport is maximum-likelihood deconvolution
• Convex histogram-based joint image segmentation with regularized optimal transport cost
• A transportation \(L^p\) distance for signal analysis
• Wasserstein discriminant analysis
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• The earth mover's distance as a metric for image retrieval
• Optimum bounds for the distributions of martingales in Banach spaces
• Self-concordant analysis for logistic regression
• Convergence of latent mixing measures in finite and infinite mixture models
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• A formula for the time derivative of the entropic cost and applications
• Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling
• Scenario reduction revisited: fundamental limits and guarantees
• Entropic regularization of continuous optimal transport problems
• Generalized self-concordant functions: a recipe for Newton-type methods
• Confidence level solutions for stochastic programming
• A note on scenario reduction for two-stage stochastic programs
• Financial scenario generation for stochastic multi-stage decision processes as facility location problems
• Power particles
• Convolutional wasserstein distances
• Optimal Transport with Proximal Splitting
• Hybrid Deterministic-Stochastic Methods for Data Fitting
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
• Persistency Model and Its Applications in Choice Modeling
• Quadratically Regularized Optimal Transport on Graphs
• Scaling algorithms for unbalanced optimal transport problems
• Wasserstein Loss for Image Synthesis and Restoration
• Discrete Choice Methods with Simulation
• An Econometric Analysis of Residential Electric Appliance Holdings and Consumption
• Smooth Optimization with Approximate Gradient
• Discretization of the 3d monge−ampere operator, between wide stencils and power diagrams
• Entropic Approximation of Wasserstein Gradient Flows
• A Numerical Algorithm forL₂Semi-Discrete Optimal Transport in 3D
• Robust Stochastic Approximation Approach to Stochastic Programming
• A Representative Consumer Theory of the Logit Model
• On the Complexity of Computing the Volume of a Polyhedron
• A method for globally minimizing concave functions over convex sets
• A new algorithm for the assignment problem
• Polar factorization and monotone rearrangement of vector‐valued functions
• An unconstrained convex programming view of linear programming
• Acceleration of Stochastic Approximation by Averaging
• Variational Analysis
• Distributionally Robust Stochastic Programming
• Technical Note—On the Relation Between Several Discrete Choice Models
• Geodesic PCA versus Log-PCA of Histograms in the Wasserstein Space
• A Convex Optimization Approach for Computing Correlated Choice Probabilities With Many Alternatives
• Earth mover's distances on discrete surfaces
• Generalized Sinkhorn Iterations for Regularizing Inverse Problems Using Optimal Mass Transport
• From Knothe's Rearrangement to Brenier's Optimal Transport Map
• Mathematical Methods and Models for Economists
• Asymptotics for Semidiscrete Entropic Optimal Transport
• Regularized Discrete Optimal Transport
• Regularization via Mass Transportation
• Iterative Bregman Projections for Regularized Transportation Problems
• Learning Theory and Kernel Machines
• Choice Prediction With Semidefinite Optimization When Utilities are Correlated
• Optimal Distributed Online Prediction using Mini-Batches
• High-dimensional integration: The quasi-Monte Carlo way
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• A Stochastic Approximation Method
• Optimal Transport
• Stochastic finance. An introduction in discrete time
• Scenario tree generation for multiperiod financial optimization of optimal discretization

This page was built for publication: Semi-discrete optimal transport: hardness, regularization and numerical solution