🔢 mathematics

Convergence Rate Analysis of the AdamW-Style Shampoo: Unifying One-sided and Two-Sided Preconditioning

Dieser Artikel liefert eine theoretische Konvergenzanalyse des AdamW-artigen Shampoo-Optimierers, die einseitige und zweiseitige Vorbedingung vereint, um eine auf der Kernnorm basierende Konvergenzrate zu etablieren, die der optimalen Rate von SGD analog ist.

Ursprüngliche Autoren: Huan Li, Yiming Dong, Zhouchen Lin

Veröffentlicht 2026-05-04

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Huan Li, Yiming Dong, Zhouchen Lin

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein riesiges, nebliges Gebirge zu navigieren, um das tiefste Tal zu finden (die perfekte Lösung für ein KI-Modell). Sie haben eine Karte, aber sie ist etwas verschwommen, und jedes Mal, wenn Sie einen Schritt machen, verschiebt sich der Boden leicht. So fühlt sich das Training eines tiefen neuronalen Netzwerks an.

Seit Jahren ist die beliebteste Methode, diese Schritte zu tun, eine Technik namens Adam. Denken Sie an Adam als einen Wanderer, der den Hang unter seinen Füßen betrachtet und seine Geschwindigkeit basierend darauf anpasst, wie steil er in jeder einzelnen Richtung ist (Nord, Süd, Ost, West). Es ist ein guter Wanderer, aber er behandelt jede Richtung unabhängig voneinander und ignoriert, wie das Gelände miteinander verbunden sein könnte.

Dann kommt Shampoo ins Spiel, ein neuerer, raffinierterer Wanderer. Anstatt die Richtungen einzeln zu betrachten, betrachtet Shampoo das Gelände als Ganzes, als eine zweidimensionale Fläche. Es versteht, dass eine Bewegung nach Norden beeinflussen kann, wie Sie sich nach Osten bewegen sollten. Diese „zweiseitige" Sichtweise ermöglicht es ihm, intelligentere und effizientere Schritte zu tun. Kürzlich hat eine Version von Shampoo namens AdamW-style Shampoo tatsächlich einen großen Wettbewerb gewonnen, um den schnellsten Weg zum Training von KI-Modellen zu finden, und damit den alten Standard geschlagen.

Doch während alle wussten, dass dieser neue Wanderer in der Praxis schnell ist, hatte niemand einen soliden mathematischen Beweis, der erklärt, warum er so gut funktioniert oder wie schnell garantiert ist, dass er den Boden erreicht.

Was diese Arbeit leistet
Diese Arbeit ist wie ein rigoroser Ingenieursbericht, der endlich die Physik hinter diesem Super-Wanderer erklärt. Die Autoren, Huan Li, Yiming Dong und Zhouchen Lin, haben drei Hauptdinge getan:

Vereinheitlichung der Regeln: Sie schufen einen einzigen mathematischen Rahmen, der sowohl die „einseitige" Version (Betrachtung von Zeilen oder Spalten separat) als auch die „zweiseitige" Version (Betrachtung des gesamten Gitters) von Shampoo abdeckt. Es ist, als würde man ein einziges Regelbuch schreiben, das erklärt, wie man sowohl eine Limousine als auch einen Lastwagen fährt.
Beweis der Geschwindigkeit: Sie berechneten genau, wie schnell dieser Algorithmus konvergiert (die Lösung erreicht). Sie fanden heraus, dass sich nach $K$ $K$ Schritten der Fehler mit einer Rate von ungefähr $1/\sqrt[4]{K}$ $1/ 4 K$ verringert.
- Die Analogie: Stellen Sie sich vor, Sie gehen auf ein Ziel zu. Der „alte" Weg (SGD) bringt Sie mit einer bestimmten Geschwindigkeit dorthin. Die Autoren bewiesen, dass diese neue Shampoo-Methode Sie im Wesentlichen mit dem gleichen theoretischen Geschwindigkeitslimit wie die bestmögliche Methode dorthin bringt, vorausgesetzt, das Gelände (die Mathematik des Problems) verhält sich ordentlich.
Überbrückung von Theorie und Realität: Es gab eine Lücke zwischen der Mathematik und der realen Welt. Die Mathematik legte nahe, dass der Algorithmus einen winzigen „Sicherheitspuffer" (eine Zahl namens $\epsilon$ ) benötigte, um zu funktionieren, aber in der Praxis setzten die Leute diesen Puffer fast auf Null. Die Autoren zeigten, dass selbst mit diesem winzigen Puffer die „Präkonditionierer" des Algorithmus (seine interne Landkarte des Geländes) natürlich groß genug bleiben, um den Wanderer sicher zu halten. Dies erklärt, warum der Algorithmus im echten Leben so gut funktioniert, selbst wenn das theoretische „Sicherheitsnetz" zu dünn erscheint.

