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

Resumo Técnico: Um Método de Descida de Coordenadas em Blocos para Otimização Composta Não Suave sob Restrições de Ortogonalidade

Formulação do Problema
O artigo aborda o desafio da otimização composta não suave sob restrições de ortogonalidade, formulada como:
$$\min_{X \in \mathbb{R}^{n \times r}} F(X) \triangleq f(X) + h(X), \quad \text{s.t. } X^T X = I_r$$
onde $n \ge r$, $f(X)$ é uma função suave (potencialmente não convexa) e $h(X)$ é uma função própria, semicontínua inferiormente e potencialmente não suave que é separável por coordenadas. O conjunto viável é a variedade de Stiefel $\mathcal{M} = \text{St}(n, r)$. Esta estrutura abrange aplicações críticas em aprendizado estatístico e ciência de dados, incluindo Análise de Componentes Principais (PCA) esparsa com regularização $\ell_0$ ou $\ell_1$, PCA não negativa, treinamento de redes neurais profundas com restrições ortogonais e aprendizado de dicionário.

Métodos existentes enfrentam limitações significativas: muitos dependem de informações de gradiente completo (alto custo computacional), falham em lidar efetivamente com objetivos não suaves por coordenada, carecem de propriedades de descida verdadeiras (frequentemente alcançando apenas viabilidade assintoticamente) ou fornecem garantias de otimalidade fracas (convergindo apenas para pontos críticos padrão).

Metodologia: O Algoritmo OBCD
Os autores propõem o OBCD (Descida de Coordenadas em Blocos Ortogonais), um método viável que atualiza $k$ linhas da matriz de solução $X$ simultaneamente, onde $k \ge 2$.

1. Esquema de Atualização Preservador de Restrições:
   Em vez de projetar sobre a variedade ou usar retrações, o OBCD emprega uma regra de atualização específica que mantém a ortogonalidade por construção. Para um conjunto de trabalho de índices de linhas $B$ (tamanho $k$), a atualização é definida como:
   $$X^{t+1} = X^t + U_B (V - I_k) U_B^T X^t$$
   onde $U_B$ seleciona as linhas em $B$, e $V \in \text{St}(k, k)$ é uma matriz ortogonal que resolve um subproblema. O Lema 2.1 prova que, se $X^t$ for viável, $X^{t+1}$ permanece viável para qualquer $V \in \text{St}(k, k)$.

2. Formulação do Subproblema:
   Em cada iteração, o OBCD resolve um subproblema de pequena escala sobre a variedade de Stiefel de dimensão $k \times k$. Utilizando uma abordagem de Majorização-Minimização (MM), a parte suave $f(X)$ é aproximada por um substituto quadrático, enquanto a parte não suave $h(X)$ é mantida exata. O subproblema resultante é:
   $$\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)$$
   onde $Z = U_B^T X^t$, $P$ envolve o gradiente de $f$, e $\tilde{Q}$ é uma matriz definida positiva derivada do Hessiano de $f$ ou de um proxy escalar.

3. Resolução de Subproblemas:

   • $k$ Geral: O artigo assume que o subproblema pode ser resolvido exatamente ou eficientemente (por exemplo, via estruturas amigáveis a proximal).
   • Caso $k=2$: Os autores introduzem um novo Método de Busca por Pontos de Quebra (BSM). Ao parametrizar matrizes ortogonais $2 \times 2$ usando rotações de Givens ($V^{rot}_\theta$) e reflexões de Jacobi ($V^{ref}_\theta$), o subproblema é reduzido a uma otimização unidimensional sobre $\theta$. O BSM identifica todos os pontos de quebra (pontos críticos) da função objetivo (incluindo aqueles que surgem do termo não suave $h$) para encontrar o minimizador global.

4. Seleção do Conjunto de Trabalho:
   O algoritmo suporta estratégias aleatórias e cíclicas para a seleção do conjunto de trabalho $B$.

Contribuições Teóricas
O artigo fornece uma análise teórica rigorosa regarding otimalidade e convergência:

