Lune

ICML2023Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. First-Order Algorithms for Min-Max Optimization in Geodesic Metric SpacesMichael I. Jordan, Tianyi Lin, Emmanouil V. Vlatakis-GkaragkounisNeurIPS 2022 · 25 citations
  2. Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal PointDavid Martínez-Rubio, Christophe Roux, Sebastian PokuttaICML 2024 · 3 citations
  3. Interior-point methods on manifolds: theory and applicationsHiroshi Hirai, Harold Nieuwboer, Michael WalterFOCS 2023 · 9 citations
  4. Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentJason M. Altschuler, Sinho Chewi, Patrik Gerber, Austin J. StrommeNeurIPS 2021 · 60 citations
  5. Strongly Convex Sets in Riemannian ManifoldsDamien Scieur, David Martínez-Rubio, Thomas Kerdreux, Alexandre d'Aspremont et al.ICLR 2026
Dusk over the sea between two cliffs drawn in fine vertical lines