2022/08/16 by Jason M. Altschuler, Enric Boix-Adserà · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Vehicle Routing Optimization Methods
paper · pdf · doi:10.1007/s10107-022-01868-7
Abstract Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n . This paper develops a general theory about what “structure” makes MOT solvable in \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time. We develop a unified algorithmic framework for solving MOT in \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time. Second, our framework makes it much simpler to develop \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle—which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> runtime; moreover, we provide the first \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first \mathrm poly(n,k) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>poly</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> time algorithms, even for approximate computation. Together, these three structures encompass many—if not most—current applications of MOT.