Alte Optimierer, neue Normen: Eine Betrachtung

Deep Learning-Optimierer werden oft durch eine Mischung aus konvexer und approximativer Theorie zweiter Ordnung motiviert. Diese theoretischen Rahmenwerke wurden verwendet, um algorithmische Ideen zu inspirieren und die Konvergenz verschiedener Optimierer zu analysieren. Es wird jedoch argumentiert, dass es im einfacheren Bereich der exakten Theorie erster Ordnung ohne Konvexitätsannahmen eine Fülle ungenutzter algorithmischer Möglichkeiten gibt. Um diese Behauptung zu untermauern, werden drei Optimierer ausgewählt, die ursprünglich im Rahmen der konvexen oder approximativen Theorie zweiter Ordnung analysiert wurden: Adam, Shampoo und Prodigy. Nach Deaktivierung ihrer exponentiellen gleitenden Durchschnitte (EMA) wird gezeigt, dass jeder Algorithmus eine einfache theoretische Erklärung als Variante des steilsten Abstiegs unter einer bestimmten Norm zulässt. EMA kann dann so interpretiert werden, dass es den Algorithmus "glättet" oder robuster gegenüber Mini-Batch-Rauschen macht, obwohl die genaue Rolle von EMA vielleicht noch ein offenes Problem ist. Unter steilstem Abstieg versteht man das Verfahren, eine Gewichtsaktualisierung Δ⁢ω zu wählen, um ein lokales quadratisches Modell der Verlustfunktion ℒ der Form ℒ⁢(ω)+∇ωℒ⁢(ω)⊤⁢Δ⁢ω+λ2⋅‖Δ⁢ω‖2 zu minimieren. Der Schärfeparameter λ und die Norm ∥⋅∥ werden dabei a priori gewählt, ohne während des Trainings eine (approximative) Hesse-Matrix zu verwenden. Daher wird der steilste Abstieg als eine reine Methode erster Ordnung und nicht als eine (approximative) Methode zweiter Ordnung betrachtet. Im gesamten Artikel wird eine duale Beschreibung des steilsten Abstiegs verwendet: Proposition 1 (Steilster Abstieg) Für jedes g∈ℝn, das als "der Gradient" betrachtet wird, und jedes λ≥0, das als "die Schärfe" betrachtet wird, und für jede Norm ∥⋅∥:ℝn→ℝ mit der dualen Norm ∥⋅∥†: arg⁢minΔ⁢ω∈ℝn⁡[g⊤⁢Δ⁢ω+λ2⁢‖Δ⁢ω‖2]=−‖g‖†λ⋅arg⁢max‖t‖=1⁡g⊤⁢t. (1) Gleichung 1 trennt die Lösung des Problems des steilsten Abstiegs in zwei Teile: Erstens die Berechnung der Schrittweite als duale Norm des Gradienten dividiert durch die Schärfe und zweitens die Lösung für die Schrittrichtung als den Einheitsvektor, der das innere Produkt mit dem Gradienten maximiert. Der Beweis dieser Aussage findet sich in Anhang B. Natürlich liegt die Kunst des steilsten Abstiegs in der Wahl einer Norm ∥⋅∥ und einer Schärfe λ, die für das jeweilige Optimierungsproblem geeignet sind. Es mag zwar möglich sein, diese Kunst in eine Wissenschaft zu verwandeln (Large et al., 2024), doch dieses Ziel würde den Rahmen dieses Artikels sprengen. Hier sei nur darauf hingewiesen, dass frühere Methoden implizit Entscheidungen über Normen getroffen haben, und zwar auf etwas willkürliche Weise. Tatsächlich weisen sie den Schichten des Netzwerks implizit unterschiedliche induzierte Matrixnormen zu: Definition 1 (Induzierte Operatornorm) Gegeben sei eine Matrix M∈ℝdout×din und zwei normierte Vektorräume (ℝdin,∥⋅∥α) und (ℝdout,∥⋅∥β). Die "α nach β" induzierte Operatornorm ist dann gegeben durch: ‖M‖α→β=max𝓍∈ℝdin⁡‖M⁢x‖β‖x‖α. (2) Gleichung 2 besagt, dass wir durch Variation der Wahl der Vektornormen ∥⋅∥α und ∥⋅∥β eine große Familie von Matrixnormen induzieren können. Dies wiederum impliziert eine entsprechend große Familie von Optimierern für den steilsten Abstieg. Indem wir dieses Thema in den Vordergrund stellen, hoffen wir, dass Entwickler von Algorithmen geeignetere Optimierer entwickeln können, indem sie ihre Wahl der Norm bewusster treffen.

Adam als steilster Abstieg unter der Max-of-Max-Norm

