Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent

Konstantin MishchenkoarXiv 2019 · OpenReview

Abstract: We present a new perspective on the celebrated Sinkhorn algorithm by showing that it is a special case of incremental/stochastic mirror descent. In order to see this, one should simply plug Kullback-Leibler divergence into both the mirror map and the objective function. Since the problem has an unbounded domain, the objective function is neither smooth nor does it have 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 and 2) an extension of the Sinkhorn algorithm beyond two constraints.

Introduction

Optimal Transport (OT) has become a cornerstone of modern machine learning, providing a robust framework for comparing probability distributions. However, the computational cost of solving the classic OT problem is often prohibitive for large-scale applications. To mitigate this, researchers frequently turn to entropy-regularized OT, which is traditionally solved using the Sinkhorn algorithm.

While Sinkhorn is prized for its simplicity and speed, its theoretical foundation has largely been restricted to the framework of "iterative Bregman projections." This perspective, while useful, presents two significant hurdles: it is difficult to generalize to complex constraints and lacks a clear path toward applying standard optimization accelerations, such as Nesterov’s method. This paper, authored by Konstantin Mishchenko (KAUST), bridges this gap by reframing the Sinkhorn algorithm as a specific instance of Stochastic Mirror Descent (SMD).

Reframing Sinkhorn as Optimization

The core contribution of this work is a mathematical re-mapping of Sinkhorn iterations into an unconstrained optimization problem. The author introduces an objective function based on the Kullback-Leibler (KL) divergence:

$$f(x) = KL(Ax || b)$$

In this formulation, the function acts as a penalty for violating the linear constraints of the OT problem. By shifting the focus from projections to objective minimization, the algorithm can be analyzed using the tools of modern convex optimization.

The Challenge of Unbounded Gradients

A primary difficulty in this re-mapping is that the objective function $f(x)$ is not "smooth" in the traditional sense; its gradients are not Lipschitz continuous and can be unbounded. To resolve this, the paper employs the concept of relative smoothness. The author proves that the objective is smooth relative to the entropy function used in the mirror map. Specifically, the stochastic objective is shown to be 1-relatively smooth, a property that ensures stable convergence within the Mirror Descent framework.

The Equivalence Theorem

The theoretical heart of the paper is Theorem 1, which establishes that a single step of Mirror Descent on the KL-divergence objective—using a step size of $\eta = 1$—is mathematically identical to a Bregman projection.

This equivalence yields several immediate insights:

  1. Sinkhorn is SMD: The standard Sinkhorn update (alternating row and column normalizations) is actually Stochastic Mirror Descent where constraints are sampled one at a time.
  2. Greenkhorn is Greedy SMD: The "Greenkhorn" algorithm, which greedily selects the most violated constraint to update, is revealed to be a greedy version of SMD.
  3. The Role of Step Size: The fact that the equivalence requires $\eta = 1$ suggests that Sinkhorn is a very specific, aggressive configuration of a much broader family of optimization algorithms.

New Algorithmic Frontiers

By placing Sinkhorn within the Mirror Descent family, the author introduces new methods for solving Optimal Transport:

  • Pinkhorn (Penalty Sinkhorn): A non-stochastic version of the algorithm that utilizes the full gradient of the objective function.
  • Accelerated Pinkhorn: By applying Nesterov-like acceleration techniques designed for relatively smooth functions, the author provides a blueprint for OT solvers that can potentially outperform standard Sinkhorn in convergence speed.
  • Beyond Two Constraints: While the classic Sinkhorn algorithm is designed for two marginal constraints (rows and columns), the Mirror Descent framework naturally extends to any number of linear constraints, allowing for the solution of more complex multi-marginal transport problems.

Conclusion and Future Directions

This work provides a unifying theory that integrates the Sinkhorn algorithm into the broader landscape of stochastic optimization. While the paper is primarily theoretical, it sets the stage for future empirical research into accelerated OT solvers.

There remain open questions regarding the variance of these stochastic updates, as standard SGD convergence results do not apply directly to this unbounded domain. Furthermore, the integration of proximal operators to handle non-smooth objective components remains an area for future exploration. Nevertheless, by proving that Sinkhorn is a special case of SMD, this research opens a new toolbox for the next generation of Optimal Transport algorithms.

Summary updated

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.
BibTeX
@misc{mishchenko2019sinkhorn,
  author = {Konstantin Mishchenko},
  title = {{Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent}},
  year = {2019},
  eprint = {1909.06918},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.06918},
}
Figure