Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

1. Enunciato del Problema

Il documento affronta l'ottimizzazione della norma generalizzata dell'operatore e del quoziente di Rayleigh generalizzato estremo sotto vincoli di ordine zero (senza derivate). Nello specifico, l'obiettivo è risolvere:
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
dove $A \in \mathbb{R}^{m \times d}$ e $B \in \mathbb{R}^{\ell \times d}$ sono matrici accessibili solo tramite valutazioni in avanti (accesso a scatola nera).

Vincoli e Sfide Chiave:

• Senza Adiunto/Senza Matrice: Gli adiunti $A^T$ e $B^T$ non sono disponibili o sono inconsistenti con gli operatori in avanti (comune nei codici legacy, nei solutori di PDE e nella tomografia).
• Benessere: $B$ deve avere rango di colonna pieno ($\text{rank}(B)=d$) in modo che $B^TB \succ 0$.
• Limitazioni dei Metodi Esistenti: I recenti metodi all'avanguardia di ordine zero (ad esempio Bresch et al. [7–9]) si basano sul campionamento nello spazio tangente su una sfera generalizzata ($S^{d-1}_{B^TB}$). Ciò richiede la conoscenza della metrica $B^TB$ o della sua radice quadrata per proiettare le direzioni di ricerca, il che è impraticabile in contesti di stretta scatola nera.

2. Metodologia

Il documento propone un approccio fondamentalmente diverso basato sul campionamento non vincolato sull'intera sfera unitaria piuttosto che su spazi tangenti ristretti.

A. Strategia di Campionamento Non Vincolato

Invece di campionare le direzioni di ricerca $x_k$ dallo spazio tangente della sfera generalizzata (che richiede $B^TB$), il metodo campiona $x_k$ uniformemente dalla sfera unitaria standard $S^{d-1}$:
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
Ciò elimina la necessità di proiezioni dipendenti dalla metrica o di informazioni sugli adiunti.

B. Passo Ottimale tramite Soluzione in Forma Chiusa

Per un iterato corrente $v_k$ e una direzione di ricerca $x_k$, l'algoritmo cerca un passo ottimale $\tau_k$ per massimizzare l'obiettivo lungo il percorso di retrazione. La funzione obiettivo lungo il percorso diventa un quoziente di funzioni quadratiche:
$$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}$$
I coefficienti ($a_k, \dots, f_k$) sono calcolati utilizzando solo valutazioni in avanti di $A$ e $B$.

• Svolta Teorica: Il documento dimostra che trovare il $\tau_k$ ottimale è equivalente a risolvere un problema agli autovalori generalizzato 2D che coinvolge le matrici di Gram $2 \times 2$ $M_k$ e $N_k$.
• Risultato: Viene derivata una soluzione in forma chiusa per $\tau_k$ (Teorema 3.1), garantendo che il passo sia ottimale per la specifica direzione casuale senza euristiche di ricerca lineare.

C. Framework di Ottimizzazione Riemanniana di Ordine Zero

Il metodo costruisce stimatori per le quantità di ottimizzazione Riemanniana utilizzando solo valutazioni della funzione:

1. Stimatore del Gradiente: Viene costruito uno stimatore non distorto del gradiente Riemanniano utilizzando la direzione casuale $x_k$ e la logica del passo ottimale.
2. Stimatore dell'Hessiano (Quasi-Newton): Il documento deriva uno stimatore non distorto per l'Hessiano Riemanniano (Corollario 3.3) utilizzando i momenti del quarto ordine della distribuzione uniforme sulla sfera. Ciò abilita un metodo Quasi-Newton di ordine zero (Algoritmo 3).
3. Riduzione della Varianza: Mediando $m$ campioni indipendenti (Algoritmo 2), la varianza dello stimatore del gradiente viene ridotta, accelerando la convergenza.

3. Contributi Chiave

1. Campionamento Non Vincolato su $S^{d-1}$:
   Il documento introduce uno schema di campionamento che opera sull'intera sfera unitaria piuttosto che sullo spazio tangente di una sfera generalizzata. Ciò elimina il requisito di $B^TB$ o del suo adiunto, rendendo il metodo applicabile a scenari di stretta scatola nera dove i metodi precedenti fallivano.

