A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
We consider the problem of computing a Wasserstein barycenter for a set of discrete probability distributions with finite supports, which finds many applications in areas such as statistics, machine learning and image processing. When the support points of the barycenter are pre-specified, this problem can be modeled as a linear programming (LP) problem whose size can be extremely large. To handle this large-scale LP, we analyse the structure of its dual problem, which is conceivably more tractable and can be reformulated as a well-structured convex problem with 3 kinds of block variables and a coupling linear equality constraint. We then adapt a symmetric Gauss-Seidel based alternating direction method of multipliers (sGS-ADMM) to solve the resulting dual problem and establish its global convergence and global linear convergence rate. As a critical component for efficient computation, we also show how all the subproblems involved can be solved exactly and efficiently. This makes our method suitable for computing a Wasserstein barycenter on a large-scale data set, without introducing an entropy regularization term as is commonly practiced. In addition, our sGS-ADMM can be used as a subroutine in an alternating minimization method to compute a barycenter when its support points are not pre-specified. Numerical results on synthetic data sets and image data sets demonstrate that our method is highly competitive for solving large-scale Wasserstein barycenter problems, in comparison to two existing representative methods and the commercial software Gurobi.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Globally Convergent Algorithm for Neural Network Parameter Optimization Based on Difference-of-Convex Functions
We propose an algorithm for optimizing the parameters of single hidden layer neural networks. Specifically, we derive a blockwise difference-of-convex (DC) functions representation of the objective function. Based on the…
A Globally Convergent Estimator of the Parameters of the Classical Model of a Continuous Stirred Tank Reactor
In this paper we provide the first solution to the challenging problem of designing a globally exponentially convergent estimator for the parameters of the standard model of a continuous stirred tank reactor. Because of …
regressionGPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs
We investigate the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through a cardinality constraint. While Branch-and-Bound (BnB) frameworks can certify optimality…
A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With $O(r^3 \kappa^2 n \log n)…
Globally Composite-Learning-Based Intelligent Fast Finite-Time Control for Uncertain Strict-Feedback Systems with Nonlinearly Periodic Disturbances
This brief aims at the issue of globally composite-learning-based neural fast finite-time (F-FnT) tracking control for a class of uncertain systems in strict-feedback form subject to nonlinearly periodic disturbances. Fi…
valid