Global optimality for Euclidean CCCP under Riemannian convexity
Melanie Weber, Suvrit Sra
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, Mestimators 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- First-Order Algorithms for Min-Max Optimization in Geodesic Metric SpacesMichael I. Jordan, Tianyi Lin, Emmanouil V. Vlatakis-GkaragkounisNeurIPS 2022 · 25 citations
- Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal PointDavid Martínez-Rubio, Christophe Roux, Sebastian PokuttaICML 2024 · 3 citations
- Interior-point methods on manifolds: theory and applicationsHiroshi Hirai, Harold Nieuwboer, Michael WalterFOCS 2023 · 9 citations
- Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentJason M. Altschuler, Sinho Chewi, Patrik Gerber, Austin J. StrommeNeurIPS 2021 · 60 citations
- Strongly Convex Sets in Riemannian ManifoldsDamien Scieur, David Martínez-Rubio, Thomas Kerdreux, Alexandre d'Aspremont et al.ICLR 2026
