Die kurze Fassung

• Der stochastische Gradientenabstieg (SGD) trainiert die meisten heutigen tiefen Netze, doch seine Konvergenz bei nichtkonvexen Verlustfunktionen ist nur teilweise verstanden. Die meisten Garantien setzen einen global Lipschitz-stetigen Gradienten voraus, und den hat der quadratische Verlust eines tiefen linearen Netzes nicht.
• Dieses Preprint mit Bubacarr Bah, Holger Rauhut und Ulrich Terstiege überträgt die Konvergenzergebnisse unseres Papers zum Gradientenabstieg auf SGD mit Mini-Batches bei regularisiertem quadratischem Verlust. Mit Wahrscheinlichkeit 1 bleiben die Iterierten beschränkt, der Verlust konvergiert, die Gradienten gehen gegen null, und der Abstand zur Menge der kritischen Punkte geht gegen null. Das gilt für deterministische und adaptive Schrittweiten und für jede Batch-Größe bis hinunter zu 1.
• Der entscheidende Schritt ist ein direkter Beweis der Beschränktheit, ohne Lipschitz-Annahme. Beschränkte Iterierte lassen den SGD-Pfad dem Gradientenfluss als asymptotische Pseudotrajektorie folgen, und der regularisierte Verlust ist eine Lyapunov-Funktion, die festlegt, wo SGD ankommt. Nach unserem Kenntnisstand ist es das erste Ergebnis zur fast sicheren Konvergenz von SGD in tiefen linearen Netzen in diesem Rahmen.
• Was Ihnen das in der Praxis bringt: Schrittweitenpläne mit expliziten Konstanten, berechnet aus den Daten, der Batch-Größe, der Regularisierung und den Startgewichten, unter denen die Konvergenz garantiert ist.

Aufgabenstellung und Forschungsziel

Der Kontext und seine Bedeutung

Mit SGD und seinen Varianten werden stark parametrisierte Modelle trainiert. Jeder Schritt nutzt den Gradienten auf einem zufälligen Mini-Batch, und das ist bei großen Datensätzen günstiger als ein Gradient über alle Daten. Der Preis ist Rauschen. Im nichtkonvexen Fall, in dem die Verlustlandschaft voller Sattelpunkte und lokaler Minima ist, hinkt die Theorie der Praxis hinterher.

Die meisten Konvergenzergebnisse für SGD setzen beschränkte Gradienten oder einen Lipschitz-stetigen Gradienten voraus. Diese Eigenschaft liefert das Abstiegslemma, beschränkt das zweite Moment des Gradienten, und über sie zeigen die bisherigen Beweise, dass die Iterierten beschränkt bleiben. Der Gradient des quadratischen Verlusts eines tiefen linearen Netzes ist nicht global Lipschitz-stetig. Diese allgemeinen Ergebnisse greifen deshalb nur, wenn die Beschränktheit auf anderem Weg bewiesen wird.

Die mathematische Formulierung

Ein tiefes lineares Netz der Tiefe N ≥ 2 multipliziert seine Eingabe nacheinander mit N Gewichtsmatrizen. Es berechnet eine lineare Abbildung, doch die faktorisierten Parameter machen den Verlust nichtkonvex. So behält es zentrale Eigenschaften des Deep Learning und bleibt trotzdem analysierbar. Der Trainingsverlust ist der quadratische Verlust plus ein Regularisierer λ(½‖W‖²)^β auf allen Gewichten, mit λ > 0 und β ≥ N. In jedem Schritt zieht SGD gleichverteilt zufällig einen Mini-Batch der Größe T und aktualisiert jede Gewichtsmatrix mit dem Gradienten des regularisierten Mini-Batch-Verlusts, dessen Erwartungswert der volle Gradient ist. Den Regularisierer begründet der Artikel ausdrücklich: Für den unregularisierten quadratischen Verlust hat sich der Beweis, dass SGD beschränkt bleibt, als sehr schwierig erwiesen und ist weiter offen.

