Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework
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.
Cite
Text
Rahbar et al. "Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework." International Conference on Machine Learning, 2023.Markdown
[Rahbar et al. "Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/rahbar2023icml-recovery/)BibTeX
@inproceedings{rahbar2023icml-recovery,
title = {{Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework}},
author = {Rahbar, Arman and Panahi, Ashkan and Haghir Chehreghani, Morteza and Dubhashi, Devdatt and Krim, Hamid},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {28549-28577},
volume = {202},
url = {https://mlanthology.org/icml/2023/rahbar2023icml-recovery/}
}