Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Wasserstein Mirror Gradient Flow as the limit of the Sinkhorn Algorithm
We prove that the sequence of marginals obtained from the iterations of the Sinkhorn algorithm or the iterative proportional fitting procedure (IPFP) on joint densities, converges to an absolutely continuous curve on the…
Improved Rate of First Order Algorithms for Entropic Optimal Transport
This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. The resulting rate for approximating the optimal transport (OT) has been improved from $\widetil…
Sinkhorn Distributionally Robust Optimization
We study distributionally robust optimization with Sinkhorn distance -- a variant of Wasserstein distance based on entropic regularization. We derive a convex programming dual reformulation for general nominal distributi…
Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm
Many problems in machine learning can be formulated as solving entropy-regularized optimal transport on the space of probability measures. The canonical approach involves the Sinkhorn iterates, renowned for their rich ma…
Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes
Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimi…
Point Cloud Registration