Ein adaptiver Algorithmus für zweistufige Optimierung auf Riemannschen Mannigfaltigkeiten

Grundinformationen

• Paper-ID: 2504.06042
• Titel: An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
• Autoren: Xu Shi, Rufeng Xiao, Rujun Jiang (Fakultät für Datenwissenschaft, Fudan-Universität)
• Klassifizierung: math.OC (Optimierung und Kontrolle)
• Veröffentlichungskonferenz: NeurIPS 2025 (39. Konferenz für Neuronale Informationsverarbeitungssysteme)
• Paper-Link: https://arxiv.org/abs/2504.06042

Zusammenfassung

Bestehende Methoden zur Lösung von Riemannschen zweistufigen Optimierungsproblemen (RBO) erfordern Vorkenntnisse über Informationen erster und zweiter Ordnung sowie Krümmungsparameter der Riemannschen Mannigfaltigkeit zur Bestimmung der Schrittweite. Dies stellt praktische Einschränkungen dar, wenn Parameter unbekannt oder rechnerisch nicht durchführbar sind. In diesem Papier wird der adaptive Riemannsche Hypergradientenabstieg (AdaRHD) zur Lösung von RBO-Problemen vorgeschlagen. Soweit wir wissen, ist AdaRHD die erste Methode in RBO, die eine vollständig adaptive Schrittweiten-Strategie verwendet und die Abhängigkeit von problemspezifischen Parametern eliminiert. Wir zeigen, dass AdaRHD eine Iterationskomplexität von O(1/ε) zum Finden eines ε-stationären Punktes erreicht, was der Komplexität bestehender nicht-adaptiver Methoden entspricht. Darüber hinaus zeigen wir, dass die Ersetzung der Exponentialabbildung durch eine Kontraktionsabbildung die gleiche Komplexitätsgrenze beibehält. Experimente zeigen, dass AdaRHD eine vergleichbare Leistung mit bestehenden nicht-adaptiven Methoden erzielt und gleichzeitig robustere Eigenschaften aufweist.

Forschungshintergrund und Motivation

Problemhintergrund

Zweistufige Optimierungsprobleme haben breite Anwendungen im maschinellen Lernen, einschließlich Reinforcement Learning, Meta-Learning, Hyperparameter-Optimierung und adversariales Lernen. Riemannsche zweistufige Optimierung (RBO) ist die Erweiterung zweistufiger Optimierung auf Riemannsche Mannigfaltigkeiten mit der allgemeinen Form:

$\min_{x \in \mathcal{M}_x} F(x) := f(x, y^*(x))$$\text{s.t. } y^*(x) = \arg\min_{y \in \mathcal{M}_y} g(x,y)$

wobei $\mathcal{M}_x, \mathcal{M}_y$ Riemannsche Mannigfaltigkeiten sind, $f,g$ glatte Funktionen sind, und $g(x,y)$ bezüglich $y$ geodätisch stark konvex ist.

Einschränkungen bestehender Methoden

1. Parameterabhängigkeit: Bestehende RBO-Methoden (wie RHGD, RieBO usw.) erfordern Vorkenntnisse über Parameter der starken Konvexität, Lipschitz-Konstanten und Krümmungsparameter zur Bestimmung der Schrittweite
2. Praktische Einschränkungen: Diese Parameter sind in praktischen Anwendungen oft schwer zu schätzen oder rechnerisch zu aufwändig
3. Unzureichende Robustheit: Strategien mit fester Schrittweite sind empfindlich gegenüber Initialisierung und Problembedingungen

Forschungsmotivation

Die Kernmotivation dieses Papiers ist die Entwicklung eines vollständig adaptiven RBO-Algorithmus, der:

• Keine Vorkenntnisse über problemspezifische Parameter benötigt
• Die Schrittweite automatisch an Problemeigenschaften anpasst
• Die theoretische Komplexität nicht-adaptiver Methoden beibehält
• Stärkere praktische Robustheit bietet

Kernbeiträge

