New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

99% of Worker-Master Communication in Distributed Optimization Is Not Needed #3

Open

nocotan opened this issue May 11, 2021 · 0 comments

Assignees

Labels

theoretical analysis

Member

nocotan commented May 11, 2021 •

edited

Loading

一言でいうと

分散学習において99%の通信が無駄になっていることを指摘．

論文リンク

著者/所属機関

Konstantin Mishchenko, Filip Hanzely, Peter Richtarik
KAUST

投稿日付(yyyy/MM/dd)

UAI2020

概要

ナイーブなgradient sparcificationでは，各ワーカーごとにτ-fractionだけ勾配を通信するが，この定数がワーカーごとに独立であるために，収束速度が1/τになってしまうことが知られている．
一方，これ以外のボトルネックとして，Server-Workers間の通信の非対称性がある：

Workers -> Server：ワーカーごとに異なるベクトルを通信
Server -> Workers：同一のベクトルを通信

この部分のボトルネックに注目して，分散学習における通信の無駄を明らかにした．

新規性・差分

independent block samplingによって条件付きで問題を解決できることを主張

手法

定理：n個のワーカーで分散学習をするとき，すべてのワーカーは1/nだけsparcificationしても収束レートを維持できる．

収束レートの導出のために，以下のような仮定を置く：

IBCDとさまざまなアルゴリズムへの適用

結果

コメント

presentation video

nocotan self-assigned this

nocotan added the theoretical analysis label

nocotan changed the title ~~[WIP] 99% of Worker-Master Communication in Distributed Optimization Is Not Needed~~ 99% of Worker-Master Communication in Distributed Optimization Is Not Needed

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment