The Martingale Sinkhorn Algorithm

This paper introduces and proves the convergence of a Martingale Sinkhorn algorithm in arbitrary dimensions for solving the martingale Benamou–Brenier optimal transport problem, extending the theory to marginals with finite moments of order $p > 1$ without requiring compact support.

The Gist

Here is an explanation of the paper "The Martingale Sinkhorn Algorithm" using simple language and creative analogies.

The Big Picture: A Dance of Probability

Imagine you have two groups of people standing in a field.

• Group A (The Start): They are scattered in a specific pattern (let's say, a tight circle).
• Group B (The End): They need to end up in a different pattern (let's say, a wide ring).

In the world of Optimal Transport (a branch of math that studies moving things efficiently), the usual goal is to move Group A to Group B using the least amount of energy. Think of it like a choreographer telling every dancer exactly where to step so they get from the circle to the ring without bumping into each other or taking a detour.

But this paper is about a special, stricter version of this dance called the Martingale problem.

The "Martingale" Rule: The Fair Game

In this special version, there is a rule: The dancers cannot cheat.
If you look at a dancer at any moment during the dance, their expected future position must be exactly where they are right now. They can't plan to drift systematically to the left or right. They must move like a "fair game" (like a random walk or a drunkard's walk).

In math terms, this is called a Martingale. In the real world, this is crucial for finance. If you are pricing a stock option, you assume the stock price moves randomly (a martingale) but must start at today's price and end at a specific distribution of future prices.

The Problem: Finding the "Stretched" Path

The authors are trying to solve a specific puzzle:

• We know where the dancers start (Distribution $\mu_0$).
• We know where they must end (Distribution $\mu_1$).
• We know they must follow the "fair game" rule (Martingale).
• The Goal: Find the path that looks most like Brownian Motion (pure, random jittering, like a pollen grain in water).

Why? Because Brownian Motion is the "default" way things move randomly. If you have to move from A to B under the fair-game rule, the "best" way is the one that stays as close as possible to pure randomness.

This path is called the Bass Martingale (or "Stretched Brownian Motion").

The Old Problem: We Could Only Do 1D

For a long time, mathematicians could only solve this puzzle if the dancers were moving in a straight line (1 dimension). It was like choreographing a line of people.
But in the real world (finance, physics), things move in 2D, 3D, or even higher dimensions. Until now, there was no good way to calculate this "best path" for complex shapes in multiple dimensions.

The Solution: The "Martingale Sinkhorn" Algorithm

The authors invented a new computer algorithm to solve this. They call it the Martingale Sinkhorn Algorithm.

To understand it, let's use an analogy: The "Hot Potato" Game of Potentials.

Imagine you are trying to find the perfect shape for a mold (a "potential") that fits both the start and the end of the dance.

1. Step 1 (The Push): You take the starting group and push them through a "filter" (a mathematical transformation) to see where they land.
2. Step 2 (The Pull): You look at the target group and pull them back through a different filter to see where they came from.
3. The Loop: You keep swapping these filters back and forth. Every time you swap, you check: "Did we get closer to the perfect shape?"

In the classic "Sinkhorn" algorithm (used for normal transport), this process is like a famous iterative method that quickly finds the answer. The authors realized they could do the exact same thing for the Martingale problem, but with a twist: they have to account for the "fair game" rule (the martingale constraint) at every step.

Why This Paper is a Big Deal

1. It Works in Any Dimension: Before this, we were stuck in 1D. Now, we can calculate these paths for complex, multi-dimensional shapes (like moving a cloud of data points in 3D space).
2. It's Robust: The authors proved that this algorithm works even if the groups of people are very messy or spread out (mathematically, they don't need the "finite second moment" assumption, which is a fancy way of saying "the data doesn't have to be perfectly tidy").
3. The "Strict Descent" Secret: The magic behind why the algorithm works is that every time they swap the filters, the "error" (or the distance from the ideal random path) gets strictly smaller. It's like a ball rolling down a hill; it never goes back up, so it eventually settles at the bottom (the solution).

The Real-World Impact

Why should you care?

• Finance: Banks use this to price complex financial derivatives (options) more accurately. If you want to know the price of an option that depends on a stock's path over time, this algorithm helps find the most realistic "random path" the stock could take.
• Machine Learning: It helps in generating new data that looks like real data but follows specific rules.
• Physics: It helps model how particles diffuse and move in fluids under constraints.

Summary in One Sentence

The authors created a new, powerful computer method that acts like a "mathematical choreographer," allowing us to calculate the most natural, random-looking path for data to move from one shape to another in any number of dimensions, while strictly obeying the rules of fair randomness.

Technical Summary

Here is a detailed technical summary of the paper "The Martingale Sinkhorn Algorithm" by Hasenbichler, Joseph, Loepier, Obłój, and Pammer.

1. Problem Statement

The paper addresses the Martingale Benamou–Brenier (mBB) problem, a dynamic optimal transport problem with a martingale constraint.

• Objective: Given two probability measures $\mu_0$ and $\mu_1$ on $\mathbb{R}^d$ in convex order (i.e., $\mu_0 \leq_{cvx} \mu_1$), find a martingale process $(M_t)_{t \in [0,1]}$ such that $M_0 \sim \mu_0$, $M_1 \sim \mu_1$, which minimizes the distance to a standard Brownian motion (or a scaled Brownian motion).
• Mathematical Formulation:
  $$\text{MT}_{\mu_0, \mu_1} = \inf_{M} \mathbb{E}\left[ \int_0^1 |\sigma_t - \bar{\sigma} I_d|_{HS}^2 dt \right]$$
  where $M_t = M_0 + \int_0^t \sigma_s dB_s$.
