Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds

Diese Arbeit stellt einen Rahmen für die riemannsche Nullter-Ordnung-Optimierung auf geodätisch unvollständigen Mannigfaltigkeiten vor, der durch die Konstruktion strukturerhaltender, geodätisch vollständiger Metriken und die Verwendung eines intrinsischen, symmetrischen Zwei-Punkt-Schätzers konvergente Konvergenzgarantien bietet, die denen im vollständigen Fall entsprechen.

Das Wesentliche

Das Problem: Die gefährliche Kante auf der Landkarte

Stell dir vor, du bist ein Wanderer auf einer sehr speziellen, krummen Welt (einem sogenannten Riemannschen Mannigfaltigkeit). Dein Ziel ist es, den tiefsten Punkt in einer Landschaft zu finden (das Minimum einer Funktion), wo du am glücklichsten bist.

Normalerweise nutzen Wanderer einen Kompass (einen Gradienten), um zu wissen, in welche Richtung es bergab geht. Aber in diesem speziellen Szenario ist dein Kompass kaputt oder zu teuer. Du kannst ihn nicht benutzen. Du musst also raten: „Ich gehe ein kleines Stück nach links, schaue, ob es besser wird, und dann ein Stück nach rechts." Das nennt man Nullter-Ordnung-Optimierung (man nutzt nur die Höhe, nicht die Steigung).

Das große Problem:
Deine Welt hat eine gefährliche Eigenschaft: Sie ist nicht überall sicher. Es gibt Ränder, Abgründe oder Löcher, an denen die Regeln der Geometrie aufhören zu funktionieren. Wenn du zufällig in eine Richtung gehst, könntest du plötzlich über den Rand der Welt fallen und verschwinden. In der Mathematik nennt man das „geodätische Unvollständigkeit".

• Beispiel: Stell dir einen Ballon vor, der nur die innere Oberfläche hat. Wenn du versuchst, geradeaus zu laufen, kommst du irgendwann an den Rand und kannst nicht weiter, ohne aus dem Ballon zu fallen.

Frühere Methoden sagten: „Oh, die Welt ist unvollständig? Dann können wir nicht suchen." Oder sie versuchten, die Welt in einen riesigen, flachen Raum zu packen, was aber oft zu kompliziert oder unmöglich war.

Die Lösung: Ein neuer, sicherer Maßstab

Die Autoren dieses Papiers haben eine geniale Idee entwickelt, um dieses Problem zu lösen. Sie bauen sich eine neue Landkarte für dieselbe Welt.

1. Der „Strukturerhaltende Maßstab" (Das unsichtbare Gummiband)

Stell dir vor, deine Welt ist aus Gummi. An den gefährlichen Rändern (wo man sonst abstürzen würde) ziehen sie das Gummi so stark zusammen, dass es unmöglich wird, über den Rand zu laufen.

• Was passiert? Die Welt wird jetzt „vollständig". Du kannst in jede Richtung laufen, ohne jemals aus der Welt zu fallen.
• Der Clou: Obwohl sich die Form der Welt verändert hat, bleiben die Höhenpunkte und Täler genau dort, wo sie waren. Der tiefste Punkt ist immer noch der tiefste Punkt. Die „Stationären Punkte" (wo du stehen bleiben willst) ändern sich nicht.
• Das Ergebnis: Du kannst jetzt sicher herumlaufen und suchen, ohne Angst zu haben, über den Rand zu fallen.

2. Der „Innere Kompass" (Ohne Außenwelt)

Normalerweise nutzen Forscher, um auf einer gekrümmten Welt zu navigieren, eine große, flache Welt als Referenz (wie eine Landkarte, die man auf einen Tisch legt). Aber unsere neue „Gummi-Welt" passt nicht mehr auf einen flachen Tisch.
Die Autoren sagen: „Wir brauchen keine flache Referenz!"
Sie entwickeln einen inneren Kompass, der sich nur auf die Krümmung der Welt selbst verlässt.

• Die Entdeckung: Sie haben herausgefunden, dass je „krummer" die Welt ist, desto ungenauer wird dein Raten (die Schätzung der Richtung). Je flacher die Welt ist, desto besser funktioniert dein Raten.
• Die Analogie: Wenn du auf einem flachen Feld stehst, ist „links" klar. Wenn du auf einer extrem gekrümmten Kugel stehst, ist „links" schwer zu definieren. Ihr Kompass berücksichtigt diese Krümmung automatisch.

