🔢 mathematics

Sparsity and uniform regularity for regularised optimal transport

This paper establishes uniform interior regularity estimates for transport-like maps and potentials in regularised quadratic optimal transport, proving their local convergence to unregularised solutions and deriving sharp local support bounds that improve existing global bias results.

Original authors: Rishabh S. Gvalani, Lukas Koch

Published 2026-02-06

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Rishabh S. Gvalani, Lukas Koch

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Moving Furniture with a "Magic" Rule

Imagine you have a warehouse full of boxes (Source) and a set of empty shelves (Destination). Your goal is to move every box to a shelf in the most efficient way possible, minimizing the total distance traveled. In math, this is called Optimal Transport.

However, solving this perfectly is like trying to solve a giant, messy puzzle where the pieces don't fit together smoothly. It's hard to calculate, and small changes in the warehouse layout can cause the whole plan to crash.

To fix this, mathematicians add a "regularization" rule. Think of this as adding a soft, stretchy rubber band to the moving plan. This rubber band makes the problem easier to solve and smoother to calculate. But there's a catch:

The Rubber Band Problem: If the rubber band is too stretchy (like in "entropic" transport), the boxes end up spreading out everywhere, even to shelves that are far away. This is called having "full support," and it makes the math messy and the computer slow.
The Goal: The authors want to find a "Goldilocks" rubber band—one that makes the math easy but keeps the boxes clustered tightly where they belong (sparse support), just like the original, perfect plan.

What the Authors Did

The paper investigates two specific types of these "rubber bands":

Entropic: The very stretchy kind (boxes spread out).
Sub-quadratic Polynomial: A stiffer kind (boxes stay closer together).

They wanted to prove two main things:

Sparsity: Even with the rubber band, the boxes don't wander off too far. They stay in a tight neighborhood.
Smoothness: The path the boxes take is smooth and predictable, not jagged or chaotic.

The Key Discoveries

1. The "Invisible Fence" (Sparsity)

The authors proved that for certain types of rubber bands, there is an invisible fence around the boxes.

The Analogy: Imagine you are walking a dog on a leash. If the leash is too long, the dog runs everywhere. But these authors found that no matter how you adjust the leash (the math parameter $\varepsilon$ ), the dog (the transport plan) never strays beyond a specific, predictable distance from the owner.
The Result: They calculated exactly how big this "fence" is. It depends on how stiff the rubber band is. If the band is stiff, the fence is tiny. If it's stretchy, the fence is bigger, but it still exists. This is a huge improvement because previous math only worked for very specific, stiff bands.

2. The "Smooth Road" (Regularity)

Once they knew the boxes stay within the fence, they looked at the road the boxes travel on.

The Analogy: Imagine the transport plan is a road. Sometimes, roads have potholes or sharp cliffs (mathematical "singularities"). The authors proved that for their specific rubber bands, the road is smooth.
The Result: They showed that the "map" telling the boxes where to go is not just continuous, but has a consistent slope (Lipschitz continuity). This means you can predict exactly where a box will go if you nudge the starting point slightly. The road doesn't suddenly turn into a cliff.

3. The "Universal" Rule (Uniformity)

This is the most powerful part of their discovery.

The Analogy: Usually, as you tighten the rubber band to make it behave more like the original perfect plan, the math gets wilder and harder to handle. It's like trying to balance a pencil on its tip; the closer you get to the perfect balance, the harder it is to keep it steady.
The Result: The authors proved that their "smooth road" and "invisible fence" rules work equally well whether the rubber band is loose or extremely tight. They don't break down as you get closer to the perfect solution. This allows them to say: "As we tighten the rubber band to zero, the boxes smoothly and predictably turn into the perfect, original transport plan."

Why This Matters (According to the Paper)

The paper doesn't talk about clinical uses or future apps. Instead, it focuses on the mathematical foundation:

Better Algorithms: Because the math is now proven to be smooth and predictable, computer algorithms (like the famous Sinkhorn algorithm) can be trusted to work better and faster without crashing.
Connecting the Dots: It bridges the gap between the "messy" world of regularized transport (used for easy computing) and the "perfect" world of unregularized transport (the theoretical ideal). They proved that as you clean up the math, the solution doesn't jump around; it glides smoothly into place.

Summary in One Sentence

The authors proved that by using specific types of mathematical "rubber bands," we can keep moving plans both easy to calculate and tightly organized, ensuring that as we remove the rubber band to get the perfect solution, the path remains smooth and predictable all the way.

Problem Statement
This paper investigates the properties of minimisers for regularised optimal transport (ROT) problems, specifically focusing on quadratic optimal transport regularised by either sub-quadratic polynomial terms or entropic terms. The primary objective is to establish uniform regularity estimates for the transport-like map and the associated potentials that are independent of the regularisation parameter $\varepsilon$ .

