PaperlayerView exact revision on arXiv

Source-linked AI summary

Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions

Wenzhou Xia, Qiaoqiao Ding, Jingwei Liang, Xiaoqun Zhang

arXiv:2609.13010v1cs.LG

TL;DR

Large-scale discrete OT is challenging because its LP has quadratically many transport variables, while sparse methods face a trade-off between costly updates and narrowed search. HELLO uses dual scores to initialize and refine sparse supports hierarchically, with full-space KKT verification. In a GW evaluation, it achieves a lower objective than LOT-GW and runs faster than Sinkhorn-GW on the largest reported instance.

  • Problem

    At million-sample scales, discrete OT has trillions of transport variables, while sparse active-support methods face costly updates or narrowed searches across dimensions.

    Source: §I · pp. 1–2

  • Method

    HELLO propagates coarse dual potentials to initialize candidate edges, then uses dual violations to refine active supports under a linear-size budget.

    Source: §I · p. 2, A. The Overall Framework · p. 3

  • Results

    10.3% lower GW objective than LOT-GW at n = 216; HELLO-GW runs 5.1× faster than Sinkhorn-GW.

    Source: B. Full Scaling Results for… · p. 38

  • Takeaways & Limitations

    HELLO serves beyond discrete OT as an oracle for Gromov–Wasserstein and unbalanced OT, and supports semi-discrete OT and Flow Matching applications.

    Source: §III · p. 6, §V · p. 12

Abstract

from arXiv · show

Optimal transport (OT) compares distributions and aligns datasets in machine learning, yet unregularized discrete OT requires a linear program with quadratically many transport variables. We propose HELLO, a hierarchical solver that casts large-scale discrete OT as edge localization and uses dual potentials to guide both coarse-to-fine initialization and within-level refinement. Initialization propagates coarse dual potentials across a recursive subsampling hierarchy to assign candidate edges. Refinement then iteratively inserts the largest dual violators in each row and column until the relative KKT residual meets a prescribed tolerance, while budgeted pruning ensures linear memory complexity. For exact-arithmetic refinement, we prove finite termination at a global optimum under a symbolic lexicographic rule. At the million-point scale, HELLO attains lower transport objectives with order-of-magnitude runtime improvements over strong baselines across feature dimensions from single digits to thousands. It further scales to 1.28 million samples per marginal in 8192 dimensions on a single H100, using 41.6 GiB peak GPU memory while satisfying a full relative KKT residual below $10^{-6}$. Beyond standard discrete OT, the framework supports general pairwise costs and serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.

I. INTRODUCTION

Discrete OT becomes computationally prohibitive at million-sample scales, while scalable sparse approaches face a trade-off between costly updates and narrowed search. HELLO uses dual scores for hierarchical initialization and refinement, with full-space KKT verification and a linear-size active support.

I. INTRODUCTION

  • At million-sample scales, the discrete OT LP has trillions of variables, making direct exact solution prohibitive in memory and computation.For comparable marginal sizes, the dense representation has quadratic memory complexity.Source: §I · p. 1
  • Sparse OT methods leave open how one signal can guide both initialization and refinement across dimensions without costly updates or narrowed search.Prior hierarchical methods propagate primal supports, while single-scale column-generation approaches use heuristic initialization.Source: §I · p. 2

II. HELLO: DUAL-GUIDED HIERARCHICAL EDGE LOCALIZATION FOR LARGE-SCALE OT

  • HELLO uses dual scores for coarse-to-fine edge assignment and within-level refinement, with a recursive hierarchy and full-space KKT verification.Its budgeted pruning maintains an O(m + n) active support.Source: §I · p. 2, A. The Overall Framework · p. 3

A. The Overall Framework

  • An optimal basic solution has at most m + n − 1 positive entries, framing large-scale OT as locating the edges supporting the coupling.HELLO solves restricted OT over a sparse active support and uses dual violations to update it.Source: A. The Overall Framework · pp. 2–3
  • A restricted optimum is globally optimal when its support contains an optimal plan's support or its dual is feasible on every excluded edge.The paper also proves finite termination at a global optimum for exact-arithmetic refinement under a symbolic lexicographic rule.Source: A. The Overall Framework · p. 2, §I · p. 2

