Detailansicht
Convergence rate analysis of optimisation and minimax algorithms for machine learning
Michael Sedlmayer
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium NAWI aus dem Bereich Naturwissenschaften (DissG: Mathematik)
Betreuer*innen
Radu Ioan Bot ,
Tara Lee Andrews
DOI
10.25365/thesis.73600
URN
urn:nbn:at:at-ubw:1-19801.28749.909784-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Optimierungs- und Sattelpunktprobleme, bei denen die Minimierung von einer inneren Maximierung begleitet wird, werden bekannterweise erfolgreich durch Methoden aus der Theorie zu Monotonen Inklusionen und Variationsungleichungen gelöst. In diesem Kontext sind wir besonders an Verfahren erster Ordnung interessiert, die "full splitting" sind. Das heißt, dass ausschließlich Gradienteninformationen von glatten Funktionen und proximale Auswertungen von einfachen konvexen nichtglatten Funktionen verwendet werden. Außerdem verlangen wir, dass die Algorithmen keine verschachtelten inneren Schleifen beinhalten, sondern alle involvierten Operatoren separat ausgewertet werden. Damit beschäftigen wir uns auf drei unterschiedlichen konzeptionellen Ebenen: (i) Monotonen Inklusionen, die am allgemeinsten sind und (ii) Variationsungleichungen beinhalten, die bereits mehr Struktur aufweisen und (iii) Minimax-/Sattelpunktprobleme inkludieren, die sich in der Spieltheorie oder im Kontext der Bestimmung von primal-dualen Paaren von optimalen Lösungen zu eingeschränkten konvexen Optimierungsproblemen ergeben. Wir stellen "full splitting" Lösungsverfahren erster Ordnung vor, zeigen asymptotische Konvergenz der Algorithmen und beweisen nicht-asymptotische Konvergenzraten im Fall von Variationsungleichungen und Minimax-Problemen. Um alle betrachteten Methoden empirisch zu validieren, stellen wir einfache, konzeptuelle Probleme vor, die das Konvergenzverhalten der vorgestellten Verfahren anschaulich machen. Das wird von komplexeren Experimenten komplimentiert, die relevante reale Anwendungen (beispielsweise in den Digitalen Geisteswissenschaften -- "Digital Humanities") des Maschinellen Lernens umfassen, wo wir uns unter anderem mit "Generative Adversarial Nets" (GANs) und "Multikernel Support Vector Machines" beschäftigen. GANs haben sich als eine leistungsstarke Klasse generativer Modelle erwiesen, die mit herkömmlichen Trainingsmethoden bekanntermaßen schwer zu optimieren sind. Sie können jedoch als Minimax-Problem betrachtet werden und profitieren deutlich von der Anwendung fundierter Algorithmen, die für diese Art von Problemen entwickelt wurden.
Abstract
(Englisch)
Optimisation and saddle point problems, where the minimisation is accompanied by an inner maximisation, are well-known to be successfully treated by methods from monotone inclusion and variational inequality theory. In this context we are particularly interested in first order methods that are full splitting. This means that only gradient information for smooth functions and proximal evaluations of simple convex nonsmooth functions are used. Furthermore we require that the algorithms do not include convoluted inner loops but evaluate the involved operators separately. We do this on three different conceptual levels: (i) monotone inclusions that are most general and include (ii) variational inequalities that already contain more structure and include (iii) minimax/saddle point problems that arise from game theory or in the context of determining primal-dual pairs of optimal solutions of constrained convex optimisation problems. We propose full splitting, first order solution methods, establish asymptotic convergence of the algorithm and prove convergence rates in the case of variational inequalities and minimax problems. To empirically validate all considered methods we provide simple, conceptual problems that showcase the convergence behaviour of the proposed methods. This is complemented by more complex experiments covering relevant real-world machine learning applications (for example in Digital Humanities), treating, among other things, Generative Adversarial Nets (GANs) and Multikernel Support Vector Machines. GANs have proven to be a powerful class of generative models that are notoriously hard to optimise by conventional training methods, but can be cast as a minimax problem and observably benefit from employing more principled algorithms established for this type of problem.
Schlagwörter
Schlagwörter
(Deutsch)
Konvexe Optimierung Sattelpunktprobleme Minimax Algorithmen Konvergenzraten Maschinelles Lernen
Schlagwörter
(Englisch)
convex optimisation saddle point problems minimax algorithms convergence rates machine learning
Autor*innen
Michael Sedlmayer
Haupttitel (Englisch)
Convergence rate analysis of optimisation and minimax algorithms for machine learning
Paralleltitel (Deutsch)
Konvergenzratenanalyse von Optimierungs- und Sattelpunktalgorithmen für Maschinelles Lernen
Publikationsjahr
2022
Umfangsangabe
x, 167 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Pontus Giselsson ,
Defeng Sun
Klassifikationen
31 Mathematik > 31.49 Analysis. Sonstiges ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC16864986
Utheses ID
65664
Studienkennzahl
UA | 796 | 605 | 405 |