Exploring Non-commutative Optimization & Tensor Methods in Science 🌐

Tensor Methods and Emerging Applications to the Physical and Data Sciences 2021
Workshop IV: Efficient Tensor Representations for Learning and Computational Complexity

"Towards a Theory of Non-commutative Optimization: Geodesic First and Second Order Methods for Moment Maps and Polytopes"
Peter Bürgisser - Technische Universität Berlin

Abstract: We outline a systematic development of a theory of non-commutative optimization for natural geodesically convex optimization problems on Riemannian manifolds that arise from symmetries given by the action of a reductive group on a complex vector space. This setting captures a diverse set of problems in different areas of computer science, mathematics, and physics, and our work unifies and generalizes a growing body of work.

We develop two general methods in the geodesic setting, a first order and a second order method. They minimize the moment map (capturing the the gradient) and test membership in null cones and moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity). 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 the null cone membership problem in several concrete situations. Our work points to intriguing open problems and suggests further research directions.

Joint work with Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson

https://arxiv.org/abs/1910.12375

Institute for Pure and Applied Mathematics, UCLA
May 20, 2021

For more information: https://www.ipam.ucla.edu/tmws4