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

Abstract

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.

108 pages, long version of paper presented at FOCS 2019. v3: various typos fixed

References in corpus (31)

• Normal forms and entanglement measures for multipartite quantum states
• Entanglement Polytopes: Multiparticle Entanglement from Single-Particle Information
• The Pauli principle revisited
• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• Quantum marginal problem and representations of the symmetric group
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
• On Nonzero Kronecker Coefficients and their Consequences for Spectra
• On vanishing of Kronecker coefficients
• Quantum state transformations and the Schubert calculus
• Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Algorithms and Hardness for Robust Subspace Recovery
• Towards Riemannian Accelerated Gradient Methods
• Combinatorial and algorithmic aspects of hyperbolic polynomials
• Inequalities for Moment Cones of Finite-Dimensional Representations
• Multipartite Quantum States and their Marginals
• Membership in moment polytopes is in NP and coNP
• Algorithms for orbit closure separation for invariants and semi-invariants of matrices
• Geometric Complexity III: on deciding positivity of Littlewood-Richardson coefficients
• The honeycomb model of GL(n) tensor products I: proof of the saturation conjecture
• Constructive noncommutative rank computation is in deterministic polynomial time
• Computation of Dilated Kronecker Coefficients
• Maximum likelihood estimation for tensor normal models via castling transforms
• Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
• On Radial Isotropic Position: Theory and Algorithms
• Interior-point methods for unconstrained geometric programming and scaling problems
• The Horn inequalities from a geometric point of view
• Horn inequalities and quivers
• Barriers for recent methods in geodesic optimization
• Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties)

Cited by in corpus (20)

• The minimal canonical form of a tensor network
• Quantum Brascamp-Lieb Dualities
• Maximum likelihood estimation for tensor normal models via castling transforms
• Interior-point methods on manifolds: theory and applications
• Rigorous Guarantees for Tyler's M-estimator via quantum expansion
• Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
• Interior-point methods for unconstrained geometric programming and scaling problems
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Ranks of linear matrix pencils separate simultaneous similarity orbits
• Polynomial time algorithms in invariant theory for torus actions
• On the Computability of Continuous Maximum Entropy Distributions: Adjoint Orbits of Lie Groups
• Barriers for recent methods in geodesic optimization
• Submodule codes as spherical codes in buildings
• Saturation of Rota's basis conjecture
• Capacity Lower Bounds via Productization
• Quantum algorithms for matrix scaling and matrix balancing
• Computing the nc-rank via discrete convex optimization on CAT(0) spaces
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity
• Generalized Pauli constraints in large systems: the Pauli principle dominates
• Optimization and Sampling Under Continuous Symmetry: Examples and Lie Theory