• Theoretical Context: The problem admits a unique solution in distribution known as the Stretched Brownian Motion (sBM) or Bass martingale. The solution is characterized by a Bass potential $v$ and a Bass measure $\alpha$.
• The Gap: While the existence of the optimal martingale was established theoretically (under finite second-moment assumptions), no numerical methods existed for dimensions $d \geq 2$. Previous numerical approaches were limited to the one-dimensional case using explicit formulas for the optimal transport map.

2. Methodology: The Martingale Sinkhorn Algorithm

The authors propose an iterative numerical scheme, the Martingale Sinkhorn Algorithm, which serves as a martingale analogue to the celebrated Sinkhorn algorithm used in Entropic Optimal Transport.

Core Mechanism

The algorithm alternates between two steps to update a latent measure $\alpha$ and a convex potential $v$:

1. Input: Initial convex potential $v_0$ and marginals $\mu_0, \mu_1$.
2. Step 1 (Latent Measure Update): Given the current potential $v_{i-1}$, compute the intermediate measure $\alpha_i$ by pushing forward $\mu_0$ via the gradient of the $C$-transform of $v_{i-1}$:
   $$\alpha_i = (\nabla v_{i-1}^C) \# \mu_0$$
   where $v^C = (v^* * \gamma)^*$, $\gamma$ is the Gaussian measure, and $*$ denotes convolution.
3. Step 2 (Potential Update): Given $\alpha_i$, find a new convex potential $v_i$ such that the pushforward of the smoothed measure $\alpha_i * \gamma$ via $\nabla v_i^*$ equals the target marginal $\mu_1$:
   $$\mu_1 = (\nabla v_i^*) \# (\alpha_i * \gamma)$$
   This step is equivalent to solving a standard Optimal Transport (OT) problem between $\alpha_i * \gamma$ and $\mu_1$.

Implementation Details

• Neural Network Approximation: The authors implement the algorithm using deep learning. The potentials are parameterized by neural networks (MLPs) with specific growth constraints (quadratic growth for $d \geq 2$ with $L^2$ cost).
• Alternating Training:
  • OT Step: Solve the dual OT problem between $\alpha_i * \gamma$ and $\mu_1$ using Expectile-Regularized Neural OT (ENOT) to update the potential $v_i$.
  • Generator Step: Train a generator network to approximate the map $\nabla (v_i^* * \gamma)$ that pushes $\mu_0$ to the new latent measure $\alpha_{i+1}$, minimizing a Fenchel-Young loss.

3. Key Contributions

1. First General Algorithm for $d \geq 2$: The paper provides the first constructive numerical method to compute the Bass potential and Bass measure in arbitrary dimensions.
2. Relaxation of Moment Assumptions:
   • Previous existence proofs required finite second moments ($\mu \in \mathcal{P}_2$).
   • This work proves convergence and existence under finite moments of order $p > 1$ ($\mu \in \mathcal{P}_p$). This is a significant theoretical extension, as the Bass measure itself may not have finite second moments even if the marginals do (as shown in Example 4.3).
3. Convergence Proof via Strict Descent:
   • The authors prove that the algorithm strictly decreases the dual objective function $E(v) = \int v d\mu_1 - \int v^C d\mu_0$ at each iteration.
   • Technical Challenge: In the non-compact case (general marginals), the standard descent argument fails because the intermediate measures $\alpha_i$ may not have finite first moments, making the OT cost infinite.
   • Solution: The authors introduce a tightness argument (Lemma 3.9). They show that boundedness of the dual objective implies that the sequence of potentials is locally uniformly bounded on the relative interior of the convex hull of $\text{supp}(\mu_1)$. This allows them to establish convergence without assuming compact support.
4. Uniqueness in 1D: The paper establishes that in one dimension, the Bass potential is unique (up to affine transformation), implying the algorithm converges to a unique solution.

4. Main Results

• Theorem 3.10 (Convergence): Under minimal assumptions ($\mu_0, \mu_1 \in \mathcal{P}_p$ for $p>1$, convex order, and irreducibility), the sequence of normalized potentials generated by the algorithm converges (in the sense of epi-convergence) to a Bass potential. The associated sequence of measures converges weakly to the Bass measure.
• Strong Duality: The algorithm attains the dual problem (dmBB), providing a constructive proof of the existence of the optimal martingale in arbitrary dimensions under $p > 1$ moment conditions.
• Example 4.3 (Uniform Disk to Circle): Demonstrates a case where $\mu_0$ and $\mu_1$ are compactly supported, but the resulting Bass measure $\alpha$ has infinite second moment (and even infinite first moment in a variation). This highlights the necessity of the $p > 1$ framework over the $p=2$ framework.

5. Significance

• Bridging Theory and Computation: The paper closes a major gap in Martingale Optimal Transport (MOT) by enabling the computation of solutions in high dimensions, which is crucial for applications in mathematical finance (e.g., model calibration to option prices across multiple maturities).
• Theoretical Advancement: By extending existence results to $p > 1$ and proving convergence without compact support assumptions, the work deepens the understanding of the structural properties of the mBB problem and the behavior of Bass martingales.
• Algorithmic Innovation: The "Martingale Sinkhorn" framework offers a robust, scalable approach that leverages modern neural OT techniques, making it applicable to complex, real-world distributions that are not analytically tractable.

In summary, this work transforms the Martingale Benamou–Brenier problem from a purely theoretical construct into a computationally solvable problem in high dimensions, with rigorous convergence guarantees under relaxed moment conditions.