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

Resumen Técnico: Un Método de Descenso de Coordenadas por Bloques para Optimización Compuesta No Suave bajo Restricciones de Ortogonalidad

Enunciado del Problema
El artículo aborda el desafío de la optimización compuesta no suave bajo restricciones de ortogonalidad, formulada como:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.a. } X^T X = I_r$$
donde $n \ge r$, $f(X)$ es una función suave (potencialmente no convexa) y $h(X)$ es una función propia, semicontinua inferiormente, potencialmente no suave y separable por coordenadas. El conjunto factible es la variedad de Stiefel $\mathcal{M} = \text{St}(n, r)$. Este marco abarca aplicaciones críticas en aprendizaje estadístico y ciencia de datos, incluyendo el Análisis de Componentes Principales (PCA) disperso con regularización $\ell_0$ o $\ell_1$, PCA no negativo, entrenamiento de redes neuronales profundas con restricciones de ortogonalidad y aprendizaje de diccionarios.

Los métodos existentes enfrentan limitaciones significativas: muchos dependen de información de gradiente completo (alto costo computacional), no manejan eficazmente objetivos no suaves por coordenadas, carecen de propiedades de descenso reales (a menudo solo logran factibilidad asintóticamente) o proporcionan garantías de optimalidad débiles (convergen solo a puntos críticos estándar).

Metodología: El Algoritmo OBCD
Los autores proponen OBCD (Descenso de Coordenadas por Bloques Ortogonales), un método factible que actualiza $k$ filas de la matriz solución $X$ simultáneamente, donde $k \ge 2$.

1. Esquema de Actualización que Preserva Restricciones:
   En lugar de proyectar sobre la variedad o utilizar retracciones, OBCD emplea una regla de actualización específica que mantiene la ortogonalidad por construcción. Para un conjunto de trabajo de índices de filas $B$ (tamaño $k$), la actualización se define como:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   donde $U_B$ selecciona las filas en $B$, y $V \in \text{St}(k, k)$ es una matriz ortogonal que resuelve un subproblema. El Lema 2.1 demuestra que si $X^t$ es factible, $X^{t+1}$ permanece factible para cualquier $V \in \text{St}(k, k)$.

2. Formulación del Subproblema:
   En cada iteración, OBCD resuelve un subproblema a pequeña escala sobre la variedad de Stiefel de dimensión $k \times k$. Utilizando un enfoque de Mayorización-Minimización (MM), la parte suave $f(X)$ se aproxima mediante un sustituto cuadrático, mientras que la parte no suave $h(X)$ se mantiene exacta. El subproblema resultante es:
   $$\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)$$
   donde $Z = U_B^T X^t$, $P$ involucra el gradiente de $f$, y $\tilde{Q}$ es una matriz definida positiva derivada del Hessiano de $f$ o de un proxy escalar.

3. Resolución de Subproblemas:

   • $k$ general: El artículo asume que el subproblema puede resolverse exacta o eficientemente (por ejemplo, mediante estructuras amigables con el proximal).
   • Caso $k=2$: Los autores introducen un nuevo Método de Búsqueda de Puntos de Quiebre (BSM). Al parametrizar las matrices ortogonales $2 \times 2$ utilizando rotaciones de Givens ($V^{rot}_\theta$) y reflexiones de Jacobi ($V^{ref}_\theta$), el subproblema se reduce a una optimización unidimensional sobre $\theta$. El BSM identifica todos los puntos de quiebre (puntos críticos) de la función objetivo (incluyendo aquellos que surgen del término no suave $h$) para encontrar el minimizador global.

4. Selección del Conjunto de Trabajo:
   El algoritmo admite tanto estrategias aleatorias como cíclicas para seleccionar el conjunto de trabajo $B$.

Contribuciones Teóricas
El artículo proporciona un análisis teórico riguroso sobre optimalidad y convergencia:

