# Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes

arXiv: https://arxiv.org/abs/1910.12375 · HTML: https://mlsanity.com/paper/1910.12375/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2019.

## Built on by (most cited first, 7 of 7)

- [Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory](https://mlsanity.com/paper/2109.01080/) (2021)
- [No-go Theorem for Acceleration in the Hyperbolic Plane](https://mlsanity.com/paper/2101.05657/) (2021)
- [Near optimal sample complexity for matrix and tensor normal models via geodesic convexity](https://mlsanity.com/paper/2110.07583/) (2021)
- [Understanding Riemannian Acceleration via a Proximal Extragradient Framework](https://mlsanity.com/paper/2111.02763/) (2021)
- [Position: Quantum Kernel Machines Should Move Beyond Scalar-Valued Kernels to Realize Their Potential](https://mlsanity.com/paper/2506.03779/) (2025)
- [Optimal Bounds for Tyler's M-Estimator for Elliptical Distributions](https://mlsanity.com/paper/2510.13751/) (2025)
- [Fast Matrix Multiplication in fp8: Certified Coefficient Optimization and Measured Error](https://mlsanity.com/paper/2609.26077/) (2026)

## Abstract (arXiv)

This paper initiates a systematic development of a theory of non-commutative optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesically convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. These algorithms minimize the moment map (a non-commutative notion of the usual gradient) and test membership in null cones and moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which arise from this a priori non-convex, non-linear setting). This setting captures a diverse set of problems in different areas of computer science, mathematics, and physics. Several of them were solved efficiently for the first time using non-commutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the "derivatives" of the function to be optimized. These in particular subsume all past results. The main technical work goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of "smoothness" are far more complex and require significant algebraic and analytic machinery. Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We show how to bound these parameters and hence obtain efficient algorithms for null cone membership in several concrete situations. Our work points to intriguing open problems and suggests further research directions.