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

Resumen Técnico: Sobre la convergencia lineal de los métodos de gradiente proximal de Bregman con aplicaciones a la regresión de Kullback–Leibler

Planteamiento del problema
El artículo aborda la minimización de funcionales compuestos convexos de la forma $J(x) = F(x) + R(x)$, donde $F$ es una función convexa diferenciable y $R$ es un regularizador convexo no diferenciable. Aunque los Métodos de Gradiente Proximal (PGM) son estándar para tales problemas, sus tasas de convergencia son típicamente sublineales ($O(1/k)$), a menos que $F$ satisfaga la convexidad fuerte. Sin embargo, muchas aplicaciones prácticas, particularmente en problemas inversos como la regresión de Poisson y la regresión de Kullback–Leibler (KL), involucran términos suaves $F$ que no son fuertemente convexos (por ejemplo, cuando la matriz de medición $A$ tiene deficiencia de rango).

Aunque se han introducido los Métodos de Gradiente Proximal de Bregman (BPGM) para adaptarse a la geometría de $J$ mediante un mapa de espejo $\phi$, las garantías de convergencia lineal existentes para BPGM generalmente requieren que $F$ sea globalmente fuertemente convexa respecto a $\phi$. Esta condición suele ser demasiado restrictiva para los problemas prácticos de regresión KL, dejando un vacío en la comprensión teórica de cuándo y por qué ocurre la convergencia lineal en estos entornos.

Metodología y marco teórico
Los autores proponen un nuevo marco teórico para establecer la convergencia lineal para BPGM bajo condiciones más débiles que la convexidad fuerte relativa global.

1. Convexidad Fuerte Relativa Restringida (RRSC): El artículo introduce una nueva propiedad denominada Convexidad Fuerte Relativa Restringida. Esta extiende el concepto de Convexidad Fuerte Restringida (RSC) de los espacios euclidianos al entorno de Bregman. Específicamente, $F$ se dice que es RRSC respecto a $\phi$ si existe $\mu > 0$ tal que para todo $x$ en el dominio:
   $$\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$$
   donde $\bar{x}_{\ell_2}$ es la proyección euclidiana de $x$ sobre el conjunto de soluciones $S$. Crucialmente, esta condición depende de la proyección euclidiana en lugar de la proyección de Bregman, lo cual es técnicamente necesario para manejar la geometría de la divergencia KL.

2. Coeficiente de simetría restringido: Para manejar la asimetría inherente a las divergencias de Bregman (que no son simétricas a menos que $\phi$ sea cuadrática), los autores definen un coeficiente de simetría restringido $\alpha_S(\phi)$. Este coeficiente mide la simetría de la divergencia $D_\phi$ restringida específicamente al conjunto de soluciones $S$. Los autores requieren que $\alpha_S(\phi) > 0$ para asegurar la convergencia.

3. Análisis de convergencia: Bajo los supuestos de RRSC, suavidad relativa (condición de tipo Lipschitz) y un coeficiente de simetría restringido positivo, los autores demuestran que la divergencia de Bregman entre las iteraciones y el conjunto de soluciones, así como los valores de la función objetivo, convergen linealmente. También extienden estos resultados para incluir una regla de selección automática del tamaño de paso mediante retroceso (backtracking).

Aplicación a la regresión de Kullback–Leibler
El marco teórico se aplica a problemas de regresión KL (regularizados), donde $F(x) = KL(y, Ax+b)$. Los autores analizan el comportamiento de convergencia para tres elecciones específicas de la función generadora de distancia $\phi$:

• Norma $\ell_2$ al cuadrado: El caso euclidiano estándar.
• Entropía de Burg: Una elección popular para problemas KL ($\phi_B(x) = -\sum \log x_n$).
• Entropía de Burg suavizada: Una propuesta novedosa ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Hallazgos clave y resultados

• Limitaciones de la entropía de Burg: El análisis revela que el uso de la entropía de Burg estándar ($\phi_B$) no garantiza la convergencia lineal para todos los escenarios de regresión KL. Específicamente, si el conjunto de soluciones se encuentra en el límite del ortante no negativo ($\partial C$) o si las iteraciones se aproximan al núcleo de $A$ de una manera específica, la condición RRSC falla, y solo se observa una convergencia sublineal.
• Ventaja de la entropía de Burg suavizada: Los autores demuestran que el empleo de la versión suavizada ($\phi_{sB}$) induce la geometría necesaria para satisfacer la condición RRSC y asegurar un coeficiente de simetría positivo en un rango más amplio de escenarios, incluyendo aquellos donde las soluciones se encuentran en el límite.
• Validación numérica: Los experimentos en problemas inversos de Poisson sintéticos confirman las predicciones teóricas.
  • Para $\phi_{sB}$, se observa una convergencia lineal de manera consistente, independientemente de si la solución es única o no única, o si se encuentra en el interior o en el límite del conjunto de restricciones.
  • Para $\phi_B$, la convergencia lineal se observa solo cuando la solución se encuentra estrictamente en el interior del conjunto de restricciones; de lo contrario, la convergencia se degrada a tasas sublineales.
  • El rendimiento de $\phi_{sB}$ es sensible al parámetro de suavizado $\xi$, presentando un compromiso óptimo entre la constante de convexidad fuerte y la constante de suavidad relativa.

Significancia y afirmaciones
El artículo afirma proporcionar la primera generalización de la Convexidad Fuerte Restringida al entorno de Bregman, estableciendo así tasas de convergencia lineal para BPGM sin requerir la convexidad fuerte relativa global. La contribución principal es la identificación de las condiciones geométricas específicas (RRSC y simetría restringida) requeridas para la convergencia lineal en la regresión KL.

Los autores destacan que su trabajo explica por qué la popular entropía de Burg puede fallar en producir convergencia lineal en ciertos entornos prácticos (por ejemplo, soluciones en el límite) y propone la entropía de Burg suavizada como una alternativa robusta que garantiza la convergencia lineal. Los resultados son validados tanto teórica como numéricamente, mostrando una fuerte alineación entre las condiciones derivadas y el comportamiento empírico observado. El trabajo no pretende resolver problemas no convexos ni extender la regresión KL no convexa, sino que refina la comprensión de la optimización compuesta convexa en el contexto de la divergencia KL.