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

Résumé technique : Sur la convergence linéaire des méthodes de gradient proximal de Bregman avec des applications à la régression de Kullback–Leibler

Énoncé du problème
L'article traite de la minimisation de fonctionnelles composées convexes de la forme $J(x) = F(x) + R(x)$, où $F$ est une fonction convexe différentiable et $R$ est un régularisateur convexe non différentiable. Bien que les méthodes de gradient proximal (PGM) soient standard pour de tels problèmes, leurs taux de convergence sont typiquement sous-linéaires ($O(1/k)$), à moins que $F$ ne soit fortement convexe. Cependant, de nombreuses applications pratiques, particulièrement dans les problèmes inverses comme la régression de Poisson et la régression de Kullback–Leibler (KL), impliquent des termes lisses $F$ qui ne sont pas fortement convexes (par exemple, lorsque la matrice de mesure $A$ est de rang déficient).

Bien que des méthodes de gradient proximal de Bregman (BPGM) aient été introduites pour s'adapter à la géométrie de $J$ via une application miroir $\phi$, les garanties de convergence linéaire existantes pour la BPGM exigent généralement que $F$ soit globalement fortement convexe par rapport à $\phi$. Cette condition est souvent trop restrictive pour les problèmes de régression KL pratiques, laissant un vide dans la compréhension théorique de quand et pourquoi une convergence linéaire se produit dans ces contextes.

Méthodologie et cadre théorique
Les auteurs proposent un nouveau cadre théorique pour établir la convergence linéaire pour la BPGM sous des conditions plus faibles que la forte convexité relative globale.

1. Convexité forte relative restreinte (RRSC) : L'article introduit une nouvelle propriété nommée Convexité forte relative restreinte. Elle étend le concept de convexité forte restreinte (RSC) des espaces euclidiens vers le cadre de Bregman. Plus précisément, $F$ est dite RRSC par rapport à $\phi$ s'il existe $\mu > 0$ tel que pour tout $x$ dans le domaine :
   $$\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$$
   où $\bar{x}_{\ell_2}$ est la projection euclidienne de $x$ sur l'ensemble des solutions $S$. Crucialement, cette condition repose sur la projection euclidienne plutôt que sur la projection de Bregman, ce qui est techniquement nécessaire pour gérer la géométrie de la divergence KL.

2. Coefficient de symétrie restreint : Pour gérer l'asymétrie inhérente aux divergences de Bregman (qui ne sont pas symétriques à moins que $\phi$ ne soit quadratique), les auteurs définissent un coefficient de symétrie restreint $\alpha_S(\phi)$. Ce coefficient mesure la symétrie de la divergence $D_\phi$ spécifiquement restreinte à l'ensemble des solutions $S$. Les auteurs exigent que $\alpha_S(\phi) > 0$ pour assurer la convergence.

3. Analyse de convergence : Sous les hypothèses de RRSC, de lissité relative (condition de type Lipschitz) et d'un coefficient de symétrie restreint positif, les auteurs prouvent que la divergence de Bregman entre les itérés et l'ensemble des solutions, ainsi que les valeurs de la fonction objectif, convergent linéairement. Ils étendent également ces résultats pour inclure une règle de sélection automatique du pas de calcul via le backtracking.

Application à la régression de Kullback–Leibler
Le cadre théorique est appliqué à des problèmes de régression KL (régularisés), où $F(x) = KL(y, Ax+b)$. Les auteurs analysent le comportement de convergence pour trois choix spécifiques de la fonction génératrice de distance $\phi$ :

• Norme $\ell_2$ au carré : Le cas euclidien standard.
• Entropie de Burg : Un choix populaire pour les problèmes KL ($\phi_B(x) = -\sum \log x_n$).
• Entropie de Burg lissée : Une proposition novatrice ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Principaux résultats et conclusions

• Limites de l'entropie de Burg : L'analyse révèle que l'utilisation de l'entropie de Burg standard ($\phi_B$) ne garantit pas la convergence linéaire pour tous les scénarios de régression KL. Spécifiquement, si l'ensemble des solutions se situe sur la frontière de l'orthant non négatif ($\partial C$) ou si les itérés approchent du noyau de $A$ d'une certaine manière, la condition RRSC échoue, et seule une convergence sous-linéaire est observée.
• Avantage de l'entropie de Burg lissée : Les auteurs démontrent que l'emploi de la version lissée ($\phi_{sB}$) induit la géométrie nécessaire pour satisfaire la condition RRSC et assurer un coefficient de symétrie positif à travers un éventail plus large de scénarios, y compris ceux où les solutions se situent sur la frontière.
• Validation numérique : Des expériences sur des problèmes inverses de Poisson synthétiques confirment les prédictions théoriques.
  • Pour $\phi_{sB}$, une convergence linéaire est observée de manière constante, que la solution soit unique ou non, ou qu'elle se trouve dans l'intérieur ou sur la frontière de l'ensemble de contrainte.
  • Pour $\phi_B$, la convergence linéaire n'est observée que lorsque la solution se situe strictement dans l'intérieur de l'ensemble de contrainte ; sinon, la convergence se dégrade vers des taux sous-linéaires.
  • La performance de $\phi_{sB}$ est sensible au paramètre de lissage $\xi$, présentant un compromis optimal entre la constante de forte convexité et la constante de lissité relative.

Signification et revendications
L'article affirme fournir la première généralisation de la convexité forte restreinte au cadre de Bregman, établissant ainsi des taux de convergence linéaire pour la BPGM sans nécessiter une forte convexité relative globale. La principale contribution est l'identification des conditions géométriques spécifiques (RRSC et symétrie restreinte) requises pour la convergence linéaire dans la régression KL.

Les auteurs soulignent que leur travail explique pourquoi la célèbre entropie de Burg peut échouer à produire une convergence linéaire dans certains contextes pratiques (par exemple, les solutions de frontière) et propose l'entropie de Burg lissée comme une alternative robuste qui garantit la convergence linéaire. Les résultats sont validés tant théoriquement que numériquement, montrant un fort alignement entre les conditions dérivées et le comportement empirique observé. Le travail ne prétend pas résoudre des problèmes non convexes ou étendre la régression KL non convexe, mais plutôt affiner la compréhension de l'optimisation composée convexe dans le contexte de la divergence KL.