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

Technische Samenvatting: Een Bloccoördinaat-afdaalmethodiek voor niet-gladde samengestelde optimalisatie onder orthogonaliteitsbeperkingen

Probleemstelling
Het artikel behandelt de uitdaging van niet-gladde samengestelde optimalisatie onder orthogonaliteitsbeperkingen, geformuleerd als:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{zodat } X^T X = I_r$$
waarbij $n \ge r$, $f(X)$ een gladde (potentieel niet-convexe) functie is, en $h(X)$ een proper, onderaan semicontinue, potentieel niet-gladde functie is die coördinaatsgewijs scheidbaar is. De toelaatbare verzameling is de Stiefel-maand $\mathcal{M} = \text{St}(n, r)$. Dit kader omvat kritieke toepassingen in statistisch leren en datawetenschap, waaronder schaarse Hoofdkomponentenanalyse (PCA) met $\ell_0$- of $\ell_1$-regularisatie, niet-negatieve PCA, training van diepe neurale netwerken met orthogonaliteitsbeperkingen, en dictionary learning.

Bestaande methoden ondervinden aanzienlijke beperkingen: veel methoden vertrouwen op volledige gradiëntinformatie (hoge rekenkosten), slagen er niet in om coördinaatsgewijs niet-gladde doelstellingen effectief te behandelen, missen echte afdaaleigenschappen (vaak alleen asymptotisch haalbaarheid bereikend), of bieden zwakke optimaliteitsgaranties (die alleen convergeren naar standaard kritieke punten).

Methodologie: Het OBCD-algoritme
De auteurs stellen OBCD (Orthogonal Block Coordinate Descent) voor, een haalbare methode die $k$ rijen van de oplossingsmatrix $X$ gelijktijdig bijwerkt, waarbij $k \ge 2$.

1. Beperkingbehoudend Bijwerkingschema:
   In plaats van projectie op de variëteit of het gebruik van retractions, hanteert OBCD een specifieke bijwerkingsregel die orthogonaliteit bij constructie behoudt. Voor een werkset van rijindices $B$ (grootte $k$) wordt de bijwerking gedefinieerd als:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   waarbij $U_B$ de rijen in $B$ selecteert, en $V \in \text{St}(k, k)$ een orthogonale matrix is die een deelvraagstuk oplost. Lemma 2.1 bewijst dat als $X^t$ haalbaar is, $X^{t+1}$ voor elke $V \in \text{St}(k, k)$ haalbaar blijft.

2. Formulering van het Deelvraagstuk:
   In elke iteratie lost OBCD een kleinschalig deelvraagstuk op over de Stiefel-maand van dimensie $k \times k$. Met behulp van een Majorisatie-Minimalisatie (MM) benadering wordt het gladde deel $f(X)$ benaderd door een kwadratische surrogaat, terwijl het niet-gladde deel $h(X)$ exact wordt gehouden. Het resulterende deelvraagstuk is:
   $$\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)$$
   waarbij $Z = U_B^T X^t$, $P$ de gradiënt van $f$ bevat, en $\tilde{Q}$ een positief-definiete matrix is afgeleid van de Hessian van $f$ of een scalair proxy.

3. Oplossen van Deelvraagstukken:

   • Algemene $k$: Het artikel neemt aan dat het deelvraagstuk exact of efficiënt kan worden opgelost (bijvoorbeeld via proximaal-vriendelijke structuren).
   • Geval $k=2$: De auteurs introduceren een nieuwe Breakpoint Search Method (BSM). Door $2 \times 2$ orthogonale matrices te parametriseren met Givens-rotaties ($V^{rot}_\theta$) en Jacobi-reflecties ($V^{ref}_\theta$), wordt het deelvraagstuk gereduceerd tot een een-dimensionale optimalisatie over $\theta$. De BSM identificeert alle breekpunten (kritieke punten) van de doelwitfunctie (inclusief die voortkomend uit de niet-gladde term $h$) om de globale minimizer te vinden.

4. Selectie van Werkset:
   Het algoritme ondersteunt zowel willekeurige als cyclische strategieën voor het selecteren van de werkset $B$.

Theoretische Bijdragen
Het artikel biedt een rigoureuze theoretische analyse met betrekking tot optimaliteit en convergentie:

