論文の概要: Push--Pull with Device Sampling

• arxiv url: http://arxiv.org/abs/2206.04113v1
• Date: Wed, 8 Jun 2022 18:18:18 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-10 16:26:34.765780
• Title: Push--Pull with Device Sampling
• Title（参考訳）: デバイスサンプリングによるプッシュプル
• Authors: Yu-Guan Hsieh, Yassine Laguel, Franck Iutzeler, J\'er\^ome Malick
• Abstract要約: 複数のエージェントが協力して、基礎となる通信グラフを交換することで、ローカル関数の平均を最小化する分散最適化問題を考察する。 ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。 理論解析により,局所目的関数が強凸である場合,アルゴリズムは線形に収束することを示した。
• 参考スコア（独自算出の注目度）: 8.344476599818826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking and variance reduction over the entire network. This enables each node to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.
• Abstract（参考訳）: 我々は,複数のエージェントが協調して,基礎となる通信グラフを交換することにより,局所関数の平均を最小化する分散最適化問題を考える。 具体的には、各イテレーションにおいてノードのランダムな部分だけが計算を行う非同期モデルに自分自身を配置し、一方情報交換はすべてのノード間で、非対称な方法で行うことができる。 そこで本研究では,ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。 これにより、各ノードは目的関数の勾配の平均を追跡することができる。 理論解析により, 局所目的関数が強凸である場合, 想定混合行列上の穏やかな接続条件下で, アルゴリズムは線形収束することを示した。 特に、この結果は混合行列が二重確率的である必要はない。 実験では,計算ノードから隣接ノードへ情報を送信するブロードキャスト機構を調査し,合成データと実世界データの両方において,提案手法の線形収束を確認した。

関連論文リスト

• Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization [5.685037987395183]
  ノード連続体を持つグラフオン上での分散最適化問題について検討する。 グラノン上での勾配降下と勾配追従アルゴリズムを提案する。 時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
  論文  参考訳（メタデータ） (2024-07-03T02:47:39Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。 グラフが現在の勾配を混合する能力を定量化する計量法を提案する。 そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
  論文  参考訳（メタデータ） (2022-04-13T15:54:35Z)
• Decentralized Multi-Task Stochastic Optimization With Compressed Communications [22.31884634659446]
  本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能バウンダリを求める。 グローバルな最小値からの逸脱と制約の違反は$mathcalO(T-frac12)$と$mathcalO(T-frac14)$によって上界されることを示す。
  論文  参考訳（メタデータ） (2021-12-23T05:54:42Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  本稿では,分散マルチエージェント凸最適化問題について検討する。 提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。 実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
  論文  参考訳（メタデータ） (2021-08-19T13:19:54Z)
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
  本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。 エージェントは問題を解くためにzo座標法を近似する。
  論文  参考訳（メタデータ） (2021-03-24T03:07:46Z)
• Optimizing Mode Connectivity via Neuron Alignment [84.26606622400423]
  経験的に、損失関数の局所ミニマは、損失がほぼ一定であるようなモデル空間の学習曲線で接続することができる。 本稿では,ネットワークの重み変化を考慮し,対称性がランドスケープ・コネクティビティに与える影響を明らかにするための,より一般的な枠組みを提案する。
  論文  参考訳（メタデータ） (2020-09-05T02:25:23Z)
• Model Fusion with Kullback--Leibler Divergence [58.20269014662046]
  異種データセットから学習した後続分布を融合する手法を提案する。 我々のアルゴリズムは、融合モデルと個々のデータセット後部の両方に対する平均場仮定に依存している。
  論文  参考訳（メタデータ） (2020-07-13T03:27:45Z)

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

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