Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-10712
Authors: Holzmüller, David
Title: Convergence Analysis of Neural Networks
Issue Date: 2019
metadata.ubs.publikation.typ: Abschlussarbeit (Master)
metadata.ubs.publikation.seiten: 77
URI: http://elib.uni-stuttgart.de/handle/11682/10729
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-107298
http://dx.doi.org/10.18419/opus-10712
Abstract: We prove that two-layer (Leaky)ReLU networks with one-dimensional input and output trained using gradient descent on a least-squares loss and He et al. initialization are not universally consistent. Specifically, we define a submanifold of all data distributions on which gradient descent fails to spread the nonlinearities across the data with high probability, i.e. it only finds a bad local minimum or valley of the optimization landscape. In these cases, the network found by gradient descent essentially only performs linear regression. We provide numerical evidence that this happens in practical situations and that stochastic gradient descent exhibits similar behavior. We relate the speed of convergence to such a local optimum to a stable linear system whose eigenvalues have different asymptotics. We also provide an upper bound on the learning rate based on this observation. While we mainly operate in the underparameterized regime like most consistency results for classical algorithms, our proof also applies to certain overparameterized cases that are not covered by recent results showing convergence of overparameterized neural nets to a global optimum.
Diese Masterarbeit beweist, dass zweischichtige neuronale Netze mit ReLU- oder LeakyReLU-Aktivierungsfunktionen und einem Input- und Output-Neuron, die mit Gradientenabstieg auf einem Least-Squares-Loss optimiert werden, nicht universell konsistent sind, solange das weit verbreitete Initialisierungsverfahren von He et al. verwendet wird. Speziell beruht der Beweis auf der Beobachtung, dass ein solches neuronales Netz bei der Initialisierung nur in x = 0 nichtlinear ist und es sich unter gewissen Voraussetzungen wie ein lineares Regressionsverfahren verhält, anstatt auf den Daten hinreichend nichtlinear zu werden. Die Existenz entsprechender lokaler Minima wurde bereits von Yun et al. gezeigt. Die Neuerung dieser Arbeit besteht darin, die Dynamik des Gradientenabstiegs zu untersuchen, um unter gewissen Voraussetzungen zu zeigen, dass diese lokalen Minima mit hoher Wahrscheinlichkeit erreicht werden. Die Beweisidee besteht darin, dass sich die Änderung der Netzgewichte, also die Größe der Komponenten des Gradienten, in etwa proportional zur Abweichung der Netzfunktion von den optimalen linearen Regressionsgeraden verhält. Eine schnelle Konvergenz gegen die optimalen linearen Regressionsgeraden bedeutet, dass sich die Netzgewichte während des Trainings nur wenig ändern und sich daher die Nichtlinearitäten nicht weit vom Ursprung $x = 0$ entfernen können. Falls die optimalen linearen Regressionsgeraden annähernd durch den Ursprung $(0, 0)$ verlaufen, dann zeigt diese Arbeit, dass die Netzfunktion mit hoher Wahrscheinlichkeit schnell gegen ein solches Optimum konvergiert und daher nur ein suboptimales lokales Minimum findet. Tatsächlich wird bewiesen, dass sich diese Wahrscheinlichkeit wie 1 - O(n^{-gamma) für alle gamma < 1/2 verhält, wobei n die Anzahl der Neuronen in der verborgenen Schicht ist. Es wird gezeigt, dass sich die Konvergenz des Netzes wie ein vierdimensionales diskretes lineares System verhält. Die Annahme an die optimalen linearen Regressionsgeraden stellt sicher, dass die Initialisierung nahe an den stark negativen Eigenwerten liegt, sodass die Konvergenz schnell genug ist. Die in Abschnitt 5 eingeführte Theorie mündet in Abschnitt 5.5 in mehrere Inkonsistenzresultate. Die Eigenwertanalyse liefert eine effizient berechenbare obere Schranke an die Optimierungsschrittweite h, unterhalb derer das inkonsistente Verhalten auftritt. Mithilfe der vorgestellten Theorie wird in Abschnitt 6 durch Monte-Carlo-Experimente die Wahrscheinlichkeit abgeschätzt, dass sich im obigen Szenario die Nichtlinearitäten über die Datenpunkte hinweg verteilen. Die Experimente bestätigen die theoretische Rate O(n^{-gamma) für alle gamma < 1/2 und zeigen, dass diese Asymptotik bereits für realistische Netzgrößen eintritt. Sie zeigen auch ein analoges Verhalten von stochastischem Gradientenabstieg. Darüber hinaus wird diskutiert, inwieweit dieses Ergebnis auf ähnliche Initialisierungsverfahren zutrifft. Das vorgestellte Inkonsistenzresultat steht im Kontrast zu anderen Arbeiten, die universelle Konsistenz unter der unrealistischen Annahme einer perfekten Optimierung oder Konvergenz gegen ein globales Optimum für gewisse überparametrisierte Netze zeigen.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
MA_David_Holzmueller_oneside.pdf1,28 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.