Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

1. Probleemstelling

Het artikel behandelt de optimalisatie van de gegeneraliseerde operatornorm en de extremale gegeneraliseerde Rayleigh-kwotiënt onder nulde-orde (afgeleidenvrije) beperkingen. Specifiek is het doel om het volgende op te lossen:
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
waarbij $A \in \mathbb{R}^{m \times d}$ en $B \in \mathbb{R}^{\ell \times d}$ matrices zijn die alleen toegankelijk zijn via voorwaartse evaluaties (black-box toegang).

Belangrijkste Beperkingen en Uitdagingen:

• Adjoint-Vrij/Matrices-Vrij: De adjoints $A^T$ en $B^T$ zijn niet beschikbaar of inconsistent met de voorwaartse operatoren (veelvoorkomend in legacy codes, PDE-oplossers en tomografie).
• Welgesteldheid: $B$ moet volledige kolomrang hebben ($\text{rank}(B)=d$) zodat $B^TB \succ 0$.
• Beperkingen van Bestaande Methoden: Recente state-of-the-art nulde-orde methoden (bijv. Bresch et al. [7–9]) vertrouwen op sampling in de raakruimte op een gegeneraliseerde bol ($S^{d-1}_{B^TB}$). Dit vereist kennis van de metriek $B^TB$ of zijn wortel om zoekrichtingen te projecteren, wat onhaalbaar is in strikte black-box settings.

2. Methodologie

Het artikel stelt een fundamenteel andere aanpak voor, gebaseerd op ongelimiteerde sampling op de volledige eenheidsbol in plaats van beperkte raakruimten.

A. Ongelimiteerde Sampling Strategie

In plaats van zoekrichtingen $x_k$ te samplen vanuit de raakruimte van de gegeneraliseerde bol (wat $B^TB$ vereist), samplet de methode $x_k$ uniform van de standaard eenheidsbol $S^{d-1}$:
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
Dit elimineert de behoefte aan metriek-afhankelijke projecties of adjoint-informatie.

B. Optimale Stapgrootte via Gesloten-Vorm Oplossing

Voor een huidige iteratie $v_k$ en zoekrichting $x_k, zoekt het algoritme een optimale stapgrootte$\tau_k$ om de doelstelling langs het retractiepad te maximaliseren. De doelstellingsfunctie langs het pad wordt een kwotiënt van kwadratische functies:
$$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}$$
De coëfficiënten ($a_k, \dots, f_k$) worden berekend met uitsluitend voorwaartse evaluaties van $A$ en $B$.

• Theoretische Doorbraak: Het artikel bewijst dat het vinden van de optimale $\tau_k$ equivalent is aan het oplossen van een 2D gegeneraliseerd eigenwaardeprobleem met $2 \times 2$ Gram-matrices $M_k$ en $N_k$.
• Resultaat: Een gesloten-vorm oplossing voor $\tau_k$ wordt afgeleid (Stelling 3.1), waardoor de stapgrootte optimaal is voor de specifieke willekeurige richting zonder heuristieken voor lijnzoeken.

C. Nulde-Orde Riemanniaans Optimalisatiekader

De methode construeert schatters voor Riemanniaans optimalisatiegrootheden met uitsluitend functiewaarden:

1. Gradiëntschatter: Een onbevooroordeelde schatter van de Riemanniaanse gradiënt wordt geconstrueerd met behulp van de willekeurige richting $x_k$ en de logica voor de optimale stapgrootte.
2. Hessiaanse Schatter (Quasi-Newton): Het artikel leidt een onbevooroordeelde schatter voor de Riemanniaanse Hessiaan af (Corollarium 3.3) met behulp van momenten van de vierde orde van de uniforme verdeling op de bol. Dit maakt een Nulde-Orde Quasi-Newton methode (Algoritme 3) mogelijk.
3. Variance Reductie: Door het middelen van $m$ onafhankelijke steekproeven (Algoritme 2) wordt de variantie van de gradiëntschatter verminderd, wat de convergentie versnelt.

3. Belangrijkste Bijdragen

1. Ongelimiteerde Sampling op $S^{d-1}$:
   Het artikel introduceert een samplingsschema dat werkt op de volledige eenheidsbol in plaats van de raakruimte van een gegeneraliseerde bol. Dit elimineert de vereiste voor $B^TB$ of zijn adjoint, waardoor de methode toepasbaar is in strikte black-box scenario's waar eerdere methoden faalden.

2. Gesloten-Vorm Optimale Stapgrootte:
   In tegenstelling tot standaard nulde-orde methoden die vaste of heuristische stapgroottes gebruiken, leidt dit werk een exacte, gesloten-vorm oplossing af voor de optimale stapgrootte $\tau_k$ voor het specifieke kwadratische kwotiëntdoel. Dit transformeert het subprobleem naar een oplosbaar 2D gegeneraliseerd eigenwaardeprobleem.

3. Onbevooroordeelde Hessiaanse Schatting:
   De auteurs bieden een principiële afleiding van een onbevooroordeelde schatter voor de Riemanniaanse Hessiaan in een afgeleidenvrije setting. Dit maakt de constructie van een tweede-orde nulde-orde algoritme (Quasi-Newton) mogelijk dat krommingsinformatie vastlegt zonder expliciete afgeleiden.

4. Theoretische Convergentiegaranties:

   • Bijna Zekere Convergentie: De rij van iteraten convergeert bijna zeker naar de leidende gegeneraliseerde eigenruimte (Stelling 3.7).
   • Kritiek Punt Analyse: Het artikel bewijst dat de rij van gradiëntproxies ($\alpha_k$) bijna zeker convergeert naar nul, waardoor het algoritme niet vastloopt in niet-optimale kritieke punten (onder milde spectrale aannames).
   • Welgedefinieerdheid: Er wordt bewezen dat de noemer in de berekening van de stapgrootte bijna zeker niet-nul blijft, waardoor het algoritme welgedefinieerd is.

4. Numerieke Resultaten

Experimenten werden uitgevoerd op synthetische willekeurige Gauss-matrices met afmetingen tot $d=1000$.

• Prestaties versus State-of-the-Art:
  • In lage dimensies is de voorgestelde methode vergelijkbaar met recente raakruimte-sampling methoden [9].
  • In hoge dimensies ($d \gg 10$) presteert de ongelimiteerde bolsampling significant beter dan raakruimtemethoden. Dit wordt toegeschreven aan de grotere zoekruimte en het vermijden van dure projectieoperaties (matrix-matrix vermenigvuldigingen) die door raakruimtemethoden worden vereist.
• Convergentiesnelheden:
  • De methode vertoont lineaire convergentie voor de Relatieve Kwotiëntfout (RQE).
  • De minimale kwadratische residu (MSQR) voor de gegeneraliseerde eigenvergelijking toont een convergentiesnelheid van $O(1/k)$, wat superieur is aan de sublineaire snelheden die vaak worden gezien in afgeleidenvrije methoden.
• Tweede-Orde Voordeel:
  De Quasi-Newton variant (Algoritme 3) vertoont een strengere convergentiegedrag en snellere foutreductie in de buurt van kritieke punten in vergelijking met de eerste-orde variant (Algoritme 2), waardoor de prestatiekloof in de buurt van optima effectief wordt gesloten.

5. Betekenis

Dit werk vertegenwoordigt een aanzienlijke vooruitgang in afgeleidenvrije optimalisatie voor spectrale problemen.

• Praktische Impact: Het maakt de berekening van operatornormen en Rayleigh-kwotiënten mogelijk in scenario's waar adjoint-operatoren niet beschikbaar, inconsistent of te kostbaar zijn om te berekenen (bijv. legacy simulatiecodes, complexe PDE-oplossers).
• Theoretische Impact: Het overbrugt de kloof tussen nulde-orde willekeurig zoeken en Riemanniaanse optimalisatie door het leveren van onbevooroordeelde schatters voor zowel gradiënten als Hessians op variëteiten zonder expliciete variëteitsprojecties.
• Algoritmische Efficiëntie: De gesloten-vorm stapgrootte en het vermogen om te opereren zonder raakruimteprojecties maken het algoritme computationeel efficiënt en schaalbaar naar hoog-dimensionale problemen.

Samenvattend generaliseert Bresch nulde-orde methoden om kwotiënten van kwadratische functies te behandelen door beperkte raakruimte-sampling te vervangen door ongelimiteerde bolsampling, exacte stapgroottes af te leiden en een rigoureus tweede-orde kader te vestigen dat bestaande state-of-the-art technieken overtreft in hoog-dimensionale, black-box settings.