A Convergence Analysis of Distributed SGD with Communication-Efficient Gradient Sparsification

[nocotan]

一言でいうと

gTop-k S-SGDアルゴリズムの収束性についての理論解析．

論文リンク

https://www.ijcai.org/proceedings/2019/473

著者/所属機関

Shaohuai Shi , Kaiyong Zhao , Qiang Wang , Zhenheng Tang and Xiaowen Chu
Department of Computer Science, Hong Kong Baptist University

投稿日付(yyyy/MM/dd)

IJCAI2019

概要

ワーカーごとにtop-kの勾配のみを通信するTop-k S-SGDの計算量はO(kP)であった．
これに対して，以下の更新式を用いるgTop-k S-SGDは計算量O(k log P)を達成する：

直感的にはワーカーごとのtop-kでなくグローバルなtop-kの勾配を更新する戦略．
擬似アルゴリズムは以下：

gTop-k S-SGDは計算量を大きく削減できる一方で，理論的に妥当な操作なのかという疑問も当然ある．
本研究ではgTop-k S-SGDの収束性について理論解析を行い，現実的な仮定のもとで収束が保証されることを示した．

新規性・差分

• 現実には成り立たない仮定を置いていた既存の収束性解析に対して，より弱い仮定の元で成り立つ結果を導出
• gTop-k S-SGDが非凸な問題において収束性の保証を持つことを証明
• 学習率を適当に選ぶことでgTop-k S-SGDが一般的なのmini-batch SGDと同等の収束性を持つことを示した

手法

理論展開のために以下の仮定を置く：

この仮定は，gTop-kで選ばれる勾配がランダムにk個選んだ勾配よりも大きいことを期待する．
この仮定の緩さは実験からも確かめられる．

このかこの仮定のもとで成り立つ主定理は以下：

以上から，gTop-k S-SGDの収束レートは以下の2つの項で構成されることがわかる：

• ミニバッチサイズに依存する項
• 学習率と圧縮率に依存する項

結果

仮定の実現性

収束性の証明の際に置いたAssumption1が実験的にも成り立つことを示している．
学習時に以下の指標を評価し，δ≦1が成り立つとき仮定が成り立つ：

収束レートと圧縮率

収束レートと圧縮率についてトレードオフの関係が確認できることを実験で示唆．

コメント

次に読むべき論文：
gTop-k S-SGD

• Shaohuai Shi, Qiang Wang, Kaiyong Zhao, et al. A distributed synchronous SGD algorithm with global Top-k sparsification for low bandwidth networks. In IEEE ICDCS, 2019

S-SGDの収束性に関する理論解析

• Shaohuai Shi, Wang Qiang, and Xiaowen Chu. Performance modeling and evaluation of distributed
  deep learning frameworks on GPUs. In IEEE DataCom, pages 949–957, 2018.
• Dan Alistarh, Torsten Hoefler, Mikael Johansson, et al. The convergence of sparsified gradient methods. In NeurIPS, pages 5977–5987, 2018.