3. Das faire Würfeln (Zufall ohne Bias)

Um zu raten, musst du zufällige Richtungen wählen. Auf einer normalen Kugel würfelst du einfach. Aber auf unserer gekrümmten, neuen Welt ist das schwierig.

• Das Problem: Wenn du einfach einen Würfel wirfst und die Richtung anpasst, landen die Punkte oft an den falschen Stellen (wie wenn man versucht, Punkte auf einem Ellipsoid gleichmäßig zu verteilen, aber sie alle in die Mitte drückt). Das führt zu einem verzerrten Ergebnis.
• Die Lösung: Die Autoren nutzen eine Methode namens „Aussortieren" (Rejection Sampling). Stell dir vor, du wirfst viele Punkte auf die Welt. Die, die nicht genau genug verteilt sind, wirfst du weg und wirfst neu, bis du einen perfekten, fairen Treffer hast. So stellst du sicher, dass deine Suche wirklich zufällig und fair ist.

Warum ist das wichtig? (Die echten Anwendungen)

Warum sollten wir uns dafür interessieren? Weil diese Probleme in der echten Welt überall auftreten:

1. Netzwerk-Optimierung (Mesh Optimization): Stell dir ein 3D-Modell eines Autos oder eines Gesichts vor, das aus vielen kleinen Dreiecken besteht. Wenn du die Form veränderst, darfst du keine Dreiecke überlappen lassen (das würde das Modell zerstören). Die erlaubten Formen bilden eine Welt mit „Rändern". Die Autoren zeigen, wie man die Form verbessert, ohne dass das Modell kollabiert.
2. Bewässerungssysteme: Wo platziert man Sprinkler, damit das Wasser den Garten am besten bedeckt? Man darf sie nicht direkt an den Zaun stellen. Auch hier gibt es Grenzen.
3. Statistik: Bei der Berechnung von Wahrscheinlichkeiten gibt es oft mathematische Grenzen, die man nicht überschreiten darf.

Zusammenfassung in einem Satz

Die Autoren haben einen Weg gefunden, wie man in einer Welt mit gefährlichen Rändern sicher suchen kann, indem sie die Welt so verformen, dass die Ränder verschwinden, aber die Ziele gleich bleiben, und dabei einen neuen Kompass bauen, der die Krümmung der Welt selbst versteht, statt auf eine flache Landkarte zu schauen.

Das Ergebnis: Selbst wenn die Mathematik „kaputt" oder unvollständig aussieht, können wir trotzdem effizient und stabil das beste Ergebnis finden.

Technische Zusammenfassung

Titel: Riemannische Nullter-Ordnung-Gradientenschätzung mit strukturerhaltenden Metriken für geodätisch unvollständige Mannigfaltigkeiten

Autoren: Shaocong Ma, Heng Huang (University of Maryland)
Veröffentlicht: ICLR 2026

---

1. Problemstellung

Das Paper adressiert das Problem der stochastischen Optimierung auf glatten Riemannschen Mannigfaltigkeiten $(M, g)$, bei dem der Gradient der Zielfunktion $f$ nicht direkt verfügbar ist (Black-Box-Szenario). Stattdessen muss der Gradient mittels Nullter-Ordnung-Methoden (nur Funktionsauswertungen) approximiert werden.

Das zentrale Hindernis, das in der Literatur oft übersehen wird, ist die geodätische Unvollständigkeit der zugrunde liegenden Metrik $g$.

• Kontext: In vielen praktischen Anwendungen (z. B. Mesh-Optimierung, Bewässerungsplanung, Kovarianzschätzung) wird die Mannigfaltigkeit oft als Untermannigfaltigkeit eines euklidischen Raums betrachtet, wobei die induzierte euklidische Metrik verwendet wird.
• Das Problem: Diese induzierten Metriken sind oft nicht geodätisch vollständig. Das bedeutet, dass der Exponentialabbildung $\exp_p(v)$ für bestimmte Tangentialvektoren $v$ nicht definiert ist (die Geodäte verlässt die Mannigfaltigkeit oder trifft auf eine Singularität).
• Folge: Bei der Nullter-Ordnung-Optimierung werden zufällige Störungsvektoren $v$ generiert. Wenn diese Vektoren außerhalb des Definitionsbereichs des Exponentialabbildung liegen, ist der geschätzte Gradient undefiniert, was zu Instabilität oder Divergenz führt. Bestehende Konvergenzgarantien setzen typischerweise geodätische Vollständigkeit voraus.

