Loading…
Thumbnail Image

Invariant theory in computational complexity and algebraic statistics

Reichenbach, Philipp

Invariant theory is a branch of algebra that is classically intertwined with computation, but it also led to important contributions in mathematics and applications in other sciences. For example, the problem of deciding null cone membership (NCM) has, thanks to the general abstract setting of invariant theory, manifold applications in mathematics, physics, computer science and statistics. In this thesis we study invariant theory in two regards: computational complexity and algebraic statistics. As indicated by its title the thesis consists of three parts. The first part collects preliminary knowledge on invariant theory that is used throughout the thesis. Thus, it only contains known results and concepts. The second part focuses on the computational complexity of current geodesic convex optimization methods for the NCM problem and its “approximate” versions: norm minimization and scaling. First, we prove that complexity parameters, that capture the required precision for deciding NCM via optimization methods, are exponentially small for several important group actions. Second, in the high precision regime the diameter (“bit complexity”) of approximate minimizers may be exponentially large for tensor scaling. The provided bounds exclude, for the respective group actions, polynomial running time of current geodesic methods for the three computational problems. Therefore, our results highly motivate the search for and the advancement of new sophisticated methods for geodesic convex optimization. The third part builds a bridge between invariant theory and algebraic statistics, which establishes novel relations to maximum likelihood estimation (MLestimation). We connect norm minimization under a group action to maximizing the likelihood in a statistical model, which is related to the group action. In particular, norm minimizers yield maximum likelihood estimates. Strikingly, this approach yields a dictionary between stability notions from invariant theory and notions from ML estimation. We obtain fruitful applications on the interplay of invariant theory and statistics. First, we recover known statistical results, and even get some new characterizations, via invariant theory. Second, we obtain algorithmic consequences, e.g., complexity results from invariant theory carry over to statistics. Third, one can translate problems from statistics to invariant theory, and vice versa. This has already been used in the literature with great benefit. Fourth, the invariant theoretic approach fostered the development of new statistical models and the understanding of their ML estimation. Namely, we study the new concepts of Gaussian group models and of RDAG models.
Invariantentheorie ist ein Bereich der Algebra, der klassischerweise eng verbunden ist mit Berechnungen und Algorithmen, der jedoch auch zu wichtigen Beiträgen in der Mathematik selbst sowie ihren Anwendungsbereichen geführt hat. Zum Beispiel hat das Entscheidungsproblem der Nullkegel-Zugehörigkeit (NKZ), dank des allgemeinen, abstrakten Settings der Invariantentheorie, vielfältige Anwendungen in Mathematik, Physik, Informatik und Statistik. In dieser Dissertation studieren wir Invariantentheorie in zweierlei Hinsicht: bezüglich Komplexitätstheorie und bezüglich Algebraischer Statistik. Wie der Titel bereits andeutet besteht die Arbeit aus drei Teilen. Der erste Teil umfasst und wiederholt wesentliche Vorkenntnisse aus der Invariantentheorie. Deshalb enthält er nur bereits bekannte Resultate und Konzepte. Der zweite Teil beschäftigt sich mit der Komplexität von aktuellen geodätisch-konvexen Optimierungsalgorithmen für das NKZ-Problem sowie seiner „approximativen“ Versionen: Norm-Minimierung und Skalierung. Erstens zeigen wir, dass Komplexitätsparameter, welche die nötige Präzision zum Entscheiden des NKZProblems mittels Optimierungsalgorithmen erfassen, exponentiell klein sind für mehrere wichtige Gruppenaktionen. Zweitens, im Fall von hoher Präzision kann der Durchmesser („Bit-Komplexität“) eines approximativen Minimierers exponentiell groß sein für Tensor-Skalierung. Diese bereitgestellten Schranken schließen, für die jeweiligen Gruppenaktionen, eine polynomiale Laufzeit der aktuellen geodätisch-konvexen Methoden für die drei genannten Probleme aus. Deshalb motivieren die Resultate in hohem Maße die Suche nach und die Weiterentwicklung von ausgeklügelten Methoden für geodätisch-konvexe Optimierung. Der dritte Teil baut eine Brücke zwischen Invariantentheorie und Algebraischer Statistik, welche völlig neuartige Verbindungen zur Maximum-Likelihood-Methode (ML Methode) etabliert. Wir verbinden Norm-Minimierung unter einer Gruppenaktion zum Maximierungsproblem der Plausibilität in einem statistischen Modell, welches in Beziehung zur Gruppenaktion steht. Insbesondere, geben Norm-Minimierer einen zugehörigen Maximum-Likelihood-Schätzer. Bemerkenswerterweiseführt dieses Vorgehen zu einem Wörterbuch zwischen Stabilitätsnotationen aus der Invariantentheorie und Notationen bezüglich der ML Methode. Dieses Zusammenspiel von Invariantentheorie und Statistik trägt große Früchte. Erstens erhalten wir bereits bekannte statistische Resultate, und manchmal sogar ganz neue Charakterisierungen, mittels Invariantentheorie. Zweitens gibt es algorithmische Folgerungen, zum Beispiel können komplexitätstheoretische Resultate von Invariantentheorie auf die Statistik übertragen werden. Drittens kann man Probleme der Statistik zu Problemen in Invariantentheorie übersetzen, und vice versa. Dies wurde bereits mit großem Erfolg in anderen wissenschaftlichen Arbeiten verwendet. Viertens hat der Zugang mittels Invariantentheorie die Entwicklung von neuen statistischen Modellen sowie das Verständnis ihrer ML-Methode gefördert. Nämlich studieren wir die neuartigen Konzepte der Gaußschen Gruppenmodelle sowie der RDAG Modelle.