論文の概要: Distributed gradient-based optimization in the presence of dependent aperiodic communication

• arxiv url: http://arxiv.org/abs/2201.11343v1
• Date: Thu, 27 Jan 2022 06:44:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-28 15:36:03.395729
• Title: Distributed gradient-based optimization in the presence of dependent aperiodic communication
• Title（参考訳）: 依存的非周期通信の存在下での分散勾配に基づく最適化
• Authors: Adrian Redder, Arunselvan Ramaswamy, Holger Karl
• Abstract要約: 反復分散最適化アルゴリズムは、グローバルな目的を最小化/最大化するために、時間とともに相互に通信する複数のエージェントを含む。 信頼できない通信網の存在下では、受信したデータの鮮度を測定するAOI( Age-of-Information)は、大きくなり、アルゴリズムの収束を妨げる可能性がある。 AoIプロセスに付随する確率変数が有限な第一モーメントを持つ確率変数に支配されている場合、収束が保証されることを示す。
• 参考スコア（独自算出の注目度）: 4.34720256795424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Iterative distributed optimization algorithms involve multiple agents that communicate with each other, over time, in order to minimize/maximize a global objective. In the presence of unreliable communication networks, the Age-of-Information (AoI), which measures the freshness of data received, may be large and hence hinder algorithmic convergence. In this paper, we study the convergence of general distributed gradient-based optimization algorithms in the presence of communication that neither happens periodically nor at stochastically independent points in time. We show that convergence is guaranteed provided the random variables associated with the AoI processes are stochastically dominated by a random variable with finite first moment. This improves on previous requirements of boundedness of more than the first moment. We then introduce stochastically strongly connected (SSC) networks, a new stochastic form of strong connectedness for time-varying networks. We show: If for any $p \ge0$ the processes that describe the success of communication between agents in a SSC network are $\alpha$-mixing with $n^{p-1}\alpha(n)$ summable, then the associated AoI processes are stochastically dominated by a random variable with finite $p$-th moment. In combination with our first contribution, this implies that distributed stochastic gradient descend converges in the presence of AoI, if $\alpha(n)$ is summable.
• Abstract（参考訳）: 反復的分散最適化アルゴリズムは、グローバル目的を最小化/最大化するために、時間とともに互いに通信する複数のエージェントを含む。 信頼できない通信ネットワークが存在する場合、受信したデータの鮮度を測定する情報年齢(aoi)は大きく、それゆえアルゴリズム的な収束を妨げる可能性がある。 本稿では,一般分散勾配に基づく最適化アルゴリズムの収束を,周期的にも確率的にも時間的に独立な点でも起こり得ない通信の存在下で検討する。 aoiプロセスに関連する確率変数が確率的に有限第一モーメントの確率変数に支配されている場合、収束は保証される。 これは、最初の瞬間以上の境界性の以前の要求を改善する。 次に,時間変動ネットワークのための新しい確率的接続性である確率的強結合(ssc)ネットワークを紹介する。 任意の$p \ge0$に対して、sscネットワーク内のエージェント間の通信の成功を記述するプロセスが$\alpha$-mixingで$n^{p-1}\alpha(n)$ summableであれば、関連するaoiプロセスは確率的に、有限の$p$-thモーメントを持つ確率変数によって支配される。 最初の寄与と組み合わせると、分散確率勾配は AoI の存在下で収束し、$\alpha(n)$ が総和可能であることを意味する。

関連論文リスト

• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
  論文  参考訳（メタデータ） (2024-03-25T22:49:56Z)
• 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)
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
  マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。 我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
  論文  参考訳（メタデータ） (2021-10-27T08:01:17Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Improving the Transient Times for Distributed Stochastic Gradient Methods [5.215491794707911]
  拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。 EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。 我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
  論文  参考訳（メタデータ） (2021-05-11T08:09:31Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。