Skip to yearly menu bar Skip to main content


Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework

Arman Rahbar · Ashkan Panahi · Morteza Haghir Chehreghani · Devdatt Dubhashi · Hamid Krim

Exhibit Hall 1 #131
[ ]
[ PDF [ Poster


We develop a novel theoretical framework for understating Optimal Transport (OT) schemes respecting a class structure. For this purpose, we propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. Furthermore, we derive an accelerated proximal algorithm with a closed-form projection and proximal operator scheme, thereby affording a more scalable algorithm for computing optimal transport plans. We provide a novel argument for the uniqueness of the optimum even in the absence of strong convexity. Our experiments show that the new regularizer not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry, compared to previous regularizers.

Chat is not available.