Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework
Arman Rahbar, Ashkan Panahi, Morteza Haghir Chehreghani, Devdatt Dubhashi, Hamid Krim
Abstract
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.
BibTeX
@inproceedings{icml2023_recoveryboundson,
title = {Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework},
author = {Arman Rahbar and Ashkan Panahi and Morteza Haghir Chehreghani and Devdatt Dubhashi and Hamid Krim},
booktitle = {ICML 2023},
year = {2023}
}