Der Rahmen

Im Rahmen: SGD mit Mini-Batches auf tiefen linearen Netzen beliebiger Tiefe N ≥ 2 mit regularisiertem quadratischem Verlust, Batch-Größen von 1 bis zum ganzen Datensatz, deterministische und adaptive Schrittweitenpläne und numerische Experimente mit synthetischen Daten, darunter ein Test an Netzen mit tanh-Aktivierung in der letzten Schicht. Außerhalb des Rahmens: der unregularisierte quadratische Verlust, für SGD weiter offen, und ein Beweis für nichtlineare Netze, die die Experimente erkunden, die Theorie aber nicht abdeckt.

Die Erfolgskriterien

Die fast sichere Beschränktheit der SGD-Iterierten ohne Lipschitz-Annahme an den Gradienten beweisen, danach die fast sichere Konvergenz zur kritischen Menge unter Schrittweiten mit expliziten Konstanten, für den deterministischen und den adaptiven Plan. Anschließend numerisch prüfen, wie scharf die Bedingungen an die Schrittweite sind.

Methodik und Vorgehen

Die Beschränktheit der SGD-Iterierten, direkt bewiesen

Alles hängt daran, dass die Iterierten beschränkt bleiben. Frühere SGD-Analysen bekamen das aus einem Lipschitz-stetigen Gradienten, dieser Artikel bekommt es aus dem Regularisierer. Für β ≥ N und Schrittweiten, die mit expliziten Konstanten skaliert sind, bleibt die Norm jeder Iterierten unter max{‖W(0)‖, M + B}. M und B hängen von den Daten, der Batch-Größe, λ, β, N und den Startgewichten ab. Bei β = N muss λ zusätzlich über einer Schwelle liegen, die die Daten festlegen. Der adaptive Plan erhält eine explizite Schranke derselben Art, bestimmt durch M, die Obergrenze D und die Daten.

Von SGD zum Gradientenfluss: asymptotische Pseudotrajektorien

Mit der Beschränktheit in der Hand behandelt die Analyse SGD als verrauschte Diskretisierung des Gradientenflusses des regularisierten Verlusts. Sie verbindet die Iterierten zu einem stetigen Pfad und zeigt, dass dieser Pfad eine asymptotische Pseudotrajektorie ist, ein Werkzeug der stochastischen Approximation: Auf jedem festen Zeitfenster folgt der Pfad dem Gradientenfluss mit fortschreitendem Training immer genauer. Dafür muss sich das Rauschen der Mini-Batches ausmitteln, und das leisten Schrittweiten, deren Summe divergiert und deren Quadratsumme endlich ist.

Ankunft auf der kritischen Menge

Der regularisierte Verlust ist eine Lyapunov-Funktion für den Gradientenfluss, er fällt also entlang des Flusses. Ein Ergebnis von Benaïm zu asymptotischen Pseudotrajektorien macht dann aus einer beschränkten Pseudotrajektorie und dieser Lyapunov-Funktion die Konvergenz der Verlustwerte und der Iterierten zur Menge der kritischen Punkte, mit Wahrscheinlichkeit 1.

Zwei Schrittweitenpläne

Beide Pläne multiplizieren eine Folge b_k mit Werten in (0, 1] mit einem Skalierungsfaktor. Der Satz verlangt, dass die Summe der b_k unendlich und die Summe ihrer Quadrate endlich ist, wie bei b_k = 1/(k + 1)^γ mit γ über ½.

• Deterministisch. Der Faktor steht vor dem Training fest, berechnet aus den Daten, der Batch-Größe, den Startgewichten und den Regularisierungskonstanten.
• Adaptiv. Die Schrittweite liest die aktuelle Norm der Gewichte und sinkt, wenn die Gewichte wachsen, nach oben begrenzt durch eine Konstante D. Der Artikel empfiehlt in der Praxis ein großes D, damit meist der adaptive Term greift.

