Non-asymptotic convergence bounds for Wasserstein approximation using point clouds

• URL: http://arxiv.org/abs/2106.07911v1
• Date: Tue, 15 Jun 2021 06:53:08 GMT
• Title: Non-asymptotic convergence bounds for Wasserstein approximation using point clouds
• Authors: Quentin Merigot (LMO, IUF), Filippo Santambrogio (ICJ, IUF), Cl\'ement Sarrazin (LMO)
• Abstract summary: We show how to generate discrete data as if sampled from a model probability distribution. We provide explicit upper bounds for the convergence-type algorithm.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Properties of Discrete Sliced Wasserstein Losses [11.280151521887076]
  The Sliced Wasserstein (SW) distance has become a popular alternative to the Wasserstein distance for comparing probability measures. Widespread applications include image processing, domain adaptation and generative modelling, where it is common to optimise some parameters in order to minimise SW. We investigate the regularity and optimisation properties of this energy, as well as its Monte-Carlo approximation $mathcalE_p$.
  arXiv  Detail & Related papers  (2023-07-19T21:21:18Z)
• Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
  We consider the block coordinate descent of Gauss-Sdel type with regularization (BCD-PR) We show that an W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(W(
  arXiv  Detail & Related papers  (2023-06-04T17:52:49Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Understanding Entropic Regularization in GANs [5.448283690603358]
  We study the influence of regularization on the learned solution of Wasserstein distance. We show that entropy regularization promotes the solution sparsification, while replacing the Wasserstein distance with the Sinkhorn divergence recovers the unregularized solution. We conclude that these regularization techniques can improve the quality of the generator learned from empirical data for a large class of distributions.
  arXiv  Detail & Related papers  (2021-11-02T06:08:16Z)
• Large-Scale Wasserstein Gradient Flows [84.73670288608025]
  We introduce a scalable scheme to approximate Wasserstein gradient flows. Our approach relies on input neural networks (ICNNs) to discretize the JKO steps. As a result, we can sample from the measure at each step of the gradient diffusion and compute its density.
  arXiv  Detail & Related papers  (2021-06-01T19:21:48Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization [106.70006655990176]
  A distributional optimization problem arises widely in machine learning and statistics. We propose a novel particle-based algorithm, dubbed as variational transport, which approximately performs Wasserstein gradient descent. We prove that when the objective function satisfies a functional version of the Polyak-Lojasiewicz (PL) (Polyak, 1963) and smoothness conditions, variational transport converges linearly.
  arXiv  Detail & Related papers  (2020-12-21T18:33:13Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• The Wasserstein Proximal Gradient Algorithm [23.143814848127295]
  Wasserstein gradient flows are continuous time dynamics that define curves of steepest descent to minimize an objective function over the space of probability measures. We propose a Forward Backward (FB) discretization scheme that can tackle the case where the objective function is the sum of a smooth and a nonsmooth geodesically convex terms.
  arXiv  Detail & Related papers  (2020-02-07T22:19:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.