• Completitud del Esquema de Actualización: Los autores demuestran que el esquema de actualización por filas propuesto es completo. Específicamente, cualquier punto en la variedad de Stiefel puede alcanzarse desde cualquier otro punto factible mediante una secuencia de estas actualizaciones de $k$ filas (Teorema 3.1, Corolario 3.2).
• Condiciones de Optimalidad Más Fuertes: El artículo define Puntos Estacionarios Globales por Bloque-$k$ (Puntos BSk). Una solución es un punto BSk si no se puede lograr ninguna mejora optimizando cualquier bloque de $k$ filas. Los autores establecen una jerarquía de optimalidad:
  $$\{\text{Óptimos Globales}\} \subseteq \{\text{Puntos BSk}\} \subseteq \{\text{Puntos BSk+1}\} \subseteq \{\text{Puntos Críticos}\}$$
  Esto implica que los puntos BSk (para $k \ge 2$) satisfacen una condición de optimalidad estrictamente más fuerte que los puntos críticos estándar, permitiendo teóricamente que el algoritmo escape de mínimos locales pobres que atrapan a los métodos estándar.
• Complejidad de Iteración:
  • OBCD encuentra un punto estacionario por bloque-$k$ de $\epsilon$ con una complejidad de iteración de $O(1/\epsilon)$.
  • Bajo la suposición de la desigualdad de Kurdyka–Łojasiewicz (KL), el artículo establece tasas de convergencia no ergódicas (de última iteración). Dependiendo del exponente KL $\sigma$, la convergencia es finita ($\sigma=0$), lineal ($\sigma \in (0, 1/2]$) o sublineal ($\sigma \in (1/2, 1)$).

Resultados Experimentales
Los autores evalúan OBCD en PCA dispersa regularizada con L0, PCA dispersa regularizada con L1 y PCA no negativa utilizando conjuntos de datos del mundo real (por ejemplo, MNIST, Gisette, 20News) y datos sintéticos.

• Rendimiento: OBCD supera consistentemente a las líneas base más avanzadas, incluyendo ADMM Linealizado (LADMM), ADMM Riemanniano (RADMM), Método de División Basado en Penalización (PSM) y Gradiente Proximal en Variedad (ManPG).
• Valores de la Función Objetivo: En términos del valor final de la función objetivo, OBCD logra valores más bajos que los métodos competidores, a menudo escapando de mínimos locales donde otros quedan atrapados.
• Eficiencia: Aunque los métodos de gradiente completo pueden requerir menos iteraciones, el menor costo por iteración de OBCD (actualizaciones de gradiente parcial) resulta en un rendimiento superior cuando se mide por tiempo de CPU.
• Factibilidad: A diferencia de algunos métodos infactibles (por ejemplo, ciertos métodos de división) que solo satisfacen las restricciones en el límite, OBCD mantiene la ortogonalidad estricta (y la no negatividad en la variante de PCA no negativa) a lo largo de todo el proceso de optimización.

Significado y Afirmaciones
El artículo afirma que OBCD ofrece un avance significativo al combinar eficiencia computacional con fuertes garantías teóricas. Su significado principal radica en:

1. Manejo de la No Suavidad: Aborda eficazmente objetivos no suaves por coordenadas bajo restricciones de ortogonalidad, un escenario donde muchos métodos existentes de optimización en variedades luchan.
2. Optimalidad Más Fuerte: Al utilizar actualizaciones por bloques ($k \ge 2$), el método apunta a puntos BSk, que son teóricamente superiores a los puntos críticos estándar, proporcionando un mecanismo para evitar mínimos locales subóptimos.
3. Factibilidad: Es un método estrictamente factible, asegurando que las restricciones se satisfagan en cada iteración, a diferencia de enfoques de división basados en penalización o infactibles.
4. Eficiencia Práctica: El algoritmo está diseñado para problemas a gran escala donde los cálculos de gradiente completo son prohibitivos, ofreciendo una alternativa escalable con propiedades de convergencia probadas.