Session: Manifold optimization with special metrics
Chair: André Uschmajew
Cluster: Optimization on Manifolds
Talk 1: Optimal transport barycenter via nonconvex concave minimax optimization
Speaker: Xiaohui Chen
Abstract: The optimal transport 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 approximating the barycenter problem are based on entropic regularization. In this paper, we introduce a nearly linear time $O(m \log{m})$ primal-dual algorithm for computing the exact barycenter when the input probability density functions are discretized on an $m$-point grid. The key success of our Wasserstein-Descent $\dot{\mathbb{H}}^1$-Ascent (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 the proposed algorithm to its stationary point when the step size is appropriately chosen for the gradient updates. Superior computational efficacy and approximation accuracy over the existing Wasserstein gradient descent and Sinkhorn's algorithms are demonstrated on 2D synthetic and real data.
Talk 2: Information geometry of operator scaling
Speaker: Tasuku Soma
Abstract: Matrix scaling is a classical problem with a wide range of applications. It is known that the Sinkhorn algorithm for matrix scaling is interpreted as alternating e-projections from the viewpoint of classical information geometry. Recently, a generalization of matrix scaling to completely positive maps called operator scaling has been found to appear in various fields of mathematics and computer science, and the Sinkhorn algorithm has been extended to operator scaling. In this talk, we discuss operator scaling from the viewpoint of quantum information geometry. For example, the operator Sinkhorn algorithm is shown to coincide with alternating e-projections with respect to the symmetric logarithmic derivative metric, which is a Riemannian metric on the space of quantum states relevant to quantum estimation theory.
Talk 3: Operator Sinkhorn iteration with overrelaxation
Speaker: André Uschmajew
Abstract: We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated methods via linearization, which allows us to determine the asymptotically optimal relaxation parameter based on Young's SOR theorem. Based on the Hilbert metric on positive definite cones, we also obtain a global convergence result for a geodesic version of overrelaxation in a specific range of relaxation parameters. Numerical experiments demonstrate that the proposed methods outperform the original operator Sinkhorn iteration in certain applications.