Ziel: Entwicklung eines Rahmens für die Riemannsche Nullter-Ordnung-Optimierung, der auch dann funktioniert, wenn die ursprüngliche Metrik geodätisch unvollständig ist, ohne dabei die Stationaritätseigenschaften der ursprünglichen Funktion zu verlieren.

---

2. Methodik

Die Autoren schlagen einen dreistufigen Ansatz vor, der auf intrinsischen geometrischen Eigenschaften basiert und keine Einbettung in einen größeren euklidischen Raum voraussetzt.

A. Konstruktion strukturerhaltender Metriken (Structure-Preserving Metrics)

Um das Problem der Unvollständigkeit zu lösen, konstruieren die Autoren eine neue Metrik $g'$, die folgende Eigenschaften besitzt (Definition 2.5, Theorem 2.6):

1. Geodätische Vollständigkeit: Die neue Metrik $g'$ ist vollständig, sodass der Exponentialabbildung für alle Richtungen und Längen definiert ist.
2. Konforme Äquivalenz: $g'$ ist konform äquivalent zur ursprünglichen Metrik $g$ ($g' = h \cdot g$ für eine positive glatte Funktion $h$).
3. Erhaltung der Stationarität: Jeder $\epsilon$-stationäre Punkt unter $g$ ist auch ein $\epsilon$-stationärer Punkt unter $g'$. Dies garantiert, dass die Optimierung unter $g'$ nicht zu falschen Lösungen führt.

Die Konstruktion basiert auf einer Modifikation des Satzes von Nomizu & Ozeki (1961), wobei der konforme Faktor $h$ so gewählt wird, dass er das Wachstum der Geodäten kontrolliert und gleichzeitig die Stationaritätseigenschaften erhält.

B. Intrinsische Nullter-Ordnung-Gradientenschätzung

Anstatt die neue Metrik $g'$ in einen euklidischen Raum einzubetten (was numerisch schwierig wäre), entwickeln die Autoren einen intrinsischen Schätzer.

• Sie analysieren den klassischen symmetrischen Zwei-Punkt-Schätzer:
  $$\hat{\nabla}f(p) = \frac{f(\exp_p(\mu v)) - f(\exp_p(-\mu v))}{2\mu} v$$
• Theorem 2.7 leitet eine obere Schranke für den mittleren quadratischen Fehler (MSE) dieses Schätzers her. Wichtig ist, dass diese Schranke intrinsisch ist und nur von der Geometrie der Mannigfaltigkeit abhängt (insbesondere der Schnittkrümmung $\kappa$), nicht von einer Einbettung.
• Die Fehleranalyse zeigt, dass die Genauigkeit des Gradientenschätzers direkt mit der Schnittkrümmung der Mannigfaltigkeit zusammenhängt: Höhere Krümmung führt zu größeren Approximationsfehlern.

C. Unverzerrtes Sampling auf der Einheitskugel

Ein praktisches Problem bei nicht-euklidischen Metriken ist das gleichmäßige Sampling von Vektoren auf der Einheitskugel $S^{d-1}$ bezüglich $g$.

• Der naive Ansatz (Gauß-Vektor ziehen und auf $g$-Einheitslänge skalieren) führt zu einer verzerrten Verteilung (Bias), was die Konvergenz stört.
• Algorithmus 1 verwendet eine Rejektionsstichprobe (Rejection Sampling), um Vektoren exakt gleichverteilt auf der $g$-Einheitskugel zu generieren.
• Proposition 2.8 beweist, dass dieser Algorithmus eine unverzerrte, gleichmäßige Verteilung liefert.

D. Konvergenzanalyse

Unter Verwendung der strukturerhaltenden Metrik $g'$, des intrinsischen Schätzers und des korrekten Samplings wird die Konvergenz des stochastischen Gradientenabstiegs (SGD) analysiert (Theorem 2.9).

