Peter Bürgisser: "Towards a Theory of Non-commutative Optimization: Geodesic 1st & 2nd Order Met..."

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