B. Hierarchy

HELLO builds a recursively subsampled hierarchy whose adjacent levels share one side, allowing coarse dual potentials to be inherited for finer-level initialization. The finer supports are ranked by dual scores before restricted OT is solved.

B. Hierarchy

  • Adjacent hierarchy levels share one side so its dual potentials can be inherited directly from coarse to fine.The hierarchy recursively subsamples the larger support and renormalizes retained marginal weights.Source: B. Hierarchy · p. 3

C. Dual-Guided Initialization

  • The initializer propagates adjacent coarse dual potentials and ranks finer-level candidate edges by their dual scores to construct the initial active support.It then solves restricted OT on the constructed support.Source: C. Dual-Guided Initialization · p. 3

1) Dual Propagation:

HELLO carries dual potentials across adjacent hierarchy levels, completing the non-inherited side to form a feasible finer-level pair. It uses the resulting scores to assign initial edges, then augments that support with a feasible basis.

2) Dual Assignment:

  • The same dual-score rule guides coarse-to-fine assignment and within-level refinement, where positive scores identify edges violating full dual constraints.The initial support is followed by restricted solves and active-support updates until the full relative KKT tolerance is met.Source: Figure 1 · p. 4, 1) Dual Propagation · p. 4

1) Dual Propagation:

  • When one support side is retained, its dual potential is inherited and the other side is completed through the c-transform, yielding a finer-level feasible dual pair.The source-retained case is symmetric; the inherited potential's fine-level semi-dual suboptimality is bounded by the Wasserstein distance between adjacent source measures.Source: 1) Dual Propagation · p. 4

2) Dual Assignment:

  • Dual assignment ranks candidate edges using scores from the propagated dual pair, which approximates the finer-level optimum.The support is augmented with a northwest-corner feasible basis before refinement.Source: 2) Dual Assignment · pp. 4–5

D. Dual-Guided Refinement

Refinement uses positive dual scores to find constraints missing from the restricted problem, inserting selected violators and pruning to a linear-size support. It continues until the full-problem relative KKT tolerance is satisfied.

D. Dual-Guided Refinement

  • Refinement alternates restricted OT solves and active-support updates until the prescribed full-problem KKT tolerance is met.Each update detects violated constraints using dual scores and prunes under a linear-size budget.Source: D. Dual-Guided Refinement · p. 5

1) Dual-Violation Detection:

  • Positive dual scores on excluded edges reveal unchecked constraints; inserting a violator imposes its constraint in the next restricted solve.Detection selects the top γ positive violators separately by row and column.Source: 1) Dual-Violation Detection · p. 5

2) Budgeted Pruning:

  • Each support update caps the active support at ⌈β(|I| + |J|)⌉ edges, maintaining O(|I|+|J|) memory.The retained set includes a feasible basis, the current primal support, and detected violators.Source: 2) Budgeted Pruning · p. 5

3) Cost-Perturbed Warm Start:

HELLO uses cost-perturbed warm starts and exact-arithmetic active-support refinement, then applies its balanced-OT oracle to semi-discrete OT, Gromov–Wasserstein, and unbalanced OT. The paper also proposes an averaged dual-potential estimator for semi-discrete OT.

3) Cost-Perturbed Warm Start:

  • For challenging costs such as ℓ1 and ℓ∞, a perturbed-cost auxiliary OT solve reconstructs a fresh support before refinement under the original cost.This warm start discards edges retained only from earlier auxiliary iterations; the final stopping test uses the original cost and prescribed KKT tolerance.Source: 3) Cost-Perturbed Warm Start · p. 5

E. Convergence Analysis

  • Symbolic lexicographic refinement with admissible updates terminates finitely, and its returned coupling’s constant term is globally optimal.The symbolic rule ensures connected feasible supports for the strict-descent argument; it is not instantiated as a floating-point perturbation.Source: E. Convergence Analysis · p. 6

