📊 statistics

Minimax Optimal Estimation of Transport-Growth Pairs in Unbalanced Optimal Transport

This paper establishes the statistical foundation for Monge-type estimation in unbalanced optimal transport by introducing the concept of transport-growth pairs, proposing two minimax optimal estimators for them, and proving their optimality through a novel value-based stability reduction and matching lower bounds.

Original authors: Donlapark Ponnoprat, Noboru Isobe, Masaaki Imaizumi

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Donlapark Ponnoprat, Noboru Isobe, Masaaki Imaizumi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 Movers Who Also Build and Demolish

Imagine you are a logistics manager. Your job is to move a pile of sand (Source) to a construction site (Target).

The Old Way (Balanced Transport):
In the classic version of this problem, the amount of sand you start with must exactly equal the amount of sand you end up with. If you have 100 tons of sand, you must deliver exactly 100 tons. You just need to figure out where to move each grain. This is called Optimal Transport (OT). Mathematicians have been very good at this for a long time.

The New Reality (Unbalanced Transport):
But in the real world, things aren't always so neat.

Maybe you start with 100 tons of sand but the construction site only needs 80 tons (you have to throw away 20).
Maybe you start with 50 tons but the site needs 100 tons (you have to bring in more from a quarry).
Maybe some sand disappears into a sinkhole, or new sand is magically created.

This is Unbalanced Optimal Transport (UOT). The paper argues that to solve this, you can't just look for a "moving map" (where to send the sand). You also need a "growth map" (how much to multiply or shrink the sand at each spot). The authors call this a Transport-Growth Pair.

The Problem: How Do We Learn the Rules from a Sample?

In the real world, we rarely know the exact amount of sand at every single point. We only have a bucket of samples (a few handfuls of sand from the source and a few from the target).

The big question the paper asks is: If we only have a few samples, how accurately can we guess the true "Moving Map" and the true "Growth Map"?

Previous research had some guesses, but they were either too slow, didn't work for high dimensions, or didn't prove that they were the best possible way to do it.

The Solution: Two New Tools

The authors developed two new "estimators" (tools to guess the maps) and proved they are the best possible tools for the job.

1. The "Plan-Based" Estimator (The Discrete Solver)

How it works: Imagine you have a grid of dots representing your sand samples. You draw lines connecting the source dots to the target dots to minimize the total distance traveled, while allowing some dots to disappear or multiply.
The Metaphor: Think of this like a connect-the-dots puzzle. You connect the dots you have, and then you fill in the gaps between them using a "nearest neighbor" rule (if you are standing near a dot, you assume the rules are the same as that dot).
Best for: High-dimensional data (like 3D shapes or complex images) where the data is messy and doesn't follow a smooth pattern.

2. The "Kernel-Based" Estimator (The Smooth Painter)

How it works: This method assumes the sand distribution is "smooth" (like a gentle hill rather than a jagged mountain). It uses a special mathematical brush (a "kernel") to paint a smooth density map over the data before calculating the transport.
The Metaphor: Instead of connecting dots, imagine smoothing out a rough sketch. You take your noisy samples and use a brush to create a smooth, continuous picture of where the sand likely is. Then you calculate the move and growth based on that smooth picture.
Best for: Data that is known to be smooth. Because it assumes smoothness, it learns much faster and more accurately than the first method.

The "Secret Sauce": Stability and the Gap

How did they prove these tools are the best?

In math, proving something is the "best" usually involves two steps:

Upper Bound: Showing your tool works at least this well.
Lower Bound: Showing that no one can possibly do better than this.

The authors' main technical breakthrough was a "Stability Reduction."

The Analogy: Imagine you are trying to measure the stability of a house of cards. If you push the table (perturb the data), how much does the house wobble?
The authors found a way to translate the "wobble" of the entire complex system (the UOT objective) directly into the errors of the Moving Map and the Growth Map. They proved that if your data is slightly off, the error in your map grows in a predictable, controlled way. This allowed them to prove that their tools hit the theoretical speed limit of accuracy (the Minimax Optimal Rate).

What Did They Find?

The "Growth" Factor Matters: You cannot ignore the fact that mass is created or destroyed. If you try to force a "balanced" solution on an "unbalanced" problem, you get the wrong answer. You must estimate both the move and the growth.
The Smooth Method is a Winner: If your data is smooth, the "Kernel-Based" estimator is incredibly efficient. It learns the rules much faster as you add more samples compared to the "Plan-Based" method.
Proven Optimality: They didn't just say "this works well." They proved mathematically that you cannot invent a better tool than theirs for these specific conditions. They hit the "speed limit" of statistical estimation.

Real-World Test (The Experiments)

The authors tested their tools on two things:

Simulated Data: They created fake sand distributions with known rules and checked if their tools could find them. The tools worked perfectly, matching the theoretical predictions.
3D Shape Completion: They used the tools to fix broken 3D models of chairs and cars.
- The Challenge: The input data had "outliers" (broken cars mixed in with chairs).
- The Result: The "Plan-Based" method tried to force the broken cars to look like chairs. The "Kernel-Based" method, however, realized the cars didn't fit the pattern and effectively "ignored" them (growth factor close to zero), successfully reconstructing the chairs while discarding the noise.

Summary

This paper provides the mathematical "rulebook" for moving things when the amount of stuff changes during the move. They built two new calculators to figure out the rules from limited data and proved that these calculators are the fastest and most accurate possible. It turns out that to move things correctly when mass is created or destroyed, you need to estimate the "move" and the "growth" simultaneously, and they showed exactly how to do that optimally.

Technical Summary: Minimax Optimal Estimation of Transport-Growth Pairs in Unbalanced Optimal Transport

Problem Statement
Unbalanced Optimal Transport (UOT) extends classical Optimal Transport (OT) to scenarios where the total masses of the source and target measures differ, or where mass creation/destruction is intrinsic to the phenomenon. While computational frameworks for UOT (e.g., entropy-transport formulations, Sinkhorn-type solvers) are well-established, the statistical theory for estimating Monge-type objects in UOT remains underdeveloped.

In balanced OT, the statistical target is a transport map $T$ . In UOT, however, the natural population target is not a map alone but a transport-growth pair $(T_0, \lambda_0)$ , where $T_0$ is the transport map and $\lambda_0$ is a growth factor (weight) that rescales mass after transport to reconcile mass discrepancies. The paper addresses the statistical estimation of this pair from finite samples, aiming to establish minimax optimal convergence rates and provide a rigorous foundation for Monge-type estimation in the UOT setting.

Methodology
The authors study UOT with quadratic cost and Kullback-Leibler (KL) marginal penalties. They propose two distinct estimators for the transport-growth pair, tailored to different data regimes:

Plan-Based Estimator (1NN):
- Approach: Solves the discrete Kantorovich problem under empirical measures to obtain an optimal transport plan matrix. It then constructs the transport map via Fréchet projection (barycentric projection) of the plan rows and estimates the growth factor using the ratio of fitted row masses to empirical source masses, adjusted by the transport cost.
- Extension: The discrete estimates at sample points are extended to the entire domain using a nearest-neighbor (Voronoi) method.
- Applicability: Designed for general cases, including high-dimensional data where density smoothness is not assumed.
Kernel-Based Estimator:
- Approach: Assumes the measures have smooth densities on a hypercube $\Omega = [0, 1]^d$ . It first estimates the densities using a boundary-adapted kernel density estimator based on a cosine basis (Neumann kernel), which avoids the periodicity assumptions required by standard Fourier methods.
- Estimation: The transport-growth pair is estimated by solving the UOT problem between the smoothed density estimates (plug-in approach).
- Applicability: Adaptive to the smoothness of the underlying densities, offering faster convergence rates in smooth regimes.

Key Technical Contributions
The paper's primary technical innovation is a value-based stability reduction. Unlike balanced OT, where semi-dual potentials can be used to bound transport errors directly, UOT involves a growth map that complicates the error analysis. The authors:

Derive a first-order expansion of the UOT objective under perturbations of the marginals.
Establish a stability bound that converts perturbations of the UOT value into separate risks for the transport map and the growth factor.
Introduce a "UOT gap condition" (Lemma 2) that relates the dual potential gap to the squared distance between the estimated and true transport maps, isolating the UOT-specific analytic steps from the choice of marginal estimator.

Main Results
The authors derive upper bounds on the estimation error for both estimators and prove matching lower bounds to establish minimax optimality.

Plan-Based Estimator Rates: The estimation error converges at a rate determined by the Wasserstein distance of the empirical measures. For dimension $d \ge 5$ , the rate is $\tilde{O}(N^{-2/d})$ , where $N = \min(n, m)$ . This matches the rate for balanced OT in high dimensions but applies to the joint estimation of the transport and growth maps.
Kernel-Based Estimator Rates: Under smoothness assumptions (Hölder class $C^\alpha$ ), the kernel estimator achieves a rate of $\tilde{O}(N^{-2\alpha/(2\alpha - 2 + d)})$ . This rate improves upon the plan-based estimator by mitigating the curse of dimensionality through density smoothness.
Minimax Optimality: The paper establishes a minimax lower bound for the smooth hypercube regime that matches the upper bound of the kernel-based estimator (up to logarithmic factors). This confirms that the proposed estimators are statistically optimal.
Mass Estimation: The analysis explicitly accounts for the error in estimating total masses ( $M_\mu, M_\nu$ ), showing that if mass estimators converge at parametric rates, they do not degrade the overall convergence rate of the transport-growth pair.

Significance and Claims
The paper claims to provide the first statistical foundation for Monge-type estimation in unbalanced optimal transport. Its significance lies in:

Reframing the Target: Correctly identifying the transport-growth pair as the fundamental statistical object in UOT, rather than just a transport map.
Optimality: Proving that estimators can achieve minimax optimal rates, improving upon existing evaluations (e.g., [VV22, VV23]) which focused on semi-dual potentials or provided suboptimal rates for Monge maps.
Methodological Advancement: Introducing a stability-based proof technique that circumvents the limitations of semi-dual potential arguments in the presence of mass penalties, enabling the evaluation of optimality for the full Monge-type solution.

Experimental Validation
Theoretical results are supported by simulations on synthetic data and an application to 3D shape completion.

Synthetic Data: Experiments confirm that plug-in estimators (kernel and wavelet) achieve learning rates closely matching the theoretical upper bounds and outperform plan-based estimators and existing baselines (SSUOT) in terms of Mean Squared Error (MSE).
3D Shape Completion: Applied to the Completion3D dataset, the plan-based kernel estimator successfully reconstructs shapes and implicitly rejects outliers (cars) by assigning near-zero growth weights, demonstrating the practical utility of the growth map in handling unpaired data with noise.

Limitations
The authors note that their current setup does not cover entropic regularization, which is a common computational tool in UOT, identifying this as a direction for future work. The theoretical analysis is also restricted to quadratic costs and specific domain geometries (bounded convex domains and hypercubes).