Entropic Regularization

Adding entropy to transport spreads the plan slightly, buying a unique smooth solution and fast Sinkhorn iterations at a small accuracy cost.

Entropy trades a sharp sparse plan for a smooth dense one as epsilon grows

Why Does This Exist?

Exact OT plans sit on extreme points: sparse, non-unique, and expensive. A touch of entropy $- \epsilon H(\pi)$ pulls the solution inside the polytope toward the independent coupling, making it unique, smooth in the inputs, and computable by Sinkhorn. Gradients flow through it, so regularized OT becomes a differentiable loss layer.

The price is blur: regularized cost overestimates and shrinks toward the product coupling as $\epsilon$ grows. Debiased Sinkhorn divergences refund most of that bias. Solver: Sinkhorn.

The one idea you need first

Entropy $H(\pi) = -\sum \pi_{ij}\log\pi_{ij}$ peaks at spread-out plans. Penalizing $-H$ (equivalently rewarding spread) trades cost against diffusivity with temperature $\epsilon$ .

Think of It Like This

Hot metal versus cold forging

Cold-forged joints are exact but brittle and slow to shape. Heated metal flows into molds fast and smoothly, then hardens slightly off the cold exact shape.

Epsilon is the heat. Hot plans flow through Sinkhorn in milliseconds with rounded edges; cold plans are exact but demand cubic LP labor. Debiasing is the cooling quench that recovers sharpness.

Where the analogy stops: overheating destroys all structure (plan collapses to independent coupling), unlike metal which just melts.

How It Actually Works

$\min_\pi \langle C,\pi\rangle - \epsilon H(\pi)$ over couplings gives $\pi_{ij} = u_i K_{ij} v_j$ with $K = e^{-C/\epsilon}$ . As $\epsilon \to 0$ the plan converges to the max-entropy exact optimizer; as $\epsilon \to \infty$ it converges to $\mu\nu^T$ with cost equal to independent matching. Debiased divergence $S_\epsilon(\mu,\nu) = OT_\epsilon(\mu,\nu) - \frac{1}{2}(OT_\epsilon(\mu,\mu) + OT_\epsilon(\nu,\nu))$ restores $S_\epsilon(\mu,\mu) = 0$ .

Worked example

Two-point example from Sinkhorn page, $C = [[0,1],[1,0]]$ , $\mu = \nu = (0.5,0.5)$ :

$\epsilon = 0.1$ : $K \approx [[1, 0],[0,1]]$ (off-diagonal $e^{-10} \approx 0$ ). Plan $\approx$ identity, cost $\approx 0$ . Sharp.
$\epsilon = 0.5$ : plan $[[0.44,0.06],[0.06,0.44]]$ , cost $0.12$ (computed earlier).
$\epsilon = 5$ : $K \approx [[1,0.819],[0.819,1]]$ . Symmetric solution tends to $[[0.275,0.225],[0.225,0.275]]$ , cost $\approx 0.450$ . Near the independent cost $0.5$ . Epsilon dials blur from $0$ to $0.5$ continuously.

Watch Out For

Comparing raw regularized costs across different epsilons

$OT_\epsilon$ shifts with $\epsilon$ , so a smaller number can mean larger smoothing rather than closer distributions. Model selection on raw values picks the blurriest setting.

Fix one $\epsilon$ per comparison or use debiased $S_\epsilon$ for cross-setting judgments.

Differentiating through unrolled Sinkhorn naively

Backprop through 1000 iterations wastes memory and amplifies numerical error. Implicit differentiation of the optimality conditions is cheaper and stabler.

Use OTT or GeomLoss implicit gradients instead of unrolling the loop.

The Quick Version

Entropy smoothing makes OT unique, smooth, and Sinkhorn-solvable.
Epsilon trades exactness against speed: zero recovers LP, infinity gives independence.
Raw regularized costs are biased upward and incomparable across epsilons.
Debiased Sinkhorn divergences restore zero self-distance.
Differentiate optimality conditions implicitly, not by unrolling iterations.