🔢 mathematics

RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization

Das Papier schlägt RanSOM vor, ein einheitliches Optimierungsframework, das durch den Einsatz randomisierter Schrittweiten und Stein-artiger Identitäten die durch Krümmung verursachte Verzerrung in Momentum-Methoden eliminiert, um optimale Konvergenzraten sowohl für restringierte als auch für unrestringierte Probleme zu erreichen, ohne teure zusätzliche Stichproben zu benötigen.

Ursprüngliche Autoren: El Mahdi Chayti

Veröffentlicht 2026-05-18

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: El Mahdi Chayti

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

Das große Problem: Die „veraltete Karte"

Stellen Sie sich vor, Sie wandern im dichten Nebel einen Berg hinab (dies repräsentiert das Training eines komplexen KI-Modells). Sie möchten so schnell wie möglich unten ankommen.

Standard-Wanderstrategien (sogenannte Momentum-Methoden) funktionieren wie folgt: Sie schauen sich die Steigung an, an der Sie stehen, machen einen Schritt und gehen dann noch eine Weile in dieselbe Richtung weiter, weil Sie Schwung aufgebaut haben. Das ist großartig für glatte, gerade Pfade.

Berge sind jedoch gekrümmt. Während Sie wandern, neigt und verdreht sich der Boden. Die Richtung, in die Sie vor einem Moment gegangen sind (Ihr „Schwung"), ist jetzt veraltet. Sie zeigt darauf, wo der Boden war, nicht wo er jetzt ist. Dies erzeugt eine „Verzerrung" – Sie drängen in die falsche Richtung, weil Ihre Karte veraltet ist. In der Welt der KI führt dies dazu, dass das Training stecken bleibt oder sich sehr langsam bewegt.

Die alten Lösungen: Teuer oder fehlerhaft

Wissenschaftler haben versucht, dieses Problem der „veralteten Karte" zuvor zu lösen, hatten aber zwei Hauptprobleme:

Die „Doppel-Check"-Methode: Einige versuchten, einen zweiten Schritt zu machen, nur um das neue Gelände zu prüfen, und korrigierten dann ihren Pfad. Das funktioniert, verdoppelt aber die Arbeit, die Sie leisten müssen, und macht die Wanderung doppelt so langsam.
Die Annahme „Perfektes Wetter": Andere Methoden gingen davon aus, dass der Berg perfekt glatt und vorhersehbar ist. Aber echte Berge (und KI-Modelle) sind zerklüftet und unvorhersehbar. Wenn das Gelände rau wird, versagen diese Methoden.

Die neue Lösung: RanSOM (Der „randomisierte Schritt")

Die Autoren schlagen eine neue Methode namens RanSOM vor. Anstatt einen festen, vorhersehbaren Schritt zu machen, schlagen sie einen randomisierten Schritt vor.

Stellen Sie es sich so vor: Anstatt zu sagen: „Ich werde genau 1 Meter geradeaus laufen", sagen Sie: „Ich werde eine zufällige Distanz laufen, aber im Durchschnitt wird es 1 Meter sein." Sie machen vielleicht einen winzigen Schritt oder einen riesigen Sprung, aber der Durchschnitt ist derselbe.

Warum hilft Zufälligkeit?
Das ist der Trick. Indem die Schrittlänge zufällig gemacht wird, erlaubt die Mathematik dem Wanderer, einen cleveren Abkürzungsweg (eine sogenannte „Stein-Identität") zu nutzen, um genau herauszufinden, wie stark sich das Gelände verdreht hat, ohne diesen teuren „Doppel-Check"-Schritt machen zu müssen.

Es ist wie ein magischer Kompass, der Ihnen sagt: „Der Boden hat sich um X-Menge geneigt", nur indem Sie schauen, wo Sie nach Ihrem zufälligen Sprung gelandet sind, anstatt eine Leiter hochklettern zu müssen, um sich umzusehen.

Wie es in zwei Szenarien funktioniert

Das Papier bietet zwei Versionen dieser Wanderstrategie an, abhängig vom Gelände:

1. RanSOM-E (Für offene Felder / Unbeschränkt)

Das Szenario: Sie befinden sich auf einem offenen Feld, wo Sie überallhin laufen können.
Der Trick: Sie verwenden eine Exponentialverteilung für Ihre Schritte. Das bedeutet, Sie machen normalerweise kleine Schritte, aber gelegentlich einen sehr langen Sprung.
Das Ergebnis: Dies ermöglicht es der KI, ihre Richtung sofort unter Verwendung der Mathematik dieses zufälligen Sprungs zu korrigieren, wodurch die Geschwindigkeit hoch und der Pfad genau bleibt.

2. RanSOM-B (Für ummauerte Gärten / Beschränkt)

Das Szenario: Sie befinden sich in einem Garten mit Zäunen. Sie können nicht außerhalb der Mauern laufen. Wenn Sie einen zufälligen Sprung machen, könnten Sie gegen einen Zaun krachen.
Der Trick: Sie verwenden eine Beta-Verteilung. Dies ist eine spezielle Art von Zufälligkeit, die garantiert, dass Ihr Schritt immer innerhalb des Gartens landet, niemals außerhalb. Es ist wie ein „sicherer zufälliger Spaziergang".
Das Ergebnis: Sie erhalten die gleichen Geschwindigkeits- und Genauigkeitsvorteile wie auf dem offenen Feld, aber Sie brechen nie die Regeln des Gartens (die Beschränkungen).

Warum ist das eine große Sache?

Das Papier behauptet drei große Erfolge:

Es ist schnell (Keine zusätzliche Arbeit): Im Gegensatz zu früheren Methoden, die zusätzliche „Vorausblick"-Schritte erforderten (was die Dinge verlangsamt hat), führt RanSOM die Korrektur mit genau demselben Schritt durch, den es ohnehin geplant hatte. Es erhält die Informationen der „zweiten Ordnung" (Krümmung) kostenlos.
Es ist robust (Bewältigt raues Gelände): Es funktioniert sogar dann, wenn der Berg zerklüftet (nicht glatt) ist oder wenn der Nebel chaotisch ist (schweres, langschwänziges Rauschen). Es benötigt nicht die Annahmen von „perfektem Wetter", die ältere Methoden erforderten.
Es ist die bestmögliche Geschwindigkeit: Mathematisch haben sie bewiesen, dass diese Methode den Berg so schnell hinabsteigt, wie es theoretisch möglich ist, selbst unter schwierigen Bedingungen.

Der Realitäts-Test

Die Autoren haben dies auf digitalen „Bergen" (Datensätze wie MNIST1D und MovieLens) getestet.

Das Ergebnis: Ihre Methode (RanSOM) kletterte schneller und gleichmäßiger als die derzeit besten Methoden (wie STORM oder Muon).
Die Beobachtung: Während andere Methoden stolperten und wackelten (Instabilität), hielt RanSOM ein gleichmäßiges, schnelles Tempo, was bewies, dass der Trick mit dem „randomisierten Schritt" in der Praxis tatsächlich funktioniert.

Zusammenfassung

RanSOM ist eine neue Art, KI zu trainieren, die das Problem der „veralteten Richtungen" durch randomisierte Schritte löst. Diese Zufälligkeit wirkt als mathematische Abkürzung, die es der KI ermöglicht, ihren Pfad sofort zu korrigieren, ohne zusätzliche Arbeit zu leisten oder perfekte Bedingungen zu benötigen. Es ist schneller, robuster und funktioniert sowohl auf offenen Flächen als auch in eingeschränkten Bereichen.

Technischer Überblick: RanSOM

1. Problemstellung

Die Arbeit adressiert eine fundamentale Einschränkung in der stochastischen Optimierung für Deep Learning: den durch Krümmung induzierten Bias bei Standard-Momentum-Methoden (z. B. Polyaks Heavy Ball) bei der Anwendung auf nicht-konvexe Landschaften.

In stochastischen Settings aggregiert der Momentum-Vektor $m_t$ Gradienten aus vorherigen Iterationen. Während der Optimierer von $x_{t-1}$ zu $x_t$ fortschreitet, bewirkt die Krümmung der Verlustlandschaft eine Änderung der Gradientenrichtung. Folglich wird $m_{t-1}$ zu einem „veralteten" Schätzer des aktuellen Gradienten $\nabla f(x_t)$ . Dieser Bias, der proportional zum Integral der Hesse-Matrix entlang des Aktualisierungspfades ist, verhindert, dass Standard-Momentum-Methoden die für nicht-konvexe Optimierung erforderliche optimale Probenkomplexität von $O(\epsilon^{-3})$ erreichen, und beschränkt sie oft auf suboptimale Raten von $O(\epsilon^{-4})$ .

Bestehende Korrekturstrategien stehen vor einem „Bias-Varianz-Engpass":

Differenzbasierte Schätzer (z. B. STORM): Erfordern individuelle Sample-Glättung (oft verletzt durch ReLU-Aktivierungen) oder leiden unter hoher Varianz.
Deterministischer Second-Order Momentum (SOM): Erfordert starke globale Lipschitz-Annahmen bezüglich der Hesse-Matrix (beschränkte dritte Ableitungen).
Stochastischer SOM (SOM-Unif): Lockert Glättungsannahmen, verursacht jedoch prohibitiven Rechenaufwand durch die Notwendigkeit zusätzlicher „Look-Ahead"-Abfragen (3 Vorwärts-/Rückwärtsdurchgänge pro Iteration).

2. Methodik: Das RanSOM-Framework

Die Autoren schlagen RanSOM (Randomized Second-Order Momentum) vor, ein einheitliches Framework, das Krümmungsbias ohne zusätzliche Annahmen oder Rechenaufwand eliminiert. Die Kerninnovation besteht im Ersetzen deterministischer Schrittweiten durch randomisierte Schrittweiten, die aus spezifischen Verteilungen gezogen werden.

2.1 Randomisierte partielle Integration

Anstatt einer festen Schrittweite $\eta_t$ wird die Schrittweite $s_t$ als Zufallsvariable mit dem Erwartungswert $\mathbb{E}[s_t] = \eta_t$ behandelt. Durch die Nutzung von Stein-artigen Identitäten (Formeln zur partiellen Integration) verknüpft die Methode die endliche Differenz der Gradienten (den Bias) mit einem einzigen Hesse-Matrix-Vektor-Produkt (HVP), das am zufälligen Endpunkt ausgewertet wird.

Das Framework nutzt zwei spezifische Identitäten:

Exponentielle Identität (Unbeschränkt): Wenn $s \sim \text{Exp}(\lambda)$ , dann gilt:
$\mathbb{E}[g(s) - g(0)] = \frac{1}{\lambda} \mathbb{E}[g'(s)]$
Dies ermöglicht es, den Bias $\nabla f(x_{t+1}) - \nabla f(x_t)$ durch Skalierung des HVP bei $x_{t+1}$ mit $\eta_t$ zu schätzen.
Beta-Identität (Beschränkt): Wenn $s \sim \text{Beta}(1, K)$ , dann gilt:
$\mathbb{E}[g(s) - g(0)] = \mathbb{E}\left[ \frac{1-s}{K} g'(s) \right]$
Dies berücksichtigt den kompakten Träger der Beta-Verteilung und gewährleistet die Machbarkeit bei beschränkter Optimierung.

2.2 Algorithmische Ausprägungen

Das Framework wird in zwei Algorithmen konkretisiert:

RanSOM-E (Unbeschränkt): Verwendet exponentiell verteilte Schritte. Es integriert sich mit einem Linear Minimization Oracle (LMO), um verschiedene geometrische Aktualisierungen zu vereinen, und stellt Normalized SGD ( $L_2$ -Kugel), SignSGD ( $L_\infty$ -Kugel) sowie Muon-artige spektrale Aktualisierungen wieder her.
RanSOM-B (Beschränkt): Verwendet Beta-verteilte Schritte auf $[0, 1]$ . Dies stellt sicher, dass die Aktualisierung $x_{t+1} = (1-s_t)x_t + s_t v_t$ (wobei $v_t$ die LMO-Richtung ist) strikt innerhalb der konvexen zulässigen Menge $C$ bleibt und Projektionsoperationen vermeidet.

2.3 Recheneffizienz

Ein kritischer Vorteil von RanSOM sind seine Rechenkosten. Der Korrekturterm erfordert ein HVP bei $x_{t+1}$ . In modernen automatischen Differenzierungs-Frameworks (z. B. PyTorch, JAX) kann dieses HVP mittels Pearlmutters Trick in einem einzelnen kombinierten Rückwärtsdurchgang zusammen mit der Standard-Gradientenberechnung berechnet werden.

Kosten: $2(F_c + B_c)$ (entspricht zwei Vorwärts-/Rückwärtsdurchgängen).
Vergleich: Dies entspricht den Kosten herkömmlicher varianzreduzierter Methoden wie STORM und ist deutlich günstiger als SOM-Unif, das eine dedizierte Hilfsabfrage erfordert ( $3(F_c + B_c)$ ).

3. Hauptbeiträge

Einheitliches Framework: Eine Methode, die durch randomisierte Schrittweiten und Stein-Identitäten Krümmungsbias eliminiert und sowohl für unbeschränkte als auch beschränkte Optimierung anwendbar ist.
Optimale Konvergenzraten: Die theoretische Analyse beweist, dass RanSOM unter Standardannahmen beschränkter Rauschanteile die optimale Probenkomplexität von $O(\epsilon^{-3})$ erreicht.
Robustheit gegenüber schweren Verteilungsenden: Die Methode erweitert sich auf herausfordernde Settings mit schwer verteiltem Gradientenrauschen ( $p \in (1, 2]$ ) und verallgemeinerter $(L_0, L_1)$ -Glätte (wobei die Hesse-Norm mit der Gradientennorm wächst), ohne dass die Hesse-Matrix Lipschitz-stetig sein muss.
Kein zusätzlicher Overhead: Im Gegensatz zu früheren Second-Order-Korrekturen benötigt RanSOM keine zusätzlichen „Look-Ahead"-Punkte und behält die Standard-Abfragekomplexität von $2(F_c + B_c)$ bei.
Klippungsfrei: Die Methode erreicht optimale Raten ohne explizites Gradienten-Klipping, sondern verlässt sich auf die intrinsische Normalisierung durch LMO-Aktualisierungen und die statistischen Eigenschaften der randomisierten Schritte.

4. Theoretische Ergebnisse

Die Arbeit etabliert die Konvergenz für nicht-konvexe Optimierung unter folgenden Bedingungen:

Annahmen: Das Ziel ist nach unten beschränkt und erfüllt punktweise $(L_0, L_1)$ -Glätte. Stochastische Gradienten und HVPs sind unverzerrt mit affinem schwer verteiltem Rauschen (Momente $p, q \in (1, 2]$ ).
Unbeschränkt (RanSOM-E): Konvergiert zu einem stationären Punkt mit der Rate:
$\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[\|\nabla f(x_t)\|_*] \leq O\left( T^{-\frac{q(p-1)}{2q(p-1)+p}} \right)$
Für den Standardfall ( $p=q=2$ ) wird die optimale Rate $O(T^{-1/3})$ wiederhergestellt.
Beschränkt (RanSOM-B): Konvergiert in Bezug auf die Frank-Wolfe-Lücke $G(x)$ mit derselben optimalen Rate $O(T^{-1/3})$ für $p=q=2$ .

Die Analyse hebt eine asymmetrische Skalierung des Momentum-Parameters $\beta$ hervor: Ein kleineres $\beta$ hilft, hochvarianzige Gradienten zu mitteln, während ein größeres $\beta$ die Krümmungskorrektur wirkungsvoller macht. Der optimale $\beta$ balanciert diese Effekte aus.

5. Experimentelle Ergebnisse

Die Autoren bewerten RanSOM an drei nicht-konvexen Aufgaben:

Binäre Klassifikation (SPLICE): RanSOM-E (Muon-Variante) erreichte die höchste Testgenauigkeit (84,90 %) mit signifikant geringerer Varianz im Vergleich zu STORM (73,35 % ± 10,77 %).
Sequenzklassifikation (MNIST1D): RanSOM-E (Muon) erreichte 91,90 % Genauigkeit, übertraf STORM (88,83 %) und klassisches SOM und behielt gleichzeitig eine hohe Stabilität bei (Standardabweichung ±0,36 vs. ±1,38 für STORM).
Beschränkte Matrix-Vervollständigung (MovieLens): RanSOM-B konvergierte zu einem niedrigeren finalen RMSE als stochastische Frank-Wolfe-Baselines (SFW-Polyak, SFW-SOM) und demonstrierte Wirksamkeit bei der Navigation durch komplexe Geometrien von Nebenbedingungen.

6. Bedeutung und Behauptungen

Die Arbeit behauptet, dass RanSOM das „Dilemma" der Second-Order-Momentum-Korrekturen löst: Es erreicht die optimale Konvergenzrate von $O(\epsilon^{-3})$ ohne die einschränkenden Annahmen von Lipschitz-Hessen-Matrizen oder individueller Sample-Glättung und ohne den Rechenaufwand zusätzlicher Stichproben.

Indem Schrittweiten als Zufallsvariablen behandelt werden, ermöglicht RanSOM eine robuste Second-Order-Bias-Korrektur, die:

Annahmen-arm ist: Handhabt nicht-glatte individuelle Verluste (z. B. ReLU-Netze) und schwer verteiltes Rauschen.
Recheneffizient ist: Entspricht den Kosten von Standard-SGD mit Momentum.
Geometrisch flexibel ist: Generalisiert natürlich zu normalisierten Optimierern und beschränkten Settings über LMOs.

Die Autoren positionieren RanSOM als eine einheitliche Lösung für moderne nicht-konvexe Optimierung, insbesondere in Deep-Learning-Architekturen, bei denen Standard-Glättungsannahmen versagen und Recheneffizienz von höchster Priorität ist.