Adam ist ein weit verbreiteter Deep Learning-Optimierer: Das Originalpapier von Kingma und Ba (2015) hat inzwischen weit über 100.000 Zitate. Adam wurde auf verschiedene Weise motiviert, unter anderem durch konvexe Analysis (Kingma und Ba, 2015) und als approximative Methode zweiter Ordnung (Sun und Spall, 2021). Es gab jedoch auch Bemühungen, ein direkteres Verständnis von Adam zu entwickeln: Wenn man beispielsweise die exponentiellen gleitenden Durchschnitte (EMA) ausschaltet, ist Adam nur noch ein Vorzeichengradientenabstieg (Balles und Hennig, 2018; Bernstein et al., 2018), was einem steilsten Abstieg unter der Unendlichkeitsnorm entspricht (Carlson et al., 2015). In diesem Abschnitt wird Adam mit einer bestimmten "Max-of-Max"-Norm in Verbindung gebracht und gezeigt, wie Adam die Tensorstruktur eines neuronalen Netzes auf eine ganz bestimmte Weise berücksichtigt. Zunächst soll kurz erläutert werden, wie Adam mit dem Vorzeichengradientenabstieg zusammenhängt. Ohne Berücksichtigung von Bias-Korrekturen und numerischen Stabilisierungen ist Adam durch das folgende System von Aktualisierungen gegeben: mt =β1⋅mt−1+(1−β1)⋅gt, (3) vt =β2⋅vt−1+(1−β2)⋅gt2, (4) ωt+1 =ωt−η⋅mt/vt, (5) wobei t den Zeitschritt, gt∈ℝn den Gradientenvektor und η>0 die Schrittweite bezeichnet. Die EMA-Zeitskalen des ersten Gradientenmoments mt und des zweiten Moments vt werden durch 0≤β1,β2<1 festgelegt. Alle Operationen werden elementweise durchgeführt. Wenn wir EMA ausschalten, indem wir β1=β2=0 setzen, reduzieren sich die Adam-Updates auf einen reinen Vorzeichengradientenabstieg: ωt+1 =ωt−η⋅gt/gt2 (6) =ωt−η⋅sign⁡(gt). (7) Diese Verbindung zum Vorzeichenabstieg sollte nicht überraschen, da Adam, das 2015 veröffentlicht wurde, auf dem RMSprop-Optimierer aufbaut, den Tieleman und Hinton (2012) bereits als "die Mini-Batch-Version der Verwendung des Vorzeichens des Gradienten" bezeichneten. Und RMSprop selbst baute auf dem RPROP-Optimierer auf (Riedmiller und Braun, 1993), der ebenfalls Gradientenvorzeichen verwendet. Warum aber sollte die Verwendung des Vorzeichens des Gradienten beim Deep Learning eine gute Idee sein? Auf der Suche nach einer Motivation ist es interessant zu bedenken, dass der Vorzeichenabstieg das Problem des steilsten Abstiegs unter der Vektor-ℓ∞-Norm, ‖v‖∞:=maxi⁡|vi| löst (Carlson et al., 2015, 2016; Fan, 2017): Proposition 2 (Vorzeichenabstieg als steilster Abstieg unter der Unendlichkeitsnorm) Für jeden Gradientenvektor g∈ℝn und jede Schärfe λ>0 gilt: arg⁢minΔ⁢ω∈ℝn⁡[g⊤⁢Δ⁢ω+λ2⁢‖Δ⁢ω‖∞2]=−‖g‖1λ⁢sign⁡(g). (8) Mit anderen Worten: Der Vektor, der ein lineares Funktional unter einer Unendlichkeitsnormbeschränkung minimiert, ist ein skalares Vielfaches eines Vorzeichenvektors. Der Beweis findet sich in Anhang B. Diese Verbindung zwischen Adam, dem Vorzeichenabstieg und dem steilsten Abstieg ist zwar vielleicht ganz nett, beantwortet aber nicht die grundlegende Frage: Was hat die Vektor-ℓ∞-Norm mit dem Training neuronaler Netze zu tun? Insbesondere scheint die Annahme, dass der Gewichtsraum ℝn ist, der mit der einfachen Unendlichkeitsnorm ausgestattet ist, die Tatsache zu "ignorieren", dass der Gewichtsraum eines neuronalen Netzes auf strukturierte Weise aus Schichten von Matrizen (und vielleicht anderen Tensoren) aufgebaut ist. Um dieses Rätsel zu lösen, schlagen wir vor, dass die Vektor-ℓ∞-Norm auf dem abgeflachten Gewichtsraum eigentlich nichts mit Deep Learning zu tun hat. Stattdessen liegt hier ein Zufall vor. Die ℓ∞-Norm hat eine besondere Eigenschaft, die mit dem Slogan "Ein Maximum eines Maximums ist ein Maximum" zusammengefasst werden kann. Um dies zu verdeutlichen, betrachten wir ein neuronales Netz mit einer Liste von L Gewichtsmatrizen W1,…,WL. Sei rowr⁢(Wl) die r-te Zeile von Wl. Dann gilt für die durch Adam induzierte Norm auf dem Raum der Gewichtsmatrizen: ‖(W1,…,WL)‖Adam:=maxl⁡‖Wl‖∞→∞=maxl⁡maxr⁡‖rowr⁢(Wl)‖1. (9) Mit anderen Worten: Die von Adam induzierte Norm ist das Maximum der Eins-Normen aller Zeilen aller Gewichtsmatrizen. Im Gegensatz dazu würde die naive Verwendung der Vektornorm ℓ∞ auf dem abgeflachten Gewichtsraum die Norm als das Maximum aller Einträge aller Gewichtsmatrizen berechnen. Obwohl die Max-of-Max-Norm gut zum Ausdruck bringt, wie Adam die Tensorstruktur eines neuronalen Netzes berücksichtigt, ist unklar, ob sie aussagekräftig ist. In der Tat könnte man argumentieren, dass die Max-of-Max-Norm für neuronale Netze zu "empfindlich" ist. Betrachten Sie zum Beispiel zwei neuronale Netze mit identischen Gewichten, mit der Ausnahme, dass ein einzelner Eintrag in einer einzigen Gewichtsmatrix in einem Netz größer ist als in dem anderen. Dann hätten diese beiden Netze unter der Max-of-Max-Norm sehr unterschiedliche Normen, obwohl sie sich nur in einem einzigen Eintrag unterscheiden.

