Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations

• URL: http://arxiv.org/abs/2307.13370v1
• Date: Tue, 25 Jul 2023 09:42:31 GMT
• Title: Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations
• Authors: L\'ena\"ic Chizat, Tomas Va\v{s}kevi\v{c}ius
• Abstract summary: We propose and analyze an algorithm for computing doubly regularized Wasserstein barycenters. An inexact variant of our algorithm, implementable using approximate Monte Carlo sampling, offers the first non-asymptotic convergence guarantees.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the computation of doubly regularized Wasserstein barycenters, a recently introduced family of entropic barycenters governed by inner and outer regularization strengths. Previous research has demonstrated that various regularization parameter choices unify several notions of entropy-penalized barycenters while also revealing new ones, including a special case of debiased barycenters. In this paper, we propose and analyze an algorithm for computing doubly regularized Wasserstein barycenters. Our procedure builds on damped Sinkhorn iterations followed by exact maximization/minimization steps and guarantees convergence for any choice of regularization parameters. An inexact variant of our algorithm, implementable using approximate Monte Carlo sampling, offers the first non-asymptotic convergence guarantees for approximating Wasserstein barycenters between discrete point clouds in the free-support/grid-free setting.

Related papers

• On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussians [24.473522267391072]
  We develop algorithms on Bures-Wasserstein manifold, named the Exact Geodesic Gradient Descent and Hybrid Gradient Descent algorithms. We establish theoretical convergence guarantees for both methods and demonstrate that the Exact Geodesic Gradient Descent algorithm attains a dimension-free convergence rate.
  arXiv  Detail & Related papers  (2024-10-10T17:01:57Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• Variational Wasserstein Barycenters with c-Cyclical Monotonicity [17.26436842450489]
  We develop a novel continuous approximation method for the Wasserstein barycenters problem given sample access to the input distributions. We provide theoretical analysis on convergence and demonstrate the practical effectiveness of our method on real applications of posterior aggregation and synthetic data.
  arXiv  Detail & Related papers  (2021-10-22T11:06:50Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Sampling From the Wasserstein Barycenter [0.0]
  This work presents an algorithm to sample from the Wasserstein barycenter of absolutely continuous measures. Our method is based on the gradient flow of the multimarginal formulation of the Wasserstein barycenter, with an additive penalization to account for the marginal constraints.
  arXiv  Detail & Related papers  (2021-05-04T18:57:41Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport. We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
  arXiv  Detail & Related papers  (2021-02-02T21:01:13Z)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  We introduce a new dual formulation for the regularized Wasserstein barycenter problem. We establish strong duality and use the corresponding primal-dual relationship to parametrize the barycenter implicitly using the dual potentials of regularized transport problems.
  arXiv  Detail & Related papers  (2020-08-28T08:28:06Z)
• 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)
• Debiased Sinkhorn barycenters [110.79706180350507]
  Entropy regularization in optimal transport (OT) has been the driver of many recent interests for Wasserstein metrics and barycenters in machine learning. We show how this bias is tightly linked to the reference measure that defines the entropy regularizer. We propose debiased Wasserstein barycenters that preserve the best of both worlds: fast Sinkhorn-like iterations without entropy smoothing.
  arXiv  Detail & Related papers  (2020-06-03T23:06:02Z)

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.