Research map / Learning theory and algorithms / Optimal transport
Hierarchical Refinement: Optimal Transport to Infinity and Beyond
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Hierarchical Refinement (HiRef), which recursively co-clusters two equal-size datasets with low-rank OT subproblems to recover a full-rank Monge map in linear space and log-linear time.
Problem
Computing full-rank (one-to-one) optimal transport between large datasets: Sinkhorn needs quadratic memory, low-rank OT cannot produce bijections, and mini-batch OT is biased.
Approach
Optimal low-rank factors co-cluster each point with its Monge image, so recursively partitioning both datasets with rank-r low-rank OT subproblems (uniform inner marginal) yields a bijective Monge map at the finest scale in linear space and log-linear time.
Key results
- On ImageNet (1.281M points, 2048-d embeddings), HiRef achieves OT cost 18.97 versus 19.58 for mini-batch OT (B=1024) and 24.12 for FRLC (r=40).
- On 1024-pair synthetic alignments, HiRef outputs a bijection with exactly 1024 nonzero entries, whereas Sinkhorn and ProgOT have 624,733 to 678,720 and 271,087 to 337,258 nonzeros.
- HiRef scales to 2^20 points per dataset (2,097,152 points aligned) on Half-Moon and S-Curve, while Sinkhorn and ProgOT run only up to 16,384 points.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HiRef instead of MB 1024 | ImageNet alignment · ImageNet alignment | primal OT cost: 19.58 -> 18.97 | Helped |
| Use HiRef instead of MB 1024 | MOSTA transcriptomics alignment · E12-13.5, E13-14.5, E14-15.5, E15-16.5 | Kantorovich cost: 14.45 -> 14.35; 13.86 -> 13.78; 14.43 -> 14.29; 12.91 -> 12.79 | Helped |
| Use HiRef instead of FRLC | ImageNet alignment · ImageNet alignment | primal OT cost: 24.12 -> 18.97 | Helped |
| Use HiRef instead of FRLC or LOT | MERFISH brain atlas alignment · Five spatially-varying genes | cosine similarity | Helped |
| Refine coarse low-rank couplings hierarchically | HiRef · Synthetic datasets | primal OT cost | Helped |
| Use HiRef instead of MOP | Synthetic datasets · Checkerboard, MAF Moons & Rings, and Half Moon & S-Curve | primal OT cost | Helped |
| Use HiRef instead of Sinkhorn or ProgOT | Full-rank OT alignment · Synthetic datasets with 1024 aligned pairs | number of non-zero coupling entries: 1024 vs 624733 to 678720 and 271087 to 337258 | Helped |
Surprising findings
- HiRef often matches or slightly beats Sinkhorn's primal cost despite producing a bijection, while Sinkhorn yields a dense coupling.
- On MOSTA, HiRef's cost is lower than the low-rank FRLC even though HiRef uses FRLC as its subroutine.
Limitations
- Assumes both datasets have the same number of samples.
- Constant factors from the low-rank OT subroutine are large; practical solvers are non-convex and not guaranteed optimal.
Experimental setup
Datasets: Half-Moon and S-Curve Checkerboard MAFMoons and Rings MOSTA mouse organogenesis spatiotemporal transcriptomics MERFISH mouse brain atlas ImageNet ILSVRC
Benchmarks: Half-Moon and S-Curve Checkerboard MAFMoons and Rings MOSTA MERFISH ImageNet
Metrics: primal OT cost Wasserstein-1 Wasserstein-2 number of non-zero coupling entries runtime scaling cosine similarity of transferred gene expression
Baselines: Sinkhorn ProgOT mini-batch OT LOT FRLC MOP dual revised simplex
Builds on: Sinkhorn algorithm FRLC multiscale optimal transport (Gerber and Maggioni) ProgOT
Closest papers by meaning
- Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling (NeurIPS 2024 · similarity 0.90)
- Hierarchical Optimal Transport for Multimodal Distribution Alignment (NeurIPS 2019 · similarity 0.90)
- Double-Bounded Optimal Transport for Advanced Clustering and Classification (AAAI 2024 · similarity 0.87)
- Progressive Entropic Optimal Transport Solvers (NeurIPS 2024 · similarity 0.86)
- A Biconvex Formulation for Stable Transport of Mixture Models with a Unique Solution (NeurIPS 2026 · similarity 0.86)
- Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.