1. Erster adaptiver RBO-Algorithmus: Vorschlag von AdaRHD, dem ersten Riemannschen zweistufigen Optimierungsalgorithmus mit vollständig adaptiver Schrittweiten-Strategie, der die Abhängigkeit von starker Konvexität, Lipschitz-Konstanten und Krümmungsparametern eliminiert
2. Theoretische Komplexitätsübereinstimmung: Beweis, dass AdaRHD eine Iterationskomplexität von O(1/ε) zum Finden eines ε-stationären Punktes erreicht, was der Komplexität bestehender nicht-adaptiver Methoden entspricht
3. Erweiterung auf Kontraktionsabbildungen: Beweis, dass die Ersetzung der Exponentialabbildung durch rechnerisch effizientere Kontraktionsabbildungen die gleiche Komplexitätsgarantie beibehält
4. Experimentelle Validierung: Validierung der Algorithmuseffektivität und Robustheit auf mehreren RBO-Problemen, einschließlich Riemannscher Hyperrepräsentationslernens und robuster Optimierungsprobleme

Methodische Details

Aufgabendefinition

Betrachten Sie das Riemannsche zweistufige Optimierungsproblem:

• Oberes Problem: Minimierung von $F(x) = f(x, y^*(x))$ auf der Mannigfaltigkeit $\mathcal{M}_x$
• Unteres Problem: Für gegebenes $x$, Lösen von $y^*(x) = \arg\min_y g(x,y)$ auf der Mannigfaltigkeit $\mathcal{M}_y$
• Einschränkungen: $g(x,y)$ ist geodätisch stark konvex bezüglich $y$, $f$ muss nicht konvex sein

Kerntechnik: Riemannscher Hypergradient

Der Riemannsche Hypergradient ist definiert als: $G_F(x) = G_x f(x, y^*(x)) - G^2_{xy}g(x, y^*(x))[H^{-1}_y g(x, y^*(x))[G_y f(x, y^*(x))]]$

Da eine exakte Berechnung schwierig ist, wird ein approximierter Riemannscher Hypergradient verwendet: $\hat{G}_F(x, \hat{y}, \hat{v}) = G_x f(x, \hat{y}) - G^2_{xy}g(x, \hat{y})[\hat{v}]$

wobei $\hat{y}$ eine Näherungslösung des unteren Problems ist und $\hat{v}$ eine Näherungslösung des linearen Systems ist.

AdaRHD-Algorithmus-Architektur

Algorithmus 1: Hauptschritte von AdaRHD

1. Lösung des unteren Problems: Verwendung adaptiven Gradientenabstiegs
   • Schrittweiten-Update: $b^2_{k+1} = b^2_k + \|G_y g(x_t, y^k_t)\|^2$
   • Iterations-Update: $y^{k+1}_t = \text{Exp}_{y^k_t}(-\frac{1}{b_{k+1}} G_y g(x_t, y^k_t))$
2. Lösung des linearen Systems: Zwei Strategien
   • Gradientenabstieg: Ähnlich dem unteren Problem mit adaptiver Schrittweite
   • Konjugierter Gradient: Verwendung der konjugierten Gradienten-Methode im Tangentialraum
3. Oberes Update: Adaptiver Hypergradientenabstieg
   • Schrittweiten-Update: $a^2_{t+1} = a^2_t + \|\hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t)\|^2$
   • Iterations-Update: $x_{t+1} = \text{Exp}_{x_t}(-\frac{1}{a_{t+1}} \hat{G}_F(x_t, y^{K_t}_t, v^{N_t}_t))$

Technische Innovationen

1. Kumulative Gradienten-Norm-Strategie: Verwendung des "Kehrwerts der kumulativen Riemannschen Gradienten-Norm" als adaptive Schrittweite, ohne Vorkenntnisse über Problemparameter
2. Dreischichtige Adaptivität: Adaptive Schrittweiten für oberes, unteres Problem und lineares System, bildend einen vollständigen adaptiven Rahmen
3. Kontraktionsabbildungs-Optimierung: Bereitstellung einer Version mit Kontraktionsabbildungen statt Exponentialabbildungen zur Reduzierung der Rechenkomplexität
4. Theoretische Garantien: Strenge Konvergenzanalyse, die technische Herausforderungen der Riemannschen Geometrie bewältigt

