提出 HELLO 算法，提升大规模最优传输计算效率
Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
学术研究者或算法工程师如果对提升大规模最优传输（OT）计算效率感兴趣，可以看看这篇论文，它提出的 HELLO 算法在百万级数据点上的表现很有参考价值。
论文提出 HELLO 算法，通过分层求解和双引导机制优化大规模离散最优传输问题。在百万级数据点规模下，相比强基线模型，在单维度到数千维度的特征空间中，计算速度提升一个数量级，并在单张 H100 显卡上处理 128 万样本/边际的 8192 维数据。
Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
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.