Schlussfolgerung

In diesem Artikel haben wir uns drei beliebte Deep Learning-Optimierer - Adam, Shampoo und Prodigy - angesehen und argumentiert, dass jeder von ihnen als eine Form des steilsten Abstiegs unter einer bestimmten Norm verstanden werden kann. Dieser neue Blickwinkel wirft eine Reihe von Fragen auf. Erstens: Sind die von diesen Optimierern implizit gewählten Normen "gut"? Zweitens: Können wir bessere Normen finden, indem wir die von uns gewählte Norm auf die jeweilige Aufgabe abstimmen? Und schließlich: Was ist die Rolle von exponentiellen gleitenden Durchschnitten, die in der Praxis oft verwendet werden, aber in unserer theoretischen Analyse ignoriert wurden? Wir hoffen, dass diese Fragen die Leser dazu anregen, über neue Möglichkeiten für die Entwicklung von Optimierern nachzudenken, und vielleicht sogar zu schnelleren, stabileren und skalierbareren Trainingsalgorithmen führen.

Bibliographie

- Bernstein, J., Wang, Y.-X., Li, K., und E, L. (2018). signSGD: Compressed Optimisation for Non-Convex Problems. *International Conference on Machine Learning*. - Balles, L. und Hennig, P. (2018). Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients. *International Conference on Learning Representations*. - Carlson, D., Recht, B., und Packard, A. (2015). Efficient Iterative Algorithms for L\_infinity Problems. *Proceedings of the 54th IEEE Conference on Decision and Control (CDC)*, 1493–1498. - Carlson, D., Han, J., und Recht, B. (2016). Stochastic Spectral Descent for Restricted Boltzmann Machines. *International Conference on Artificial Intelligence and Statistics*. - Fan, J. (2017). Comments on “Stochastic Spectral Descent for Restricted Boltzmann Machines”. *International Conference on Artificial Intelligence and Statistics*. - Kingma, D. P. und Ba, J. (2015). Adam: A Method for Stochastic Optimization. *International Conference on Learning Representations*. - Large, J., L, X., und Maddison, C. (2024). Beyond SGD: Automated Optimization of Machine Learning Models. *Under Review*. - Riedmiller, M. und Braun, H. (1993). A Direct Adaptive Method for Faster Backpropagation Learning: The RPROP Algorithm. *IEEE International Conference on Neural Networks*. - Sun, T. und Spall, J. C. (2021). On the Equivalence Between Momentum and Stochastic Approximation: From Accelerated Optimization to Adaptive Control. *IEEE Transactions on Automatic Control*, 66(9), 3992–4007. - Tieleman, T. und Hinton, G. (2012). Lecture 6.5-rmsprop: Divide the Gradient by a Running Average of Its Recent Magnitude. *COURSERA: Neural Networks for Machine Learning*. https://www.arxiv.org/abs/2409.20325 https://arxiv.org/html/2409.20325v1 https://chatpaper.com/chatpaper/zh-CN?id=5&date=1727712000&page=1 https://gist.github.com/mjpost/201a1b2753d82f6aaf0654e499bbfbcc https://www.ims.uni-stuttgart.de/institut/team/Pado-00001/ https://www.ipu-berlin.de/en/ipu-spotlight/ https://aclanthology.org/2024.naacl-long.351.pdf https://github.com/acl-org/acl-anthology/issues/434 https://journals.ieeeauthorcenter.ieee.org/wp-content/uploads/sites/7/IEEE-Editorial-Style-Manual-for-Authors.pdf