Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory

Abstract

Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).

48 pages

Cited by in corpus (15)

• Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes
• A complete hierarchy for the pure state marginal problem in quantum mechanics
• Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
• Maximum likelihood estimation for tensor normal models via castling transforms
• Rigorous Guarantees for Tyler's M-estimator via quantum expansion
• Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
• No-go Theorem for Acceleration in the Hyperbolic Plane
• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
• Universal points in the asymptotic spectrum of tensors
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Polynomial time algorithms in invariant theory for torus actions
• Orbits of monomials and factorization into products of linear forms
• Quantum algorithms for matrix scaling and matrix balancing
• Near optimal sample complexity for matrix and tensor normal models via geodesic convexity
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography