A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints

Sintesi Tecnica: Un Metodo di Discesa per Coordinate a Blocchi per l'Ottimizzazione Composita Non Liscia sotto Vincoli di Ortogonalità

Enunciato del Problema
Il lavoro affronta la sfida dell'ottimizzazione composita non liscia sotto vincoli di ortogonalità, formulata come:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
dove $n \ge r$, $f(X)$ è una funzione liscia (potenzialmente non convessa) e $h(X)$ è una funzione propria, semicontinua inferiormente, potenzialmente non liscia e separabile per coordinate. L'insieme ammissibile è la varietà di Stiefel $\mathcal{M} = \text{St}(n, r)$. Questo quadro concettuale abbraccia applicazioni critiche nell'apprendimento statistico e nella scienza dei dati, inclusa l'Analisi delle Componenti Principali (PCA) sparsa con regolarizzazione $\ell_0$ o $\ell_1$, la PCA non negativa, l'addestramento di reti neurali profonde con vincoli di ortogonalità e l'apprendimento di dizionari.

I metodi esistenti presentano limitazioni significative: molti si basano su informazioni di gradiente completo (alto costo computazionale), non riescono a gestire efficacemente obiettivi non lisci per coordinate, mancano di proprietà di discesa vere (spesso raggiungendo solo l'ammissibilità asintoticamente) o forniscono garanzie di ottimalità deboli (convergenza solo verso punti critici standard).

Metodologia: L'Algoritmo OBCD
Gli autori propongono OBCD (Orthogonal Block Coordinate Descent), un metodo ammissibile che aggiorna simultaneamente $k$ righe della matrice soluzione $X$, dove $k \ge 2$.

1. Schema di Aggiornamento che Preserva i Vincoli:
   Invece di proiettare sulla varietà o utilizzare retrazioni, OBCD impiega una regola di aggiornamento specifica che mantiene l'ortogonalità per costruzione. Per un insieme di lavoro di indici di riga $B$ (di dimensione $k$), l'aggiornamento è definito come:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   dove $U_B$ seleziona le righe in $B$, e $V \in \text{St}(k, k)$ è una matrice ortogonale che risolve un sottoproblema. Il Lemma 2.1 dimostra che se $X^t$ è ammissibile, $X^{t+1}$ rimane ammissibile per ogni $V \in \text{St}(k, k)$.

2. Formulazione del Sottoproblema:
   In ogni iterazione, OBCD risolve un sottoproblema su piccola scala sulla varietà di Stiefel di dimensione $k \times k$. Utilizzando un approccio di Massimizzazione-Minimizzazione (MM), la parte liscia $f(X)$ è approssimata da un surrogato quadratico, mentre la parte non liscia $h(X)$ è mantenuta esatta. Il sottoproblema risultante è:
   $$\bar{V}_t \in \arg\min_{V \in \text{St}(k, k)} \left( \frac{1}{2} \|V - I_k\|_{\tilde{Q}}^2 + \langle V, P \rangle + h(V Z) \right)$$
   dove $Z = U_B^T X^t$, $P$ coinvolge il gradiente di $f$, e $\tilde{Q}$ è una matrice definita positiva derivata dall'Hessiano di $f$ o da un proxy scalare.

3. Risoluzione dei Sottoproblemi:

   • Caso generale $k$: Il lavoro assume che il sottoproblema possa essere risolto esattamente o efficientemente (ad esempio, tramite strutture amichevoli dei proximali).
   • Caso $k=2$: Gli autori introducono un nuovo Metodo di Ricerca dei Punti di Rottura (BSM). Parametrizzando le matrici ortogonali $2 \times 2$ mediante rotazioni di Givens ($V^{rot}_\theta$) e riflessioni di Jacobi ($V^{ref}_\theta$), il sottoproblema è ridotto a un'ottimizzazione unidimensionale su $\theta$. Il BSM identifica tutti i punti di rottura (punti critici) della funzione obiettivo (inclusi quelli derivanti dal termine non liscio $h$) per trovare il minimizzatore globale.

4. Selezione dell'Insieme di Lavoro:
   L'algoritmo supporta sia strategie casuali che cicliche per la selezione dell'insieme di lavoro $B$.

Contributi Teorici
Il lavoro fornisce un'analisi teorica rigorosa riguardo all'ottimalità e alla convergenza:

• Completezza dello Schema di Aggiornamento: Gli autori dimostrano che lo schema di aggiornamento riga per riga proposto è completo. Nello specifico, qualsiasi punto sulla varietà di Stiefel può essere raggiunto da qualsiasi altro punto ammissibile tramite una sequenza di questi aggiornamenti a $k$ righe (Teorema 3.1, Corollario 3.2).
• Condizioni di Ottimalità Più Forti: Il lavoro definisce i Punti Stazionari Globali a Blocchi-$k$ (BSk-points). Una soluzione è un punto BSk se non è possibile ottenere miglioramenti ottimizzando qualsiasi blocco di $k$ righe. Gli autori stabiliscono una gerarchia di ottimalità:
  $$\{\text{Ottimi Globali}\} \subseteq \{\text{Punti BSk}\} \subseteq \{\text{Punti BSk+1}\} \subseteq \{\text{Punti Critici}\}$$
  Ciò implica che i punti BSk (per $k \ge 2$) soddisfano una condizione di ottimalità strettamente più forte rispetto ai punti critici standard, permettendo teoricamente all'algoritmo di sfuggire a minimi locali poveri che intrappolano i metodi standard.
• Complessità Iterativa:
  • OBCD trova un punto stazionario a blocchi-$k$ $\epsilon$-approssimato con una complessità iterativa di $O(1/\epsilon)$.
  • Sotto l'assunzione della disuguaglianza di Kurdyka–Łojasiewicz (KL), il lavoro stabilisce tassi di convergenza non ergodici (dell'ultima iterazione). A seconda dell'esponente KL $\sigma$, la convergenza è finita ($\sigma=0$), lineare ($\sigma \in (0, 1/2]$) o sublineare ($\sigma \in (1/2, 1)$).

