Unifying Optimal Transport and Sampling via Mirror Descent

18 concepts12 papers1 proposal

For a long time, machine learning treated sampling from a probability distribution, computing optimal transport plans, and minimizing a loss function as fundamentally distinct problems. Sampling relied on the physics of stochastic differential equations; optimal transport relied on geometric matrix-scaling algorithms; optimization relied on gradients.

Recently, a profound theoretical unification has emerged: many of these disparate algorithms are actually different expressions of a single optimization framework—Entropic Mirror Descent. By viewing probability distributions as an optimization domain and using the Kullback-Leibler (KL) divergence to define its geometry, we can re-interpret classical heuristics as principled gradient steps.

The Bridge Between Sampling and Optimization

To understand why this unification works, we must first look at how sampling algorithms can be viewed as continuous optimization.

In standard optimization, we move a point down a gradient landscape to find a minimum. In sampling, we move an entire probability distribution to match a target landscape. Arnak S. Dalalyan in Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent formalized this connection by demonstrating that Langevin Monte Carlo (LMC) is a continuous generalization of gradient descent. If you introduce a temperature parameter to control the stochastic noise and scale it toward zero, the sampling path mathematically collapses into a deterministic optimization trajectory. This relationship allows for unified software frameworks, such as the library introduced by Samuel Duffield et al. in Scalable Bayesian Learning with posteriors, which seamlessly transitions between point-estimate optimization and posterior sampling by adjusting a temperature parameter.

High Temperature (Sampling)  ───►  Zero Temperature (Optimization)
   [Stochastic SDE Path]              [Deterministic Gradient Path]

But the connection runs deeper than the zero-temperature limit. Consider tempering, a widely used sampling heuristic where a distribution's temperature is gradually altered to help particles escape local minima. Nicolas Chopin et al. proved in A connection between Tempering and Entropic Mirror Descent that these discrete tempering sequences are mathematically identical to performing Entropic Mirror Descent steps on the reverse KL divergence.

Why does this equivalence hold? In standard gradient descent, steps are taken in a flat, Euclidean space. However, probability distributions live on a constrained simplex where additive steps can violate non-negativity. Mirror descent solves this by mapping the primal space to a dual space via a "mirror map" (in this case, negative entropy), taking a linear gradient step there, and mapping back. Changing a distribution's temperature shifts the balance between the energy landscape and the entropy regularizer in exactly the same way a mirror descent step balances a loss function against its entropic Bregman divergence penalty.

The Sinkhorn Algorithm as Primal Mirror Descent

This same geometric insight redefines how we solve Entropic Optimal Transport (eOT). The workhorse method for eOT is the Sinkhorn algorithm, which adds an entropic regularization term to the transport cost to make the problem strictly convex. Traditionally, Sinkhorn is interpreted as a geometric alternating projection method that iteratively scales the rows and columns of a matrix to satisfy marginal constraints.

However, Mohammad Reza Karimi et al. in Sinkhorn Flow as Mirror Flow: A Continuous-Time Framework for Generalizing the Sinkhorn Algorithm shifted this view from geometry to optimization, proving that Sinkhorn's convergence is fundamentally driven by its underlying mirror map.

Specifically, the Sinkhorn algorithm is a primal Mirror Descent scheme with a fixed step size. As shown by Pierre-Cyril Aubin-Frankowski et al. in Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM, treating the algorithm as optimization over the space of joint distributions yields a unified path to proving convergence rates. Because the entropic mirror map naturally produces exponential, multiplicative updates rather than additive ones, it perfectly matches the matrix-scaling operations of Sinkhorn. This optimization perspective allows researchers to port stability guarantees directly to complex generative frameworks; for example, Dong-Sig Han et al. in Variational Online Mirror Descent for Robust Learning in Schrödinger Bridge leveraged this exact equivalence to apply online optimization theory and regret bounds to Schrödinger Bridge models.

Dual and Semi-Dual Optimization Perspectives

While the primal view operates directly on joint distributions, analyzing optimal transport through its dual formulations reveals why these algorithms converge so rapidly.

Instead of optimizing the massive joint distribution matrix, we can optimize lower-dimensional dual potentials. Lénaïc Chizat et al. demonstrated in Sharper exponential convergence rates for Sinkhorn's algorithm in continuous settings that entropic optimal transport can be framed as coordinate ascent on a dual objective function. By leveraging the curvature and log-concavity of this dual space, the authors proved exponential convergence rates that remain robust even when entropic regularization is small.

Primal Space (Joint Distributions)   ◄───[Mirror Map]───►   Dual Space (Potentials)
   Sinkhorn Matrix Scaling                                     Coordinate Ascent

Alternatively, one can look at the semi-dual formulation, where only one set of constraints is dualized. Vishwak Srinivasan et al. in Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective showed that the semi-dual objective is an unconstrained, concave function. This perspective naturally leads to gradient ascent-like procedures for updating dual potentials, generalizing Sinkhorn and providing a recipe for designing entirely new algorithms. This aligns with the framework used by Wei Deng et al. in On Convergence of Approximate Schr"{o}dinger Bridge with Bounded Cost, who utilized concave maximization via duality to prove that Schrödinger Bridge algorithms maintain linear convergence even when their internal projections are approximated.

Replacing Heuristics with Principled Optimization

By reframing these diverse problems as mirror descent, empirical heuristics can be replaced with mathematically grounded optimization techniques.

  • Temperature Annealing: In optimal transport, practitioners often start with high entropic regularization (high temperature) for fast initial convergence and gradually lower it to recover a sharp, unregularized transport plan. Allan Douglas Jepson et al. in Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients proved that this annealing process is exactly a sequence of Mirror Descent steps on the primal objective. This realization allows practitioners to swap out heuristic cooling schedules for advanced optimization strategies like warm-starting.
  • Information Theory: The classical Blahut-Arimoto algorithm, used to compute channel capacities, can be reinterpreted as an instance of entropic mirror descent. Kerry He et al. demonstrated this in A Bregman Proximal Perspective on Classical and Quantum Blahut-Arimoto Algorithms, providing a unified convergence analysis that extends seamlessly to quantum information settings.
  • Retrieval Heuristics: In natural language processing, empirical retrieval tricks like the inverted softmax—used to prevent "hubness" in bilingual lexicon induction—can be mathematically derived as specific iterations of an entropy-regularized optimal transport solver, as shown by Jiaji Huang et al. in Hubless Nearest Neighbor Search for Bilingual Lexicon Induction.

Ultimately, the mirror descent framework reveals that sampling, tempering, and matrix scaling are not distinct algorithmic paradigms. They are simply the natural expressions of gradient optimization when forced to operate within the intrinsic, entropic geometry of probability spaces.

Key Foundational Work

Hubless Nearest Neighbor Search for Bilingual Lexicon Induction (2019) — contributed 1 concept elements to this direction.
Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_primal_mirror_descent_0b1fd48d,
  title = {primal mirror descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/primal-mirror-descent/rdr_0b1fd48d951f44189756097cc9699fb1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_primal_mirror_descent_0b1fd48d_v1,
  title = {primal mirror descent},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/primal-mirror-descent/rdr_0b1fd48d951f44189756097cc9699fb1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake