オンライン分散並列学習

ミニバッチ確率的降下勾配法

• 各更新で$B$個のデータ（ミニバッチ）を使って並列で勾配を計算し，その平均を使って，パラメータを更新する
  • $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$以下なら，最適解に収束する

参考文献

• オンライン機械学習本の4.2を参照