論文の概要: Asynchronous Distributed Optimization with Stochastic Delays
- arxiv url: http://arxiv.org/abs/2009.10717v3
- Date: Wed, 10 Mar 2021 05:35:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-15 22:06:45.055148
- Title: Asynchronous Distributed Optimization with Stochastic Delays
- Title（参考訳）: 確率遅延を用いた非同期分散最適化
- Authors: Margalit Glasgow, Mary Wootters
- Abstract要約: 中央パラメータサーバを用いた分散データ設定における非同期性について検討する。
分散データ設定のためのSAGAに基づくADSAGAを開発する。
本研究は,SGD や同期手法に対する分散誘導型非同期手法のウォールクロックの利点を実証するものである。
- 参考スコア（独自算出の注目度）: 22.069731881164895
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study asynchronous finite sum minimization in a distributed-data setting
with a central parameter server. While asynchrony is well understood in
parallel settings where the data is accessible by all machines -- e.g.,
modifications of variance-reduced gradient algorithms like SAGA work well --
little is known for the distributed-data setting. We develop an algorithm
ADSAGA based on SAGA for the distributed-data setting, in which the data is
partitioned between many machines. We show that with $m$ machines, under a
natural stochastic delay model with an mean delay of $m$, ADSAGA converges in
$\tilde{O}\left(\left(n + \sqrt{m}\kappa\right)\log(1/\epsilon)\right)$
iterations, where $n$ is the number of component functions, and $\kappa$ is a
condition number. This complexity sits squarely between the complexity
$\tilde{O}\left(\left(n + \kappa\right)\log(1/\epsilon)\right)$ of SAGA
\textit{without delays} and the complexity $\tilde{O}\left(\left(n +
m\kappa\right)\log(1/\epsilon)\right)$ of parallel asynchronous algorithms
where the delays are \textit{arbitrary} (but bounded by $O(m)$), and the data
is accessible by all. Existing asynchronous algorithms with distributed-data
setting and arbitrary delays have only been shown to converge in
$\tilde{O}(n^2\kappa\log(1/\epsilon))$ iterations. We empirically compare on
least-squares problems the iteration complexity and wallclock performance of
ADSAGA to existing parallel and distributed algorithms, including synchronous
minibatch algorithms. Our results demonstrate the wallclock advantage of
variance-reduced asynchronous approaches over SGD or synchronous approaches.
- Abstract（参考訳）: 中央パラメータサーバを用いた分散データ設定における非同期有限和最小化について検討する。
非同期性は、データがすべてのマシンでアクセス可能な並列環境ではよく理解されている — 例えば、sagaのような分散縮小勾配アルゴリズムの変更はうまく機能する — 分散データ設定では、ほとんど知られていない。
分散データ設定のためのSAGAに基づくアルゴリズムADSAGAを開発し、多くのマシン間でデータを分割する。
m$マシンの場合、$m$の平均遅延は$m$で、ADSAGAは$\tilde{O}\left(\left(n + \sqrt{m}\kappa\right)\log(1/\epsilon)\right)$イテレーション、$n$はコンポーネント関数の数であり、$\kappa$は条件数である。
この複雑さは、複雑さ $\tilde{O}\left(\left(n + \kappa\right)\log(1/\epsilon)\right)$ of SAGA \textit{without delays} と複雑性 $\tilde{O}\left(\left(n + m\kappa\right)\log(1/\epsilon)\right)$ of parallel asynchronous algorithm ここでは遅延が \textit{arbitrary} ($O(m)$で束縛されている)であり、データは全アクセス可能である。
分散データ設定と任意の遅延を持つ既存の非同期アルゴリズムは、$\tilde{O}(n^2\kappa\log(1/\epsilon))$ iterationsに収束することが示されている。
我々は,adsagaの反復複雑性とウォールクロック性能を,同期ミニバッチアルゴリズムを含む既存の並列分散アルゴリズムと比較した。
この結果から,SGD や同期手法に対する分散還元非同期手法のウォールクロックの利点が示された。
関連論文リスト
- Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching [25.95786289683455]
遅延に関する事前の知識を必要とせずに、全ての量子化に同時に適応する手法を示す。
さらに、非サイズの$O(inf_q tau_q2/(q T)2+sigma/sqrtqT)$と、凸問題に対する$O(tau_q2/(q T)2+sigma/sqrtqT)$の収束率を得る。
論文 参考訳（メタデータ） (2024-08-14T12:30:51Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Towards Understanding the Generalizability of Delayed Stochastic
Gradient Descent [63.43247232708004]
非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。
既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。
我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
論文 参考訳（メタデータ） (2023-08-18T10:00:27Z) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。
我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文 参考訳（メタデータ） (2022-07-26T08:47:54Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Asynchronous Advantage Actor Critic: Non-asymptotic Analysis and Linear
Speedup [56.27526702716774]
本稿では、A3CアルゴリズムをTD(0)で修正し、A3C-TD(0)と呼ばれ、証明可能な収束を保証する。
i.i.d.
サンプリング a3c-td(0) は、作業者あたり $mathcalo(epsilon-2.5/n)$ のサンプル複雑性を取得して $epsilon$ 精度を達成する。
2 に対して $mathcalO(epsilon-2.5/N)$ の最もよく知られたサンプル複雑性との比較
論文 参考訳（メタデータ） (2020-12-31T09:07:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。