オンライン分散並列学習
ミニバッチ確率的降下勾配法
- 各更新で$B$個のデータ（ミニバッチ）を使って並列で勾配を計算し，その平均を使って，パラメータを更新する
- 並列プロセスは更新のたびに同期する必要が有る
- Bulk Synchronous Parallel (BSP)とよばれる
Parallel SGD
- 更新のたび毎回同期して平均計算するのではなく，最後に平均をとる
- 学習データを並列プロセス数$P$で分割する
- プロセスごとに，確率的降下勾配法を$T$回反復して$\bold{w}_p^{(T+1)}$を得る
- 平均$\frac{1}{P} \sum_p \bold{w}_p^{(T+1)}$をとる
- 損失関数が凸で，その勾配がリプシッツ連続なら最適解に収束する
Iterative Parameter Mixture (IPM)
- 最後に平均をとるのではなく，各プロセスが担当するデータを1回舐めたら，その時同期して平均をとる
- これを$T$回繰り返す
Stale Synchronous Parallel (SSP)
- IPMは理論的保証がしにくい
- 各プロセスのパラメータがどれくらいずれるか（分散）が評価しづらいため
- 各プロセスのパラメータが大きく離れすぎないような制約が必要
- SSPはBSPの一般化
- 差分ベクトル
- BSPは，あるプロセス$p$の時刻$T$におけるパラメータ更新時には，残りの全てのプロセスの時刻$t<T$における差分ベクトルが必要だった
- この制約を緩和して，「残りの全てのプロセスの時刻$t<T-s$における差分ベクトルが必要」とする
- $s$はstalenessと呼ばれる定数
- $s=0$ならBSPと等価
- 確率的勾配降下法に対するSSPは，目的関数がK-リプシッツ連続な凸関数で，どの2つのデータ間のユークリッド距離がある定数$F$以下なら，最適解に収束する
参考文献
