# Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 29 Oct 2025.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [Asymptotics for semi-discrete entropic optimal transport](https://mlsanity.com/paper/2106.11862/) (2021)
- [DPM-OT: A New Diffusion Probabilistic Model Based on Optimal Transport](https://mlsanity.com/paper/2307.11308/) (2023)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)
- [A gradual, semi-discrete approach to generative network training via explicit Wasserstein minimization](https://mlsanity.com/paper/1906.03471/) (2019)
- [Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings](https://mlsanity.com/paper/2407.01202/) (2024)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)
- [Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings](https://mlsanity.com/paper/2311.02172/) (2023)
- [Quantitative stability in the geometry of semi-discrete optimal transport](https://mlsanity.com/paper/2002.02022/) (2020)

## Abstract (arXiv)

We investigate the semi-discrete Optimal Transport (OT) problem, where a continuous source measure μ is transported to a discrete target measure nu, with particular attention to the OT map approximation. In this setting, Stochastic Gradient Descent (SGD) based solvers have demonstrated strong empirical performance in recent machine learning applications, yet their theoretical guarantee to approximate the OT map is an open question. In this work, we answer it positively by providing both computational and statistical convergence guarantees of SGD. Specifically, we show that SGD methods can estimate the OT map with a minimax convergence rate of O(1/√n), where n is the number of samples drawn from μ. To establish this result, we study the averaged projected SGD algorithm, and identify a suitable projection set that contains a minimizer of the objective, even when the source measure is not compactly supported. Our analysis holds under mild assumptions on the source measure and applies to MTW cost functions,whic include |·|p for p ∈ (1, ∞). We finally provide numerical evidence for our theoretical results.