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

Technische Zusammenfassung: Über die lineare Konvergenz von Bregman-Proximal-Gradient-Verfahren mit Anwendungen auf die Kullback–Leibler-Regression

Problemstellung
Die vorliegende Arbeit befasst sich mit der Minimierung konvexer zusammengesetzter Funktionale der Form $J(x) = F(x) + R(x)$, wobei $F$ eine differenzierbare konvexe Funktion und $R$ ein nicht-differenzierbarer konvexer Regularisierer ist. Während Proximal-Gradient-Verfahren (PGM) Standard für solche Probleme sind, weisen ihre Konvergenzraten typischerweise sublineare Geschwindigkeiten ($O(1/k)$) auf, sofern $F$ nicht stark konvex ist. Viele praktische Anwendungen, insbesondere in inversen Problemen wie der Poisson-Regression und der Kullback–Leibler (KL)-Regression, beinhalten jedoch glatte Terme $F$, die nicht stark konvex sind (z. B. wenn die Messmatrix $A$ einen Defekt im Rang aufweist).

Obwohl Bregman-Proximal-Gradient-Verfahren (BPGM) eingeführt wurden, um die Geometrie von $J$ über eine Mirror-Map $\phi$ anzupassen, erfordern die bestehenden Garantien für die lineare Konvergenz von BPGM im Allgemeinen, dass $F$ global relativ stark konvex in Bezug auf $\phi$ ist. Diese Bedingung ist für viele praktische KL-Regressionsprobleme oft zu restriktiv und hinterlässt eine Lücke im theoretischen Verständnis darüber, wann und warum eine lineare Konvergenz auftritt.

Methodik und theoretischer Rahmen
Die Autoren schlagen einen neuartigen theoretischen Rahmen vor, um die lineare Konvergenz für BPGM unter schwächeren Bedingungen als der globalen relativen starken Konvexität zu etablieren.

1. Restriktive relative starke Konvexität (RRSC): Die Arbeit führt eine neue Eigenschaft namens Restricted Relative Strong Convexity ein. Diese erweitert das Konzept der Restricted Strong Convexity (RSC) aus euklidischen Räumen auf den Bregman-Kontext. $F$ heißt RRSC relativ zu $\phi$, wenn es ein $\mu > 0$ gibt, so dass für alle $x$ im Definitionsbereich gilt:
   $$\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$$
   wobei $\bar{x}_{\ell_2}$ die euklidische Projektion von $x$ auf die Lösungsmenge $S$ ist. Entscheidend ist, dass diese Bedingung auf der euklidischen Projektion und nicht auf der Bregman-Projektion beruht, was technisch notwendig ist, um die Geometrie der KL-Divergenz zu handhaben.

2. Restriktiver Symmetriekoeffizient: Um die inhärente Asymmetrie von Bregman-Divergenzen zu handhaben (die nicht symmetrisch sind, sofern $\phi$ nicht quadratisch ist), definieren die Autoren einen restriktiven Symmetriekoeffizienten $\alpha_S(\phi)$. Dieser Koeffizient misst die Symmetrie der Divergenz $D_\phi$, die spezifisch auf die Lösungsmenge $S$ beschränkt ist. Die Autoren setzen voraus, dass $\alpha_S(\phi) > 0$ ist, um die Konvergenz zu gewährleisten.

3. Konvergenzanalyse: Unter den Annahmen von RRSC, relativer Glattheit (Lipschitz-ähnliche Bedingung) und einem positiven restriktiven Symmetriekoeffizienten beweisen die Autoren, dass die Bregman-Divergenz zwischen den Iteraten und der Lösungsmenge sowie die Funktionswerte linear konvergieren. Sie erweitern diese Ergebnisse auch auf eine automatische Schrittweitenwahl mittels Backtracking.

Anwendung auf die Kullback–Leibler-Regression
Der theoretische Rahmen wird auf (regulierte) KL-Regressionsprobleme angewendet, bei denen $F(x) = KL(y, Ax+b)$. Die Autoren analysieren das Konvergenzverhalten für drei spezifische Wahlmöglichkeiten der distanzgenerierenden Funktion $\phi$:

• Quadratische $\ell_2$-Norm: Der Standardfall der euklidischen Geometrie.
• Burg-Entropie: Eine populäre Wahl für KL-Probleme ($\phi_B(x) = -\sum \log x_n$).
• Geglättete Burg-Entropie: Ein neuartiger Vorschlag ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Wesentliche Erkenntnisse und Ergebnisse

• Limitierungen der Burg-Entropie: Die Analyse zeigt, dass die Verwendung der Standard-Burg-Entropie ($\phi_B$) in allen KL-Regressionsszenarien keine lineare Konvergenz garantiert. Speziell wenn die Lösungsmenge am Rand des nicht-negativen Orthants ($\partial C$) liegt oder wenn die Iterationen in einer bestimmten Weise dem Kern von $A$ nähern, versagt die RRSC-Bedingung und es ist nur eine sublineare Konvergenz zu beobachten.
• Vorteil der geglätteten Burg-Entropie: Die Autoren zeigen, dass die Verwendung der geglätteten Version ($\phi_{sB}$) die notwendige Geometrie induziert, um die RRSC-Bedingung zu erfüllen und einen positiven Symmetriekoeffizienten über einen breiteren Bereich von Szenarien hinweg sicherzustellen, einschließlich jener, in denen die Lösungen am Rand liegen.
• Numerische Validierung: Experimente an synthetischen Poisson-Inversenproblemen bestätigen die theoretischen Vorhersagen.
  • Für $\phi_{sB}$ wird konsistent eine lineare Konvergenz beobachtet, unabhängig davon, ob die Lösung eindeutig oder nicht eindeutig ist oder ob sie im Inneren oder am Rand der Beschränkungsmenge liegt.
  • Für $\phi_B$ wird lineare Konvergenz nur beobachtet, wenn die Lösung strikt im Inneren der Beschränkungsmenge liegt; andernfalls degradiert die Konvergenz zu sublinearen Raten.
  • Die Leistung von $\phi_{sB}$ ist sensitiv gegenüber dem Glättungsparameter $\xi$, wobei ein optimaler Trade-off zwischen der starken Konvexitätskonstante und der relativen Glattheitskonstante besteht.

Bedeutung und Ansprüche
Das Paper beansprucht, die erste Verallgemeinerung der Restricted Strong Convexity auf den Bregman-Kontext zu liefern und damit lineare Konvergenzraten für BPGM zu etablieren, ohne globale relative starke Konvexität vorauszusetzen. Der primäre Beitrag ist die Identifizierung der spezifischen geometrischen Bedingungen (RRSC und restriktive Symmetrie), die für die lineare Konvergenz in der KL-Regression erforderlich sind.

Die Autoren heben hervor, dass ihre Arbeit erklärt, warum die populäre Burg-Entropie in bestimmten praktischen Settings (z. B. bei Randlösungen) möglicherweise keine lineare Konvergenz liefert, und schlägt die geglättete Burg-Entropie als robuste Alternative vor, die eine lineare Konvergenz garantiert. Die Ergebnisse werden sowohl theoretisch als auch numerisch validiert, was eine starke Übereinstimmung zwischen den abgeleiteten Bedingungen und dem beobachteten empirischen Verhalten zeigt. Die Arbeit beansprucht nicht, nicht-konvexe Probleme zu lösen oder die nicht-konvexe KL-Regression zu erweitern, sondern verfeinert das Verständnis der konvexen zusammengesetzten Optimierung im Kontext der KL-Divergenz.