High-probability zeroth-order online convex optimisation beyond Euclidean geometry

Riepilogo Tecnico: Ottimizzazione convessa online di ordine zero ad alta probabilità oltre la geometria euclidea

Impostazione del Problema
Questo lavoro affronta il problema dell'ottimizzazione convessa online (OCO) in un contesto di ordine zero, dove l'apprendente ha accesso solo alle valutazioni della funzione, non ai gradienti. L'impostazione specifica coinvolge una sequenza di perdite casuali Lipschitziane $f_t$ estratte da una distribuzione $\mu$. Sebbene le realizzazioni $f_t$ non debbano essere convesse, si assume che la loro funzione media $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ sia convessa. L'apprendente opera su un insieme compatto e convesso $\Theta \subset \mathbb{R}^d$ e mira a minimizzare il pseudo-rimorso:
$$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$$
Il modello di feedback permette all'apprendente di interrogare la funzione in due punti per turno, $x_t \pm h_t \zeta_t$, dove la direzione $\zeta_t$ è campionata dal bordo di una palla $\ell_r$ secondo la misura del cono. Si assume che le perdite siano $L$-Lipschitziane rispetto a una norma $\ell_q$, e l'algoritmo impiega un regolarizzatore fortemente convesso $\ell_p$ all'interno di un quadro Follow-The-Regularised-Leader (FTRL).

Metodologia
Il documento propone un algoritmo adattivo e "anytime" (SOLO FTRL) che utilizza stimatori del gradiente a due punti randomizzati basati su differenze finite. Le innovazioni metodologiche fondamentali risiedono nella generalizzazione geometrica e nell'analisi probabilistica:

1. Stimolazione del Gradiente Generalizzata: Lo stimatore del gradiente è costruito utilizzando direzioni campionate dalla misura del cono sul bordo di una palla $\ell_r$ ($\zeta \sim \partial B_d^r$). Lo stimatore è definito come:
   $$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$$
   dove $n_r(\zeta)$ è il normale unitario alla sfera $\ell_r$ in $\zeta$. Questo generalizza gli stimatori sferici classici ($r=2$) e permette geometrie di campionamento $\ell_1$ o $\ell_\infty$.

2. Analisi dei Momenti e Concentrazione: A differenza di lavori precedenti che si basano su limiti in valore atteso (tipicamente utilizzando momenti secondi), questa analisi stabilisce limiti su tutti i momenti per lo stimatore del gradiente nella norma duale $\ell_{p^*}$. Dimostrando che la sequenza degli errori al quadrato nella norma duale soddisfa una condizione di momento di Bernstein sequenziale (SBM), gli autori derivano disuguaglianze di concentrazione ad alta probabilità uniformi nel tempo. Ciò comporta il controllo del comportamento della coda dello stimatore del gradiente utilizzando risultati di concentrazione della misura per funzioni Lipschitziane su sfere $\ell_r$.

3. Algoritmo Adattivo: L'algoritmo è interamente guidato dai dati e non richiede la conoscenza dell'orizzonte temporale $n$ o delle costanti nel caso peggiore derivate dall'analisi dei momenti. Richiede solo la specificazione dei parametri geometrici ($p, r$), del regolarizzatore e di un limite superiore sulla dimensione del dominio.

Contributi Chiave

1. Limiti Unificati ad Alta Probabilità: Il documento fornisce i primi limiti unificati ad alta probabilità per il rimorso nell'OCO di ordine zero per tutte le combinazioni geometriche $p, q, r \in [1, \infty]$. Questi limiti valgono per perdite Lipschitziane casuali con media convessa, rafforzando le precedenti garanzie in valore atteso in affermazioni ad alta probabilità uniformi nel tempo.
2. Limiti dei Momenti per lo Stimatore del Gradiente: Gli autori dimostrano nuovi limiti dei momenti per stimatori del gradiente a due punti randomizzati $\ell_r$ nella norma duale $\ell_{p^*}$. Questi risultati tracciano la dipendenza dalla geometria di campionamento ($r$) e dalla norma Lipschitziana ($q$), stabilendo che le norme duali al quadrato cumulative si comportano come un processo subgamma.
3. Limiti Inferiori Indipendenti dall'Algoritmo: Il documento stabilisce limiti inferiori a probabilità costante per la stessa classe di problemi. Questi limiti migliorano i precedenti risultati in valore atteso (specificamente per $p=q=1$ rimuovendo un fattore $\sqrt{\log d}$) e coprono l'intero intervallo di $p, q \in [1, \infty]$ con una singola costruzione.
4. Identificazione di un Divario per $q > 2$: L'analisi rivela una discrepanza tra i limiti superiori e inferiori quando $q > 2$. Gli autori sostengono che ciò non sia un artefatto della dimostrazione, ma indichi una subottimalità intrinseca degli stimatori standard del gradiente a due punti randomizzati in questo regime, poiché non riescono a sfruttare la sparsità inherente alle funzioni Lipschitziane ad alto $q$.

Risultati Principali
Il risultato teorico primario (Teorema 2.3) afferma che con probabilità almeno $1-\delta$, il rimorso soddisfa:
$$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$$
dove $\nu_r$ è una varianza proxy che dipende da $L, d, p, q, r$, e $\gamma_r = (1/p - 1/r)_+$. Il termine $\sqrt{\log \log n}$ deriva dalla natura "anytime" del limite.

Il limite inferiore (Teorema 2.4) mostra che per qualsiasi algoritmo a due punti, esiste un'istanza del problema in cui il rimorso è almeno dell'ordine $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ con probabilità costante.

Significato e Affermazioni
Il documento afferma di fornire il primo trattamento unificato dell'ottimizzazione convessa online di ordine zero oltre l'impostazione euclidea ($p=q=r=2$). Passando dall'analisi in valore atteso a quella ad alta probabilità, i risultati offrono garanzie più forti e uniformi nel tempo, adatte a contesti adattivi e "anytime".

Il lavoro evidenzia una limitazione specifica nella metodologia attuale: per $q > 2$, gli stimatori standard del gradiente randomizzati sembrano subottimali rispetto al limite inferiore teorico. Gli autori suggeriscono che il divario sorge perché questi stimatori mancano di un meccanismo per sfruttare la sparsità delle istanze "difficili" nel regime $q > 2$, una proprietà che la costruzione del limite inferiore utilizza esplicitamente. Questa scoperta suggerisce che i futuri miglioramenti in questo regime potrebbero richiedere strutture di stimatori fondamentalmente diverse, piuttosto che una semplice analisi raffinata dei metodi esistenti basati su differenze finite.