arXiv cs.LG

対抗的ストラグラー軽減のためのブロックデザインに基づく勾配コーディング

Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers

http://arxiv.org/abs/1904.13373v1


勾配ベースの分散処理方法では、サーバーがワーカーに勾配計算を分配するが、一部のワーカーが遅延することによって発生する問題、いわゆる「ストラグラー」が存在する。本論文では、ストラグラーがいる状況でもサーバーが勾配の合計を復元できるようにするための「勾配コーディング」のフレームワークを提案する。特に「近似勾配コード」を利用し、計算と保存のオーバーヘッドを削減しつつ、対抗的なストラグラーを想定したコードの構築を目指す。この研究では、バランスの取れた不完全ブロックデザイン(BIBD)に基づく近似勾配コードを提案し、これらのコードの近似誤差がストラグラーの数にのみ依存することを示す。さらに、サーバーでの効率的なデコーディングを可能にし、対抗的ストラグラーの限界を考察。対抗者が一定の近似誤差を引き起こすために必要な最小のワーカー数、つまり「対抗的しきい値」を計算し、BIBDに基づくコードがこの下限を最大化することを明らかにする。