論文の概要: Asynchronous Stochastic Optimization Robust to Arbitrary Delays
- arxiv url: http://arxiv.org/abs/2106.11879v1
- Date: Tue, 22 Jun 2021 15:50:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 18:24:03.939137
- Title: Asynchronous Stochastic Optimization Robust to Arbitrary Delays
- Title（参考訳）: 任意遅延に対する非同期確率最適化ロバスト
- Authors: Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, Mariano Schain
- Abstract要約: 遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
- 参考スコア（独自算出の注目度）: 54.61797739710608
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider stochastic optimization with delayed gradients where, at each
time step $t$, the algorithm makes an update using a stale stochastic gradient
from step $t - d_t$ for some arbitrary delay $d_t$. This setting abstracts
asynchronous distributed optimization where a central server receives gradient
updates computed by worker machines. These machines can experience computation
and communication loads that might vary significantly over time. In the general
non-convex smooth optimization setting, we give a simple and efficient
algorithm that requires $O( \sigma^2/\epsilon^4 + \tau/\epsilon^2 )$ steps for
finding an $\epsilon$-stationary point $x$, where $\tau$ is the \emph{average}
delay $\smash{\frac{1}{T}\sum_{t=1}^T d_t}$ and $\sigma^2$ is the variance of
the stochastic gradients. This improves over previous work, which showed that
stochastic gradient decent achieves the same rate but with respect to the
\emph{maximal} delay $\max_{t} d_t$, that can be significantly larger than the
average delay especially in heterogeneous distributed systems. Our experiments
demonstrate the efficacy and robustness of our algorithm in cases where the
delay distribution is skewed or heavy-tailed.
- Abstract（参考訳）: 遅延勾配による確率的最適化を考えると、ステップ$t$ の各段階で、アルゴリズムは、任意の遅延$d_t$ に対して、ステップ$t - d_t$ から古い確率的勾配を使用して更新する。
この設定は、中央サーバがワーカマシンによって計算された勾配更新を受け取る非同期分散最適化を抽象化する。
これらのマシンは、時間とともに大きく変化する計算と通信の負荷を経験できる。
一般的な非凸スムーズな最適化設定では、$O( \sigma^2/\epsilon^4 + \tau/\epsilon^2 )$ steps for find a $\epsilon$-stationary point $x$, where $\tau$ is the \emph{average} delay $\smash{\frac{1}{T}\sum_{t=1}^T d_t}$および$\sigma^2$は確率勾配の分散である。
これは従来の研究よりも改善され、確率勾配が同じ速度を達成するが、特に異種分散システムにおける平均遅延よりもかなり大きい 'emph{maximal} delay $\max_{t} d_t$ についても同様であることを示した。
本実験は遅延分布が歪んだり重みを付けたりした場合のアルゴリズムの有効性と頑健性を示す。
関連論文リスト
- 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) - Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。
所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
論文 参考訳（メタデータ） (2024-05-23T11:46:03Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。