Stochastic multilevel methods for deep learning

As the use cases for neural networks become increasingly complex, modern neural networks must also grow deeper and more intricate to keep up. However, with increased depth and complexity, common training methods like stochastic gradient descent methods (SGD) become more computationally expensive. Multilevel methods, traditionally used to solve differential equations through hierarchies of discretizations, offer the potential to reduce computational effort. These methods operate across multiple levels of complexity. On lower levels, a coarse approximation of the solution can be obtained quickly and at low computational cost. These coarse approximations are then refined on higher levels to achieve a more accurate solution. By alternating between levels, multilevel methods can accelerate convergence while maintaining precision.

This thesis introduces a multilevel stochastic gradient descent algorithm (MLSGD) that combines both concepts aiming to accelerate neural network training through multilevel techniques. The core contribution of this thesis is the development and analysis of MLSGD. As in traditional multilevel methods, prolongation and restriction operators enable transitions between levels. To ensure first-order coherence, a gradient correction is added to the objective function as well as additional conditions including step size regularization and an angle condition. We analyze the convergence properties of the method under the assumption of fixed step sizes. Additionally, we investigate the influence of stochastic directions in the gradient correction as a replacement for full gradients as well as the effect of variance reduction in both cases.

Finally, we evaluate the practical performance of the method as well as the effect of stochastic gradient correction and variance reduction. To this end, MLSGD is applied to the image classification dataset CIFAR-10. We explore two different approaches to constructing a hierarchy, based either on network depth or image resolution. For both approaches, we construct suitable prolongation and restriction operators.

Da die Anwendungsfälle für neuronale Netze immer komplexer werden, werden zugleich auch moderne neuronale Netze größer und komplexer, um mithalten zu können. Mit zunehmender Tiefe und Komplexität solcher Netze steigt jedoch auch der Rechenaufwand von gängigen Trainingsmethoden wie dem stochastischen Gradientenverfahren (SGD).

Multilevelverfahren, die traditionell zur Lösung von Differentialgleichungen mit Hilfe von Hierarchien an Diskretisierungen verwendet werden, bieten die Möglichkeit, den Rechenaufwand zu reduzieren. Diese Methoden arbeiten mit verschiedenen Stufen an Komplexität. Auf den unteren Stufen kann eine grobe Näherung der Lösung schnell und mit geringem Aufwand berechnet werde. Diese Näherungen werden dann auf höheren Stufen schrittweise verfeinert, um genauere Näherungen zu erhalten. Durch den Wechsel zwischen den Stufen können Multilevelverfahren schneller konvergieren ohne an Genauigkeit einzubüßen.

In dieser Arbeit wird ein Multilevel stochastisches Gradientenverfahren (MLSGD) vorgestellt, das beide Ansätze miteinander kombiniert. Ziel dabei ist es, das Training von neuronalen Netzen durch den Einsatz von Multilevelmethoden zu beschleunigen. Der zentrale Beitrag dieser Arbeit liegt in der Entwicklung und Analyse von MLSGD. Wie üblich bei Multilevelverfahren, werden Prolongations- und Restriktionsoperatoren verwendet, um den Wechsel zwischen verschiedenen Stufen zu ermöglichen. Um Konsistenz erster Ordnung zu gewährleisten, wird ein Gradientenkorrekturterm zur Zielfunktion hinzugefügt. Des Weiteren verwenden wir zusätzliche Bedingungen, wie eine Schrittweitenregularisierung und eine Winkelbedingung. Wir diskutieren die Konvergenzeigenschaften der Methode unter der Annahme, dass konstante Schrittweiten verwendet werden. Hierbei untersuchen wir auch den Einsatz stochastischer Richtungen anstelle des Gradienten in der Gradientenkorrektur und den Einfluss von Varianzreduktion in beiden Fällen.

Anschließend untersuchen wir das Verhalten des Verfahrens in der Praxis. Auch hier untersuchen wir den Einfluss von einer stochastischen Gradientenkorrektur und Varianzreduktion. MLSGD wird dazu auf den Bildklassifizierungsdatensatz CIFAR-10 angewendet. Wir verwenden dabei zwei verschiedene Ansätze um eine Hierarchie zu bilden, basierend entweder auf der Netzwerktiefe oder der Bildauflösung. Für beide Ansätze werden geeignete Prolongations- und Restriktionsoperatoren konstruiert.