• Volledigheid van Bijwerkingschema: De auteurs bewijzen dat het voorgestelde rijgewijze bijwerkingschema volledig is. Specifiek kan elk punt op de Stiefel-maand worden bereikt vanuit elk ander haalbaar punt via een reeks van deze $k$-rij-bijwerkingen (Stelling 3.1, Corollarium 3.2).
• Sterkere Optimaliteitsvoorwaarden: Het artikel definieert Globale Blokk-$k$ Stationaire Punten (BSk-punten). Een oplossing is een BSk-punt als geen verbetering mogelijk is door optimalisatie van een willekeurig blok van $k$ rijen. De auteurs vestigen een hiërarchie van optimaliteit:
  $$\{\text{Globale Optima}\} \subseteq \{\text{BSk-punten}\} \subseteq \{\text{BS(k+1)-punten}\} \subseteq \{\text{Kritieke Punten}\}$$
  Dit impliceert dat BSk-punten (voor $k \ge 2$) een strikt sterkere optimaliteitsvoorwaarde voldoen dan standaard kritieke punten, wat theoretisch toelaat dat het algoritme slechte lokale minima ontvlucht waarin standaard methoden vastlopen.
• Iteratiecomplexiteit:
  • OBCD vindt een $\epsilon$-blok-$k$ stationair punt met een iteratiecomplexiteit van $O(1/\epsilon)$.
  • Onder de aanname van de Kurdyka–Łojasiewicz (KL) ongelijkheid, vestigt het artikel niet-ergodische (laatste-iteratie) convergentiesnelheden. Afhankelijk van de KL-exponent $\sigma$, is de convergentie eindig ($\sigma=0$), lineair ($\sigma \in (0, 1/2]$), of sublineair ($\sigma \in (1/2, 1)$).

Experimentele Resultaten
De auteurs evalueren OBCD op L0-geregulariseerde Schaarse PCA, L1-geregulariseerde Schaarse PCA, en Niet-negatieve PCA met behulp van real-world datasets (bijvoorbeeld MNIST, Gisette, 20News) en synthetische data.

• Prestaties: OBCD presteert consequent beter dan state-of-the-art baselines, waaronder Linearized ADMM (LADMM), Riemannian ADMM (RADMM), Penalty-based Splitting Method (PSM), en Manifold Proximal Gradient (ManPG).
• Doelwaarden: Wat betreft de uiteindelijke doelwaarde bereikt OBCD lagere waarden dan concurrerende methoden, vaak door lokale minima te ontvluchten waarin andere methoden vastlopen.
• Efficiëntie: Hoewel volledige-gradiëntmethodes mogelijk minder iteraties vereisen, resulteert de lagere kosten per iteratie van OBCD (gedeeltelijke gradiëntupdates) in superieure prestaties wanneer gemeten in CPU-tijd.
• Haalbaarheid: In tegenstelling tot sommige niet-haalbare methoden (bijvoorbeeld bepaalde splitsingsmethodes) die alleen in de limiet aan beperkingen voldoen, behoudt OBCD strikte orthogonaliteit (en niet-negativiteit in de variant voor Niet-negatieve PCA) gedurende het hele optimalisatieproces.

Betekenis en Claims
Het artikel claimt dat OBCD een aanzienlijke vooruitgang biedt door rekenkundige efficiëntie te combineren met sterke theoretische garanties. De primaire betekenis ligt in:

1. Omgaan met Niet-gladheid: Het adresseert effectief coördinaatsgewijs niet-gladde doelstellingen onder orthogonaliteitsbeperkingen, een setting waarin veel bestaande variëteitsoptimalisatiemethoden moeite hebben.
2. Sterkere Optimaliteit: Door het gebruik van blokbijwerkingen ($k \ge 2$) richt de methode zich op BSk-punten, die theoretisch superieur zijn aan standaard kritieke punten, en biedt een mechanisme om suboptimale lokale minima te vermijden.
3. Haalbaarheid: Het is een strikt haalbare methode, die garandeert dat beperkingen bij elke iteratie worden voldaan, in tegenstelling tot op straffen gebaseerde of niet-haalbare splitsingsbenaderingen.
4. Praktische Efficiëntie: Het algoritme is ontworpen voor grootschalige problemen waar volledige gradiëntberekeningen onbetaalbaar zijn, en biedt een schaalbaar alternatief met bewezen convergentie-eigenschappen.