Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent
arXiv:1909.06918
Abstract
We present a new perspective on the celebrated Sinkhorn algorithm by showing that is a special case of incremental/stochastic mirror descent. In order to see this, one should simply plug Kullback-Leibler divergence in both mirror map and the objective function. Since the problem has unbounded domain, the objective function is neither smooth nor it has bounded gradients. However, one can still approach the problem using the notion of relative smoothness, obtaining that the stochastic objective is 1-relative smooth. The discovered equivalence allows us to propose 1) new methods for optimal transport, 2) an extension of Sinkhorn algorithm beyond two constraints.
arXiv comment7 pages, 2 algorithms, 1 theorem, 1 lemma
References in corpus (5)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
- Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
- A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
- A Stochastic Penalty Model for Convex and Nonconvex Optimization with Big Constraints