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

• URL: http://arxiv.org/abs/2609.13010v1
• Date: Fri, 11 Sep 2026 16:07:51 GMT
• Title: Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
• Abstract summary: HELLO is a hierarchical solver that casts large-scale discrete OT as edge localization.<n>It attains lower transport objectives with order-of-runtime improvements across feature dimensions from single digits to thousands.<n> beyond standard discrete OT, it serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.
• Score: 2.9671123446635708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Scaling Parallel Sequence Models to Foundation-Scale Vision Encoders [123.58723804218151]
  Vision foundation models are bottlenecked by the quadratic cost of self-attention.<n>We present C-GSPN based on 2D spatial propagation propagation.
  arXiv  Detail & Related papers  (2026-05-30T14:29:43Z)
• Hierarchical Transformer Preconditioning for Interactive Physics Simulation [28.137076331332413]
  Hierarchical Transformer Preconditioner, a neural preconditioner anchored to a weak-admissibility H-matrix partition.<n>Network models the inverse through low-rank far-field factors.<n>Uses highway connections to propagate context across depth sparse.
  arXiv  Detail & Related papers  (2026-05-13T11:02:27Z)
• Distributed Variational Quantum Linear Solver [2.7835589988032887]
  We present a distributed VQLS framework built on NVIDIA-Q, that enables scalable distribution of the O(L2) cost-function evaluations.<n>A fast Walsh--Hadamard transform (FWHT) supercomputer-based Pauli decomposition curbs the exponential growth of LCU terms, reducing L from O(2n) to O(1) for n > 6 qubits.<n>For a 10-qubit tridiagonal Toeplitz system, this yields a 256x reduction, while preserving over $99.99% solution fidelity.
  arXiv  Detail & Related papers  (2026-04-15T21:27:16Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Transport Clustering: Solving Low-Rank Optimal Transport via Clustering [0.9558392439655014]
  We introduce transport clustering, an algorithm to compute a low-rank OT plan that reduces low-rank OT to a full-text-type problem on correspondence rates.<n> Empirically, transport clustering outperforms existing low-rank OT solvers on synthetic benchmarks and large-scale, high-dimensional datasets.
  arXiv  Detail & Related papers  (2026-03-03T23:12:14Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• Hierarchical Refinement: Optimal Transport to Infinity and Beyond [1.8749305679160366]
  We show that Hierarchical Refinement runs in log-linear time and linear space, retaining the advantages of low-rank OT while overcoming its limited resolution.<n>We demonstrate the advantages of Hierarchical Refinement on several datasets, including ones containing over a million points, scaling full-rank OT to problems previously beyond Sinkhorn's reach.
  arXiv  Detail & Related papers  (2025-03-04T22:00:12Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.