Experimentelle Einrichtung

Datensätze und Probleme

1. Einfache Matrixähnlichkeitsprobleme: Optimierung auf Stiefel- und SPD-Mannigfaltigkeiten
   • Datengröße: n=100 und n=1000
   • Parametereinstellung: d=50, r=20, λ=0,01
2. Tiefes Hyperrepräsentationslernens: AFEW-Emotionserkennungsdatensatz
   • 3-schichtige SPD-Netzwerk-Architektur
   • 7 Emotionsklassen, 1747 Trainingsproben
   • Unausgewogene Klassenverteilung
3. Robuste Optimierungsprobleme:
   • Robustes Karcher-Mittel-Problem
   • Robustes Maximum-Likelihood-Schätzungsproblem

Vergleichsmethoden

• RHGD-20/50: Riemannscher Hypergradientenabstieg mit maximalen Iterationen 20/50 für das untere Problem
• AdaRHD-GD: AdaRHD mit Gradientenabstieg zur Lösung des linearen Systems
• AdaRHD-CG: AdaRHD mit konjugiertem Gradienten zur Lösung des linearen Systems

Bewertungsmetriken

• Wert der oberen Zielfunktion
• Fehler der Hypergradient-Schätzung
• Validierungsgenauigkeit
• Konvergenzzeit und Iterationszahl

Experimentelle Ergebnisse

Hauptergebnisse

Experimente mit einfachen Problemen:

• AdaRHD zeigt schnellere Konvergenzgeschwindigkeit bei beiden Datengröße
• Fehler der Hypergradient-Schätzung ist niedriger, besonders bei AdaRHD-CG
• Vorteil in Rechenzeit, besonders bei großskaligen Problemen

Robustheitsanalyse:

• AdaRHD zeigt signifikante Robustheit unter verschiedenen Anfangsschrittweiten-Einstellungen
• RHGD schlägt bei großen Schrittweiten (5, 1, 0,5) fehl, während AdaRHD stabil konvergiert
• AdaRHD-CG ist am schnellsten beim Erreichen von 85% Validierungsgenauigkeit

Schlüsselfunde

1. Robustheitsvorteil: AdaRHD ist unempfindlich gegenüber der Wahl der Anfangsschrittweite, während RHGD bei ungeeigneten Schrittweiten völlig fehlschlägt
2. Effizienzsteigerung: Obwohl AdaRHD mehr äußere Iterationen benötigt, ist die Gesamtrechenzeit aufgrund der adaptiven Strategie wettbewerbsfähig
3. Methodenwahl: AdaRHD-CG ist AdaRHD-GD in Genauigkeit und Robustheit überlegen, letzteres konvergiert jedoch schneller in der Anfangsphase

Theoretische Analyse

Komplexitätsergebnisse

Theorem 3.1: Unter Standardannahmen erfüllt AdaRHD: $\frac{1}{T}\sum_{t=0}^{T-1} \|G_F(x_t)\|^2_{x_t} \leq \frac{C}{T} = O\left(\frac{1}{T}\right)$

Korollar 3.1: Komplexität zum Erreichen eines ε-stationären Punktes:

• Gesamtiterationen: T = O(1/ε)
• Gradienten-Komplexität: $G_f = O(1/ε)$, $G_g = O(1/ε^2)$
• Hessian-Vektor-Produkt-Komplexität: AdaRHD-GD ist O(1/ε²), AdaRHD-CG ist Õ(1/ε)

Technische Herausforderungen

1. Geometrische Struktur: Die Krümmung der Riemannschen Mannigfaltigkeit führt zu zusätzlicher Analysekomplexität
2. Dreiecksabstands-Schranken: Erfordert Verwendung von Riemannschen Mannigfaltigkeits-spezifischen Dreiecksabstands-Schranken statt euklidischer Entsprechungen
3. Adaptive Schrittweiten-Analyse: Adaptive Strategien können zu Divergenzverhalten in der Anfangsphase führen, erfordern strenge theoretische Behandlung

Verwandte Arbeiten

Zweistufige Optimierung

