圧縮通信を伴う分散オンライン凸最適化：最適な後悔（レグレット）と応用
arXiv cs.LG / 2026/4/13
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、大規模なストリーミング環境における通信ボトルネックを減らすために、ローカル学習者と中央サーバ間の圧縮通信を前提とした分散オンライン凸最適化（D-OCO）を扱う。
- 圧縮がレグレットを悪化させうることを示す下界を導出し、圧縮比δと時間ホライゾンTに関して、凸損失と強凸損失で異なる減衰率を明らかにする。
- 凸損失に対してO(δ^{-1/2}√T)、強凸損失に対してO(δ^{-1}log T)のレグレット上界を達成する「最適」アルゴリズムを提案する。
- この手法は、圧縮誤差と射影誤差の相互作用を制御するために、誤差フィードバック機構と Follow-the-Regularized-Leader を組み合わせ、双方向の圧縮によって誤差が蓄積することを防ぐためにオンライン圧縮を用いる。
- オンライン・ツー・バッチ変換によりオフラインの確率的設定へ拡張し、圧縮通信とドメイン制約を伴う非スムーズ最適化に対する収束率を提供する。
