2019/09/16 by Konstantin Mishchenko, Mishchenko, Konstantin · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1909.06918
openalex publication_date 2019/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.