Riemannian Dueling Optimization

Diese Arbeit führt Riemannian Dueling Normalized Gradient Descent und Riemannian Dueling Frank-Wolfe als neue Algorithmen zur Optimierung von Zielfunktionen auf Riemannschen Mannigfaltigkeiten unter Verwendung eines Vergleichsorakels ein und belegt deren Wirksamkeit durch theoretische Komplexitätsanalysen sowie numerische Experimente.

Das Wesentliche

Der Kampf der Kandidaten: Wie man ohne Landkarte den besten Weg findet

Stellen Sie sich vor, Sie sind ein Tourist in einer fremden Stadt, die auf einer krummen, gewölbten Oberfläche liegt – vielleicht auf einem riesigen, unsichtbaren Hügel oder in einer gewundenen Schlucht. Ihr Ziel ist es, den tiefsten Punkt (den „Taler") zu finden, wo die Sonne am schönsten scheint.

Das Problem: Sie haben keine Landkarte, keine GPS-App und niemand kann Ihnen sagen, wie hoch Sie gerade sind oder wie steil der Abhang ist. Sie dürfen auch keine Zahlenwerte ablesen.

Alles, was Sie haben, ist ein lokaler Guide, der Ihnen nur eine einzige Frage beantworten kann:
„Wenn Sie sich einen Schritt nach links bewegen und einen Schritt nach rechts, welcher Weg ist besser?"

Das ist im Grunde das, was in diesem Papier untersucht wird: Riemannsche Duell-Optimierung.

Hier ist die einfache Erklärung, wie die Autoren dieses Problem lösen:

1. Das Problem: Die Welt ist nicht flach

In der klassischen Mathematik (dem „euklidischen Raum") ist die Welt wie ein flaches Blatt Papier. Wenn man dort einen Weg sucht, kann man sich leicht vorstellen, dass „geradeaus" immer der beste Weg ist.

Aber in der echten Welt (z. B. bei Robotern, die sich drehen müssen, oder bei KI-Modellen für Bilder) ist die Welt oft wie eine Kugel oder eine gewölbte Oberfläche. Hier funktionieren die alten Regeln nicht mehr. Eine gerade Linie auf einer Kugel ist eigentlich ein Bogen (ein „Großkreis"). Wenn Sie versuchen, auf einer Kugel wie auf einem Blatt Papier zu laufen, verirren Sie sich schnell.

Zusätzlich haben wir das Problem, dass wir keine Zahlen bekommen. Wir wissen nicht, ob Punkt A „100 Meter tief" und Punkt B „90 Meter tief" ist. Wir wissen nur: „Punkt A ist besser als Punkt B". Das nennt man ein Duell (oder einen Vergleich).

2. Die Lösung: Der „Riemannsche Duell-Gradient"

Die Autoren entwickeln zwei neue Methoden, um diesen blinden Weg zu finden.

Methode A: Der „Zufalls-Taster" (RDNGD)

Stellen Sie sich vor, Sie stehen auf dem Hügel und sind unsicher, wohin Sie gehen sollen.

1. Sie strecken Ihren Arm in eine zufällige Richtung aus (auf der gekrümmten Oberfläche).
2. Sie fragen Ihren Guide: „Ist der Punkt, den ich sehe, wenn ich in diese Richtung gehe, besser als der Punkt, wenn ich in die ganz genaue Gegenrichtung gehe?"
3. Der Guide sagt: „Ja, die linke Seite ist besser!"
4. Sie machen einen Schritt in die linke Richtung.

Das klingt simpel, aber auf einer gekrümmten Welt ist das sehr schwierig zu berechnen. Die Autoren haben eine mathematische Formel entwickelt, die genau weiß, wie man diese „zufälligen Stöße" auf einer Kugel oder einem gewölbten Raum kombiniert, um langsam, aber sicher den tiefsten Punkt zu finden. Sie nennen dies RDNGD (Riemannian Dueling Normalized Gradient Descent).

• Der Clou: Sie brauchen nur einen Vergleich pro Schritt. Das ist extrem effizient.
• Das Ergebnis: Selbst ohne zu wissen, wie steil der Berg ist, finden Sie den Gipfel (oder Tal).

Methode B: Der „Projektions-freie Wanderer" (RDFW)

Manchmal ist es sehr schwierig oder teuer, einen Schritt direkt auf den besten Pfad zu setzen (man nennt das „Projektion"). Stellen Sie sich vor, Sie laufen durch einen dichten Wald mit vielen Zäunen. Es ist mühsam, genau zu berechnen, wo der nächste Zaun ist, um nicht hindurchzulaufen.

Dafür haben die Autoren eine zweite Methode entwickelt, die RDFW (Riemannian Dueling Frank-Wolfe).

• Die Analogie: Statt zu versuchen, den perfekten Pfad zu berechnen, schauen Sie sich nur die Ecken des Geländes an (die „Eckpunkte" des Waldes).
• Sie fragen: „Welche dieser Ecken ist am besten?"
• Dann gehen Sie einen kleinen Schritt in Richtung dieser besten Ecke.
• Vorteil: Sie müssen nie berechnen, ob Sie gegen einen Zaun stoßen. Sie bleiben automatisch im erlaubten Bereich, indem sie einfach nur zu den „Ecken" des Problems wandern.

3. Wo wird das genutzt? (Die echten Anwendungen)

Die Autoren zeigen, dass diese Methoden nicht nur theoretisch cool sind, sondern echte Probleme lösen:

• Angriffe auf KI (Deep Learning): Stellen Sie sich vor, Sie sind ein Hacker, der ein KI-System täuschen will. Sie dürfen dem System keine genauen Fehlerzahlen geben, sondern nur sagen: „Dieses Bild ist verwirrender als jenes." Mit ihrer Methode können sie kleine, unsichtbare Änderungen an einem Bild vornehmen, die die KI komplett durcheinanderbringen, ohne dass sie die genauen Fehlerwerte kennen.
• Horizont-Ausrichtung (Fotografie): Wenn Sie ein Foto machen, ist der Horizont oft schief. Normalerweise braucht man eine mathematische Formel, um ihn geradezurücken. Aber was, wenn Sie keine Formel haben, sondern nur ein menschliches Urteil? „Ist Bild A flacher als Bild B?" Die Methode nutzt diese menschlichen Vergleiche, um den perfekten Winkel zu finden, bei dem das Bild gerade aussieht.
• Robotik: Roboterarme bewegen sich oft auf krummen Bahnen (wie auf einer Kugel). Wenn man sie trainiert, kann man oft nur sagen: „Bewegung A war besser als Bewegung B", aber nicht genau messen, wie viel besser. Die neuen Algorithmen helfen hier, die Bewegungen zu optimieren.

Zusammenfassung in einem Satz

Die Autoren haben eine neue Art von „Blindenkompass" erfunden, der es Computern ermöglicht, den besten Weg auf gekrümmten, komplexen Oberflächen zu finden, indem sie nur Vergleiche („Ist A besser als B?") nutzen, statt genaue Zahlenwerte zu benötigen.

Das ist besonders wichtig, weil in der modernen KI und Robotik oft genau diese Art von ungenauen, vergleichenden Daten vorliegt, während die alten Methoden versagen würden.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert das Problem der Optimierung auf Riemannschen Mannigfaltigkeiten unter der Einschränkung, dass keine expliziten Funktionswerte oder Gradienten des Zielobjektivs $f(x)$ verfügbar sind. Stattdessen steht nur ein Paarvergleichs-Orakel (Dueling Oracle) zur Verfügung. Dieses Orakel $Q_f(x, y)$ gibt für zwei abgefragte Punkte $x, y$ lediglich an, welcher Punkt einen besseren (kleineren) Funktionswert hat:
$$Q_f(x, y) = 2 \cdot \mathbb{1}(f(x) > f(y)) - 1$$

Hintergrund und Motivation:
Viele moderne Anwendungen (z. B. Empfehlungssysteme, Robotik, Repräsentationslernen) finden in nicht-euklidischen Räumen statt. Beispiele sind:

• Hyperbolische Räume für hierarchische Embeddings.
• Die Gruppe der speziellen orthogonalen Matrizen $SO(3)$ für Trajektorienoptimierung in der Robotik.
• Stiefel-Mannigfaltigkeiten für Projektionsmatrizen.
• Constraints wie Sphären oder Simplexe.

Bestehende „Dueling"-Optimierungsalgorithmen konzentrieren sich fast ausschließlich auf den euklidischen Raum. Die Übertragung auf Riemannsche Mannigfaltigkeiten ist nicht trivial, da die Krümmung der Mannigfaltigkeit die Standard-Trigonometrie und Linearisierung bricht, was die Schätzung von Gradientenrichtungen erschwert.

2. Methodik

Die Autoren entwickeln Algorithmen, die Gradienteninformationen ausschließlich durch paarweise Vergleiche schätzen und diese auf Riemannschen Mannigfaltigkeiten nutzen.

A. Riemannian Dueling Normalized Gradient Descent (RDNGD)

Dies ist der Kernalgorithmus für den Fall, dass Projektionen auf die zulässige Menge $X$ möglich sind (oder $X=M$).

• Gradientenschätzer: Anstatt den Gradienten direkt zu schätzen, wird eine Richtung $u$ zufällig auf der Tangentialkugel $S_{x_k}M(1)$ gewählt. Der Algorithmus vergleicht die Funktionswerte an den exponierten Punkten $\text{Exp}_{x_k}(\nu u)$ und $\text{Exp}_{x_k}(-\nu u)$.
• Schätzer-Formel: Der Schätzer ist definiert als $h_\nu(x) = Q_f(\text{Exp}_x(\nu u), \text{Exp}_x(-\nu u)) \cdot u$.
• Theoretische Grundlage: Es wird bewiesen, dass dieser Schätzer im Erwartungswert mit dem normalisierten Gradienten $\frac{\text{grad} f(x)}{\|\text{grad} f(x)\|}$ übereinstimmt (bis auf einen konstanten Faktor $\hat{C}$ und einen Bias, der durch die Glattheit $L$ und den Störparameter $\nu$ kontrolliert wird).
• Update-Regel: Der Algorithmus führt einen Schritt entlang der negativen Schätzer-Richtung durch und projiziert zurück auf die Mannigfaltigkeit (bzw. die zulässige Menge $X$).
• Varianten: Es werden sowohl konstante als auch kosinus-angepasste (cosine annealing) Schrittweiten untersucht.

B. Riemannian Recurrent Dueling Normalized Gradient Descent (RRDNGD)

Für stark geodätisch konvexe Funktionen ($\alpha$-strongly convex) wird eine mehrstufige (phasenbasierte) Variante vorgeschlagen, um eine lineare Konvergenzrate zu erreichen.

• Das Verfahren läuft in Phasen, wobei in jeder Phase die Zielgenauigkeit $\epsilon_k$ halbiert wird.
• Durch die starke Konvexität lässt sich die Reduktion des Funktionswertfehlers direkt in eine Reduktion des quadratischen Abstands zum Optimum umwandeln.

C. Riemannian Dueling Frank-Wolfe (RDFW)

Für Fälle, in denen Projektionen auf die Menge $X$ rechnerisch zu teuer oder unmöglich sind (z. B. bei komplexen Constraints auf SPD-Matrizen), wird ein projektionsfreier Ansatz entwickelt.

• Linear Minimization Oracle (LMO): Statt einer Projektion wird ein lineares Minimierungsproblem gelöst: $\arg \min_{z \in X} \langle \bar{h}_k, \text{Log}_{x_k}(z) \rangle$.
• Rauschreduktion: Da das LMO sehr empfindlich auf Rauschen im Gradientenschätzer reagiert (im Gegensatz zu Projektionsmethoden), wird ein Batch-Schätzer verwendet. Es werden $M_k$ unabhängige Richtungen gesampelt und gemittelt, um die Varianz zu reduzieren.
• Update: Der neue Punkt wird entlang der Geodäte von $x_k$ zum gefundenen LMO-Punkt $z_k$ bewegt.

3. Hauptbeiträge

1. Erste theoretische Rahmenbedingungen: Einführung des ersten Rahmens für Riemannsche Dueling-Optimierung mit reinen Vergleichs-Orakeln.
2. RDNGD Algorithmus: Entwicklung und Analyse des ersten Riemannschen Normalized Gradient Descent für Dueling-Feedback.
   • Nachweis der Iterationskomplexität für geodätisch $L$-glatte Funktionen (nicht-konvex) und geodätisch konvexe Funktionen.
   • Verbesserung der Konstanten und der Dimensionsabhängigkeit im Vergleich zu früheren euklidischen Ergebnissen (z. B. Saha et al., 2021).
3. RRDNGD: Ein Algorithmus für stark konvexe Probleme mit linearer Konvergenzrate.
4. RDFW (Projektionsfrei): Der erste projektionsfreie Dueling-Algorithmus für Mannigfaltigkeiten. Dies ist entscheidend für Anwendungen, wo Projektionen teuer sind, aber lineare Minimierung einfach ist.
5. Theoretische Verbesserungen:
   • Schärfere Schranken für den Bias des Gradientenschätzers (Entfernung logarithmischer Faktoren im Vergleich zu euklidischen Analoga).
   • Bessere Konstanten für die Dimensionsabhängigkeit ($O(d)$ statt $O(d \log d)$ in bestimmten Szenarien).

4. Ergebnisse

Die Algorithmen wurden auf synthetischen und realen Datensätzen evaluiert:

• Synthetische Probleme:

  • Rayleigh-Quotient-Maximierung: RDNGD erreicht eine vergleichbare Genauigkeit wie Zeroth-Order Riemannian Gradient Descent (ZO-RGD), obwohl ZO-RGD Funktionswerte benötigt, während RDNGD nur Vergleiche nutzt.
  • Karcher-Mittelwert (auf SPD-Matrizen): RDNGD konvergiert erfolgreich zur Lösung.
  • Eingeschränkter Karcher-Mittelwert: RDFW löst erfolgreich das Problem mit Constraints ($H \preceq X \preceq A$), wo Projektionen schwierig wären.

• Reale Anwendungen:

  • Angriff auf Deep Neural Networks (DNN): Simulation eines Black-Box-Angriffs auf VGG-Netze (CIFAR-10) unter $\ell_2$-Norm-Beschränkung. RDNGD erreicht in weniger Iterationen und weniger CPU-Zeit eine höhere adversariale Verlustfunktion als ZO-RGD, obwohl es nur mit schwächeren Informationen (Vergleiche statt Funktionswerte) arbeitet.
  • Horizon Leveling (Horizont-Nivellierung): Optimierung einer Rotationsmatrix in $SO(2)$, um den Horizont eines Bildes zu korrigieren. Basierend auf paarweisen menschlichen Präferenzen (welches Bild ist „ebenerer?") konnte der Algorithmus in wenigen Iterationen eine präzise Korrektur finden.

5. Bedeutung und Fazit

Das Paper schließt eine signifikante Lücke zwischen der Riemannschen Optimierung und der präferenzbasierten Optimierung (Dueling Bandits).

• Allgemeingültigkeit: Der Ansatz ist unabhängig von der Quelle des Vergleichs (menschlich oder maschinell) und funktioniert in komplexen, gekrümmten Räumen.
• Praktische Relevanz: Viele reale Optimierungsprobleme (Robotik, KI-Sicherheit, Empfehlungssysteme) finden in nicht-euklidischen Räumen statt, wo Gradienten oft nicht verfügbar sind. Die vorgestellten Algorithmen bieten die erste theoretisch fundierte und praktisch erprobte Lösung für diese Kombination.
• Zukünftige Richtungen: Die Arbeit ebnet den Weg für beschleunigte Algorithmen, Hessian-basierte Methoden zur Vermeidung von Sattelpunkten und die Untersuchung, wie das Rauschen im Schätzer genutzt werden kann, um lokale Minima zu verlassen.

Zusammenfassend demonstriert das Paper, dass effiziente Optimierung auf Mannigfaltigkeiten auch dann möglich ist, wenn nur sehr begrenzte Informationen (reine Paarvergleiche) verfügbar sind, und liefert dabei theoretisch fundierte Algorithmen mit nachweisbaren Konvergenzraten.