B. Oracle Reductions for GW and UOT

  • For Gromov–Wasserstein and unbalanced OT, HELLO solves balanced-OT oracle subproblems within established outer iterations, using linearized costs or reweighted marginals.The GW implementation maintains O(m + n) storage and cost-factor updates for fixed ambient dimensions.Source: §III · p. 6, B. Oracle Reductions for GW and UOT · p. 7

A. Empirical Dual-Potential Averaging for Semi-Discrete OT

  • HELLO-SDOT gauge-aligns and averages target dual potentials from R independently sampled source batches, processing mR samples with O(m + n) peak memory independent of R.The theorem assumes regularity conditions, exact empirical OT solves, fixed target sites, size n, and marginal b as m grows.Source: A. Empirical Dual-Potential Averaging… · p. 6
  • For large fixed n, typical HELLO-SDOT executions are suggested to have population marginal error Φ(g_m,R) ≈ (n − 1)/(mR).The passage says this scaling is empirically validated and decreases with target size n.Source: A. Empirical Dual-Potential Averaging… · p. 6

IV. EXPERIMENTS

Experiments evaluate HELLO’s accuracy and scalability against exact references and established solvers on synthetic and Gaussian-to-ImageNet problems. HELLO achieves low objective error and KKT residuals in both equal-size and rectangular tests, while recovering the reported ground-truth or optimal edges.

IV. EXPERIMENTS

  • The evaluation covers numerical accuracy, scalability, cost and OT-variant generality, Flow Matching utility, and component contributions and robustness.Primary benchmarks include synthetic Monge problems and Gaussian-to-ImageNet instances reaching n = 1,281,167 and d = 8192.Source: §IV · p. 7

A. Numerical Accuracy against Exact References

1) Equal-Size Problems with Uniform Marginals:

  • On balanced uniform-marginal Monge problems, HELLO achieves objective errors and full KKT residuals below 10−6 with perfect assignment recall across dimensions.Sinkhorn has higher objective errors, while HiRef has severe objective errors and substantial support degradation.Source: 1) Equal-Size Problems with Uniform… · p. 7, Table II · p. 7

2) Rectangular Problems with Non-Uniform Marginals:

  • Across dimensions, HELLO keeps objective errors and full KKT residuals below 10−6 while recovering over 99% of exact optimal edges at precision exceeding 96.7%.These results are for rectangular Gaussian-to-ImageNet instances with non-uniform marginals, compared against exact EMD.Source: 2) Rectangular Problems with… · p. 7

B. Scalability Benchmarks on ImageNet Latents

The benchmarks compare HELLO with scalable OT baselines, characterize runtime and memory scaling, and evaluate its use across pairwise costs and OT variants. HELLO maintains high accuracy while scaling to million-sample problems, with favorable comparisons across the evaluated settings.

1) Runtime–Accuracy Comparison:

  • Across evaluated dimensions, competing configurations matching HELLO’s objective accuracy require one to three orders of magnitude more runtime, with the gap tending to widen as feature dimension increases.The comparison is at n = 2^16, where all compared solvers remain tractable.Source: 1) Runtime–Accuracy Comparison · p. 8

2) Large-Scale Comparison:

  • At the million-point scale, HELLO attains lower transport objectives and shorter runtimes than HiRef in every evaluated setting, with one-to-nearly-two-order improvements.At n = 2^20 and d = 2048, peak GPU memory is 8.7 GiB versus 48.2 GiB for HiRef, an 82.0% reduction.Source: 2) Large-Scale Comparison · p. 8, Table III · p. 9

3) Empirical Scaling and Computational Complexity:

  • HELLO’s runtime shifts from nearly linear in problem size at low dimensions toward quadratic as dimension increases, and grows linearly with feature dimension in the higher-dimensional regime.The empirical model T(n, d) ≈ An + Bn^2d fits measured runtime with R^2 = 0.9985.Source: 3) Empirical Scaling and Computational… · p. 8, Figure 3 · p. 8

4) Complete ImageNet-1k Alignment in 8192 Dimensions:

  • On ImageNet-1k latents with 1,281,167 samples per marginal and d = 8192, HELLO finishes on one GPU in 2526 s with 41.6 GiB peak memory and full relative KKT residual 9.37 × 10^-7.The reported average is over five random seeds.Source: 4) Complete ImageNet-1k Alignment in… · p. 9