The authors address a gap in the existing literature where regularity results for regularised transport often depend exponentially on $\varepsilon$ (e.g., in the entropic setting) or are limited to specific cases like quadratic regularisation ( $p=2$ ). While entropic regularisation is known for its smoothness, it suffers from full support, leading to numerical instabilities. Conversely, sub-quadratic polynomial regularisation ( $p \in (1, 2]$ ) offers sparse support but lacks comprehensive analytical regularity theory that is uniform in $\varepsilon$ . The paper aims to prove that under the assumption that the unregularised transport map is bi- $C^{1,\alpha}$ -regular, the regularised transport-like map $T_\varepsilon$ and potentials $f_\varepsilon, g_\varepsilon$ satisfy interior Lipschitz and higher-order estimates that remain bounded as $\varepsilon \to 0$ .

Methodology
The authors employ a multi-scale analysis approach, combining variational methods with structural properties of the transport plans:

Energy Closeness and Quasi-Minimality: The proof begins by establishing that the energy of the regularised problem is close to the unregularised quadratic transport energy, with a specific rate of convergence depending on $\varepsilon$ and the dimension $d$ . This allows the regularised minimisers to be treated as quasi-minimisers of the quadratic transport problem.
Campanato Iteration (Large Scales): For scales larger than a critical length $R_c$ , the authors utilise a Campanato iteration scheme adapted from the variational approach to optimal transportation. This propagates regularity information from the unregularised problem down to the critical scale.
Critical Scale Analysis: A crucial component is the derivation of a critical scale $R_c \approx \varepsilon^{\frac{2}{d(p-1)+2}}$ . Below this scale, the regularisation term dominates. The authors analyse the structure of the transport-like map $T_\varepsilon$ (defined as a weighted mean of the transport plan) on scales smaller than $R_c$ using the specific properties of the regularisation function $h$ .
Support Bounds and Monotonicity: A central technical contribution is the derivation of sharp local bounds on the size of the support of the regularised transport plan. This relies on a general monotonicity principle (cyclical monotonicity adapted for regularised transport) and local $L^\infty$ -bounds. These bounds are used to control "long trajectories" in the transport plan, which is essential for the regularity estimates.
Affine Invariance: The authors utilise affine changes of coordinates to normalise the problem, allowing them to apply local estimates uniformly across the domain.

Key Contributions and Results

Uniform Regularity Estimates: The main result (Theorem 3) establishes that if the unregularised transport map $T$ $T$ is bi- $C^{1,\alpha}$ $C^{1, α}$ -regular, then the regularised transport-like map $T_\varepsilon$ $T_{ε}$ satisfies an interior Lipschitz estimate independent of $\varepsilon$ $ε$ .
- For strictly sub-quadratic regularisation ( $p < 2$ ), $T_\varepsilon$ is shown to be $C^1$ with uniform bounds.
- For entropic regularisation ( $p=1$ ), the potentials are shown to be $C^2$ with uniform bounds.
- These results hold for general convex, superlinear regularisation terms satisfying $h'(0)=0$ .
Support Sparsity and Bias Bounds: The paper derives local bounds on the support of regularised minimisers (Theorem 6). It proves that for $p > 1$ $p > 1$ , the support of the transport plan is sparse, with the deviation from the unregularised transport map bounded by a function of $\varepsilon$ $ε$ . Specifically, the spread of the support is of order $\varepsilon^{\frac{2}{d(p-1)+2}}$ $ε^{\frac{2}{d ( p - 1 ) + 2}}$ .
- This leads to a global bias bound (Corollary 8) showing that $|y - T(x)|$ is small unless $x$ is near the boundary of the support.
- The authors note that for entropic regularisation ( $p=1$ ), $h'(0) \neq 0$ , and the support is full, consistent with known results.
Convergence Results: As a consequence of the uniform estimates, the paper proves the convergence of the regularised transport-like map to the unregularised transport map in $C^{0,1-}_{loc}$ and the potentials in $C^{1,1-}_{loc}$ (Corollary 5).
Improvement on Existing Literature: The authors state that their global bias bounds improve upon the best-known results for quadratic regularisation ( $p=2$ ) found in previous literature (specifically [35]).

Significance and Claims
The paper claims that its estimates are uniform in the regularisation parameter $\varepsilon$ , a property not generally available in the literature for regularised optimal transport, particularly for sub-quadratic polynomial regularisation. The authors emphasise that their approach provides a unified framework for both entropic and polynomial regularisation.

The derivation of sharp local bounds on the support size is presented as a result of independent interest, as it implies global bias bounds and clarifies the transition between the regularised and unregularised regimes. The authors modestly note that while their global bounds are not necessarily sharp in all regimes, they represent an improvement over existing results for quadratic regularisation. The convergence results are highlighted as particularly relevant for applications, providing a rigorous justification for the stability of regularised transport plans as $\varepsilon \to 0$ .

The work relies on the assumption that the unregularised transport map is bi- $C^{1,\alpha}$ -regular, a condition satisfied, for instance, when the supports of the measures are convex (citing [6]). The paper does not propose new numerical algorithms or experimental validations but focuses on the analytical foundations that underpin the stability and convergence of regularised transport methods.