Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework
This work addresses the problem of incorporating class structure into optimal transport for machine learning applications, representing a novel method for a known bottleneck rather than an incremental improvement.
The authors tackled the problem of optimal transport schemes that respect class structure by proposing a convex OT program with sum-of-norms regularization, which provably recovers the underlying class structure under geometric assumptions and yields better preservation of class structure and additional robustness to data geometry compared to previous regularizers.
We develop a novel theoretical framework for understating 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.