On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression

Resumo Técnico: Sobre a Convergência Linear de Métodos de Gradiente Proximal de Bregman com Aplicações à Regressão de Kullback–Leibler

Enunciado do Problema
O artigo aborda a minimização de funcionais compostos convexos da forma $J(x) = F(x) + R(x)$, onde $F$ é uma função convexa diferenciável e $R$ é um regularizador convexo não diferenciável. Embora os Métodos de Gradiente Proximal (PGM) sejam padrão para tais problemas, suas taxas de convergência são tipicamente sublineares ($O(1/k)$), a menos que $F$ satisfaça a convexidade forte. No entanto, muitas aplicações práticas, particularmente em problemas inversos como regressão de Poisson e regressão de Kullback–Leibler (KL), envolvem termos suaves $F$ que não são fortemente convexos (por exemplo, quando a matriz de medição $A$ é deficiente de posto).

Embora os Métodos de Gradiente Proximal de Bregman (BPGM) tenham sido introduzidos para adaptar-se à geometria de $J$ via um mapa de espelho $\phi$, as garantias de convergência linear existentes para BPGM geralmente exigem que $F$ seja globalmente fortemente convexo em relação a $\phi$. Esta condição é frequentemente excessivamente restritiva para problemas práticos de regressão KL, deixando uma lacuna na compreensão teórica de quando e por que ocorre a convergência linear.

Metodologia e Estrutura Teórica
Os autores propõem um novo arcabouço teórico para estabelecer a convergência linear para BPGM sob condições mais fracas do que a convexidade relativa forte global.

1. Convexidade Forte Relativa Restrita (RRSC): O artigo introduz uma nova propriedade denominada Convexidade Forte Relativa Restrita. Esta estende o conceito de Convexidade Forte Restrita (RSC) de espaços euclidianos para o cenário de Bregman. Especificamente, $F$ é dito ser RRSC em relação a $\phi$ se existir $\mu > 0$ tal que para todo $x$ no domínio:
   $$\langle \nabla F(x) - \nabla F(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle \geq \mu \langle \nabla \phi(x) - \nabla \phi(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle$$
   onde $\bar{x}_{\ell_2}$ é a projeção euclidiana de $x$ sobre o conjunto de soluções $S$. Crucialmente, esta condição depende da projeção euclidiana em vez da projeção de Bregman, o que é tecnicamente necessário para lidar com a geometria da divergência KL.

2. Coeficiente de Simetria Restrita: Para lidar com a assimetria inerente às divergências de Bregman (que não são simétricas, a menos que $\phi$ seja quadrática), os autores definem um coeficiente de simetria restrita $\alpha_S(\phi)$. Este coeficiente mede a simetria da divergência $D_\phi$ especificamente restrita ao conjunto de soluções $S$. Os autores exigem que $\alpha_S(\phi) > 0$ para garantir a convergência.

3. Análise de Convergência: Sob as suposições de RRSC, suavidade relativa (condição do tipo Lipschitz) e um coeficiente de simetria restrita positivo, os autores provam que a divergência de Bregman entre as iterações e o conjunto de soluções, bem como os valores da função objetivo, convergem linearmente. Eles também estendem estes resultados para incluir uma regra de seleção automática de tamanho de passo via backtracking.

Aplicação à Regressão de Kullback–Leibler
O arcabouço teórico é aplicado a problemas de regressão KL (regularizada), onde $F(x) = KL(y, Ax+b)$. Os autores analisam o comportamento de convergência para três escolhas específicas da função geradora de distância $\phi$:

• Norma $\ell_2$ ao quadrado: O caso euclidiano padrão.
• Entropia de Burg: Uma escolha popular para problemas KL ($\phi_B(x) = -\sum \log x_n$).
• Entropia de Burg Suavizada: Uma proposta inovadora ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Principais Descobertas e Resultados

• Limitações da Entropia de Burg: A análise revela que o uso da entropia de Burg padrão ($\phi_B$) não garante convergência linear para todos os cenários de regressão KL. Especificamente, se o conjunto de soluções estiver na fronteira do ortante não negativo ($\partial C$) ou se as iterações se aproximarem do núcleo de $A$ de uma maneira específica, a condição RRSC falha e apenas a convergência sublinear é observada.
• Vantagem da Entropia de Burg Suavizada: Os autores demonstram que o emprego da versão suavizada ($\phi_{sB}$) induz a geometria necessária para satisfazer a condição RRSC e garantir um coeficiente de simetria positivo em uma gama mais ampla de cenários, incluindo aqueles onde as soluções estão na fronteira.
• Validação Numérica: Experimentos em problemas inversos de Poisson sintéticos confirmam as previsões teóricas.
  • Para $\phi_{sB}$, a convergência linear é observada consistentemente, independentemente de a solução ser única ou não única, ou se ela está no interior ou na fronteira do conjunto de restrições.
  • Para $\phi_B$, a convergência linear é observada apenas quando a solução está estritamente no interior do conjunto de restrições; caso contrário, a convergência degrada-se para taxas sublineares.
  • O desempenho de $\phi_{sB}$ é sensível ao parâmetro de suavização $\xi$, apresentando um compromisso (trade-off) ideal entre a constante de convexidade forte e a constante de suavidade relativa.

Significância e Alegações
O artigo alega fornecer a primeira generalização da Convexidade Forte Restrita para o cenário de Bregman, estabelecendo assim taxas de convergência linear para BPGM sem exigir a convexidade relativa forte global. A principal contribuição é a identificação das condições geométricas específicas (RRSC e simetria restrita) necessárias para a convergência linear em regressão KL.

Os autores destacam que o seu trabalho explica por que a popular entropia de Burg pode falhar em produzir convergência linear em certos cenários práticos (ex: soluções de fronteira) e propõe a entropia de Burg suavizada como uma alternativa robusta que garante a convergência linear. Os resultados são validados tanto teoricamente quanto numericamente, mostrando um forte alinhamento entre as condições derivadas e o comportamento empírico observado. O trabalho não pretende resolver problemas não convexos ou estender para regressão KL não convexa, mas sim refinar a compreensão da otimização composta convexa no contexto da divergência KL.