論文の概要: Decentralized Multi-Task Stochastic Optimization With Compressed Communications

• arxiv url: http://arxiv.org/abs/2112.12373v1
• Date: Thu, 23 Dec 2021 05:54:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-25 00:46:22.796153
• Title: Decentralized Multi-Task Stochastic Optimization With Compressed Communications
• Title（参考訳）: 圧縮通信を用いた分散マルチタスク確率最適化
• Authors: Navjot Singh, Xuanyu Cao, Suhas Diggavi, Tamer Basar
• Abstract要約: 本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能バウンダリを求める。 グローバルな最小値からの逸脱と制約の違反は$mathcalO(T-frac12)$と$mathcalO(T-frac14)$によって上界されることを示す。
• 参考スコア（独自算出の注目度）: 22.31884634659446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a multi-agent network where each node has a stochastic (local) cost function that depends on the decision variable of that node and a random variable, and further the decision variables of neighboring nodes are pairwise constrained. There is an aggregate objective function for the network, composed additively of the expected values of the local cost functions at the nodes, and the overall goal of the network is to obtain the minimizing solution to this aggregate objective function subject to all the pairwise constraints. This is to be achieved at the node level using decentralized information and local computation, with exchanges of only compressed information allowed by neighboring nodes. The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes: (i) sample feedback, where each node has direct access to samples of the local random variable to evaluate its local cost, and (ii) bandit feedback, where samples of the random variables are not available, but only the values of the local cost functions at two random points close to the decision are available to each node. For both models, with compressed communication between neighbors, we have developed decentralized saddle-point algorithms that deliver performances no different (in order sense) from those without communication compression; specifically, we show that deviation from the global minimum value and violations of the constraints are upper-bounded by $\mathcal{O}(T^{-\frac{1}{2}})$ and $\mathcal{O}(T^{-\frac{1}{4}})$, respectively, where $T$ is the number of iterations. Numerical examples provided in the paper corroborate these bounds and demonstrate the communication efficiency of the proposed method.
• Abstract（参考訳）: 本稿では,各ノードが確率的(局所的な)コスト関数を持ち,そのノードの決定変数とランダム変数に依存するマルチエージェントネットワークについて考察する。 ノードにおける局所的コスト関数の期待値の加算として構成されたネットワークの集合客観関数があり、ネットワークの全体的な目標は、全ての対の制約を受けるこの集合客観関数に対する最小化解を得ることである。 これは分散情報とローカル計算を使ってノードレベルで実現され、隣のノードが許可する圧縮された情報だけを交換する。 本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能境界を求める。 (i)各ノードが局所確率変数のサンプルに直接アクセスして局所コストを評価するサンプルフィードバック、及び (ii) 確率変数のサンプルが得られないバンディットフィードバックであるが、決定に近い2つの確率点における局所コスト関数の値のみが各ノードで利用可能である。 両モデルとも, 隣人との通信を圧縮した分散サドルポイントアルゴリズムを開発し, 通信圧縮を伴わない性能を(順序的に)実現した。具体的には, 大域的最小値からの偏差と制約違反は, $\mathcal{O}(T^{-\frac{1}{2}})$ と $\mathcal{O}(T^{-\frac{1}{4}})$ で上界し, ここでは$T$ が反復数であることを示す。 論文で提示された数値例では,これらの境界をコラボレートし,提案手法の通信効率を示す。

関連論文リスト

• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Online Centralized Non-parametric Change-point Detection via Graph-based Likelihood-ratio Estimation [77.81487285123147]
  グラフの各ノードを、ほぼリアルタイムで同期して観測されるデータストリームを生成するようにします。 変更ポイント$tau$では、変更はノードのサブセット$C$で発生し、関連するノードストリームの確率分布に影響を与える。 本稿では,ポストチェンジとノードストリームの事前変更分布の確率比の直接推定に基づいて,$tau$を検出して$C$をローカライズするカーネルベースの新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-01-08T10:15:24Z)
• Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization [37.85806148420504]
  分散最適化環境では、$n$最適化ノードのネットワーク内の各エージェント$i$は、プライベート関数$f_i$を持つ。 最適化対応の選択ルールを導入し、高い2倍のコスト改善で隣人を選択する。 提案したセットワイズGSルールは,ネットワークの最大次数による高速化を実現する。
  論文  参考訳（メタデータ） (2022-07-15T15:37:03Z)
• Push--Pull with Device Sampling [8.344476599818826]
  複数のエージェントが協力して、基礎となる通信グラフを交換することで、ローカル関数の平均を最小化する分散最適化問題を考察する。 ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。 理論解析により,局所目的関数が強凸である場合,アルゴリズムは線形に収束することを示した。
  論文  参考訳（メタデータ） (2022-06-08T18:18:18Z)
• Neural Inverse Kinematics [72.85330210991508]
  逆キネマティック(英語版)(IK)法は、キネマティックチェインにおける選択された要素の所望の位置から関節のパラメータを復元する。 本稿では,問題階層構造を用いて,所望の位置に条件付き有効関節角度を逐次サンプリングするニューラルIK法を提案する。
  論文  参考訳（メタデータ） (2022-05-22T14:44:07Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Two-Bit Aggregation for Communication Efficient and Differentially Private Federated Learning [79.66767935077925]
  フェデレートラーニング(FL)では、機械学習モデルは、データをローカルに保ち、他のノードと共有しない状態で、複数のノードで分散的にトレーニングされる。 ノードからサーバに送信された情報は、各ノードのローカルデータの詳細を明らかにする可能性があるため、プライバシー上の懸念が生じる。 差分プライバシーを保証し、アップリンク通信オーバーヘッドを低減した2ビットアグリゲーションアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-06T19:03:58Z)
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning [58.6792963686231]
  フェデレートラーニング(FL)とは、複数のワーカノード(WN)がローカルデータを用いてジョイントモデルを構築するパラダイムを指す。 WNの最小更新方向、最初のミニバッチサイズ、ローカル更新頻度をどうやって選択するかは明らかになっていない。 局所的な更新頻度と局所的なミニサイズとの間にはトレードオフ曲線があることを示し、上記の複雑さを維持できることを示す。
  論文  参考訳（メタデータ） (2021-06-19T06:13:45Z)
• A hybrid variance-reduced method for decentralized stochastic non-convex optimization [15.447966950703947]
  textttGTHSGDアルゴリズムは、グローバルな勾配を追跡するためにネットワークを実装している。 textttGTHSGDは、必要なエラートレランス$epsilon$が十分小さいときに、ネットワークの複雑さを$O(n-1)$にします。
  論文  参考訳（メタデータ） (2021-02-12T20:13:05Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。 ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
  論文  参考訳（メタデータ） (2020-03-01T08:12:08Z)

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

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