1) General Pairwise Costs:

  • Across ℓ1, ℓ2, and ℓ∞ costs and evaluated dimensions, HELLO maintains objective errors and full relative KKT residuals at the 10^-6 level.At large dimensions, ℓ1 and ℓ∞ runtimes are higher, reflecting lower GPU parallelism in their dual pricing.Source: 1) General Pairwise Costs · p. 9, Table IV · p. 9

2) Semi-discrete OT:

  • For semi-discrete OT, empirical potential averaging’s marginal error follows the predicted 1/(4R) scaling in the reported finite-batch experiment.The fit over 32 repetitions is Φ(g_m,R) ≈ 1/(4.206R^0.997).Source: 2) Semi-discrete OT · p. 9, Figure 4 · p. 10
  • At comparable population marginal errors across evaluated scales, HELLO-SDOT reaches the stricter accuracy criterion with a 4.4×–5.8× speedup over Adagrad-SDOT.The comparison uses the first Adagrad-SDOT checkpoint with χ2 < 5 × 10^-2 and the first HELLO-SDOT checkpoint attaining a lower χ2.Source: 2) Semi-discrete OT · p. 9, Table V · p. 10

3) Oracle Reductions for GW and UOT:

  • At the largest evaluated GW scale, HELLO-GW has the lowest objective and shortest runtime, while HELLO-UOT is faster and has a lower optimality gap than Sinkhorn-UOT at its reported scale.For GW at n = 2^16, the objective is 10.3% lower than LOT-GW and runtime is 5.1× faster than Sinkhorn-GW; for UOT at n = 2^17, speedup is 8.1×.Source: 3) Oracle Reductions for GW and UOT · p. 10

D. Downstream Utility in Flow Matching

HELLO’s downstream Flow Matching results are comparable to or better than the reported alternatives, while component comparisons show how hierarchy construction, support updates, and pruning affect performance. The conclusion highlights broad OT applicability and identifies exhaustive dual-violation detection and direct extensions as future work.

D. Downstream Utility in Flow Matching

  • 5.74±0.15 FD for HELLO versus 6.20 ± 0.42 for MB-OT and 6.74 ± 0.68 for independent pairing; HELLO-SDOT also achieves 3.80 FID versus Adagrad-SDOT’s 3.82.The FD results are for discrete-source image translation on FFHQ; the FID comparison is for continuous-source generation on CIFAR-10.Source: HELLO-UOT · p. 10

E. Component Analysis and Robustness

1) Comparisons with Geometry-Based Designs:

  • From d = 4 onward, the dual-guided hierarchy outperforms clustering across all four diagnostics, although clustering performs better on initial errors and refinement iterations at d = 2.Diagnostics are support recall, initial objective error, initial full dual-feasibility residual, and subsequent refinement iterations.Source: 1) Comparisons with Geometry-Based… · p. 10, Figure 5 · p. 11
  • For d ≥4, truncated shielding misses the target tolerance within 200 iterations, while dual-violation detection stays within the support budget and meets tolerance throughout the evaluated range.Without truncation, shielding support grows rapidly with dimension.Source: 1) Comparisons with Geometry-Based… · p. 11, Figure 6 · p. 11

2) Internal Component Ablations:

  • On the evaluated ℓ1 instances, nodewise selection completes HELLO with the lowest runtime, iteration count, and peak support; removing hierarchy or cost perturbation loses convergence and increases runtime.Budgeted pruning enforces a linear-size support budget, but refinement stalls; cost perturbation lowers the best dFeas by two orders of magnitude.Source: 2) Internal Component Ablations · p. 11, Table VII · p. 11

3) Robustness Analyses:

  • Runtime changes from varying ρ and κ stay within a factor of two, while memory and the effects of γ and β remain remarkably stable across the tested dimensions.The study varies ρ, κ, γ, and β across d ∈ {4, 32, 256, 2048}.Source: 3) Robustness Analyses · p. 11

V. CONCLUSION

  • HELLO supports general pairwise costs and is extended to semi-discrete OT, Gromov–Wasserstein, unbalanced OT, and Flow Matching.The paper reports future work on accelerating dual-violation detection without exhaustive pairwise evaluation and directly extending the framework to multi-marginal and unbalanced OT.Source: §V · pp. 11–12

