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

Arman Rahbar, Ashkan Panahi, Morteza Haghir Chehreghani, Devdatt Dubhashi, Hamid Krim
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:28549-28577, 2023.

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 this Paper

BibTeX
@InProceedings{pmlr-v202-rahbar23a, 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 = {Proceedings of the 40th International Conference on Machine Learning}, pages = {28549--28577}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/rahbar23a/rahbar23a.pdf}, url = {https://proceedings.mlr.press/v202/rahbar23a.html}, 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.} }
Endnote
%0 Conference Paper %T Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework %A Arman Rahbar %A Ashkan Panahi %A Morteza Haghir Chehreghani %A Devdatt Dubhashi %A Hamid Krim %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-rahbar23a %I PMLR %P 28549--28577 %U https://proceedings.mlr.press/v202/rahbar23a.html %V 202 %X 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.
APA
Rahbar, A., Panahi, A., Haghir Chehreghani, M., Dubhashi, D. & Krim, H.. (2023). Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:28549-28577 Available from https://proceedings.mlr.press/v202/rahbar23a.html.

Related Material