2. Passo Ottimale in Forma Chiusa:
   A differenza dei metodi standard di ordine zero che utilizzano passi fissi o euristici, questo lavoro deriva una soluzione esatta e in forma chiusa per il passo ottimale $\tau_k$ per il specifico obiettivo di quoziente quadratico. Ciò trasforma il sottoproblema in un problema agli autovalori generalizzato 2D risolvibile.

3. Stima Non Distorta dell'Hessiano:
   Gli autori forniscono una derivazione rigorosa di uno stimatore non distorto per l'Hessiano Riemanniano in un contesto senza derivate. Ciò consente la costruzione di un algoritmo di ordine zero del secondo ordine (Quasi-Newton) che cattura le informazioni sulla curvatura senza derivate esplicite.

4. Garanzie di Convergenza Teorica:

   • Convergenza Quasi Certamente: La sequenza di iterati converge quasi certamente allo spazio degli autovettori generalizzati principale (Teorema 3.7).
   • Analisi dei Punti Critici: Il documento dimostra che la sequenza dei proxy del gradiente ($\alpha_k$) converge a zero quasi certamente, garantendo che l'algoritmo non rimanga bloccato in punti critici non ottimali (sotto lievi assunzioni spettrali).
   • Bene-definitezza: Viene dimostrato che il denominatore nel calcolo del passo rimane non nullo quasi certamente, garantendo che l'algoritmo sia ben definito.

4. Risultati Numerici

Gli esperimenti sono stati condotti su matrici gaussiane casuali sintetiche con dimensioni fino a $d=1000$.

• Prestazioni vs Stato dell'Arte:
  • In basse dimensioni, il metodo proposto è comparabile ai recenti metodi di campionamento nello spazio tangente [9].
  • In alte dimensioni ($d \gg 10$), il campionamento sulla sfera non vincolato supera significativamente i metodi basati sullo spazio tangente. Ciò è attribuito allo spazio di ricerca più ampio ed all'evitamento di operazioni di proiezione costose (moltiplicazioni matrice-matrice) richieste dai metodi basati sullo spazio tangente.
• Tassi di Convergenza:
  • Il metodo esibisce una convergenza lineare per l'Errore del Quoziente Relativo (RQE).
  • Il residuo quadratico minimo (MSQR) per l'equazione agli autovalori generalizzata mostra un tasso di convergenza di $O(1/k)$, che è superiore ai tassi sublineari spesso osservati nei metodi senza derivate.
• Vantaggio del Secondo Ordine:
  La variante Quasi-Newton (Algoritmo 3) dimostra un comportamento di convergenza più rigoroso e una riduzione più rapida dell'errore vicino ai punti critici rispetto alla variante del primo ordine (Algoritmo 2), chiudendo efficacemente il divario di prestazioni vicino agli ottimi.

5. Significato

Questo lavoro rappresenta un avanzamento significativo nell'ottimizzazione senza derivate per problemi spettrali.

• Impatto Pratico: Consente il calcolo delle norme degli operatori e dei quozienti di Rayleigh in scenari in cui gli operatori adiunti non sono disponibili, sono inconsistenti o troppo costosi da calcolare (ad esempio, codici di simulazione legacy, solutori complessi di PDE).
• Impatto Teorico: Colma il divario tra la ricerca casuale di ordine zero e l'ottimizzazione Riemanniana fornendo stimatori non distorti sia per i gradienti che per gli Hessiani su varietà senza proiezioni esplicite sulla varietà.
• Efficienza Algoritmica: Il passo in forma chiusa e la capacità di operare senza proiezioni sullo spazio tangente rendono l'algoritmo computazionalmente efficiente e scalabile a problemi ad alta dimensionalità.

In sintesi, Bresch generalizza i metodi di ordine zero per gestire i quozienti di funzioni quadratiche sostituendo il campionamento vincolato nello spazio tangente con il campionamento non vincolato sulla sfera, derivando passi esatti e stabilendo un rigoroso framework del secondo ordine che supera le tecniche all'avanguardia esistenti in contesti di scatola nera ad alta dimensionalità.