Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

技術要約：アダマール多様体を超えた、非中央集権的なオンライン・リーマン最適化

問題定式化
本論文は、アダマール多様体（非正の曲率を持つ）という限定的な設定を超え、正の曲率を持つ可能性のある多様体における非中央集権的なオンライン・リーマン最適化の問題を扱う。目標は、$n$ 個のエージェントが、各時刻 $t$ においてグローバルな目的関数 $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$ を共同で最小化することであり、ここで各エージェント $i$ は自身の局所的な損失関数 $f_{i,t}$ のみを観測する。エージェントは以下の2つのフィードバック・レジームの下で動作する：

1. フル・グラディエント・フィードバック： エージェントは、局所関数の正確なリーマン勾配にアクセスできる。
2. 2点バンディット・フィードバック： エージェントは近傍の2点における関数値のみを受け取り、勾配推定量の構築を必要とする。

決定変数および比較点 $x^*$ は、リーマン多様体 $\mathcal{M}$ の測地線凸部分集合 $\mathcal{X}$ に制約される。主な技術的課題は、正の曲率を持つ空間における大域的な凸性の欠如と、非線形な多様性が、ユークリッド的な分散型最適化で使用される標準的なコンセンサス・ステップを複雑化させる点にある。

手法
著者らは、以下の3つのコアとなる手法コンポーネントに基づく統一的なフレームワークを提案している：

1. 曲率を考慮したコンセンサス・ステップ：
   本論文では、接空間内で定義された特定のコンセンサス更新規則を利用する：
   $$x_{i,t+1} = \text{Exp}_{y_{i,t+1}}\left(s \sum_{j=1}^n w_{ij} \text{Log}_{y_{i,t+1}}(y_{j,t+1})\right)$$
   ここで、$y_{i,t+1}$ は局所的な勾配更新と射影の結果であり、$W$ は倍重確率通信行列、 $s$ はコンセンサス・ステップサイズである。アンビエント空間の線形性やアダマール多様体の大域的凸性に依存する先行研究とは異なり、本研究では、有界な断面曲率 $K \in [K_{\min}, K_{\max}]$ を持つ一般的な多様体におけるこのステップの**線形分散減少（linear variance reduction）**を分析する。分析では、曲率によって歪められる凸性と平滑性のトレードオフを調整するために、ステップサイズ $s$ を最適化する。

2. フル情報アルゴリズム（Algorithm 1）：
   フル・グラディエントの設定では、エージェントはリーマン勾配降下ステップを実行した後、実行可能集合 $\mathcal{X}$ への射影を行い、その後、上述のコンセンサス・ステップを実行する。リグレット分析は、総誤差をネットワーク誤差（局所変数とグローバルなフレシェ平均との乖離）と局所最適化誤差に分解する。ネットワーク誤差は、コンセンサス分析で確立された線形分散減少特性を用いて抑えられる。

3. バンディット・フィードバック・アルゴリズム（Algorithm 2）および平滑化：
   2点バンディットの設定では、著者らは**ランダム化平滑化（randomized smoothing）**技術を採用している。エージェントは接空間の球面から一様に方向をサンプリングし、平滑化パラメータ $\delta$ で隔てられた2点において関数値を評価する。これにより、勾配推定量 $g^\delta_{i,t}$ が生成される。

• 劣凸性（Subconvexity）分析： 平滑化は厳密な測地線凸性を損なうため、著者らは平滑化された目的関数が**$\delta$-測地線劣凸（$\delta$-geodesically subconvex）**であることを確立する。完全な凸性からの偏差が $\delta$ によって線形に制御されることを証明する。
• ドメインの縮小： 境界付近での評価における実行可能性を確保するため、アルゴリズムは元のドメインの縮小された部分集合 $(1-\tau)\mathcal{X}$ 上で動作する。

主要な貢献
本論文の具体的な技術的貢献は以下の通りである：

• 一般的な多様体における線形分散減少： 著者らは、正および負の両方の曲率を持つ多様体におけるコンセンサス・ステップの線形収束を確立した（Theorem III.2）。これは、負の曲率が凸性を自然に強化するアダマール設定には存在しない、凸性と平滑性のトレードオフを管理するためにコンセンサス・ステップサイズを最適化することによって達成される。
• フル情報における $O(\sqrt{T})$ リグレット： 一般的な多様体（正の曲率を持つ可能性がある）に対して、分散型勾配降下アルゴリズムの静的リグレット境界が $O(\sqrt{T})$ であることを証明した（Theorem IV.2）。これは、ユークリッド設定で知られている最適レートと一致しており、分散化と正の曲率が漸近的にリグレット率を劣化させないことを示している。
• バンディット・フィードバックにおける初の $O(\sqrt{T})$ リグレット： 本論文は、2点バンディット・フィードバックの下での分散型オンライン・リーマン最適化に関する初の静的リグレット境界 $O(\sqrt{T})$ を提供する（Theorem V.2）。これは、計算効率の高い勾配推定量と、平滑化された目的関数の劣凸性に関する厳密な分析によって達成される。
• 一般化された幾何学的ツール： 任意の曲率の符号の境界を持つ多様体に有効な幾何学的比較不等式（Lemmas VII.3–VII.4）を開発・拡張し、定数を $K_{\min}$ と $K_{\max}$ によって明示的に定義した。

結果

• 理論的境界： 導出された静的リグレット境界は、フル・グラディエントおよび2点バンディット・フィードバックの両方の設定において $O(\sqrt{T})$ である。これらの境界における定数は、多様体の曲率、ネットワークの連結性（$W$ の第2最大特異値を介して）、およびドメインの直径に依存するが、時間ホライゾン $T$ に対する漸近的レートは最適である。
• 数値実験： 16次元の単位球面（正の曲率を持つ多様体）を用い、50のエージェントによる実験が行われた。実験結果は、アルゴリズムが収束し、累積リグレットが予想通り増加することを確認している。実験は、より大きなコンセンサス・ステップサイズの方が、より速いコンセンサス率により低いリグレットをもたらす傾向があること、およびバンディット設定が勾配推定の分散によりフル情報設定よりも収束が遅いことを示している。

意義
本論文は、曲がった空間における分散型最適化の理論的理解における決定的なギャップを埋めることで、その意義を主張している。

• アダマールを超えて： 分散型リーマン最適化に関する従来の理論的保証は、主にアダマール多様体に制限されていた。本研究は、測地線距離がグローバルな凸構造を誘導しない正の曲率を持つ多様体へと、これらの保証を拡張する。
• バンディット設定： バンディット・フィードバックの下での分散型リーマン最適化という、これまで未開拓であった領域に対処し、この設定における初の劣線形リグレット境界を提供している。
• 最適性： 曲率を考慮したコンセンサスおよび平滑化技術が用いられる限り、ユークリッド的な分散型オンライン最適化で達成可能な基本的な $O(\sqrt{T})$ リグレット率が、正の曲率と限定的なフィードバックが存在する場合でも維持されることを示している。

著者らは、境界は $T$ に関しては最適であるが、今後の研究では、これらの境界とネットワーク連結性および曲率パラメータとの具体的な依存関係を調査し、それらの特定のパラメータに対して証明可能な最適性を備えたアルゴリズムを設計できる可能性があると述べている。