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

Technische Zusammenfassung: Eine Block-Koordinatenabstiegs-Methode für nichtglatte zusammengesetzte Optimierung unter Orthogonalitätsbedingungen

Problemstellung
Der Beitrag behandelt die Herausforderung der nichtglatten zusammengesetzten Optimierung unter Orthogonalitätsbedingungen, formuliert als:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
wobei $n \ge r$, $f(X)$ eine glatte (potenziell nichtkonvexe) Funktion ist und $h(X)$ eine eigentliche, halbstetige von unten, potenziell nichtglatte Funktion ist, die koordinatenweise separierbar ist. Die zulässige Menge ist die Stiefel-Mannigfaltigkeit $\mathcal{M} = \text{St}(n, r)$. Dieser Rahmen umfasst kritische Anwendungen im maschinellen Lernen und der Datenwissenschaft, darunter sparse Hauptkomponentenanalyse (PCA) mit $\ell_0$- oder $\ell_1$-Regularisierung, nichtnegative PCA, das Training tiefer neuronaler Netze mit orthogonalen Bedingungen sowie Dictionary Learning.

Bestehende Methoden weisen erhebliche Einschränkungen auf: Viele verlassen sich auf vollständige Gradienteninformationen (hohe Rechenkosten), versagen beim effektiven Umgang mit koordinatenweisen nichtglatten Zielfunktionen, besitzen keine echten Abstiegs-Eigenschaften (erzielen oft nur asymptotische Zulässigkeit) oder bieten schwache Optimalitätsgarantien (konvergieren nur zu Standard-Kritischen Punkten).

Methodik: Der OBCD-Algorithmus
Die Autoren schlagen OBCD (Orthogonal Block Coordinate Descent) vor, eine zulässige Methode, die $k$ Zeilen der Lösungsmatrix $X$ gleichzeitig aktualisiert, wobei $k \ge 2$ gilt.

1. Zulässigkeits-erhaltendes Aktualisierungsschema:
   Anstatt auf die Mannigfaltigkeit zu projizieren oder Retraktionen zu verwenden, verwendet OBCD eine spezifische Aktualisierungsregel, die Orthogonalität durch Konstruktion bewahrt. Für eine Arbeitsmenge von Zeilenindizes $B$ (Größe $k$) ist die Aktualisierung definiert als:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   wobei $U_B$ die Zeilen in $B$ auswählt und $V \in \text{St}(k, k)$ eine orthogonale Matrix ist, die ein Teilproblem löst. Lemma 2.1 beweist, dass, wenn $X^t$ zulässig ist, $X^{t+1}$ für jedes $V \in \text{St}(k, k)$ zulässig bleibt.

2. Formulierung des Teilproblems:
   In jeder Iteration löst OBCD ein kleines Teilproblem über die Stiefel-Mannigfaltigkeit der Dimension $k \times k$. Unter Verwendung eines Majorization-Minimization (MM)-Ansatzes wird der glatte Teil $f(X)$ durch ein quadratisches Surrogat approximiert, während der nichtglatte Teil $h(X)$ exakt beibehalten wird. Das resultierende Teilproblem lautet:
   $$\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)$$
   wobei $Z = U_B^T X^t$, $P$ den Gradienten von $f$ beinhaltet und $\tilde{Q}$ eine positiv definite Matrix ist, die aus der Hesse-Matrix von $f$ oder einem skalaren Proxy abgeleitet wird.

3. Lösen von Teilproblemen:

   • Allgemeines $k$: Der Beitrag geht davon aus, dass das Teilproblem exakt oder effizient gelöst werden kann (z. B. durch proximal-freundliche Strukturen).
   • Fall $k=2$: Die Autoren stellen eine neuartige Breakpoint-Suchmethode (BSM) vor. Durch Parametrisierung von $2 \times 2$-orthogonalen Matrizen mittels Givens-Rotationen ($V^{rot}_\theta$) und Jacobi-Reflexionen ($V^{ref}_\theta$) wird das Teilproblem auf eine eindimensionale Optimierung über $\theta$ reduziert. Die BSM identifiziert alle Breakpoints (kritische Punkte) der Zielfunktion (einschließlich derer, die aus dem nichtglatten Term $h$ resultieren), um den globalen Minimierer zu finden.

4. Auswahl der Arbeitsmenge:
   Der Algorithmus unterstützt sowohl zufällige als auch zyklische Strategien zur Auswahl der Arbeitsmenge $B$.

Theoretische Beiträge
Der Beitrag liefert eine rigorose theoretische Analyse bezüglich Optimalität und Konvergenz:

• Vollständigkeit des Aktualisierungsschemas: Die Autoren beweisen, dass das vorgeschlagene zeilenweise Aktualisierungsschema vollständig ist. Spezifisch kann jeder Punkt auf der Stiefel-Mannigfaltigkeit von jedem anderen zulässigen Punkt aus durch eine Folge dieser $k$-Zeilen-Aktualisierungen erreicht werden (Satz 3.1, Korollar 3.2).
• Stärkere Optimalitätsbedingungen: Der Beitrag definiert Globale Block-$k$-Stationäre Punkte (BSk-Punkte). Eine Lösung ist ein BSk-Punkt, wenn keine Verbesserung durch Optimierung eines beliebigen Blocks von $k$ Zeilen möglich ist. Die Autoren etablieren eine Hierarchie der Optimalität:
  $$\{\text{Globale Optima}\} \subseteq \{\text{BSk-Punkte}\} \subseteq \{\text{BS(k+1)-Punkte}\} \subseteq \{\text{Kritische Punkte}\}$$
  Dies impliziert, dass BSk-Punkte (für $k \ge 2$) eine strikt stärkere Optimalitätsbedingung erfüllen als Standard-Kritische Punkte, was theoretisch dem Algorithmus ermöglicht, schlechte lokale Minima zu verlassen, in denen Standardmethoden stecken bleiben.
• Iterationskomplexität:
  • OBCD findet einen $\epsilon$-Block-$k$-stationären Punkt mit einer Iterationskomplexität von $O(1/\epsilon)$.
  • Unter der Annahme der Kurdyka–Łojasiewicz (KL)-Ungleichung etabliert der Beitrag nicht-ergodische Konvergenzraten (letzte Iteration). Je nach KL-Exponent $\sigma$ ist die Konvergenz endlich ($\sigma=0$), linear ($\sigma \in (0, 1/2]$) oder sublinear ($\sigma \in (1/2, 1)$).

Experimentelle Ergebnisse
Die Autoren bewerten OBCD an L0-reguliertem Sparse PCA, L1-reguliertem Sparse PCA und nichtnegativer PCA unter Verwendung realer Datensätze (z. B. MNIST, Gisette, 20News) und synthetischer Daten.

• Leistung: OBCD übertrifft konsistent State-of-the-Art-Baselines, einschließlich Linearized ADMM (LADMM), Riemannian ADMM (RADMM), Penalty-based Splitting Method (PSM) und Manifold Proximal Gradient (ManPG).
• Zielfunktionswerte: Hinsichtlich des finalen Zielfunktionswerts erzielt OBCD niedrigere Werte als konkurrierende Methoden und entkommt oft lokalen Minima, in denen andere stecken bleiben.
• Effizienz: Während vollständige Gradientenmethoden möglicherweise weniger Iterationen benötigen, führt die geringeren Kosten pro Iteration von OBCD (partielle Gradientenaktualisierungen) zu überlegener Leistung, wenn diese nach CPU-Zeit gemessen wird.
• Zulässigkeit: Im Gegensatz zu einigen unzulässigen Methoden (z. B. bestimmten Splitting-Methoden), die nur im Grenzwert die Bedingungen erfüllen, bewahrt OBCD strenge Orthogonalität (und Nicht-Negativität in der Variante für nichtnegative PCA) während des gesamten Optimierungsprozesses.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass OBCD einen signifikanten Fortschritt darstellt, indem es Recheneffizienz mit starken theoretischen Garantien kombiniert. Seine primäre Bedeutung liegt in:

1. Umgang mit Nichtglätte: Es adressiert effektiv koordinatenweise nichtglatte Zielfunktionen unter Orthogonalitätsbedingungen, ein Setting, bei dem viele bestehende Methoden zur Optimierung auf Mannigfaltigkeiten Schwierigkeiten haben.
2. Stärkere Optimalität: Durch die Nutzung von Block-Aktualisierungen ($k \ge 2$) zielt die Methode auf BSk-Punkte ab, die theoretisch überlegen gegenüber Standard-Kritischen Punkten sind und einen Mechanismus bieten, um suboptimale lokale Minima zu vermeiden.
3. Zulässigkeit: Es ist eine strikt zulässige Methode, die sicherstellt, dass die Bedingungen in jeder Iteration erfüllt sind, im Gegensatz zu strafenbasierten oder unzulässigen Splitting-Ansätzen.
4. Praktische Effizienz: Der Algorithmus ist für großskalige Probleme konzipiert, bei denen vollständige Gradientenberechnungen prohibitiv sind, und bietet eine skalierbare Alternative mit bewiesenen Konvergenzeigenschaften.