Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

1. Problemstellung

Das Papier adressiert die Optimierung der verallgemeinerten Operatornorm und des extremen verallgemeinerten Rayleigh-Quotienten unter nullter Ordnung (derivatfrei) eingeschränkten Bedingungen. Das Ziel ist es spezifisch, folgendes zu lösen:
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
wobei $A \in \mathbb{R}^{m \times d}$ und $B \in \mathbb{R}^{\ell \times d}$ Matrizen sind, die ausschließlich über Vorwärtsauswertungen (Black-Box-Zugriff) zugänglich sind.

Hauptbedingungen & Herausforderungen:

• Adjungiertenfrei/Matrizenfrei: Die Adjungierten $A^T$ und $B^T$ sind nicht verfügbar oder inkonsistent mit den Vorwärtsoperatoren (häufig in Legacy-Codes, PDE-Lösern und Tomographie).
• Stellbarkeit: $B$ muss vollen Spaltenrang haben ($\text{rank}(B)=d$), sodass $B^TB \succ 0$ gilt.
• Einschränkungen bestehender Methoden: Aktuelle State-of-the-Art-Methoden nullter Ordnung (z. B. Bresch et al. [7–9]) basieren auf Tangentenraum-Abtastung auf einer verallgemeinerten Sphäre ($S^{d-1}_{B^TB}$). Dies erfordert Kenntnis der Metrik $B^TB$ oder ihrer Quadratwurzel, um Suchrichtungen zu projizieren, was in strikten Black-Box-Szenarien unpraktikabel ist.

2. Methodik

Das Papier schlägt einen grundlegend anderen Ansatz vor, der auf unbeschränkter Abtastung auf der gesamten Einheitssphäre statt auf eingeschränkten Tangenträumen basiert.

A. Unbeschränkte Abtaststrategie

Anstatt Suchrichtungen $x_k$ aus dem Tangentialraum der verallgemeinerten Sphäre zu sampeln (was $B^TB$ erfordert), sampelt die Methode $x_k$ gleichverteilt von der Standard-Einheitssphäre $S^{d-1}$:
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
Dies eliminiert die Notwendigkeit metrikabhängiger Projektionen oder Adjungierten-Informationen.

B. Optimale Schrittweite durch geschlossene Lösung

Für einen aktuellen Iterierten $v_k$ und eine Suchrichtung $x_k$ sucht der Algorithmus eine optimale Schrittweite $\tau_k$, um das Ziel entlang des Retraktionspfads zu maximieren. Die Zielfunktion entlang des Pfades wird zu einem Quotienten quadratischer Funktionen:
$$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$$
Die Koeffizienten ($a_k, \dots, f_k$) werden ausschließlich unter Verwendung von Vorwärtsauswertungen von $A$ und $B$ berechnet.

• Theoretischer Durchbruch: Das Papier beweist, dass das Finden des optimalen $\tau_k$ äquivalent zur Lösung eines 2D-verallgemeinerten Eigenwertproblems ist, das $2 \times 2$ Gram-Matrizen $M_k$ und $N_k$ beinhaltet.
• Ergebnis: Eine geschlossene Lösung für $\tau_k$ wird hergeleitet (Satz 3.1), wodurch sichergestellt wird, dass die Schrittweite für die spezifische zufällige Richtung optimal ist, ohne Heuristiken für die Liniensuche.

C. Riemannischer Optimierungsrahmen nullter Ordnung

Die Methode konstruiert Schätzer für Riemannische Optimierungsgrößen ausschließlich unter Verwendung von Funktionsauswertungen:

1. Gradientenschätzer: Ein erwartungstreuer Schätzer des Riemannschen Gradienten wird unter Verwendung der zufälligen Richtung $x_k$ und der Logik der optimalen Schrittweite konstruiert.
2. Hesse-Schätzer (Quasi-Newton): Das Papier leitet einen erwartungstreuen Schätzer für die Riemannsche Hesse-Matrix her (Korollar 3.3) unter Verwendung von Momenten vierter Ordnung der Gleichverteilung auf der Sphäre. Dies ermöglicht eine Quasi-Newton-Methode nullter Ordnung (Algorithmus 3).
3. Varianzreduktion: Durch Mittelung von $m$ unabhängigen Stichproben (Algorithmus 2) wird die Varianz des Gradientenschätzers reduziert, was die Konvergenz beschleunigt.

3. Hauptbeiträge

1. Unbeschränkte Abtastung auf $S^{d-1}$:
   Das Papier führt ein Abtastschema ein, das auf der gesamten Einheitssphäre operiert statt auf dem Tangentialraum einer verallgemeinerten Sphäre. Dies eliminiert die Anforderung an $B^TB$ oder dessen Adjungierte und macht die Methode auf strikte Black-Box-Szenarien anwendbar, in denen frühere Methoden versagten.

2. Geschlossene optimale Schrittweite:
   Im Gegensatz zu Standardmethoden nullter Ordnung, die feste oder heuristische Schrittweiten verwenden, leitet diese Arbeit eine exakte, geschlossene Lösung für die optimale Schrittweite $\tau_k$ für das spezifische Ziel des Quotienten quadratischer Funktionen her. Dies transformiert das Teilproblem in ein lösbares 2D-verallgemeinertes Eigenwertproblem.

3. Erwartungstreue Hesse-Schätzung:
   Die Autoren liefern eine prinzipielle Herleitung eines erwartungstreuen Schätzers für die Riemannsche Hesse-Matrix in einer derivatfreien Umgebung. Dies ermöglicht die Konstruktion eines zweiter Ordnung Algorithmus nullter Ordnung (Quasi-Newton), der Krümmungsinformationen ohne explizite Ableitungen erfasst.

4. Theoretische Konvergenzgarantien:

   • Fast sichere Konvergenz: Die Folge der Iterierten konvergiert fast sicher zum führenden verallgemeinerten Eigenraum (Satz 3.7).
   • Analyse kritischer Punkte: Das Papier beweist, dass die Folge der Gradienten-Proxy-Werte ($\alpha_k$) fast sicher gegen Null konvergiert, was sicherstellt, dass der Algorithmus nicht in nicht-optimalen kritischen Punkten stecken bleibt (unter milden spektralen Annahmen).
   • Wohldefiniertheit: Es wird bewiesen, dass der Nenner in der Schrittweitenberechnung fast sicher nicht null bleibt, wodurch sichergestellt wird, dass der Algorithmus wohldefiniert ist.

4. Numerische Ergebnisse

Experimente wurden mit synthetischen zufälligen Gauß-Matrizen mit Dimensionen bis zu $d=1000$ durchgeführt.

• Leistung im Vergleich zum State-of-the-Art:
  • In niedrigen Dimensionen ist die vorgeschlagene Methode mit aktuellen Tangentialraum-Abtastmethoden [9] vergleichbar.
  • In hohen Dimensionen ($d \gg 10$) übertrifft die unbeschränkte Sphären-Abtastung Tangentialraum-Methoden signifikant. Dies wird dem größeren Suchraum und der Vermeidung teurer Projektionsoperationen (Matrix-Matrix-Multiplikationen) zugeschrieben, die von Tangentialraum-Methoden erforderlich sind.
• Konvergenzraten:
  • Die Methode zeigt lineare Konvergenz für den relativen Quotientenfehler (RQE).
  • Das minimale quadratische Residuum (MSQR) für die verallgemeinerte Eigen-Gleichung zeigt eine Konvergenzrate von $O(1/k)$, was den oft bei derivatfreien Methoden zu beobachtenden sublinearen Raten überlegen ist.
• Vorteil zweiter Ordnung:
  Die Quasi-Newton-Variante (Algorithmus 3) zeigt ein strikteres Konvergenzverhalten und eine schnellere Fehlerreduktion in der Nähe kritischer Punkte im Vergleich zur Variante erster Ordnung (Algorithmus 2) und schließt effektiv die Leistungslücke in der Nähe der Optima.

5. Bedeutung

Diese Arbeit stellt einen bedeutenden Fortschritt in der derivatfreien Optimierung für spektrale Probleme dar.

• Praktische Auswirkungen: Sie ermöglicht die Berechnung von Operatornormen und Rayleigh-Quotienten in Szenarien, in denen Adjungierte nicht verfügbar, inkonsistent oder zu kostspielig zu berechnen sind (z. B. Legacy-Simulationscodes, komplexe PDE-Löser).
• Theoretische Auswirkungen: Sie schließt die Lücke zwischen zufälliger Suche nullter Ordnung und Riemannscher Optimierung, indem sie erwartungstreue Schätzer sowohl für Gradienten als auch für Hesse-Matrizen auf Mannigfaltigkeiten ohne explizite Mannigfaltigkeitsprojektionen bereitstellt.
• Algorithmische Effizienz: Die geschlossene Schrittweite und die Fähigkeit, ohne Tangentialraumprojektionen zu operieren, machen den Algorithmus recheneffizient und skalierbar auf hochdimensionale Probleme.

Zusammenfassend generalisiert Bresch Methoden nullter Ordnung für Quotienten quadratischer Funktionen, indem er eingeschränkte Tangentialraum-Abtastung durch unbeschränkte Sphären-Abtastung ersetzt, exakte Schrittweiten herleitet und einen rigorosen Rahmen zweiter Ordnung etabliert, der in hochdimensionalen Black-Box-Szenarien bestehende State-of-the-Art-Techniken übertrifft.