Parameterisierte Geometrische Optimierung: Kombinatorik, Algorithmen und Anwendungen im Maschinellen Lernen

• Applicant: Professor Dr. Joachim Giesen
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2008 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 86443165

• Final Report Year: 2018

Final Report Abstract

Das maschinelle Lernen bietet viele Beispiele von parametrisierten Optimierungsproblemen. Dabei wird, um ein Modell aus Daten zu lernen, meistens eine Verlustfunktion minimiert bzw. eine Likelihood-Funktion maximiert. Bessere Modelle erhält man oft dadurch, dass man zu der Verlustfunktion noch einen geeigneten Regularisierungsterm addiert. Das richtige Verhältnis von der Minimierung der Verlustfunktion und der Regularisierung wird durch einen Regularisierungsparameter eingestellt. In der Praxis muss also ein zweistufiges Optimierungsproblem gelöst werden. Für einen festen Regularisierungsparameter muss die regularisierte Verlustfuktion über Trainingsdaten minimiert werden. Dann muss eine gute Lösung, zum Beispiel im Sinne der Vorhersagequalität des Modells auf Validierungsdaten, über dem Raum der Regularisierungsparameter gefunden werden. Der zweite Schritt wird oft heuristisch angegangen, indem nur ein paar Werte für den Regularisierungsparameter ausprobiert werden. Die Optimierung für einen festen Regularisierungsparameter ist dagegen oft ein einfaches, konvexes Problem, das effizient, exakt oder mit Approximationsgarantien gelöst werden kann. In der parametrisierten Optimierung will man auch das zweistufige Problem mit Garantien lösen. In der Regel kann die exakte Lösungsgesamtheit, d.h. die optimale Lösung für jeden Parameterwert, nicht effizient berechnet werden. Deshalb haben wir Approximationsverfahren untersucht, die den Parameterraum so abtasten, dass die Lösungen an den Abtaststellen die Lösungsgesamtheit mit vorgegebener Güte approximieren. Wir konnten zeigen, dass Ω(1/√ε) viele Abtastpunkte notwendig sind, um die Lösungsgesamtheit einer großen Klasse von regularisierten Verfahren aus dem maschinellen Lernen mit vorgebener Approximationsgute ε > 0 zu lösen. Wir konnten auch zwei robuste, effiziente Algorithmen angeben, der die vorgegebene Approximationsgüte mit O(1/√ε) Abtastpunkten erreichen. Regularisierte Verlustfunktionsminimierung ist ein recht einfaches Beispiel eines parametrisierten Optimierungsproblems, da die Parametrisierung linear im Regularisierungsparameter ist. Das maschinelle Lernen bietet auch viele Beispiele von nicht-linearen Parametrisierungen. In die zuvor beschriebene Verlustminimierung müssen die Daten nicht direkt eingehen, sondern sie können vorher auch nicht-linear transformiert werden. Eine nicht-lineare Datentransformation kann effizient durch eine sogenannte Kernfunktion erreicht werden. Viele Kernfunktionen, zum Beispiel der oft genutzte Gauß-Kern, hängen selbst nicht-linear von einem Parameter ab. Die Nutzung von parametrisierten Kernfunktionen führt wieder auf das schon zuvor beschriebene zweistufige Verfahren. Zum einen, die Verlustminimierung für einen festen Kernparameter auf Trainingsdaten, und zum anderen, die Optimierung des Kernparameters auf Testdaten. Unser Ziel war auch hier wieder die exakte Lösungsgesamtheit des parametrisierten Problems mit vorgegebener Güte zu approximieren. Für den nicht-linearen Fall konnten wir zeigen, dass Ω(1/ε) Abtastpunkte notwendig sind, um die Lösungsgesamtheit einer großen Klasse von nicht-linear transformierten Problemen aus dem maschinellen Lernen mit vorgebener Approximationsgüte zu lösen. Wir konnten auch einen Algorithmus angeben, die die Approximationsgute mit O(1/ε) Abtastpunkten erreicht. In der Praxis verbindet man oft regularisierte Verlustminimierung mit einer nicht-linearen Transformation der Daten. Es kommt auch vor, dass mehr als ein Regularisierungsterm vorhanden ist. Das heißt, in der Praxis ist die Parametrisierung oft nicht nur über einem Interval, sondern über einer Teilmenge eines höherdimensionalen Euklidischen Raums. Auch für diesen Fall wollten wir die exakte Lösungsgesamtheit des parametrisierten Problems mit vorgegebener Güte approximieren. Wir konnten zeigen, dass die Problemkomplexität als Funktion der Approximationsgüte das Produkt der Problemkomplexitäten der eindimensionalen Probleme ist. Zum Beispiel braucht man Ω (ε^−3/2) Abtastpunkte für Probleme mit einem Regularisierungs- und einem Kernparameter. Für Probleme mit zwei Regularisierungsparametern braucht man dementsprechend Ω(1/ε) Abtastpunkte. Wir konnten auch einen effizienten Algorithmus angeben, der die vorgegebene Approximationsgute asymptotisch mit der theoretisch minimal notwendigen Anzahl von Abtastpunkten erreicht. Alle unsere Algorithmen wurden implementiert und zeigen in der Praxis auf vielen Problemen und Datensatzen eine sehr gute Übereinstimmung mit der Theorie.

Publications

• A Hybrid Algorithm for Convex Semidefinite Optimization. Proceedings of the 29th International Conference on Machine Learning (ICML), (2012)
  Sören Laue
  
• Approximating Concavely Parameterized Optimization Problems. Proceedings of the 26th Annual Conference on Neural Information Processing Systems (NIPS), (2012) 2114-2122
  Joachim Giesen, Sören Laue, Jens Mueller, Sascha Swiercy
  
• Approximating Parameterized Convex Optimization Problems. ACM Transactions on Algorithms, 9(1):10, 2012
  Joachim Giesen, Martin Jaggi, and Sören Laue
  
• Optimizing over the Growing Spectrahedron. Proceedings of the 20th Annual European Symposium on Algorithms (ESA), (2012) 503-514
  Joachim Giesen, Martin Jaggi, and Sören Laue
  
• Regularization Paths with Guarantees for Convex Semidefinite Optimization. Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), (2012) 432-439
  Joachim Giesen, Martin Jaggi, and Sören Laue
  
• Robust and Efficient Kernel Hyperparameter Paths with Guarantees. Proceedings of the 31st International Conference on Machine Learning (ICML), (2014) 1296-1304
  Joachim Giesen, Sören Laue, and Patrick Wieschollek
  
• Tracking of Approximate Solutions of Parameterized Optimization Problems over Multi-Dimensional (Hyper-)Parameter Domains. Proceedings of the 32nd International Conference on Machine Learning (ICML), (2015) 438-447
  Katharina Blechschmidt, Joachim Giesen, and Soren Laue
  
• (2019): Using Benson’s Algorithm for Regularization Parameter Tracking. In: AAAI 33, S. 3689–3696
  Joachim Giesen, Soren Laue, Andreas Lohne, and Christopher Schneider