Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate
Preprint
Abstract
We investigate the semi-discrete Optimal Transport (OT) problem, where a continuous source measure $μ$ is transported to a discrete target measure $ν$, 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 $\mathcal{O}(1/\sqrt{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 $\|\cdot\|^p$ for $p \in (1, \infty)$. We finally provide numerical evidence for our theoretical results.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Sharper exponential convergence rates for Sinkhorn’s algorithm in continuous settingsMathematical Programming, 2025
- Semi-discrete optimal transport: hardness, regularization and numerical solutionMathematical Programming, 2022
- Asymptotics for Semidiscrete Entropic Optimal TransportSIAM Journal on Mathematical Analysis, 2022
- Quantitative Stability in the Geometry of Semi-discrete Optimal TransportInternational Mathematics Research Notices, 2020
- A Stochastic Multi-layer Algorithm for Semi-discrete Optimal Transport with Applications to Texture Synthesis and Style TransferJournal of Mathematical Imaging and Vision, 2020
- A Texture Synthesis Model Based on Semi-Discrete Optimal Transport in Patch SpaceSIAM Journal on Imaging Sciences, 2018
- Monge–Kantorovich depth, quantiles, ranks and signsThe Annals of Statistics, 2017
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimizationOptimization Letters, 2014
- Asymptotic Almost Sure Efficiency of Averaged Stochastic AlgorithmsSIAM Journal on Control and Optimization, 2000
- Acceleration of Stochastic Approximation by AveragingSIAM Journal on Control and Optimization, 1992