Skip to content
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

The Convergence of Sparsified Gradient Methods #6

Open
nocotan opened this issue May 19, 2021 · 0 comments
Open

The Convergence of Sparsified Gradient Methods #6

nocotan opened this issue May 19, 2021 · 0 comments
Assignees
@nocotan
Labels
theoretical analysis Top-k S-SGD

Comments

@nocotan
Copy link
Member

nocotan commented May 19, 2021 •
edited
Loading

一言でいうと

top-K S-SGDの収束性解析の理論をつけた最初の論文

論文リンク

https://papers.nips.cc/paper/2018/hash/314450613369e0ee72d0da7f6fee773c-Abstract.html

著者/所属機関

IST Austria, ETH Zurich, KTH

投稿日付(yyyy/MM/dd)

NeurIPS2018

概要

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

Screen Shot 2021-05-25 at 17 37 23

  • 定数ξの影響はノード数Pが増えるにつれて線形に減衰．
  • Assumption 1は一般のケースおよび最悪ケースの評価で必要になる．この仮定の役割は勾配和のTop-KとTop-Kの勾配の和の差を上から抑えること．

新規性・差分

  • これ以前はヒューリスティクスであったgradient sparcificationの収束性に関する理論を初めて導出した
  • 勾配降下に基づく学習に関する幾つかのヒューリスティクス（学習率チューニング，勾配クリッピング）が収束のために不可欠であることを示した

手法

Screen Shot 2021-05-25 at 17 35 49

Convex Case

Screen Shot 2021-05-25 at 17 38 20

Non-Convex Case

Screen Shot 2021-05-25 at 17 38 47

結果

Screen Shot 2021-05-25 at 17 36 17

Screen Shot 2021-05-25 at 17 36 42

Screen Shot 2021-05-25 at 17 36 49

コメント
@nocotan nocotan self-assigned this May 25, 2021
@nocotan nocotan changed the title [WIP] The Convergence of Sparsified Gradient Methods The Convergence of Sparsified Gradient Methods May 25, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nocotan nocotan

Labels
theoretical analysis Top-k S-SGD
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@nocotan