Optimal transport (OT) compares two collections of mass, such as pixels of a predicted density map and annotated head locations, by computing the cheapest way to move one onto the other. It is increasingly used as a training loss and as a layer inside networks. The usable versions add two modifications. The first is entropic smoothing, which blurs the transport plan so it can be computed by the fast Sinkhorn iteration and differentiated. The second is an "unbalanced" relaxation, which lets mass be created or destroyed so outliers and count mismatches do not force bad matches. Both modifications silently fix an absolute scale.
That fixed scale has a visible consequence. If you feed the same problem with ten times more mass, for example a crowd image with 2,000 people instead of 200, the computed plan does not just get ten times heavier. Its shape changes. The solver also stops at a different level of accuracy, because the stopping tolerance is a fixed number. The gradients sent back to the network therefore depend on how much mass is in the batch, not only on the geometry.
This note proposes one piece of work with two parts. The first part is a memory-efficient implicit backward pass for a mass-homogeneous unbalanced OT model. The second part is a cheap, scale-free check on gradient quality that falls out of homogeneity itself. For a loss $L(a,b)$ on nonnegative mass vectors $a, b$ that is 1-homogeneous, meaning $L(\lambda a,\lambda b)=\lambda L(a,b)$ for every $\lambda>0$, Euler's theorem for homogeneous functions gives the identity
$$ \langle \nabla_a L, a\rangle + \langle \nabla_b L, b\rangle = L(a,b). $$
Here $\nabla_a L$ and $\nabla_b L$ are the gradients with respect to the two mass vectors. The identity holds exactly at convergence. Truncated or loosely converged solvers violate it. The normalized violation
$$ r = \frac{|\langle \nabla_a L, a\rangle + \langle \nabla_b L, b\rangle - L|}{|L|} $$
is dimensionless and costs one inner product per side. The proposal is to use $r$ both as a stopping rule and as a diagnostic, and to test whether it tracks true gradient error better than the fixed-tolerance and fixed-iteration rules practitioners use now.
Core Claim
Two papers motivate the work. An Homogeneous Unbalanced Regularized Optimal Transport Model builds HUROT, which replaces the static reference measure in the entropic penalty with versions of the inputs renormalized by their total mass. Lacombe proves HUROT is exactly 1-homogeneous and shows that standard unbalanced plans change structure under mass scaling while HUROT plans only rescale. The same paper states explicitly that fixed numerical stopping tolerances reintroduce inhomogeneity in software. It gives no way to differentiate HUROT efficiently.
A Unified Framework for Implicit Sinkhorn Differentiation supplies the method we reuse. It differentiates through the optimality conditions of balanced entropic OT, using the implicit function theorem plus a Schur-complement reduction. Its backward memory is independent of the iteration count, and it proves a gradient error bound proportional to forward convergence error. That bound is exactly why a scale-dependent stopping rule matters: under mass rescaling, the forward error, and with it the gradient error, drifts with batch mass. The framework also assumes balanced, fixed marginals and a static reference measure.
Our claim has three parts. First, HUROT admits an implicit backward pass with iteration-independent memory. This backward pass must account for an extra dependence that balanced implicit differentiation never sees: the reference measure itself depends on the total masses $\sum a$ and $\sum b$. Second, the Euler residual $r$ gives a stopping rule under which forward accuracy and gradient accuracy are invariant to mass rescaling by construction. Third, on tasks where per-example mass varies by orders of magnitude, this removes a source of error that is currently absorbed by per-dataset tuning of the smoothing strength. Crowd counting is the clearest such task, because total mass is the person count.
The residual is only one scalar, so it cannot certify the full gradient direction. Whether it is a useful proxy is an empirical question the experiments settle directly.
Research Program
Backward pass. We will derive the backward pass for HUROT with the Kullback-Leibler and total-variation marginal penalties studied by Lacombe. The unbalanced optimality conditions replace hard marginal constraints with smooth fixed-point equations on the dual potentials. The implicit system is therefore a perturbation of the balanced one, and we expect the Schur-complement reduction to carry over with an added rank-one term from the mass normalization. We will verify the analytic gradient against finite differences and against unrolled automatic differentiation run to high precision in float64.
Theory. We will prove that the Euler residual of the implicit gradient is bounded by the forward fixed-point error, following the style of Eisenberger et al.'s Theorem 5. Because $r$ is dimensionless, a stopping threshold on $r$ yields iteration counts that are invariant to mass rescaling. Numerically, this holds when HUROT is run in the log domain, so float32 underflow does not itself depend on scale.
Non-convexity. HUROT is not convex in the input measures, which Lacombe flags as open. We do not solve this. We will report whether it matters in practice when the inputs are network outputs, by measuring how often gradient steps increase the loss.
Extensions. A companion analysis will check whether the same Euler check applies to the 2-homogeneous unbalanced Gromov-Wasserstein divergence of The Unbalanced Gromov Wasserstein Distance. There, the right-hand side of the identity becomes $2L$. We treat this as an extension, not a core deliverable.
Scope. We deliberately do not attack the quadratic memory of the cost matrix. Sub-quadratic kernels such as LCN-Sinkhorn from Scalable Optimal Transport in High Dimensions are orthogonal, and combining them with unbalanced penalties raises separate stability issues that Gasteiger et al. already document.
Baselines
Naive and published reference. The naive reference is a pixelwise squared-error density loss for counting. The published comparison point is the unbalanced OT loss of A Generalized Loss Function for Crowd Counting and Localization, which reports MAE 79.3 on NWPU-Crowd against a previous best of 88.4, and a localization F-measure of 0.763 on UCF-QNRF. That loss uses a standard unbalanced OT formulation with fixed smoothing, making it the strongest existing competitor on exactly our question. We will reproduce it with its backbone, data splits, and training schedule. We will replace only the transport loss and its solver, and give every variant the same hyperparameter search budget over smoothing strength and marginal penalty. Beating it means lower MAE on NWPU-Crowd and a higher F-measure on UCF-QNRF, averaged over three seeds. We additionally require that the gain concentrate in the extreme count bins, since that is where the mechanism predicts it.
Strongest differentiation method. The strongest differentiation baseline is balanced implicit Sinkhorn from A Unified Framework for Implicit Sinkhorn Differentiation, applied after normalizing inputs to unit mass. Its reported memory is below 1GB regardless of iteration count, against nearly 16GB for unrolled automatic differentiation at $n=1000$ and 1000 iterations. Our backward pass should match this memory profile while handling unbalanced inputs.
Unrolled HUROT. Unrolled automatic differentiation through HUROT isolates the backward-pass contribution. It should give nearly identical gradients at far higher memory cost.
Ablations. Three ablations isolate the stopping rule. HUROT with implicit gradients is stopped by our Euler residual, by a fixed iteration cap as in pixel-level Sinkhorn layers such as Rethinking the Correlation in Few-Shot Segmentation, or by a marginal tolerance divided by total mass. A fourth ablation keeps the standard unbalanced loss but rescales the smoothing and marginal penalties per example by total mass. This tests whether a heuristic achieves what HUROT's renormalization does.
Why not just…?
Why not just normalize every input to unit mass and use balanced implicit Sinkhorn? For balanced problems this is correct and sufficient, and we make no claims there. In counting and partial matching, however, the mass difference is the signal. Normalizing a predicted density to sum to one discards the count error the loss is supposed to penalize. Lacombe and Séjourné et al. show that forcing unit mass makes outliers absorb real mass and distorts matchings. The normalized balanced baseline is included so this is measured on our tasks rather than asserted.
Why not just divide the stopping tolerance by the total mass? This is a real threat. For the forward pass alone it may work as well as the Euler rule. But in unbalanced problems, marginal violation is not a convergence measure, because marginals are never enforced exactly. What we ultimately care about is gradient accuracy, not marginal accuracy. The relative-tolerance ablation is run head to head against the Euler rule on gradient error versus a float64 reference. If the two tie, we will report that the simpler rule suffices and keep the Euler residual only as a diagnostic.
Why not just tune the smoothing strength per dataset, as current OT losses do? Per-dataset tuning cannot fix a within-dataset effect. NWPU-Crowd images differ in count by orders of magnitude, so one smoothing value is too sharp for sparse images and too blurry for dense ones. If stratifying the reproduced baseline's error by count shows no concentration at the extremes, the premise of this proposal is wrong on real data. That stratification is the first experiment we run.
Why not just rescale the smoothing and penalties by mass per example? Scaling the parameters correctly is essentially what HUROT's renormalized reference does. If the heuristic ablation matches HUROT, then homogeneity is cheap to obtain. In that case the contribution narrows to the memory-efficient unbalanced backward pass and the gradient check, and we will say so.
Proposed Experiments
Controlled synthetic study. We scale both input measures by $\lambda$ from $10^{-2}$ to $10^{3}$, in the optimal-transport-with-boundary setup of Lacombe and on 2D point clouds with injected outliers. We record four quantities: plan structure after dividing by $\lambda$, the number of iterations each stopping rule uses, relative gradient error against a float64 reference, and peak backward memory. The decisive check has two conditions. Under the Euler rule, iteration count and gradient error should be flat in $\lambda$, while fixed-iteration and fixed-tolerance rules drift. Across all runs, $r$ should rank-correlate with true gradient error more strongly than marginal violation does. If $r$ correlates weakly, the certificate claim is dropped.
Registration. The second setting is partial-visibility rigid registration on ModelNet40, following the registration-network setup in Eisenberger et al. The balanced baseline is forced to match points that are not visible in the other scan, so this tests whether unbalanced implicit gradients help registration error at matched memory.
Crowd counting. The third setting is crowd counting on NWPU-Crowd and UCF-QNRF against the Wan et al. loss, with results stratified by count bin as described above.
Partial domain adaptation (optional). Optionally, we will run partial domain adaptation on Office-Home against the relative-mass-budget method of Improving Mini-batch Optimal Transport via Partial Transportation. The file reports only its gains over standard mini-batch OT (5.75% on Office-Home, plus a 2.02% average partial-adaptation improvement), not absolute accuracies. We therefore reproduce it before comparing. Its mass fraction is already scale-invariant, so this setting tests whether end-to-end differentiable homogeneous transport can replace its grid-searched, non-differentiable CPU stage.
References
- An Homogeneous Unbalanced Regularized Optimal Transport Model with Applications to Optimal Transport with Boundary
- A Unified Framework for Implicit Sinkhorn Differentiation
- The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
- Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More
- A Generalized Loss Function for Crowd Counting and Localization
- Rethinking the Correlation in Few-Shot Segmentation: A Buoys View
- Improving Mini-batch Optimal Transport via Partial Transportation