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

Technische Samenvatting: Over de lineaire convergentie van Bregman proximale gradiëntmethoden met toepassingen op Kullback–Leibler regressie

Probleemstelling
Het artikel behandelt de minimalisatie van convexe composiete functionalen van de vorm $J(x) = F(x) + R(x)$, waarbij $F$ een differentieerbare convexe functie is en $R$ een niet-differentieerbare convexe regularisator. Hoewel Proximale Gradiëntmethoden (PGM) standaard zijn voor dergelijke problemen, zijn hun convergentiesnelheden doorgaans sublineair ($O(1/k)$), tenzij $F$ sterk convex is. Echter, veel praktische toepassingen, met name bij inverse problemen zoals Poisson-regressie en Kullback–Leibler (KL) regressie, omvatten gladde termen $F$ die niet sterk convex zijn (bijvoorbeeld wanneer de meetmatrix $A$ een lage rang heeft).

Hoewel Bregman Proximale Gradiëntmethoden (BPGM) zijn geïntroduceerd om zich aan te passen aan de geometrie van $J$ via een mirror-map $\phi$, vereisen bestaande garanties voor lineaire convergentie van BPGM over het algemeen dat $F$ globaal sterk convex is ten opzichte van $\phi$. Deze voorwaarde is vaak te restrictief voor praktische KL-regressieproblemen, waardoor er een gat ontstaat in het theoretische begrip van wanneer en waarom lineaire convergentie optreedt in deze settings.

Methodologie en Theoretisch Kader
De auteurs stellen een nieuw theoretisch kader voor om lineaire convergentie voor BPGM vast te stellen onder zwakkere voorwaarden dan globale relatieve sterke convexiteit.

1. Beperkte Relatieve Sterke Convexiteit (RRSC): Het artikel introduceert een nieuwe eigenschap genaamd Beperkte Relatieve Sterke Convexiteit. Dit breidt het concept van Restricted Strong Convexity (RSC) van Euclidische ruimten uit naar de Bregman-setting. Specifiek is $F$ RRSC ten opzichte van $\phi$ als er een $\mu > 0$ bestaat zodanig dat voor alle $x$ in het domein:
   $$\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$$
   waarbij $\bar{x}_{\ell_2}$ de Euclidische projectie van $x$ op de oplossingsverzameling $S$ is. Cruciaal is dat deze voorwaarde steunt op de Euclidische projectie in plaats van de Bregman-projectie, wat technisch noodzakelijk is om de geometrie van de KL-divergentie te behandelen.

2. Beperkte Symmetriecoëfficiënt: Om de asymmetrie te hanteren die inherent is aan Bregman-divergenties (die niet symmetrisch zijn, tenzij $\phi$ kwadratisch is), definiëren de auteurs een beperkte symmetriecoëfficiënt $\alpha_S(\phi)$. Deze coëfficiënt meet de symmetrie van de divergentie $D_\phi$, specifiek beperkt tot de oplossingsverzameling $S$. De auteurs vereisen dat $\alpha_S(\phi) > 0$ om convergentie te waarborgen.

3. Convergentieanalyse: Onder de aannames van RRSC, relatieve gladheid (Lipschitz-achtige conditie) en een positieve beperkte symmetriecoëfficiënt, bewijzen de auteurs dat de Bregman-divergentie tussen de iteraties en de oplossingsverzameling, evenals de objectieve functiewaarden, lineair convergeren. Ze breiden deze resultaten uit naar een automatische stapgrootte-selectieregel via backtracking.

Toepassing op Kullback–Leibler Regressie
Het theoretische kader wordt toegepast op (geregulariseerde) KL-regressieproblemen, waarbij $F(x) = KL(y, Ax+b)$. De auteurs analyseren het convergentiegedrag voor drie specifieke keuzes van de afstand-genererende functie $\phi$:

• Gekwadrateerde $\ell_2$-norm: De standaard Euclidische casus.
• Burg's Entropie: Een populaire keuze voor KL-problemen ($\phi_B(x) = -\sum \log x_n$).
• Gesmoothde Burg's Entropie: Een nieuw voorstel ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Belangrijkste Bevindingen en Resultaten

• Beperkingen van Burg's Entropie: De analyse laat zien dat het gebruik van de standaard Burg's entropie ($\phi_B$) geen lineaire convergentie garandeert voor alle KL-regressiescenario's. Specifiek, als de oplossingsverzameling op de grens van de niet-negatieve orthant ($\partial C$) ligt of als de iteraties op een specifieke wijze de kern van $A$ naderen, faalt de RRSC-voorwaarde en wordt er slechts sublineaire convergentie waargenomen.
• Voordeel van Gesmoothde Burg's Entropie: De auteurs demonstreren dat het gebruik van de gesmoothde versie ($\phi_{sB}$) de noodzakelijke geometrie induceert om de RRSC-voorwaarde te voldoen en een positieve symmetriecoëfficiënt te waarborgen over een breder scala aan scenario's, inclusief situaties waar oplossingen op de grens liggen.
• Numerieke Validatie: Experimenten op synthetische Poisson inverse problemen bevestigen de theoretische voorspellingen.
  • Voor $\phi_{sB}$ wordt lineaire convergentie consistent waargenomen, ongeacht of de oplossing uniek of niet-uniek is, of of deze in het binnenste of op de grens van de restrictieverzameling ligt.
  • Voor $\phi_B$ wordt lineaire convergentie alleen waargenomen wanneer de oplossing strikt in het binnenste van de restrictieverzameling ligt; anders degradeert de convergentie naar sublineaire snelheden.
  • De prestaties van $\phi_{sB}$ zijn gevoelig voor de smoothing-parameter $\xi$, met een optimaal evenwicht tussen de sterke convexiteitsconstante en de relatieve gladheidscoëfficiënt.

Betekenis en Claims
Het artikel claimt de eerste generalisatie van Restricted Strong Convexity naar de Bregman-setting te bieden, waarmee lineaire convergentieraten voor BPGM worden vastgesteld zonder de noodzaak van globale relatieve sterke convexiteit. De primaire bijdrage is de identificatie van de specifieke geometrische voorwaarden (RRSC en beperkte symmetrie) die vereist zijn voor lineaire convergentie in KL-regressie.

De auteurs benadrukken dat hun werk verklaart waarom de populaire Burg's entropie in bepaalde praktische settings (bijv. grensoplossingen) kan falen om lineaire convergentie te leveren, en stelt de gesmoothde Burg's entropie voor als een robuust alternatief dat lineaire convergentie garandeert. De resultaten worden zowel theoretisch als numeriek gevalideerd, waarbij een sterke overeenstemming wordt getoond tussen de afgeleide voorwaarden en het geobserveerde empirische gedrag. Het werk claimt geen niet-convexe problemen op te lossen of niet-convexe KL-regressie uit te breiden, maar verfijnt het begrip van convexe composiete optimalisatie in de context van KL-divergentie.