Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization

• URL: http://arxiv.org/abs/2501.14635v1
• Date: Fri, 24 Jan 2025 16:55:21 GMT
• Title: Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization
• Authors: Kaheon Kim, Rentian Yao, Changbo Zhu, Xiaohui Chen,
• Abstract summary: Wasserstein-Descent $dotmathbbH1$-Ascent (WDHA) algorithm for computing exact barycenter. We present a nearly linear time $O(m logm)$ and linear space complexity $O(m)$ primal-dual algorithm for approximating the barycenter problem.
• Score: 11.344401324787974
• License:
• Abstract: The optimal transport barycenter (a.k.a. Wasserstein barycenter) is a fundamental notion of averaging that extends from the Euclidean space to the Wasserstein space of probability distributions. Computation of the unregularized barycenter for discretized probability distributions on point clouds is a challenging task when the domain dimension $d > 1$. Most practical algorithms for approximating the barycenter problem are based on entropic regularization. In this paper, we introduce a nearly linear time $O(m \log{m})$ and linear space complexity $O(m)$ primal-dual algorithm, the Wasserstein-Descent $\dot{\mathbb{H}}^1$-Ascent (WDHA) algorithm, for computing the exact barycenter when the input probability density functions are discretized on an $m$-point grid. The key success of the WDHA algorithm hinges on alternating between two different yet closely related Wasserstein and Sobolev optimization geometries for the primal barycenter and dual Kantorovich potential subproblems. Under reasonable assumptions, we establish the convergence rate and iteration complexity of WDHA to its stationary point when the step size is appropriately chosen. Superior computational efficacy, scalability, and accuracy over the existing Sinkhorn-type algorithms are demonstrated on high-resolution (e.g., $1024 \times 1024$ images) 2D synthetic and real data.

Related papers

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
  We study the $k$-sparse Wasserstein Barycenter problem in the presence of outliers. Existing WB algorithms cannot be directly extended to handle the case with outliers. We propose a clustering based LP method that yields constant approximation factor for the $k$-sparse WB with outliers problem.
  arXiv  Detail & Related papers  (2024-04-20T15:01:35Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters [0.0]
  We present two algorithms to approximate the solution of multi-marginal optimal transport (MOT) with squared Euclidean costs for $N$ discrete probability measures. They are fast, memory-efficient and easy to implement and can be used with any sparse OT solver as a black box.
  arXiv  Detail & Related papers  (2022-02-02T10:59:54Z)
• Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
  We study dimensionality reduction techniques for the Wasserstein barycenter problem. We show that randomized dimensionality reduction can be used to map the problem to a space of dimension $O(log n)$ independent of both $d$ and $k$. We also provide a coreset construction for the Wasserstein barycenter problem that significantly decreases the number of input distributions.
  arXiv  Detail & Related papers  (2021-10-18T02:57:25Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that mitigates the curse of dimensionality.
  arXiv  Detail & Related papers  (2021-02-05T19:23:35Z)
• 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)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks [15.171726731041055]
  Wasserstein Barycenter is a principled approach to represent the weighted mean of a given set of probability distributions. We present a novel scalable algorithm to approximate the Wasserstein Barycenters aiming at high-dimensional applications in machine learning.
  arXiv  Detail & Related papers  (2020-07-08T22:41:18Z)

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.