APPENDIX A RESTRICTED-OT FOUNDATIONS, CERTIFICATES, AND

This appendix establishes guarantees and certificates for HELLO’s restricted-OT solves, covering budgeted sparsification and dual potentials inherited across a subsampling hierarchy. It gives a sufficient condition for exact support recovery at the first restricted solve and identifies refinement and the full relative KKT residual as the final certification otherwise.

A. Northwest-Corner Feasible Basis

  • Every active support containing the northwest-corner basis admits its feasible transport plan, so the corresponding restricted OT problem is feasible.The basis is constructed for positive balanced marginals; its inclusion in the active support may be strict under degeneracy.Source: A. Northwest-Corner Feasible Basis · p. 14

B. Optimality Certificates for Restricted OT

  • A restricted optimum is globally optimal when its support contains a full optimum; after an ε-accurate restricted solve, full dual feasibility is the only remaining condition for a full ε-KKT certificate.At ε = 0, full dual feasibility certifies global optimality.Source: B. Optimality Certificates for… · pp. 14–15

1) Theoretical Guarantees:

  • Cycle cancellation reduces primal support to a prescribed cap while preserving feasibility and not increasing cost; it takes at most max{0, |supp(x)| − s} updates and preserves exact optimality.With the dual correction when necessary, sparsification does not increase the restricted KKT residual.Source: 1) Theoretical Guarantees · pp. 15–16

2) Implementation and Overhead:

  • Sparsification overhead is insensitive to ambient dimension and cost type and is consistent with O(n log n); it was never triggered in the reported solver runs.The runtime comparison covers dimensions 4, 128, and 4096 after edge costs are available.Source: 2) Implementation and Overhead · p. 16, Figure 7 · p. 16

A. Hierarchy Construction via Recursive Subsampling

  • BuildHier subsamples only the larger side at each coarsening step and keeps the other side unchanged, enabling direct inheritance of the unchanged side’s dual potential.The hierarchy retains selected samples and their normalized marginal masses at each level, using the same pairwise cost function.Source: A. Hierarchy Construction via… · p. 16, Appendix B · p. 16

B. Dual Inheritance Accuracy under Random Subsampling

  • Under the stated regular-measure assumptions and fixed sampling ratio, random-subsampling discrepancy vanishes with sample size at a rate governed by intrinsic dimension q, not ambient dimension d.For Lc-Lipschitz costs, the inherited target-side dual objective gap is bounded by 2LcW1(µm, bµk), which is at most 2LcW2(µm, bµk).Source: B. Dual Inheritance Accuracy under… · pp. 17–18
  • The stated objective-gap rate assumes uniform source marginals; renormalized nonuniform marginals require mass-aware sampling or additional weight-balance assumptions.For squared Euclidean cost on bounded supports, one may take Lc = 2(RS + RD).Source: B. Dual Inheritance Accuracy under… · p. 18
  • Theorem B.2 gives a Wasserstein-based objective-value guarantee for an inherited potential and, under instance-dependent sharpness, a distance bound to the fine optimal-potential set.The guarantee applies to the target-side potential inherited between hierarchy levels; the objective-value bound also accommodates an inexact coarse potential.Source: B. Dual Inheritance Accuracy under… · p. 18
  • If the inherited dual is within the stated score-separation regime and the assignment budget covers each row’s set Mi, the first restricted solve attains the fine optimal value.Specifically, the condition is γ > 2δm and κ ≥ maxi |Mi|; then the dual-assigned support contains the support of every fine optimal plan.Source: B. Dual Inheritance Accuracy under… · p. 18

APPENDIX C EFFICIENT DUAL-SCORE EVALUATION

The appendix develops streamed dual-score evaluation and structured-cost shortcuts, then analyzes a cost-perturbed warm start that reduces cycle-induced ambiguity before refinement under the original cost.

APPENDIX C EFFICIENT DUAL-SCORE EVALUATION

  • For a fixed source or target, adding its potential preserves the opposite-side ranking, so assignment and violation detection share a pairwise-scoring primitive with different selection rules.The streamed GPU implementation supports general pairwise costs.Source: Appendix C · p. 19