Wichtige Erkenntnisse für ein allgemeines Publikum

Der „zweiseitige" Vorteil: Stellen Sie sich vor, Sie versuchen, einen Knoten zu lösen. Ein einseitiger Ansatz zieht an einem Ende. Ein zweiseitiger Ansatz (wie Shampoo) zieht gleichzeitig an beiden Enden und versteht, wie die Fäden miteinander verwoben sind. Diese Arbeit beweist, dass das Ziehen an beiden Enden mathematisch fundiert ist und genauso schnell ist wie die bestmögliche Strategie.
Das Geheimnis der „Nuklearnorm": Um zu messen, wie schnell der Wanderer unterwegs ist, verwendeten die Autoren ein spezielles mathematisches Lineal namens „Nuklearnorm". Sie zeigten, dass dieses Lineal zwar leicht anders ist als das Standard-Lineal, das in älteren Methoden verwendet wird, aber ein Ergebnis liefert, das in der realen Welt praktisch identisch ist. Es ist wie das Messen eines Raumes in „Fuß" versus „Meter" – die Zahlen sehen unterschiedlich aus, aber die Größe des Raumes ist dieselbe.
Warum es wichtig ist: Dies ist nicht nur abstrakte Mathematik. Es bestätigt, dass der Algorithmus, der von den Gewinnern des AlgoPerf-Wettbewerbs verwendet wird (der massive KI-Modelle trainiert, wie die, die Chatbots antreiben), nicht nur ein glücklicher Zufall ist. Es ist eine mathematisch robuste Methode, die garantiert, die beste Lösung effizient zu finden, selbst für die komplexesten, nichtlinearen Probleme.

Kurz gesagt nimmt diese Arbeit einen „Blackbox"-Gewinner eines Machine-Learning-Wettbewerbs, öffnet ihn und sagt: „Hier ist genau, wie es funktioniert, hier ist der Beweis, dass es schnell ist, und hier ist der Grund, warum es nicht kaputtgeht, wenn wir es in der realen Welt verwenden."

1. Problemstellung

Das Papier adressiert die theoretische Konvergenzanalyse des Optimierers AdamW-Style Shampoo, eines hochmodernen Algorithmus, der den AlgoPerf-Wettbewerb für das Training neuronaler Netze gewann. Während Shampoo (und seine Varianten wie SOAP und Muon) durch die Nutzung von Vollmatrix-Vorbedingungern (Preconditionern) eine überlegene empirische Leistung gegenüber diagonalen Vorbedingungsmethoden (wie Adam) gezeigt hat, fehlten oder waren die theoretischen Konvergenzgarantien für nichtkonvexe Optimierung unzureichend oder begrenzt.

Insbesondere standen sich in der bestehenden Literatur drei Hauptlücken gegenüber:

Nichtkonvexität: Die meisten vorherigen Analysen waren auf konvexe Settings beschränkt.
Umfang der Vorbedingung: Bisherige nichtkonvexe Analysen (z. B. Xie et al., 2026) beschränkten sich auf einseitige Vorbedingung und ignorierten die komplexere und effektivere zweiseitige Vorbedingung, die in praktischen Implementierungen verwendet wird.
Praktische Komponenten: Bestehende Theorien ließen oft kritische praktische Merkmale wie Momentum und entkoppelten Gewichtsverfall (AdamW-Style) aus, die für das Training moderner großer Sprachmodelle (LLM) unverzichtbar sind.

