Detailansicht
A non-asymptotic analysis of averaged stochastic gradient descent for least squares regression
Manuel Müller
Art der Arbeit
Magisterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Magisterstudium Statistik
Betreuer*in
Hannes Leeb
DOI
10.25365/thesis.70217
URN
urn:nbn:at:at-ubw:1-11180.01627.821674-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Stochastic Gradient Descent (SGD, dt. stochastisches Gradientenverfahren) ist wegen seiner breiten
Anwendbarkeit sowie rechnerischen Effizienz eine sehr beliebte Technik im Feld der Optimierung
und des Maschinellen Lernens. Das asymptotische Verhalten von SGD wurde recht bald nach
seiner Entstehung 1951 (siehe Robbins und Monro [1951]) ausführlich erforscht. Jüngere Literatur
befasste sich nun mit nicht-asymptotischen Resultaten. Dazu gehört insbesondere das Werk
von Bach und Moulines [2013], in dem die Autoren eine optimale Konvergenzrate von O(1/n) für
den Anwendungsfall der Kleinste-Quadrate-Regression durch die Verwendung einer konstanten
Schrittweite in Kombination mit Mittelung der erzeugten Punkte (s.g. Polyak–Ruppert averaging,
siehe Ruppert [1988], Polyak und Juditsky [1992]) erzielen.
Im Rahmen dieser Magisterarbeit werden zuerst die notwendigen Definitionen, Annahmen und
Algorithmen eingeführt und diskutiert. In weiterer Folge wird das konkrete Resultat von Bach
und Moulines [2013] analysiert. Abschließend ist ein Überblick über die Literatur inkludiert, der
den Status Quo zum Zeitpunkt der Arbeit von Bach und Moulines [2013], sowie die weiterfolgenden
Analysen und Folgeresultate erläutert. Inbesondere wird durch diesen Überblick klar, dass
SGD mit konstanter Schrittweite und Mittelung der erzeugten Punkte zwar erstrebenswerte Resultate
für das Problem der Kleinste-Quadrate-Regression erzeugt, für andere Probleme jedoch
weniger geeignet ist. Das zeigt insbesondere, dass es notwendig ist, SGD (und seine Varianten)
im Kontext der jeweiligen Problemstellung zu analysieren, um optimale Resultate zu erhalten.
Abstract
(Englisch)
Stochastic gradient descent (SGD) is a very popular tool in optimization and machine learning
due to its versatility and computational efficiency. While asymptotic properties of SGD
were soon proven after its emergence in 1951 (see Robbins and Monro [1951]), recent results
have characterized the behavior of SGD in non-asymptotic settings. The results by Bach and
Moulines [2013] belong to this line of work and provide an optimal convergence rate of order
O(1/n) of SGD for the problem of least squares regression, when combining constant step sizes
with Polyak–Ruppert averaging [Ruppert, 1988, Polyak and Juditsky, 1992].
Over the course of this thesis, the relevant definitions, assumptions and algorithms are presented
and discussed in extensive detail. The result by Bach and Moulines [2013] is analyzed and an
overview over the related literature is given, in order to provide insight into the status quo at
the time of the publication of the paper by Bach and Moulines [2013] as well as into subsequent
analyses and improvements. In particular, this will shed light on the fact that, while the usage
of SGD with constant step sizes and Polyak–Ruppert averaging shows desirable behavior for
the problem of least squares regression, it will not produce equally appealing results for other
problems. This shows that problem-specific analyses of SGD (and its variants) are necessary in
order to make full use of the possible performance of SGD.
Schlagwörter
Schlagwörter
(Englisch)
Stochastic Gradient Descent least squares regression stochastic approximation online learning
Schlagwörter
(Deutsch)
Stochastisches Gradientenverfahren Kleinste-Quadrate-Regression Stochastische Approximierung Online-Optimierung
Autor*innen
Manuel Müller
Haupttitel (Englisch)
A non-asymptotic analysis of averaged stochastic gradient descent for least squares regression
Paralleltitel (Deutsch)
Eine nicht-asymptotische Analyse des stochastischen Gradientenverfahren für Kleinste-Quadrate-Regression
Publikationsjahr
2021
Umfangsangabe
vii, 115 Seiten : Illustration
Sprache
Englisch
Beurteiler*in
Hannes Leeb
Klassifikationen
31 Mathematik > 31.73 Mathematische Statistik ,
31 Mathematik > 31.99 Mathematik: Sonstiges
AC Nummer
AC16465789
Utheses ID
60156
Studienkennzahl
UA | 066 | 951 | |