A. Streaming and Fused Scans

  • For squared-Euclidean, ℓ1, ℓ2, and ℓ∞ costs, exhaustive dual-score evaluation takes Θ(mnd) operations, while the implementation scans source–target blocks.The runtime model’s Bn2d term accounts for this computation when m = n.Source: A. Streaming and Fused Scans · p. 19
  • Streaming scans evaluate all source–target pairs without materializing an m × n cost or score matrix, using linear feature storage.At m = n = 1,281,167 and d = 8192, one resident feature set occupies approximately 39.1 GiB of the reported 41.6 GiB peak.Source: A. Streaming and Fused Scans · p. 19

1) Squared-Euclidean Costs:

2) Low-Rank Costs:

  • The low-rank cost reduction preserves the set of optimal transport plans and every dual score, allowing the squared-Euclidean formulation to be reused in factor space.The reduction applies to balanced OT with fixed marginals and an exact low-rank cost factorization.Source: 2) Low-Rank Costs · pp. 19–20

A. Perturb-and-Refine Procedure

  • The auxiliary perturbed problem supplies dual potentials for initializing support, while restricted solves and support updates under the original cost produce the certified solution.Only the auxiliary dual potentials are carried into the original-cost solve.Source: A. Perturb-and-Refine Procedure · p. 20

B. Motivation

  • A small per-edge perturbation breaks cycle-induced ties, making the auxiliary edge-localization problem structurally less ambiguous.The auxiliary optimizer is used as a witness for support initialization, not as the original-cost solution or certificate.Source: B. Motivation · pp. 20–21, A. Perturb-and-Refine Procedure · p. 20
  • A bounded nonnegative perturbation removes cycle-induced ambiguity: almost surely, the perturbed cost is cycle-generic, giving a unique restricted optimizer and a tight-edge forest of at most m + n −1 edges.The result assumes positive marginals and independent perturbations drawn from absolutely continuous distributions.Source: B. Motivation · pp. 20–21

C. Transfer to the Original Cost

The cost-perturbation analysis bounds how an auxiliary optimizer and shifted duals transfer to the original cost. The convergence analysis proves finite termination and original-problem optimality for exact symbolic refinement under specified conditions.

C. Transfer to the Original Cost

  • When 0 ≤η∆ij ≤δ, the auxiliary optimizer’s original-cost suboptimality and the shifted-dual objective gap are bounded by δM.For probability marginals, M = 1; the shifted potentials are feasible for the original dual.Source: C. Transfer to the Original Cost · p. 21
  • If every positive-support edge meets the endpoint-wise budget condition, bidirectional top-κ assignment contains the auxiliary optimizer’s support, making the first original-cost restricted solve near-optimal.This initialization guarantee is conditional on the stated endpoint budget condition.Source: C. Transfer to the Original Cost · pp. 21–22

APPENDIX E CONVERGENCE ANALYSIS OF ACTIVE-SUPPORT

  • With a symbolically feasible initial support, exact symbolic restricted solves, and admissible updates, active-support refinement terminates finitely at a global optimum of the original OT problem.The theorem’s symbolic optimum has no negative powers of ξ; its constant term is an original-problem optimum.Source: Appendix E · p. 22
  • Symbolic lexicographic marginals make every feasible transport support connected, enabling an inserted positive dual violator to yield strict descent.The descent argument uses admissible updates that preserve the current primal support and insert a violator when one exists.Source: Appendix E · p. 23
  • Because every nonterminal iteration strictly decreases the restricted value and only finitely many active supports exist, refinement cannot continue indefinitely.At termination, the returned constant term is globally optimal for the original OT problem.Source: Appendix E · p. 24

APPENDIX F ERROR ANALYSIS OF EMPIRICAL SEMI-DISCRETE

The appendix analyzes averaged empirical dual potentials for semi-discrete OT under population regularity and curvature assumptions. It establishes batch-size and repetition behavior, including a fixed-batch approximation floor.