Das Papier zielt darauf ab, eine rigorose Konvergenzrate für den allgemeinen AdamW-Style Shampoo-Algorithmus zu etablieren und sowohl einseitige als auch zweiseitige Vorbedingung unter einem nichtkonvexen Rahmen zu vereinen.

2. Methodik

Die Autoren analysieren Algorithmus 1, der den AdamW-Style Shampoo-Optimierer repräsentiert. Die Update-Regel umfasst:

Exponentielle gleitende Durchschnitte (EMA): Verfolgung der ersten Momente ( $M_k$ ) und zweiten Momente ( $L_k, R_k$ ) der Gradienten.
Zweiseitige Vorbedingung: Der Update-Schritt lautet $X_{k+1} = (1-\lambda\eta)X_k - \eta L_{k,\epsilon}^{-\frac{1}{2p}} M_k R_{k,\epsilon}^{-\frac{1}{2q}}$ , wobei $L_k$ und $R_k$ akkumulierte äußere Produkte der Gradienten sind (die $E[GG^T]$ und $E[G^TG]$ approximieren).
Vereinheitlichte Exponenten: Die Parameter $p$ und $q$ (wobei $1/p + 1/q = 1$ ) ermöglichen es dem Algorithmus, zwischen zweiseitiger ( $p, q < \infty$ ) und einseitiger ( $p=1, q=\infty$ oder umgekehrt) Vorbedingung zu wechseln.

Wichtige technische Innovationen:
Um die Komplexität der zweiseitigen Matrixvorbedingung in nichtkonvexen Settings zu bewältigen, entwickelten die Autoren neue Beweistechniken:

Schatten-p-Hölder-Ungleichung: Anstelle der in der Adam-Analyse verwendeten Standard-Vektor-basierten Hölder-Ungleichungen nutzen die Autoren die Schatten-p-Hölder-Ungleichung, um die Nuklearnorm ( $\|\cdot\|_*$ ) des Gradienten zu begrenzen. Dies ist entscheidend, da der Vorbedingung auf den Singulärwerten der Matrixparameter wirkt.
Matrix-Cauchy-Schwarz-Ungleichung: Um die Spektralnorm des Update-Schritts ( $L^{-1/2p} M R^{-1/2q}$ ) zu begrenzen, wenden sie eine matricespezifische Cauchy-Schwarz-Ungleichung an, um die Interaktion zwischen dem linken und dem rechten Vorbedingung zu behandeln.
Spektrale Boden-Analyse: Sie führen eine Bedingung (Bedingung 4) bezüglich der unteren Schranke der Vorbedingung ( $\hat{\epsilon}$ ) ein. Sie argumentieren, dass in der Praxis der effektive spektrale Boden der Vorbedingung deutlich größer ist als die numerische Regularisierung $\epsilon$ (z. B. $10^{-12}$ ), wodurch die theoretischen Schranken mit empirischen Beobachtungen übereinstimmen.

3. Hauptbeiträge

Vereinheitlichte Konvergenzrate: Das Papier etabliert die erste Konvergenzrate für AdamW-Style Shampoo in der nichtkonvexen Optimierung, die sowohl einseitige als auch zweiseitige Vorbedingung abdeckt.
Ableitung der optimalen Rate: Sie beweisen, dass die durchschnittliche erwartete Nuklearnorm des Gradienten mit einer Rate konvergiert von:
$\frac{1}{K} \sum_{k=1}^K \mathbb{E}[\|\nabla f(X_k)\|_*] \leq O\left( \frac{\sqrt{m+n} \cdot C}{K^{1/4}} \right)$
wobei $m, n$ die Matrixdimensionen sind, $K$ die Iterationsanzahl und $C$ die Konstante in der optimalen SGD-Rate entspricht.
Theoretische Rechtfertigung für praktische Settings: Die Analyse erklärt, warum die Einstellung des numerischen Regularisators $\epsilon$ auf extrem kleine Werte (z. B. $10^{-12}$ ) die Konvergenz nicht behindert. Die Theorie zeigt, dass der effektive Vorbedingung-Boden durch die Gradienten-Rauschskala bestimmt wird und nicht durch das numerische $\epsilon$ .
Norm-Beziehung: Die Autoren zeigen, dass die abgeleitete Nuklearnorm-Rate analog zur optimalen Frobenius-Norm-Rate von SGD ( $O(K^{-1/4})$ ) unter der idealen Bedingung ist, dass $\|\nabla f(X)\|_* \approx \Theta(\sqrt{\min(m,n)}) \|\nabla f(X)\|_F$ .