• Completude do Esquema de Atualização: Os autores provam que o esquema de atualização linha a linha proposto é completo. Especificamente, qualquer ponto na variedade de Stiefel pode ser alcançado a partir de qualquer outro ponto viável através de uma sequência dessas atualizações de $k$ linhas (Teorema 3.1, Corolário 3.2).
• Condições de Otimalidade Mais Fortes: O artigo define Pontos Estacionários Globais em Blocos-$k$ (Pontos BSk). Uma solução é um ponto BSk se nenhuma melhoria puder ser feita otimizando qualquer bloco de $k$ linhas. Os autores estabelecem uma hierarquia de otimalidade:
  $$\{\text{Ótimos Globais}\} \subseteq \{\text{Pontos BSk}\} \subseteq \{\text{Pontos BS(k+1)}\} \subseteq \{\text{Pontos Críticos}\}$$
  Isso implica que os pontos BSk (para $k \ge 2$) satisfazem uma condição de otimalidade estritamente mais forte do que os pontos críticos padrão, permitindo teoricamente que o algoritmo escape de mínimos locais pobres que prendem métodos padrão.
• Complexidade de Iteração:
  • O OBCD encontra um ponto estacionário em blocos-$k$ $\epsilon$ com complexidade de iteração de $O(1/\epsilon)$.
  • Sob a suposição da desigualdade de Kurdyka–Łojasiewicz (KL), o artigo estabelece taxas de convergência não ergódicas (última iteração). Dependendo do expoente KL $\sigma$, a convergência é finita ($\sigma=0$), linear ($\sigma \in (0, 1/2]$) ou sublinear ($\sigma \in (1/2, 1)$).

Resultados Experimentais
Os autores avaliam o OBCD em PCA Esparsa regularizada L0, PCA Esparsa regularizada L1 e PCA Não Negativa usando conjuntos de dados do mundo real (por exemplo, MNIST, Gisette, 20News) e dados sintéticos.

• Desempenho: O OBCD supera consistentemente as linhas de base mais avançadas, incluindo ADMM Linearizado (LADMM), ADMM Riemanniano (RADMM), Método de Divisão Baseado em Penalidade (PSM) e Gradiente Proximal em Variedade (ManPG).
• Valores da Função Objetivo: Em termos de valor final da função objetivo, o OBCD alcança valores mais baixos do que os métodos concorrentes, frequentemente escapando de mínimos locais onde outros ficam presos.
• Eficiência: Embora métodos de gradiente completo possam exigir menos iterações, o menor custo por iteração do OBCD (atualizações de gradiente parcial) resulta em desempenho superior quando medido pelo tempo de CPU.
• Viabilidade: Ao contrário de alguns métodos inviáveis (por exemplo, certos métodos de divisão) que satisfazem as restrições apenas no limite, o OBCD mantém ortogonalidade estrita (e não negatividade na variante de PCA Não Negativa) durante todo o processo de otimização.

Significância e Afirmações
O artigo afirma que o OBCD oferece um avanço significativo ao combinar eficiência computacional com fortes garantias teóricas. Sua principal significância reside em:

1. Tratamento da Não Suavidade: Aborda efetivamente objetivos não suaves por coordenada sob restrições de ortogonalidade, um cenário onde muitos métodos existentes de otimização em variedade lutam.
2. Otimalidade Mais Forte: Ao utilizar atualizações em blocos ($k \ge 2$), o método visa pontos BSk, que são teoricamente superiores aos pontos críticos padrão, fornecendo um mecanismo para evitar mínimos locais subótimos.
3. Viabilidade: É um método estritamente viável, garantindo que as restrições sejam satisfeitas em cada iteração, ao contrário de abordagens de divisão baseadas em penalidade ou inviáveis.
4. Eficiência Prática: O algoritmo é projetado para problemas de grande escala onde cálculos de gradiente completo são proibitivos, oferecendo uma alternativa escalável com propriedades de convergência comprovadas.