非同期フェデレーテッドラーニングにおける最適化のトレードオフ：確率ネットワークアプローチ

要旨: 同期型フェデレーテッドラーニングは、ストラグラー効果のためにスケールしにくい。非同期アルゴリズムは、到着した更新を処理することで更新スループットを向上させるが、2つの根本的な課題を導入する。すなわち、収束を劣化させる勾配の陳腐化（gradient staleness）と、データ分布が異質であることに起因して速いクライアントに偏ること（bias）である。AsyncSGD や Generalized AsyncSGD のようなアルゴリズムは、クライアント側のタスクキューによってこの偏りを緩和するが、既存の分析の多くは、根底にあるキューイング動力学を無視しており、更新スループットと勾配陳腐化の閉形式の特徴づけを欠いている。このギャップを埋めるために、本研究では Generalized AsyncSGD に対する確率的キューイングネットワークの枠組みを開発し、クライアントと中央サーバにおけるランダムな計算時間と、ランダムなアップリンクおよびダウンリンク通信遅延を同時にモデル化する。積の形（product-form）ネットワーク理論を活用することで、更新スループットの閉形式表現と、epsilon-定常点に到達するために必要な通信ラウンド複雑度および期待ウォールクロック時間の双方に対する閉形式の上界を導出する。これらの結果により、勾配陳腐化とウォールクロック収束速度の間のトレードオフが形式的に特徴づけられる。さらに、この枠組みを拡張して、確率的なタイミングのもとでのエネルギー消費を定量化し、収束速度とエネルギー効率の間の追加的なトレードオフを明らかにする。これらの解析結果に基づき、ルーティングと並行性を共同で最適化するための勾配ベースの最適化戦略を提案する。EMNIST による実験では、AsyncSGD と比べて収束時間が29%--46%減少し、エネルギー消費が36%--49%減少することを示す。