Global optimality for Euclidean CCCP under Riemannian convexity

Melanie Weber, Suvrit Sra
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:36790-36803, 2023.

Abstract

We study geodesically convex (g-convex) problems that can be written as a difference of Euclidean convex functions. This structure arises in key applications such as matrix scaling, M- estimators of scatter matrices, and Brascamp-Lieb inequalities. In particular, we exploit this structure to make use of the Convex-Concave Procedure (CCCP), which helps us bypass potentially expensive Riemannian operations and leads to very competitive solvers. Importantly, unlike existing theory for CCCP that ensures convergence to stationary points, we exploit the overall g-convexity structure and provide iteration complexity results for global optimality. We illustrate our results by specializing them to a few concrete optimization problems that have been previously studied in the machine learning literature. We hope our work spurs the study of mixed Euclidean-Riemannian optimization algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-weber23a, title = {Global optimality for {E}uclidean {CCCP} under {R}iemannian convexity}, author = {Weber, Melanie and Sra, Suvrit}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {36790--36803}, 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/weber23a/weber23a.pdf}, url = {https://proceedings.mlr.press/v202/weber23a.html}, abstract = {We study geodesically convex (g-convex) problems that can be written as a difference of Euclidean convex functions. This structure arises in key applications such as matrix scaling, M- estimators of scatter matrices, and Brascamp-Lieb inequalities. In particular, we exploit this structure to make use of the Convex-Concave Procedure (CCCP), which helps us bypass potentially expensive Riemannian operations and leads to very competitive solvers. Importantly, unlike existing theory for CCCP that ensures convergence to stationary points, we exploit the overall g-convexity structure and provide iteration complexity results for global optimality. We illustrate our results by specializing them to a few concrete optimization problems that have been previously studied in the machine learning literature. We hope our work spurs the study of mixed Euclidean-Riemannian optimization algorithms.} }
Endnote
%0 Conference Paper %T Global optimality for Euclidean CCCP under Riemannian convexity %A Melanie Weber %A Suvrit Sra %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-weber23a %I PMLR %P 36790--36803 %U https://proceedings.mlr.press/v202/weber23a.html %V 202 %X We study geodesically convex (g-convex) problems that can be written as a difference of Euclidean convex functions. This structure arises in key applications such as matrix scaling, M- estimators of scatter matrices, and Brascamp-Lieb inequalities. In particular, we exploit this structure to make use of the Convex-Concave Procedure (CCCP), which helps us bypass potentially expensive Riemannian operations and leads to very competitive solvers. Importantly, unlike existing theory for CCCP that ensures convergence to stationary points, we exploit the overall g-convexity structure and provide iteration complexity results for global optimality. We illustrate our results by specializing them to a few concrete optimization problems that have been previously studied in the machine learning literature. We hope our work spurs the study of mixed Euclidean-Riemannian optimization algorithms.
APA
Weber, M. & Sra, S.. (2023). Global optimality for Euclidean CCCP under Riemannian convexity. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:36790-36803 Available from https://proceedings.mlr.press/v202/weber23a.html.

Related Material