Risultati Sperimentali
Gli autori valutano OBCD su PCA Sparsa regolarizzata con L0, PCA Sparsa regolarizzata con L1 e PCA Non Negativa utilizzando dataset reali (ad esempio, MNIST, Gisette, 20News) e dati sintetici.

• Prestazioni: OBCD supera costantemente le linee di stato dell'arte, inclusi Linearized ADMM (LADMM), Riemannian ADMM (RADMM), Penalty-based Splitting Method (PSM) e Manifold Proximal Gradient (ManPG).
• Valori della Funzione Obiettivo: In termini di valore finale della funzione obiettivo, OBCD raggiunge valori inferiori rispetto ai metodi concorrenti, spesso sfuggendo a minimi locali in cui gli altri rimangono intrappolati.
• Efficienza: Sebbene i metodi a gradiente completo possano richiedere meno iterazioni, il minor costo per iterazione di OBCD (aggiornamenti di gradiente parziale) si traduce in prestazioni superiori quando misurate in tempo CPU.
• Ammissibilità: A differenza di alcuni metodi non ammissibili (ad esempio, certi metodi di splitting) che soddisfano i vincoli solo nel limite, OBCD mantiene l'ortogonalità rigorosa (e la non negatività nella variante Non Negativa PCA) durante tutto il processo di ottimizzazione.

Significato e Affermazioni
Il lavoro afferma che OBCD offre un avanzamento significativo combinando efficienza computazionale con forti garanzie teoriche. Il suo significato primario risiede in:

1. Gestione della Non Liscietà: Affronta efficacemente obiettivi non lisci per coordinate sotto vincoli di ortogonalità, un contesto in cui molti metodi esistenti di ottimizzazione su varietà faticano.
2. Ottimalità Più Forte: Utilizzando aggiornamenti a blocchi ($k \ge 2$), il metodo mira ai punti BSk, che sono teoricamente superiori ai punti critici standard, fornendo un meccanismo per evitare minimi locali subottimali.
3. Ammissibilità: È un metodo strettamente ammissibile, garantendo che i vincoli siano soddisfatti ad ogni iterazione, a differenza degli approcci di splitting basati su penalità o non ammissibili.
4. Efficienza Pratica: L'algoritmo è progettato per problemi su larga scala dove i calcoli del gradiente completo sono proibitivi, offrendo un'alternativa scalabile con proprietà di convergenza provate.