# Convergence of a Newton algorithm for semi-discrete optimal transport

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2016.

## Built on by (most cited first, 13 of 13)

- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Flow Matching with Semidiscrete Couplings](https://mlsanity.com/paper/2509.25519/) (2025)
- [Non-asymptotic convergence bounds for Wasserstein approximation using point clouds](https://mlsanity.com/paper/2106.07911/) (2021)
- [Randomized Stochastic Gradient Descent Ascent](https://mlsanity.com/paper/2111.13162/) (2021)
- [Beyond Uncertainty Sets: Leveraging Optimal Transport to Extend Conformal Predictive Distributions to Multivariate Settings](https://mlsanity.com/paper/2511.15146/) (2025)
- [Tessellations of Semi-Discrete Flow Matching](https://mlsanity.com/paper/2605.07513/) (2026)
- [Statistical Inference for Optimal Transport Maps: Recent Advances and Perspectives](https://mlsanity.com/paper/2506.19025/) (2025)
- [Stochastic optimal transport in Banach Spaces for regularized estimation of multivariate quantiles](https://mlsanity.com/paper/2302.00982/) (2023)
- [Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization](https://mlsanity.com/paper/2405.14459/) (2024)
- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)
- [Simplex-FEM Networks (SiFEN): Learning A Triangulated Function Approximator](https://mlsanity.com/paper/2511.04804/) (2025)
- [Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems](https://mlsanity.com/paper/2607.09139/) (2026)

## Abstract (arXiv)

Many problems in geometric optics or convex geometry can be recast as optimal transport problems: this includes the far-field reflector problem, Alexandrov's curvature prescription problem, etc. A popular way to solve these problems numerically is to assume that the source probability measure is absolutely continuous while the target measure is finitely supported. We refer to this setting as semi-discrete optimal transport. Among the several algorithms proposed to solve semi-discrete optimal transport problems, one currently needs to choose between algorithms that are slow but come with a convergence speed analysis (e.g. Oliker-Prussner) or algorithms that are much faster in practice but which come with no convergence guarantees Algorithms of the first kind rely on coordinate-wise increments and the number of iterations required to reach the solution up to an error of ε is of order N3/ε, where N is the number of Dirac masses in the target measure. On the other hand, algorithms of the second kind typically rely on the formulation of the semi-discrete optimal transport problem as an unconstrained convex optimization problem which is solved using a Newton or quasi-Newton method. The purpose of this article is to bridge this gap between theory and practice by introducing a damped Newton's algorithm which is experimentally efficient and by proving the global convergence of this algorithm with optimal rates. The main assumptions is that the cost function satisfies a condition that appears in the regularity theory for optimal transport (the Ma-Trudinger-Wang condition) and that the support of the source density is connected in a quantitative way (it must satisfy a weighted Poincar'e-Wirtinger inequality).