Was die Batch-Größe mit der Schrittweite macht

Ein Abschnitt, den der Artikel ausdrücklich als heuristisch und nicht als Satz kennzeichnet, vergleicht SGD mit Batch-Größe 1 und den Gradientenabstieg über alle Daten anhand dieser Schranken für die Schrittweite. Bei Daten, in denen ein einziger Punkt das ganze Signal trägt, kann der Gradientenabstieg vorn liegen. Bei Daten aus Kopien eines Punktes kann SGD vorn liegen. Der Artikel liest daraus den Hinweis, dass SGD vermutlich effizienter ist, wenn es den ganzen Datensatz in weniger Schritten sieht.

Ergebnisse und Wirkung

Die wichtigsten theoretischen Ergebnisse

Die Experimente mit synthetischen Daten

Die Experimente trainieren lineare Netze der Tiefe 3 und 4 auf 300 gaußverteilten Datenpunkten der Dimension 70, mit Zielwerten aus einem zufälligen linearen Netz und Mini-Batches der Größe 30. Mit adaptiven Schrittweiten, die den Satz erfüllen, sinkt der regularisierte Verlust in Stufen und bleibt dann bis zum Ende eines Laufs über 500 000 Epochen flach: ab etwa 5 000 Epochen bei Tiefe 3 (Abbildung 1) und ab etwa 100 000 Epochen bei Tiefe 4 (Abbildung 2). Für den deterministischen Plan berichtet der Artikel dieselbe Konvergenz des Verlusts und dieselben beschränkten Normen der Gewichte. Schrittweiten, die die Bedingungen des Satzes verletzen, hielten die Iterierten trotzdem beschränkt, was nahelegt, dass die Schranke nicht scharf ist.

Abbildung 3 vergleicht beide Pläne am selben Netz der Tiefe 3, mit dem Verlust geteilt durch seinen Startwert. Mit deterministischen Schrittweiten sinkt er langsam und pendelt sich nach etwa 20 000 Epochen bei rund 0,91 ein. Mit adaptiven Schrittweiten und D = 1 bewegt er sich in den ersten paar Hundert Epochen kaum, fällt dann um Epoche 1 000 steil ab und pendelt sich bei rund 0,68 ein. Der adaptive Plan konvergierte schneller und zu einem niedrigeren Verlust.

Ein letztes Experiment setzt eine tanh-Aktivierung in die letzte Schicht, einen Fall, den die Theorie nicht abdeckt. Mit der adaptiven Schrittweitenregel sinkt der regularisierte Verlust eines Netzes der Tiefe 3 von etwa 0,048 auf etwa 0,013, am stärksten zwischen 100 und 1 000 Epochen, und ist ab etwa 10 000 Epochen flach (Abbildung 4), ganz ähnlich wie beim linearen Netz in Abbildung 1. Die Normen seiner Gewichte sinken in den ersten 50 Epochen von etwa 1,76 auf 1,32, steigen wieder und bleiben ab etwa 2 000 Epochen stabil bei rund 1,78 (Abbildung 5). Der Artikel liest daraus den Hinweis, dass sich einige Ergebnisse auf nichtlineare Netze übertragen lassen könnten.

Grenzen und was als Nächstes kommt

Die Garantie ist Konvergenz zur Menge der kritischen Punkte des regularisierten Verlusts. Sie sagt nicht, welchen kritischen Punkt SGD erreicht und ob dieser Punkt ein globales Minimum ist. Die Analyse braucht den Regularisierer mit β ≥ N. SGD auf dem unregularisierten quadratischen Verlust, dem Rahmen der früheren Arbeit zum Gradientenabstieg, ist weiter offen, und die Autoren sehen in dieser Analyse eine Vorlage für viele der nötigen Schritte. Nichtlineare Netze sind nur numerisch getestet.

Links und Artefakte

• Paper auf arXiv
• Begleitende Fallstudie: Gradientenabstieg in tiefen linearen Netzen