License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.24
URN: urn:nbn:de:0030-drops-83510
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8351/
Bürgisser, Peter ;
Garg, Ankit ;
Oliveira, Rafael ;
Walter, Michael ;
Wigderson, Avi
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).
BibTeX - Entry
@InProceedings{brgisser_et_al:LIPIcs:2018:8351,
author = {Peter B{\"u}rgisser and Ankit Garg and Rafael Oliveira and Michael Walter and Avi Wigderson},
title = {{Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {24:1--24:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8351},
URN = {urn:nbn:de:0030-drops-83510},
doi = {10.4230/LIPIcs.ITCS.2018.24},
annote = {Keywords: alternating minimization, tensors, scaling, quantum marginal problem, null cone, invariant theory, geometric complexity theory}
}
|
Keywords: |
|
alternating minimization, tensors, scaling, quantum marginal problem, null cone, invariant theory, geometric complexity theory |
|
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.01.2018 |
