Models trained on synthetic images, such as renderings of 3D CAD models or frames from a video game, lose much of their accuracy on real photographs. A standard fix is to pull the two feature distributions together with optimal transport (OT), a way of measuring how much "mass" must move, and how far, to turn one distribution into another. Exact OT between $N$ synthetic and $N$ real samples costs roughly $O(N^3)$. That is hopeless for a benchmark like VisDA-2017, with about 152,000 synthetic and 55,000 real images, and even worse for per-pixel segmentation features. Every deep OT method for domain adaptation therefore computes transport inside small random minibatches. This discards the global structure of both datasets, and within a batch it forces unrelated classes to be matched to each other.
We propose to replace the flat feature space with a learned hierarchical tree over a memory of all source and target features. On a tree, the OT distance has an exact closed form: a weighted sum, over tree edges, of how much source and target mass sits below each edge. It costs time linear in the number of samples. This makes it possible to align the entire synthetic dataset with the entire real dataset at every training step, for about the cost of a minibatch method. The per-edge mass differences also say which semantic subtrees carry the domain gap. The central empirical question is whether global alignment beats minibatch alignment at equal compute. It must also beat the obvious cheap global alternative, OT between cluster centroids. If it does not, the tree is not earning its place.
Core Claim
The limiting factor in OT-based sim-to-real adaptation is not transport fidelity inside a batch but the loss of global coordination forced by cubic cost. A tree-Wasserstein distance computed over the whole feature bank, with soft and differentiable leaf assignments and a relaxed per-node mass constraint, restores that coordination in $O(N)$. Our prediction is that it will beat minibatch OT and minibatch unbalanced OT on synthetic-to-real benchmarks at matched compute. We expect the gap to be largest when batches are small or when the target lacks some source classes.
How This Relates to Prior Work
Several papers motivate the proposal by exposing the minibatch problem. Optimal Transport for Domain Adaptation framed adaptation as transporting source mass to the target, with class-sparsity regularization. Its exact linear program is cubic, and even its entropic (Sinkhorn) variant needs a full $N \times N$ cost matrix. DeepJDOT moved OT into a joint deep feature-and-label space and made it tractable by solving transport per minibatch, reaching 66.9% mean accuracy on VisDA-2017. Unbalanced minibatch Optimal Transport (JUMBOT) showed that forced mass conservation inside a batch causes wrong pairings. Relaxing the marginals raised Office-Home accuracy from 63.5% (their DeepJDOT run) to 70.0%, with large gains in partial adaptation. JUMBOT treats the symptom locally but leaves each batch blind to the rest of the data, and it is sensitive to its marginal penalty $\tau$ and entropic parameter $\epsilon$. We keep JUMBOT's joint feature-label cost and its unbalanced relaxation. What we remove is the batch.
Sliced Wasserstein Discrepancy avoids cubic cost differently: it projects classifier outputs onto random 1D lines, where OT reduces to sorting. It reports 76.4% on VisDA-2017 and 44.5 mIoU on GTA5→Cityscapes. It still works per batch and discards multi-scale structure. A tree keeps coarse-to-fine grouping that random 1D projections average away.
Our method comes from the tree-Wasserstein literature. UltraTWD learns tree topology and edge weights so that tree distances approximate a given cost matrix. Supervised Tree-Wasserstein Distance makes leaf-to-parent assignment differentiable through a softmax and runs in linear time on a GPU. Both papers were evaluated only on document benchmarks with fixed word embeddings. Neither handles features that change during training or compares two domains. UltraTWD's $O(n^2)$ minimum-spanning-tree construction is itself too slow for 200k points. STW, for its part, fixes the internal topology. Those limitations shape our design: we rebuild coarse topology periodically and learn only soft leaf assignments by gradient descent.
Method
We keep a feature bank holding the current embedding of every source and target sample. Embeddings are refreshed with a momentum encoder so the bank does not go stale. Every few thousand steps we rebuild a tree over the bank using hierarchical k-means, for example branching factor 16 and depth 4. This costs $O(N K \cdot \text{depth})$, where $K$ is the branching factor. Internal node heights are set so the tree is an ultrametric, meaning the distance between two leaves is determined by the height of their lowest common ancestor. Between rebuilds, each sample $x$ is assigned softly to nodes by a softmax over distances from its feature $g(x)$ to node centroids, in the style of STW. That makes the subtree masses differentiable in the features.
Let $\mu_s(v)$ and $\mu_t(v)$ be the total source and target mass under node $v$, and let $w_v$ be the length of the edge above $v$. The balanced tree distance is
$$ \mathrm{TW}(\mu_s,\mu_t) = \sum_{v} w_v \,\bigl|\mu_s(v) - \mu_t(v)\bigr|, $$
which is exact OT under the tree metric. Mass difference that cannot be matched inside a subtree must travel up through edge $v$, and that is all the formula counts. For the unbalanced version we charge each node a penalty $\tau$ per unit of mismatched mass that is created or destroyed rather than transported. This yields a closed form computable in a single bottom-up pass, and it plays the role of JUMBOT's KL relaxation. To align labels as well as features, we attach a second tree cost term computed over source labels and target pseudo-labels, as in the joint cost of DeepJDOT. The gradient on a minibatch flows only through that batch's soft assignments. The masses it is compared against come from the full bank, and that is where the global coordination comes from.
The per-node residuals $w_v|\mu_s(v)-\mu_t(v)|$ give a localized picture of the gap. They show which feature clusters have too much synthetic mass and too little real mass. We will report whether these residuals concentrate on classes known to be hard, and whether reweighting the loss toward them helps.
Research Program
The work has three parts. The first is a fidelity study. On 5,000-point subsamples of VisDA-2017 features, exact OT is still affordable, so we can measure how well tree distances and the gradients they induce track exact OT as depth, branching factor, and rebuild frequency vary. We run this before any adaptation experiment, because STW's slight underperformance of exact OT on text is a warning. The second is the main adaptation comparison under a fixed backbone and budget. The third is the large-$N$ regime, dense GTA5→Cityscapes segmentation. There the number of pixel features runs into the millions, so minibatch methods see only a tiny fraction of the distribution per step. If globality matters anywhere, it should matter there.
Baselines
The naive reference point is source-only training on the same backbone, with no alignment. The VisDA dataset paper (VisDA) reports AlexNet falling from 99% on synthetic data to 28% on real COCO images, and source-only segmentation at 21.4 mIoU. We re-run source-only with our own backbone rather than borrow those numbers.
The most directly competing method is JUMBOT, since it shares our joint cost and unbalanced relaxation and differs only in using minibatches. For VisDA-2017, no reported JUMBOT result was found on Lacuna. The file gives JUMBOT 70.0% on Office-Home, and that is the number we must beat there. We will run JUMBOT and DeepJDOT from their public formulations on the same ResNet-50 backbone, with the same augmentation, the same number of training steps, and the same hyperparameter search budget (an equal number of trials over $\tau$, $\epsilon$, and loss weight for them, and over $\tau$, depth, and loss weight for us). We match wall-clock time per epoch as well as step count, and report both. DeepJDOT's reported 66.9% on VisDA-2017 is the floor for any OT method here.
SWD is the strongest linear-time competitor, with 76.4% on VisDA-2017 and 44.5 mIoU on GTA5→Cityscapes in its paper. We re-run it on our backbone with its recommended 128 projections.
The strongest number in the file overall is CDTrans at 88.4% on VisDA-2017 (CDTrans). Its gains come mainly from a transformer backbone and center-aware pseudo-labeling, not from a distribution distance. We do not claim to beat it with a ResNet. Instead, we test tree alignment as an added loss on the same transformer backbone with the same pseudo-labeling pipeline. Improving on our own re-run of that pipeline counts as success. We will also report the gap to the published 88.4%.
Two ablations isolate the key ingredient. The first is the same tree-Wasserstein loss computed only on the current minibatch, with no bank. If this matches the global version, globality is not what helps. The second is flat unbalanced Sinkhorn between the full bank's k-means centroids, the obvious cheap global method. If this matches the tree, the hierarchy is not what helps. Success means the global tree beats both ablations and JUMBOT at matched compute on VisDA-2017 and on partial-domain Office-Home, with non-overlapping confidence intervals across three seeds.
Why not just…?
Why not just use JUMBOT with a larger batch? Larger batches reduce the minibatch artifact, and this is a real threat: if JUMBOT at batch size 512 matches our method, the argument for going global weakens. We will sweep batch size from 32 to the GPU memory limit for JUMBOT and for our method. We expect JUMBOT's accuracy to depend strongly on batch size and ours to depend weakly. We will also report where the two curves meet, if they do. Even at the largest batch, JUMBOT's per-step cost grows quadratically in batch size, while ours stays linear in the bank.
Why not just use sliced Wasserstein? It is already linear-time and simple. Its reported 76.4% on VisDA-2017, however, relies on a three-player adversarial setup, and it aligns only per-batch classifier outputs using random 1D projections. The head-to-head re-run on the same backbone settles this directly. We will also run a variant that computes SWD against the whole bank, which separates "global" from "tree" for the slicing family too.
Why not just run OT on cluster centroids? Clustering each domain into a thousand prototypes and running Sinkhorn between them gives global coordination cheaply. It is the alternative most likely to match us, because a tree is essentially nested clustering. This is exactly the second ablation above. If flat centroid OT performs as well, we will report that the benefit comes from global prototypes and drop the hierarchy claim. The tree should win only if mismatch occurs at several scales at once, as with coarse vehicle-versus-animal shifts alongside fine texture shifts. The per-level breakdown of residuals will show whether that happens.
Why not just self-train on pseudo-labels? Pseudo-labeling produced the 92.8% VisDA challenge winner and the CDTrans result, so the file shows it is the dominant strategy. Our method does not compete with it. We use it as a companion, and the transformer experiment tests whether tree alignment adds anything on top. If it adds nothing, the method's value reduces to settings where pseudo-labels are unreliable, such as early training or the partial-adaptation split. We would report that narrower result plainly.
Decisive Checks
We will judge the project by three results. On VisDA-2017 at a fixed ResNet-50 budget, the global tree loss must beat JUMBOT and the minibatch-tree ablation, and its accuracy must degrade less as batch size shrinks. On partial-domain Office-Home, it must exceed JUMBOT's reported 70.0% regime on the standard split under our re-run. On GTA5→Cityscapes, where the number of pixel features makes batching most harmful, it must beat our re-run of SWD's 44.5 mIoU setup at equal cost. If the centroid-Sinkhorn ablation matches the tree on all three, the conclusion is that global coordination matters and the tree does not, and we will publish it in those terms.
References
- Optimal Transport for Domain Adaptation
- DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation
- Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
- Sliced Wasserstein Discrepancy for Unsupervised Domain Adaptation.
- UltraTWD: Optimizing Ultrametric Trees for Tree-Wasserstein Distance
- Supervised Tree-Wasserstein Distance
- VisDA: The Visual Domain Adaptation Challenge
- CDTrans: Cross-domain Transformer for Unsupervised Domain Adaptation