POTENTIAL AVERAGING

  • HELLO-SDOT averages b-centered target dual potentials from R independent empirical OT batches, each computed by HELLO.The batches use m independent source samples and share the fixed target support.Source: POTENTIAL AVERAGING · p. 24

A. Setup and Assumptions

  • The asymptotic analysis assumes population regularity and curvature conditions, including that p is C2 near the population potential.The theorem fixes the target sites, target dimension, ambient dimension, and target marginal.Source: A. Setup and Assumptions · p. 25, B. Main Theorem · p. 25

B. Main Theorem

  • Under the stated assumptions, the main theorem quantifies population marginal-error behavior as batch size m and repetition count R vary.Its stated guarantee covers every fixed finite range 1 ≤R ≤Rmax.Source: B. Main Theorem · p. 25
  • At fixed batch size m, increasing repetitions can leave a positive population marginal error because the batch potential can differ from the population potential.The fixed-batch regime therefore has an approximation floor determined by m.Source: B. Main Theorem · p. 25

C. Key Asymptotic Linearization

  • The key linearization reduces the averaged potential’s nonlinear marginal error to an average of independent categorical fluctuations.The result is stated under the main theorem’s assumptions.Source: C. Key Asymptotic Linearization · p. 26

D. Proof of the Main Theorem

  • The proof establishes a chi-square limit and a variance limit, with the remainder uniform over the fixed finite range of repetitions.The proof also reports the expectation result through the squared-norm conclusion.Source: D. Proof of the Main Theorem · pp. 26–27

E. Proofs of the Remainder Bounds

The appendix establishes remainder bounds and the probabilistic controls needed to localize empirical dual maximizers. Its arguments combine quadratic growth and uniqueness with empirical-process bounds for ties, moving cells, and semidual fluctuations.

E. Proofs of the Remainder Bounds

  • The empirical tie residual is controlled by bounding the number of rows with multiple active targets.The tie residual bound addresses imbalance introduced by empirical ties.Source: E. Proofs of the Remainder Bounds · p. 27
  • The nonlinear population map contributes only a lower-order Taylor remainder under the theorem's assumptions.Source: E. Proofs of the Remainder Bounds · p. 27
  • The moving-cell empirical remainder is controlled uniformly over empirical dual maximizers using a finite-VC class of cell assignments.The bound applies simultaneously to all empirical dual maximizers of a realized sample.Source: E. Proofs of the Remainder Bounds · pp. 27–28

1) Quadratic margin and localization:

2) Empirical-process inequalities:

3) Root-m moments and tails:

The appendix proves uniform root-m moment control for empirical potentials and describes extensions of HELLO to Gromov–Wasserstein and unbalanced OT. The GW construction uses sparse linearized OT steps, while the unbalanced formulation uses a balanced OT oracle within a translation-invariant dual framework.

3) Root-m moments and tails:

  • Uniform root-m moments hold across measurable selections, yielding uniform integrability through a local tail bound combining quadratic margin and semidual-process control.Source: 3) Root-m moments and tails · p. 30

A. Frank–Wolfe Linearization of GW

B. Proxy Initialization

  • The GW proxy initialization solves a one-dimensional squared-Euclidean OT problem by sorting, producing a sparse initial coupling.Source: B. Proxy Initialization · p. 31

C. Low-Rank Representation of the Linearized GW Cost

D. Equivalent Squared-Euclidean OT Cost

E. Unit-Step Property

  • For squared-Euclidean costs, exact line search takes a unit step at every nonstationary GW iteration, so each update is HELLO's sparse coupling.Source: E. Unit-Step Property · p. 31

APPENDIX H ADDITIONAL DETAILS FOR UNBALANCED OT

  • Appendix H presents an unbalanced-OT extension using a translation-invariant dual formulation, a balanced OT oracle, warm start, and fully corrective Frank–Wolfe updates.Source: Appendix H · p. 31

A. Translation-Invariant Dual Formulation

B. Balanced OT Oracle and Primal–Dual Certificate

This block develops the unbalanced-OT oracle and certificate, its initialization and updates, and supporting benchmark and evaluation details. It also reports the support comparison on synthetic 2D instances and establishes conditions under which the quadratic-OT reference is almost surely unique.

