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

技術要約：カルバック・リーブレア（Kullback–Leibler）回帰への応用を伴う、ブレグマン近接勾配法の線形収束に関する研究

問題設定
本論文は、凸関数 $F$ と非微分的な凸正則化項 $R$ からなる、形式 $J(x) = F(x) + R(x)$ の凸合成関数の最小化を取り扱う。近接勾配法（PGM）はこれらの問題に対して標準的であるが、その収束レートは、$F$ が強凸性を満たさない限り、通常は劣線形（$O(1/k)$）である。しかし、ポアソン回帰やカルバック・リーブレア（KL）回帰のような実用的な逆問題の多くでは、測定行列 $A$ がランク不足である場合など、$F$ が強凸ではない滑らかな項を含む。

ブレグマン近接勾配法（BPGM）は、ミラー写像 $\phi$ を通じて $J$ の幾何学的構造に適応するために導入されてきたが、既存の BPGM における線形収束の保証は、一般に $F$ が $\phi$ に対してグローバルな相対強凸性を満たすことを要求する。この条件は、実用的な KL 回帰問題にとって非常に制約が強く、なぜこれらの設定で線形収束が発生するのかという理論的理解に空白を残している。

手法および理論的枠組み
著者らは、グローバルな相対強凸性よりも弱い条件の下で BPGM の線形収束を確立するための、新しい理論的枠組みを提案する。

1. 制限的相対強凸性 (Restricted Relative Strong Convexity: RRSC): 本論文では、「制限的相対強凸性」と称される新しい性質を導入する。これは、ユークリッド空間における制限的強凸性（RSC）の概念をブレグマンの設定へと拡張したものである。具体的には、$F$ が $\phi$ に対して RRSC であるとは、すべての $x$ に対して以下を満たす $\mu > 0$ が存在することを指す：
   $$\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$$
   ここで $\bar{x}_{\ell_2}$ は $x$ の解集合 $S$ へのユークリッド射影である。極めて重要な点として、この条件はブレグマン射影ではなく、ユークリッド射影に依存しており、これは KL ダイバージェンスの幾何学を扱うために技術的に必要である。

2. 制限的対称係数 (Restricted Symmetry Coefficient): ブレグマンダイバージェンス（$\phi$ が二次形式でない限り非対称である）に内在する非対称性を扱うため、著者らは「制限的対称係数」$\alpha_S(\phi)$ を定義する。この係数は、解集合 $S$ に限定されたダイバージェンス $D_\phi$ の対称性を測定するものである。著者らは、収束を保証するために $\alpha_S(\phi) > 0$ であることを要求する。

3. 収束解析: RRSC、相対滑らかさ（リプシッツ的条件）、および正の制限的対称係数の仮定の下で、著者らは、反復回と解集合との間のブレグマンダイバージェス、および目的関数値が線形に収束することを証明する。また、バックトラッキングによる自動ステップサイズ選択ルールを含む結果へとこれらを拡張する。

カルバック・リーブレア回帰への応用
この理論的枠組みは、距離生成関数 $\phi$ の 3 つの具体的な選択肢について、（正則化された）KL 回帰問題に適用される：

• 二乗 $\ell_2$ ノルム: 標準的なユークリッドの場合。
• Burg のエントロピー: KL 問題で一般的な選択 ($\phi_B(x) = -\sum \log x_n$)。
• 平滑化された Burg のエントロピー: 新しい提案 ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$)。

主要な知見および結果

• Burg エントロピーの限界: 解析の結果、標準的な Burg エントロピー ($\phi_B$) を使用すると、すべての KL 回帰シナリオにおいて線形収束が保証されないことが明らかになった。具体的には、解が非負直交錐の境界 ($\partial C$) に位置する場合、または反復が特定の様式で $A$ の核（カーネル）に接近する場合、RRSC 条件が成立せず、劣線形な収束のみが観察される。
• 平滑化された Burg エントロピーの利点: 平滑化されたバージョン ($\phi_{sB}$) を採用することで、解が境界にある場合を含むより広い範囲のシナリオにおいて、RRSC 条件を満たし、正の対称係数を確保するのに必要な幾何学を誘起できることを示している。
• 数値検証: 合成ポアソン逆問題を用いた実験により、理論的予測が確認された。
  • $\phi_{sB}$ の場合、解が一意的か非一意的か、あるいは制約集合の内部にあるか境界にあるかにかかわらず、一貫して線形収束が観察される。
  • $\phi_B$ の場合、解が制約集合の内部に厳密に存在する場合にのみ線形収束が観察され、それ以外では収束が劣線形レートへと劣化する。
  • $\phi_{sB}$ の性能は平滑化パラメータ $\xi$ に敏感であり、強凸定数と相対滑らかさ定数の最適なトレードオフが存在する。

意義および主張
本論文は、制限的強凸性をブレグマンの設定へと一般化した最初の事例を提供し、グローバルな相対強凸性を必要とせずに BPGM の線形収束レートを確立したと主張している。主要な貢献は、線形収束に必要な具体的な幾何学的条件（RRSC および制限的対称性）を特定したことにある。

著者らは、なぜ普及している Burg エントロピーが、特定の実際的な設定（例：境界解）において線形収束を実現できない場合があるのかを説明し、線形収束を保証する堅牢な代替案として平滑化された Burg エントロピーを提案している。これらの結果は、理論的および数値的に検証されており、導出された条件と観察された経験的挙動との間に強い一致が見られる。本研究は、非凸問題を解決したり、非凸 KL 回帰へと拡張したりすることを目的としたものではなく、KL ダイバージェンスの文脈における凸合成最適化の理解を精緻化するものである。