• Es wird gezeigt, dass SGD unter allgemeinen Riemannschen Metriken konvergiert.
• Korollar 2.10 stellt sicher, dass unter bestimmten Bedingungen (z. B. wenn die Menge der stationären Punkte kompakt ist) die Komplexitätsgrenzen des klassischen euklidischen Falls ($O(d/\epsilon^4)$) erreicht werden, auch wenn die ursprüngliche Metrik unvollständig war.

---

3. Wichtige Beiträge

1. Strukturerhaltende Metrik-Konstruktion: Ein theoretischer Beweis und eine Methode, um für jede geodätisch unvollständige Metrik eine vollständige, konform äquivalente Metrik zu konstruieren, die die Menge der stationären Punkte erhält.
2. Intrinsische Fehleranalyse: Eine neue Herleitung der MSE-Schranke für Nullter-Ordnung-Schätzer, die explizit die Schnittkrümmung der Mannigfaltigkeit einbezieht, ohne auf Einbettungen zurückzugreifen.
3. Unverzerrtes Sampling-Verfahren: Ein effizienter Algorithmus (Rejection Sampling) zur Generierung unverzerrter Störungsvektoren auf allgemeinen Riemannschen Einheitskugeln, der den Bias des üblichen Skalierungsansatzes eliminiert.
4. Erweiterte Konvergenzgarantien: Die Erweiterung der besten bekannten Komplexitätsgrenzen für Riemannsche Nullter-Ordnung-SGD von geodätisch vollständigen (oft euklidischen) Settings auf eine breitere Klasse von Mannigfaltigkeiten mit allgemeinen Metriken.

---

4. Ergebnisse und Experimente

Die Autoren validieren ihre Theorie durch synthetische und reale Experimente:

• Einfluss des Sampling-Bias: Experimente zeigen, dass der naive Skalierungsansatz zu Divergenz oder instabiler Konvergenz führt, während das vorgeschlagene Rejection Sampling (Algorithmus 1) stabile und effiziente Konvergenz gewährleistet.
• Einfluss der Krümmung: Synthetische Tests auf dem Wahrscheinlichkeits-Simplex bestätigen die theoretische Vorhersage: Die Genauigkeit des Gradientenschätzers (MSE) nimmt mit abnehmender Schnittkrümmung zu.
• Mesh-Optimierung (Praktische Anwendung):
  • Szenario: Optimierung der Knotenpositionen eines Gitters zur Lösung der Helmholtz-Gleichung. Die zulässigen Konfigurationen bilden eine Mannigfaltigkeit, die unter der euklidischen Metrik unvollständig ist (Knoten dürfen keine Kanten kreuzen).
  • Vergleich: Die Methode wird mit "Soft Projection" (schrittweise Verkleinerung des Schritts) und "Reversion" (Zurücksetzen bei ungültigen Schritten) verglichen.
  • Ergebnis: Die vorgeschlagene Methode mit strukturerhaltender Metrik erreicht die niedrigste Fehlerquote (MSE) und zeigt stabile Konvergenz über 20.000 Iterationen, während andere Methoden stagnieren oder instabil werden.

---

5. Bedeutung und Fazit

Dieses Paper schließt eine wichtige Lücke in der Theorie der Riemannschen Optimierung. Es zeigt, dass Nullter-Ordnung-Optimierung auch in Szenarien mit geodätisch unvollständigen Metriken (die in der Praxis häufig vorkommen, z. B. bei physikalischen Simulationen oder Constraints) robust durchgeführt werden kann.

• Theoretischer Fortschritt: Die Arbeit verschiebt den Fokus von der Einbettung in den euklidischen Raum hin zu einer rein intrinsischen Betrachtung der Mannigfaltigkeitsgeometrie.
• Praktische Relevanz: Der vorgeschlagene Rahmen ermöglicht Black-Box-Optimierung in komplexen physikalischen und ingenieurwissenschaftlichen Anwendungen, wo Gradienten nicht berechenbar sind und die Konfigurationsräume durch komplexe Randbedingungen eingeschränkt sind.
• Zukunftsaussichten: Die Autoren weisen auf Limitationen hin, wie den Rechenaufwand für das Sampling in hohen Dimensionen, und schlagen die Entwicklung skalierbarer Algorithmen als zukünftige Forschungsrichtung vor.

Zusammenfassend bietet das Paper einen robusten theoretischen und algorithmischen Rahmen, der die Anwendbarkeit von Riemannscher Nullter-Ordnung-Optimierung erheblich erweitert.