4. Ergebnisse

Theoretische Schranken:
- Die Worst-Case-Schranke hängt von $\sqrt{m+n}$ ab, was signifikant enger ist als die $\sqrt{mn}$ (Gesamtdimension $d$ ) Abhängigkeit, die in einigen diagonalen Methoden oder Vollmatrix-Unterschranken zu finden ist.
- Die Konvergenzrate entspricht der bekannten Unterschranke für nichtkonvexe stochastische Optimierung ( $O(K^{-1/4})$ ) bis auf einen Faktor von $\sqrt{m+n}$ .
Empirische Validierung (GPT-2 Pretraining):
- Gradienten-Norm-Verhältnis: Experimente zum GPT-2 Pretraining zeigten, dass das Verhältnis $\|\nabla f(X)\|_* / \|\nabla f(X)\|_F$ konsistent nahe an der theoretischen Obergrenze $\sqrt{\min(m,n)}$ bleibt. Dies validiert die Annahme, dass die Nuklearnorm-Rate in der Praxis effektiv der Frobenius-Norm-Rate entspricht.
- Spektraler Boden: Die kleinsten Eigenwerte der Vorbedingung ( $L_k, R_k$ ) wurden um Größenordnungen größer als das numerische $\epsilon$ ( $10^{-12}$ ) und vergleichbar mit der rauschabhängigen Skala $\hat{\sigma}^2/(m+n)$ beobachtet. Dies bestätigt, dass die „unpraktische" Annahme eines größeren spektralen Bodens im realen LLM-Training gilt.

5. Bedeutung

Brücke zwischen Theorie und Praxis: Diese Arbeit liefert die erste rigorose theoretische Grundlage für die spezifische Shampoo-Variante, die den AlgoPerf-Wettbewerb gewann, und erklärt, warum sie in der Praxis so gut funktioniert.
Fortschritt gegenüber diagonalen Methoden: Sie validiert theoretisch die Überlegenheit nicht-diagonaler (Vollmatrix-) Vorbedingung gegenüber diagonalen Methoden (wie Adam) für Matrix-strukturierte Parameter und zeigt, dass die von Shampoo erfassten Kreuz-Parameter-Korrelationen zu besseren Konvergenzrichtungen führen.
Leitfaden für Hyperparameter: Die Analyse bietet theoretische Rechtfertigung für die Wahl von Hyperparametern (z. B. die Beziehung zwischen Momentum $\theta$ und zweitem Moment-Abklingfaktor $\beta$ sowie die Rolle von $\epsilon$ ) und leitet Praktiker bei der Feinabstimmung dieser Optimierer für großskalige Modelle an.
Grundlage für zukünftige Optimierer: Durch die Vereinheitlichung von einseitiger und zweiseitiger Vorbedingung sowie die Integration von Momentum/Gewichtsverfall setzt dieser Rahmen einen neuen Standard für die Analyse fortschrittlicher, zweiter Ordnung ähnlicher Optimierer im Deep Learning.

Zusammenfassend vereint das Papier erfolgreich die theoretische Analyse von Shampoo, indem es beweist, dass es eine optimale Konvergenzrate für nichtkonvexe Probleme erreicht und gleichzeitig die komplexen Matrixstrukturen einfängt, die in modernen Deep-Learning-Modellen inhärent sind.

1. Problemstellung

2. Methodik

3. Hauptbeiträge

4. Ergebnisse

5. Bedeutung

Mehr davon