論文の概要: Distributed Online Optimization with Stochastic Agent Availability

• arxiv url: http://arxiv.org/abs/2411.16477v1
• Date: Mon, 25 Nov 2024 15:20:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-26 14:19:32.532344
• Title: Distributed Online Optimization with Stochastic Agent Availability
• Title（参考訳）: Stochastic Agent 可用性を備えた分散オンライン最適化
• Authors: Juliette Achddou, Nicolò Cesa-Bianchi, Hao Qiu,
• Abstract要約: エージェントが各ステップで既知の確率$p$でアクティブである分散オンライン最適化の変種について検討する。 我々は,そのネットワーク後悔を,アクティブエージェントの即時後悔の平均から分析する。
• 参考スコア（独自算出の注目度）: 14.801853435122904
• License:
• Abstract: Motivated by practical federated learning settings where clients may not be always available, we investigate a variant of distributed online optimization where agents are active with a known probability $p$ at each time step, and communication between neighboring agents can only take place if they are both active. We introduce a distributed variant of the FTRL algorithm and analyze its network regret, defined through the average of the instantaneous regret of the active agents. Our analysis shows that, for any connected communication graph $G$ over $N$ agents, the expected network regret of our FTRL variant after $T$ steps is at most of order $(\kappa/p^2)\min\big\{\sqrt{N},N^{1/4}/\sqrt{p}\big\}\sqrt{T}$, where $\kappa$ is the condition number of the Laplacian of $G$. We then show that similar regret bounds also hold with high probability. Moreover, we show that our notion of regret (average-case over the agents) is essentially equivalent to the standard notion of regret (worst-case over agents), implying that our bounds are not significantly improvable when $p=1$. Our theoretical results are supported by experiments on synthetic datasets.
• Abstract（参考訳）: クライアントが常に利用できないような実践的なフェデレーション学習環境によって動機付けされ、各タイミングでエージェントが既知の確率$p$でアクティブであり、隣接するエージェント間の通信は、両方がアクティブである場合に限られる分散オンライン最適化の亜種を調査する。 我々は,FTRLアルゴリズムの分散変種を導入し,そのネットワーク後悔を,アクティブエージェントの即時後悔の平均を通じて解析する。 我々の分析は、接続された通信グラフの$G$ over $N$エージェントに対して、$T$ステップ後のFTRL変種に対する期待されたネットワーク後悔は、最も多くは$(\kappa/p^2)\min\big\{\sqrt{N},N^{1/4}/\sqrt{p}\big\}\sqrt{T}$であり、$\kappa$は$G$のラプラシアンの条件数であることを示している。 そして、同様の後悔の境界も高い確率で成り立つことを示す。 さらに、我々の後悔の概念(エージェントに対する平均ケース)は、本質的には後悔の標準的な概念(エージェントに対するWorst-case)と等価であることを示す。 我々の理論的結果は、合成データセットの実験によって支えられている。

関連論文リスト

• Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
  マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。 そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。 通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
  論文  参考訳（メタデータ） (2024-11-13T05:59:04Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
  論文  参考訳（メタデータ） (2024-03-25T22:49:56Z)
• Fair Multi-Agent Bandits [14.614647884175657]
  残念な$Oleft(N3 log fracBDelta f(log T) log T right)$, where $f(t)$ は infinity に $t$ で分岐する任意の関数である。 これにより、オーダー$O(f(log T) log T )$と同じ上限を持つ前の結果を大幅に改善するが、エージェントの数に指数関数的に依存する。
  論文  参考訳（メタデータ） (2023-06-07T15:05:53Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
  我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。 すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
  論文  参考訳（メタデータ） (2022-05-12T19:46:35Z)
• Communication-efficient Decentralized Local SGD over Undirected Networks [2.3572498744567123]
  我々は、$n$エージェントのネットワークがグローバル関数$F$を最小化しようとする分散学習問題を考察する。 通信ラウンド数と各エージェントの計算労力のトレードオフを分析する。 その結果,R=Omega(n)$通信ラウンドのみを用いることで,O(1/nT)$というスケールの誤差を実現できることがわかった。
  論文  参考訳（メタデータ） (2020-11-06T09:34:00Z)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  最短経路 (SSP) は計画と制御においてよく知られた問題である。 また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。 我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
  論文  参考訳（メタデータ） (2020-06-20T12:10:35Z)

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

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