On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression

Sintesi Tecnica: Sulla Convergenza Lineare dei Metodi di Gradiente Prossimale di Bregman con Applicazioni alla Regressione Kullback–Leibler

Enunciato del Problema
Il documento affronta la minimizzazione di funzionali compositi convessi della forma $J(x) = F(x) + R(x)$, dove $F$ è una funzione convessa differenziabile e $R$ è un regolarizzatore convesso non differenziabile. Sebbene i Metodi del Gradiente Prossimale (PGM) siano standard per tali problemi, i loro tassi di convergenza sono tipicamente sublineari ($O(1/k)$) a meno che $F$ non sia fortemente convessa. Tuttavia, molte applicazioni pratiche, in particolare nei problemi inversi come la regressione di Poisson e la regressione Kullback–Leibler (KL), coinvolgono termini $F$ che non sono fortemente convessi (ad esempio, quando la matrice di misura $A$ è a rango ridotto).

Sebbene i Metodi del Gradiente Prossimale di Bregman (BPGM) siano stati introdotti per adattarsi alla geometria di $J$ tramite una mappa di mirror $\phi$, le garanzie di convergenza lineare esistenti per BPGM richiedono generalmente che $F$ sia globalmente fortemente convessa rispetto a $\phi$. Questa condizione è spesso troppo restrittiva per i problemi pratici di regressione KL, lasciando un vuoto nella comprensione teorica di quando e perché avvenga la convergenza lineare.

Metodologia e Quadro Teorico
Gli autori propongono un nuovo quadro teorico per stabilire la convergenza lineare per BPGM sotto condizioni più deboli rispetto alla forte convessità relativa globale.

1. Convessità Forte Relativa Restretta (RRSC): Il documento introduce una nuova proprietà denominata Convessità Forte Relativa Restretta. Essa estende il concetto di Convessità Forte Restretta (RSC) dagli spazi euclidei al contesto di Bregman. Nello specifico, $F$ è detta RRSC rispetto a $\phi$ se esiste $\mu > 0$ tale che per ogni $x$ nel dominio:
   $$\langle \nabla F(x) - \nabla F(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle \geq \mu \langle \nabla \phi(x) - \nabla \phi(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle$$
   dove $\bar{x}_{\ell_2}$ è la proiezione euclidea di $x$ sull'insieme delle soluzioni $S$. Fondamentalmente, questa condizione si basa sulla proiezione euclidea piuttosto che sulla proiezione di Bregman, il che è tecnicamente necessario per gestire la geometria della divergenza KL.

2. Coefficiente di Simmetria Restretto: Per gestire l'asimmetria inerente alle divergenze di Bregman (che non sono simmetriche a meno che $\phi$ non sia quadratica), gli autori definiscono un coefficiente di simmetria ristretto $\alpha_S(\phi)$. Questo coefficiente misura la simmetria della divergenza $D_\phi$ specificamente ristretta all'insieme delle soluzioni $S$. Gli autori richiedono che $\alpha_S(\phi) > 0$ per garantire la convergenza.

3. Analisi della Convergenza: Sotto le assunzioni di RRSC, di regolarità relativa (condizione di tipo Lipschitz-like) e di un coefficiente di simmetria ristretto positivo, gli autori dimostrano che la divergenza di Bregman tra le iterazioni e l'insieme delle soluzioni, nonché i valori della funzione obiettivo, convergono linearmente. Estendono inoltre questi risultati per includere una regola di selezione automatica della dimensione del passo tramite backtracking.

Applicazione alla Regressione Kullback–Leibler
Il quadro teorico è applicato a problemi di regressione KL (regolarizzati), dove $F(x) = KL(y, Ax+b)$. Gli autori analizzano il comportamento della convergenza per tre scelte specifiche della funzione generatrice della distanza $\phi$:

• Norma $\ell_2$ al quadrato: Il caso euclideo standard.
• Entropia di Burg: Una scelta popolare per i problemi KL ($\phi_B(x) = -\sum \log x_n$).
• Entropia di Burg Smussata: Una proposta innovativa ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Risultati Chiave e Conclusioni

• Limitazioni dell'Entropia di Burg: L'analisi rivela che l'utilizzo della standard entropia di Burg ($\phi_B$) non garantisce la convergenza lineare per tutti gli scenari di regressione KL. Nello specifico, se l'insieme delle soluzioni giace sul confine dell'ortante non negativo ($\partial C$) o se le iterazioni si avvicinano al nucleo di $A in un modo specifico, la condizione RRSC fallisce e si osserva solo una convergenza sublineare.
• Vantaggio dell'Entropia di Burg Smussata: Gli autori dimostrano che l'impiego della versione smussata ($\phi_{sB}$) induce la geometria necessaria per soddisfare la condizione RRSC e garantire un coefficiente di simmetria positivo in una gamma più ampia di scenari, inclusi quelli in cui le soluzioni giacciono sul confine.
• Validazione Numerica: Esperimenti su problemi inversi di Poisson sintetici confermano le previsioni teoriche.
  • Per $\phi_{sB}$, si osserva una convergenza lineare costante, indipendentemente dal fatto che la soluzione sia unica o non unica, o se si trovi nell'interno o sul confine dell'insieme di vincolo.
  • Per $\phi_B$, la convergenza lineare si osserva solo quando la soluzione giace strettamente nell'interno dell'insieme di vincolo; altrimenti, la convergenza degrada a tassi sublineari.
  • Le prestazioni di $\phi_{sB}$ sono sensibili al parametro di smoothing $\xi$, con un trade-off ottimale tra la costante di forte convessità e la costante di regolarità relativa.

Significatività e Rivendicazioni
Il documento sostiene di fornire la prima generalizzazione della Convessità Forte Restretta al contesto di Bregman, stabilendo così tassi di convergenza lineare per BPGM senza richiedere la forte convessità relativa globale. Il contributo primario è l'identificazione delle specifiche condizioni geometriche (RRSC e simmetria ristretta) richieste per la convergenza lineare nella regressione KL.

Gli autori sottolineano come il loro lavoro spieghi perché la popolare entropia di Burg possa fallire nel garantire la convergenza lineare in determinati contesti pratici (ad esempio, soluzioni di confine) e propone l'entropia di Burg smussata come un'alternativa robusta che garantisce la convergenza lineare. I risultati sono validati sia teoricamente che numericamente, mostrando un forte allineamento tra le condizioni derivate e il comportamento empirico osservato. Il lavoro non pretende di risolvere problemi non convessi o di estendere la regressione KL non convessa, bensì perfeziona la comprensione dell'ottimizzazione composita convessa nel contesto della divergenza KL.