• Euklidische zweistufige Optimierung: AID, ITD, Neumann-Reihen, konjugierte Gradienten und andere Methoden
• Neuere adaptive Methoden: D-TFBO usw.

Riemannsche Optimierung

• Klassische Methoden: Riemannscher Gradientenabstieg, nichtlinearer konjugierter Gradient, Varianzreduktion stochastischer Gradienten usw.
• Adaptive Methoden: RASA, RAMSGrad, Riemannian SAM usw.

Riemannsche zweistufige Optimierung

• RieBO/RieSBO: Deterministische und stochastische Riemannsche zweistufige Optimierung
• RHGD: Riemannscher Hypergradientenabstiegs-Rahmen
• RF2SA: Vollständig zufällige Erste-Ordnung-Methode

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. AdaRHD ist der erste vollständig adaptive Riemannsche zweistufige Optimierungsalgorithmus, der die Abhängigkeit von problemspezifischen Parametern eliminiert
2. Theoretisch erreicht die gleiche O(1/ε)-Komplexität wie nicht-adaptive Methoden
3. Experimente validieren die Effektivität des Algorithmus und signifikante Robustheitsvorzüge

Einschränkungen

1. Komplexitätslücke: Gradienten- und Hessian-Vektor-Produkt-Komplexität sind um den Faktor 1/ε höher als nicht-adaptive Methoden
2. Annahmebedingungen: Erfordert immer noch geodätische starke Konvexität des unteren Problems
3. Einfach- vs. Doppelschleife: Derzeit nur Doppelschleife-Algorithmen berücksichtigt

Zukünftige Richtungen

1. Einfachschleife-Algorithmen: Entwurf adaptiver Einfachschleife-Riemannscher zweistufiger Optimierungsalgorithmen
2. Stochastische Einstellung: Erweiterung auf stochastische Riemannsche zweistufige Optimierung
3. Schwache Konvexität: Behandlung geodätisch konvexer (nicht stark konvexer) unterer Ziele
4. Komplexitätsoptimierung: Erkundung adaptiver Strategien zur Beseitigung der 1/ε-Lücke

Tiefgreifende Bewertung

Stärken

1. Theoretische Innovation: Erste vollständig adaptive Implementierung in RBO mit strenger theoretischer Analyse
2. Praktischer Wert: Signifikante Verbesserung der Algorithmus-Robustheit und Benutzerfreundlichkeit
3. Technische Tiefe: Erfolgreiche Bewältigung technischer Herausforderungen der Riemannschen Geometrie
4. Umfassende Experimente: Vollständige Validierung über mehrere Anwendungsszenarien

Mängel

1. Komplexitätskosten: Adaptivität geht mit zusätzlichen Rechenkomplexitätskosten einher
2. Annahmebeschränkungen: Erfordert immer noch relativ starke Annahmebedingungen
3. Anwendungsbereich: Hauptsächlich auf spezifische Riemannsche Mannigfaltigkeiten konzentriert

Auswirkungen

• Akademischer Beitrag: Wichtiger Fortschritt im Schnittstellenbereich von Riemannscher Optimierung und zweistufiger Optimierung
• Praktischer Wert: Bietet robustere Werkzeuge für Riemannsche zweistufige Optimierung in praktischen Anwendungen
• Nachfolgeforschung: Legt Grundlagen für weitere Forschung zu adaptiver Riemannscher Optimierung

Anwendungsszenarien

• Riemannsches Meta-Learning und Neuronale Architektursuche
• Bildsegmentierung und Low-Rank-Adaptation
• Robuste Statistik und geometrisches maschinelles Lernen
• Alle Anwendungen, die zweistufige Optimierung unter Mannigfaltigkeits-Einschränkungen erfordern

Dieses Papier leistet einen wichtigen Beitrag im Bereich der Riemannschen zweistufigen Optimierung und realisiert erstmals ein vollständig adaptives Algorithmus-Design, das die theoretische Komplexität beibehält und gleichzeitig die praktische Anwendbarkeit und Robustheit erheblich verbessert. Trotz gewisser Komplexitätskosten machen seine theoretischen Innovationen und praktischen Werte es zu einem wichtigen Fortschritt in diesem Bereich.