B. Balanced OT Oracle and Primal–Dual Certificate

C. Warm-Start Initialization

D. Fully Corrective Frank–Wolfe Update

1) Monge Benchmarks with Known Ground Truth:

2) Two-Dimensional Distributions for Support Visualization:

  • On both 2D synthetic instances, HELLO and EMD supports coincide, while Sinkhorn produces diffuse couplings under entropic regularization.Figure 8 shows Gaussian-to-Rings and Checkerboard transport supports, with source and target points and active transport pairs.Source: Figure 8 · p. 34, 2) Two-Dimensional Distributions for… · p. 34

B. ImageNet Latent Feature Benchmarks

C. Evaluation Validity: Almost-Sure Uniqueness of the Quadratic-OT Reference

  • With fixed pairwise-distinct targets and continuously sampled sources, discrete quadratic OT has a unique optimal plan almost surely.This makes the Gaussian-to-ImageNet optimal support an unambiguous reference when retained target latents are pairwise distinct.Source: C. Evaluation Validity: Almost-Sure… · pp. 34–35

D. Cross-Domain Gromov–Wasserstein Benchmark (MNIST– Fashion-MNIST)

This section evaluates HELLO on cross-domain alignment benchmarks, covering MNIST–Fashion-MNIST Gromov–Wasserstein and complete ImageNet latent alignment. It reports comparisons and, for ImageNet alignment, convergence, ablations, LP-backend robustness, and parameter sensitivity.

1) Data Sources and Sampling:

  • The benchmark aligns MNIST digit samples with Fashion-MNIST clothing samples, drawing n ∈ {2^14, 2^15, 2^16} images from each domain’s combined train/test pools.Each dataset has 60,000 training and 10,000 test images; images are flattened to 784-dimensional vectors with pixel values scaled to [0, 1].Source: 1) Data Sources and Sampling · p. 35

2) Dimensionality Reduction and Intra-Domain Metrics:

B. Full Scaling Results for Gromov–Wasserstein

  • At n = 216, HELLO-GW achieves the lowest GW objective, cuts the objective 10.3% versus LOT-GW, and runs 5.1× faster than Sinkhorn-GW.The comparison reports final GW objective and end-to-end runtime across n ∈ {2^14, 2^15, 2^16}.Source: B. Full Scaling Results for… · p. 38, Table IX · p. 39

D. Rectangular OT with Non-Uniform Marginals

  • At 1,281,167 samples per marginal and 8,192 dimensions, HELLO converges in 4,648 s using 41.6 GiB peak GPU memory, with KKT∞ = 8.50 × 10−7.Results are averaged over five random seeds on a single H100 GPU.Source: D. Rectangular OT with Non-Uniform… · p. 40

F. End-to-End Comparison with HALO

  • Across dimensions 4–16, HELLO maintains bounded active support and converges, while HALO shows substantial support growth and fails to converge or runs out of memory in several settings.The comparison uses Gaussian-to-ImageNet instances with n = m = 216 and includes capped-shielding and untruncated HALO variants.Source: F. End-to-End Comparison with HALO · p. 40

G. Leave-One-Out Component Ablation

  • Removing the hierarchy or cost perturbation loses convergence and increases runtime; global top-B selection is most costly, while budgeted pruning mainly provides the O(m + n) memory guarantee.Removing pruning slightly lowers runtime at unchanged support and convergence when support already stays within budget.Source: G. Leave-One-Out Component Ablation · p. 40

H. Robustness to LP Backends

  • Across tested settings, cuPDLPx and HPRLP yield identical objective values to reported precision, with runtime and memory differing by at most 5.5% and 11.8%, respectively.The comparison evaluates Gaussian-to-ImageNet instances with m = n = 218.Source: H. Robustness to LP Backends · p. 40

I. Full Parameter-Sensitivity Results Across Dimensions

  • The sensitivity analysis varies one parameter at a time across dimensions 4, 32, 256, and 2,048, with the other parameters set to their defaults.The defaults are ρ = 0.25, κ = 16, γ = 2, and β = 10.0.Source: §I · p. 40, Table XVIII · p. 41

Related papers

Loading 2609.13010v1…