# Non-asymptotic convergence bounds for Wasserstein approximation using point clouds

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 24 references that are in the map.
- First posted on arXiv 15 Jun 2021.

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

- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Optimal Transport for Diffeomorphic Registration](https://mlsanity.com/paper/1706.05218/) (2017)
- [Convergence of a Newton algorithm for semi-discrete optimal transport](https://mlsanity.com/paper/1603.05579/) (2016)

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

- [Generative Modeling through the Semi-dual Formulation of Unbalanced Optimal Transport](https://mlsanity.com/paper/2305.14777/) (2023)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [Properties of Discrete Sliced Wasserstein Losses](https://mlsanity.com/paper/2307.10352/) (2023)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Analyzing and Improving Optimal-Transport-based Adversarial Networks](https://mlsanity.com/paper/2310.02611/) (2023)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs](https://mlsanity.com/paper/2311.01404/) (2023)
- [Towards Understanding Gradient Dynamics of the Sliced-Wasserstein Distance via Critical Point Analysis](https://mlsanity.com/paper/2502.06525/) (2025)
- [Exploring Ordinality in Text Classification: A Comparative Study of Explicit and Implicit Techniques](https://mlsanity.com/paper/2405.11775/) (2024)

## Abstract (arXiv)

Several issues in machine learning and inverse problems require to generate discrete data, as if sampled from a model probability distribution. A common way to do so relies on the construction of a uniform probability distribution over a set of N points which minimizes the Wasserstein distance to the model distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. Yet, in most cases, a suitably adjusted version of Lloyd's algorithm -- in which Voronoi cells are replaced by Power cells -- leads to configurations with small Wasserstein error. This is surprising because, again, of the non-convex nature of the problem, as well as the existence of spurious critical points. We provide explicit upper bounds for the convergence speed of this Lloyd-type algorithm, starting from a cloud of points sufficiently far from each other. This already works after one step of the iteration procedure, and similar bounds can be deduced, for the corresponding gradient descent. These bounds naturally lead to a modified Poliak-Lojasiewicz inequality for the Wasserstein distance cost, with an error term depending on the distances between Dirac masses in the discrete distribution.