論文の概要: Finite-Time Error Bounds for Distributed Linear Stochastic Approximation

• arxiv url: http://arxiv.org/abs/2111.12665v2
• Date: Thu, 28 Sep 2023 20:08:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-02 19:58:26.823079
• Title: Finite-Time Error Bounds for Distributed Linear Stochastic Approximation
• Title（参考訳）: 分布線形確率近似に対する有限時間誤差境界
• Authors: Yixuan Lin, Vijay Gupta, Ji Liu
• Abstract要約: 本稿ではマルコフ雑音と一般コンセンサス型相互作用によって駆動される新しいマルチエージェント線形分散近似アルゴリズムについて考察する。 本稿では,プッシュサム型分散近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.732502693144218
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers a novel multi-agent linear stochastic approximation algorithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends on the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the convergence of consensus-based stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the interconnection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination of the local equilibria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper proposes a push-sum-type distributed stochastic approximation algorithm and provides its finite-time bound for the time-varying step-size case by leveraging the analysis for the consensus-type algorithm with stochastic matrices and developing novel properties of the push-sum algorithm. Distributed temporal difference learning is discussed as an illustrative application.
• Abstract（参考訳）: 本稿では,マルコフ雑音と一般コンセンサス型相互作用によって駆動される新しいマルチエージェント線形確率近似アルゴリズムについて考察する。 エージェント間の相互接続構造を時間変化有向グラフにより記述する。 エージェント間の相互接続を2つの確率行列(少なくとも予想において)で記述する場合、コンセンサスに基づく確率近似アルゴリズムの収束が研究されているが、相互接続行列が単に確率行列である場合についてはあまり知られていない。 関連する相互作用行列が確率的である任意の一様連結グラフ列に対して、この論文は、関連する常微分方程式の特異平衡点からのアルゴリズムの出力の偏差として定義される平均二乗誤差上の有限時間境界を導出する。 相互結合行列が確率的である場合、平衡点は、通信がない場合、すべてのエージェントの局所平衡の任意の非特定凸結合となる。 時間的に異なるステップサイズを持つ場合も考慮される。 In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper proposes a push-sum-type distributed stochastic approximation algorithm and provides its finite-time bound for the time-varying step-size case by leveraging the analysis for the consensus-type algorithm with stochastic matrices and developing novel properties of the push-sum algorithm. 分散時間差分学習を図解的応用として論じる。

関連論文リスト

• A general error analysis for randomized low-rank approximation with application to data assimilation [42.57210316104905]
  中心行列および非標準行列に対するフロベニウスノルムにおける低ランク近似誤差の解析のための枠組みを提案する。 最小限の仮定の下では、期待と確率の正確な境界を導出する。 私たちの境界には、プロパティを導出し、実践的な選択を動機付けるための明確な解釈があります。
  論文  参考訳（メタデータ） (2024-05-08T04:51:56Z)
• A unified consensus-based parallel ADMM algorithm for high-dimensional regression with combined regularizations [3.280169909938912]
  並列交互乗算器 (ADMM) は大規模分散データセットの処理に有効であることが広く認識されている。 提案アルゴリズムは,財務事例の信頼性,安定性,スケーラビリティを示す。
  論文  参考訳（メタデータ） (2023-11-21T03:30:38Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Decentralized Online Regularized Learning Over Random Time-Varying Graphs [4.065547532041163]
  ランダムな時間変化グラフを用いたオンライン正規化線形回帰アルゴリズムを開発した。 後悔の上限は$O(T1-tauln T)$であり、$tauin (0.5,1)$はアルゴリズムのゲインに依存する定数である。 さらに、後悔の上限は$O(T1-tauln T)$であり、$tauin (0.5,1)$はアルゴリズムのゲインに依存する定数であることを示す。
  論文  参考訳（メタデータ） (2022-06-07T12:55:08Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。 この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
  論文  参考訳（メタデータ） (2021-01-16T17:11:02Z)
• Distributed Value Function Approximation for Collaborative Multi-Agent Reinforcement Learning [2.7071541526963805]
  本稿では,多エージェントオフポリシー学習のための分散勾配に基づく時間差分アルゴリズムを提案する。 提案するアルゴリズムは,その形式,可視性トレースの定義,時間スケールの選択,コンセンサス反復を組み込む方法などによって異なる。 より弱い情報構造制約の下で時間差分アルゴリズムにどのように適用できるかを示す。
  論文  参考訳（メタデータ） (2020-06-18T11:46:09Z)

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

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