A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems

What the math gives to ML

The paper provides a constructive coarse-to-fine strategy for solving enormous nonnegative transport problems without materializing the full variable set: initialize a sparse active support from a coarser solution, refine it, and warm-start a primal-dual Newton method on each related subproblem. The transferable asset is not vanilla optimal transport itself, but the combination of support continuation, reduced Schur-complement solves, and explicit diagonal conditioning bounds. A strong neural-network use is balanced transport attention or token routing in which dense query-key edges are replaced by an adaptively refined sparse support, while preserving row and column mass constraints. The main falsifiable benefit is lower attention memory and solve cost at comparable retrieval quality or perplexity.