Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Completely Parameter-Free Single-Loop Algorithms for Nonconvex-Concave Minimax Problems
Due to their importance in various emerging applications, efficient algorithms for solving minimax problems have recently received increasing attention. However, many existing algorithms require prior knowledge of the pr…
Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization
We study the problem of finding a near-stationary point for smooth minimax optimization. The recent proposed extra anchored gradient (EAG) methods achieve the optimal convergence rate for the convex-concave minimax probl…
Stochastic OptimizationFederated Minimax Optimization: Improved Convergence Analyses and Algorithms
In this paper, we consider nonconvex minimax optimization, which is gaining prominence in many modern machine learning applications such as GANs. Large-scale edge-based collection of training data in these applications c…
Distributed OptimizationFederated LearningWhat is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these …
BIG-bench Machine LearningMulti-agent Reinforcement LearningReinforcement LearningA Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems
Much recent research effort has been directed to the development of efficient algorithms for solving minimax problems with theoretical convergence guarantees due to the relevance of these problems to a few emergent appli…