FedSEA：分散連合型オンライン学習における並列化の恩恵の実現

Abstract

オンラインフェデレーテッドラーニング（OFL）は、クライアントのプライバシーを損なうことなく、連続したデータストリーム上で分散型の意思決定を行うための人気のある枠組みとして注目されている。しかし、標準的なOFLで仮定される敵対者モデルは通常、並列化によって得られる潜在的な利点を排除してしまう。さらに、OFL問題における統計的変動の異なる発生源を適切に捉えられていない。本論文では、確率的に拡張された敵対者（SEA）を統合することで、OFLパラダイムを拡張する。この枠組みにおいて、損失関数は時間を通じてクライアント間で固定されたままである。だが、敵対者は各時点で各クライアントのためのデータ分布を、動的かつ独立に選択する。我々はこの問題を解くための algoOFL{} アルゴリズムを提案する。このアルゴリズムは、クライアント側でオンライン確率的勾配降下法を用い、サーバによる定期的なグローバル集約を併用する。時間範囲 \(T\) にわたるグローバルネットワークの後悔（regret）について、2種類の関数に対する境界を確立する：(1) 滑らかで凸な損失に対しては \mathcal{O}(\sqrt{T}) の上界を証明し、(2) 滑らかで強凸な損失に対しては \mathcal{O}(\log T) の上界を証明する。さらに、空間的異質性（クライアント間）と時間的異質性（時間の経過）という、後悔境界へのそれぞれの個別の寄与を、慎重な解析により定量化する。その結果、確率的勾配の分散に対して相対的に小さい時間変動（穏やかな時間変動）の領域では、後悔が並列化によって改善することを特定する。したがって、SEAの設定において、我々の結果はオンラインフェデレーテッドラーニングにおける既存の悲観的な最悪ケース結果を改善する。