論文の概要: Private Weighted Random Walk Stochastic Gradient Descent
- arxiv url: http://arxiv.org/abs/2009.01790v2
- Date: Tue, 16 Mar 2021 10:10:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-22 08:17:00.810743
- Title: Private Weighted Random Walk Stochastic Gradient Descent
- Title(参考訳): 重み付きランダムウォーク確率勾配ディフレッシュ
- Authors: Ghadir Ayache and Salim El Rouayheb
- Abstract要約: グラフ内のノードに分散したデータを分散する分散学習環境を考える。
本稿では,データの一様サンプリングと重要サンプリングという2種類のランダムウォークに基づく2つのアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 21.23973736418492
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a decentralized learning setting in which data is distributed
over nodes in a graph. The goal is to learn a global model on the distributed
data without involving any central entity that needs to be trusted. While
gossip-based stochastic gradient descent (SGD) can be used to achieve this
learning objective, it incurs high communication and computation costs, since
it has to wait for all the local models at all the nodes to converge. To speed
up the convergence, we propose instead to study random walk based SGD in which
a global model is updated based on a random walk on the graph. We propose two
algorithms based on two types of random walks that achieve, in a decentralized
way, uniform sampling and importance sampling of the data. We provide a
non-asymptotic analysis on the rate of convergence, taking into account the
constants related to the data and the graph. Our numerical results show that
the weighted random walk based algorithm has a better performance for
high-variance data. Moreover, we propose a privacy-preserving random walk
algorithm that achieves local differential privacy based on a Gamma noise
mechanism that we propose. We also give numerical results on the convergence of
this algorithm and show that it outperforms additive Laplace-based privacy
mechanisms.
- Abstract(参考訳): グラフ内のノードに分散したデータを分散する分散学習環境を考える。
目標は、信頼できる必要のある中央のエンティティを必要とせずに、分散データでグローバルモデルを学ぶことだ。
この学習目標を達成するためにゴシップベースの確率勾配降下 (sgd) が用いられるが、全てのノードで全ての局所モデルが収束するのを待つ必要があるため、高い通信コストと計算コストがかかる。
収束を高速化するため,グラフ上のランダムウォークに基づいてグローバルモデルを更新したランダムウォークに基づくSGDを提案する。
本研究では,データの均一サンプリングと重要サンプリングを実現する2種類のランダムウォークに基づく2つのアルゴリズムを提案する。
データとグラフに関連する定数を考慮して,収束率の非漸近的解析を行う。
その結果, 重み付きランダムウォークに基づくアルゴリズムは, 高分散データに対して優れた性能を示すことがわかった。
さらに,提案するガンマノイズ機構に基づき,局所微分プライバシーを実現するプライバシ保存ランダムウォークアルゴリズムを提案する。
また,このアルゴリズムの収束に関する数値的な結果を示し,付加的ラプラスに基づくプライバシ機構よりも優れていることを示す。
関連論文リスト
- The Entrapment Problem in Random Walk Decentralized Learning [10.355835466049088]
ローカルデータに基づくグローバルモデル更新にランダムウォークを利用する分散SGDアルゴリズムについて検討する。
我々の焦点は収束を早めるために遷移確率行列を設計することである。
本稿では,ランダムな摂動(ジャンプ)を組み込んだL'evy Jumps (MHLJ) アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-07-30T07:36:13Z) - Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
異種データを用いた因果推論のための協調的逆確率スコア推定器を提案する。
異質性の増加に伴うメタアナリシスに基づく手法に対して,本手法は有意な改善を示した。
論文 参考訳(メタデータ) (2024-04-24T09:04:36Z) - Differentially Private Decentralized Learning with Random Walks [15.862152253607496]
ランダムウォークアルゴリズムを用いて分散学習のプライバシー保証を特徴付ける。そこでは、あるノードから別のノードへ通信グラフのエッジに沿って移動することで、モデルを更新する。
その結果、ランダムウォークアルゴリズムは、互いに近接するノードに対するゴシップアルゴリズムよりも、より優れたプライバシ保証をもたらす傾向があることが明らかとなった。
論文 参考訳(メタデータ) (2024-02-12T08:16:58Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳(メタデータ) (2022-12-06T12:42:11Z) - Clustering for directed graphs using parametrized random walk diffusion
kernels [5.145741425164946]
我々は,P-RWDKC(Parametrized Random Walk Diffusion Kernel Clustering)という新しいクラスタリングフレームワークを導入する。
我々のフレームワークは拡散幾何学と一般化スペクトルクラスタリングフレームワークに基づいている。
実世界のデータセットと実世界のグラフから構築した$K$-NNグラフの実験は、我々のクラスタリングアプローチがすべてのテストケースでうまく機能していることを示しています。
論文 参考訳(メタデータ) (2022-10-01T16:13:40Z) - Walk for Learning: A Random Walk Approach for Federated Learning from
Heterogeneous Data [17.978941229970886]
私たちは標準的アプリケーションとしてフェデレートラーニング(FL)に注目します。
FLの主な課題の1つは、ノードとパラメータサーバの間の通信ボトルネックである。
適応型ランダムウォーク学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-06-01T19:53:24Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳(メタデータ) (2021-12-07T11:26:41Z) - Degree-Based Random Walk Approach for Graph Embedding [0.0]
計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。
提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
論文 参考訳(メタデータ) (2021-10-21T19:16:16Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。
目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。
提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
論文 参考訳(メタデータ) (2020-07-07T18:25:25Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。