論文の概要: Tackling Data Heterogeneity: A New Unified Framework for Decentralized
SGD with Sample-induced Topology
- arxiv url: http://arxiv.org/abs/2207.03730v1
- Date: Fri, 8 Jul 2022 07:50:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-11 14:53:52.176579
- Title: Tackling Data Heterogeneity: A New Unified Framework for Decentralized
SGD with Sample-induced Topology
- Title(参考訳): データの不均一性に取り組む:サンプル誘起トポロジーを用いた分散sgdのための新しい統一フレームワーク
- Authors: Yan Huang, Ying Sun, Zehan Zhu, Changzhi Yan, Jinming Xu
- Abstract要約: 我々は,経験的リスク最小化問題に対して,勾配に基づく最適化手法を統一する汎用フレームワークを開発した。
本稿では,SAGA,Local-SVRG,GT-SAGAなどの分散還元(VR)および勾配追跡(GT)手法の統一的な視点を提供する。
その結果、VRとGTの手法は、それぞれデバイス内およびデバイス間のデータを効果的に排除し、アルゴリズムを最適解に正確に収束させることができることがわかった。
- 参考スコア(独自算出の注目度): 6.6682038218782065
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a general framework unifying several gradient-based stochastic
optimization methods for empirical risk minimization problems both in
centralized and distributed scenarios. The framework hinges on the introduction
of an augmented graph consisting of nodes modeling the samples and edges
modeling both the inter-device communication and intra-device stochastic
gradient computation. By designing properly the topology of the augmented
graph, we are able to recover as special cases the renowned Local-SGD and DSGD
algorithms, and provide a unified perspective for variance-reduction (VR) and
gradient-tracking (GT) methods such as SAGA, Local-SVRG and GT-SAGA. We also
provide a unified convergence analysis for smooth and (strongly) convex
objectives relying on a proper structured Lyapunov function, and the obtained
rate can recover the best known results for many existing algorithms. The rate
results further reveal that VR and GT methods can effectively eliminate data
heterogeneity within and across devices, respectively, enabling the exact
convergence of the algorithm to the optimal solution. Numerical experiments
confirm the findings in this paper.
- Abstract(参考訳): 我々は,集中型および分散型のシナリオにおける経験的リスク最小化問題に対して,いくつかの勾配に基づく確率的最適化手法を統合する汎用フレームワークを開発した。
このフレームワークは、サンプルをモデル化したノードとデバイス間通信とデバイス内確率勾配計算の両方をモデル化したエッジからなる拡張グラフの導入に基づいている。
拡張グラフのトポロジを適切に設計することにより、有名なローカルSGDおよびDSGDアルゴリズムの特殊なケースとして回復し、SAGA、ローカルSVRG、GT-SAGAといった分散還元(VR)および勾配追跡(GT)手法の統一的な視点を提供する。
また,適切な構造を持つリアプノフ関数に依存する滑らかで(強く)凸対象に対する統一収束解析も提供し,得られた速度は既存のアルゴリズムにおいて最もよく知られた結果を復元することができる。
さらに,vr法とgt法が,デバイス内およびデバイス間におけるデータの不均一性を効果的に除去し,最適な解へのアルゴリズムの正確な収束を可能にすることを明らかにした。
数値実験により,本研究の成果が確認された。
関連論文リスト
- Stability and Generalization for Distributed SGDA [70.97400503482353]
分散SGDAのための安定性に基づく一般化分析フレームワークを提案する。
我々は, 安定性の誤差, 一般化ギャップ, 人口リスクの包括的分析を行う。
理論的結果から,一般化ギャップと最適化誤差のトレードオフが明らかになった。
論文 参考訳(メタデータ) (2024-11-14T11:16:32Z) - Structure Learning with Adaptive Random Neighborhood Informed MCMC [0.0]
観測データに基づく構造学習の課題に対して,新しいMCMCサンプルであるPARNI-DAGを導入する。
因果補充性の仮定の下で、このアルゴリズムは方向非巡回グラフ(DAG)の後方分布から直接近似的なサンプリングを行うことができる。
種々の実験でDAG構造を学習する際の混合効率と精度を実証的に実証した。
論文 参考訳(メタデータ) (2023-11-01T15:47:18Z) - Stability and Generalization of the Decentralized Stochastic Gradient
Descent Ascent Algorithm [80.94861441583275]
本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。
本研究は,D-SGDAの一般化における各因子の影響を解析した。
また、最適凸凹設定を得るために一般化とバランスをとる。
論文 参考訳(メタデータ) (2023-10-31T11:27:01Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳(メタデータ) (2023-05-24T17:26:22Z) - The Novel Adaptive Fractional Order Gradient Decent Algorithms Design
via Robust Control [5.5491171448159715]
バニラ分数次降下は、目的関数が強く凸である場合には、正確な最小点に収束する代わりに、大域最小点の周りの領域に振動的に収束することがある。
この問題に対処するために,新しい適応分数次降下法 (AFDOG) と新しい分数次降下法 (AFOAGD) を提案する。
論文 参考訳(メタデータ) (2023-03-08T02:03:30Z) - Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent [7.6860514640178]
分散強化学習のための新しいゼロ階最適化アルゴリズムを提案する。
これにより、各エージェントはコンセンサスプロトコルを使わずに、コスト評価を独立してローカル勾配を推定できる。
論文 参考訳(メタデータ) (2021-07-26T18:11:07Z) - Cogradient Descent for Dependable Learning [64.02052988844301]
双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。
CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。
また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
論文 参考訳(メタデータ) (2021-06-20T04:28:20Z) - SGD with Coordinate Sampling: Theory and Practice [0.0]
MUSKETEERは大規模問題に対する適応勾配降下アルゴリズムである。
ノイズ勾配上で最も座標座標をサンプリングし、一方向に沿って動き、座標が大幅に減少する。
合成データと実データの両方に関する数値実験により,大規模問題におけるMUSKETEERの有効性が確認された。
論文 参考訳(メタデータ) (2021-05-25T10:37:50Z) - Decentralized Statistical Inference with Unrolled Graph Neural Networks [26.025935320024665]
分散最適化アルゴリズムをグラフニューラルネットワーク(GNN)にアンロールする学習ベースフレームワークを提案する。
エンドツーエンドトレーニングによるリカバリエラーを最小限にすることで、この学習ベースのフレームワークは、モデルのミスマッチ問題を解決する。
コンバージェンス解析により,学習したモデルパラメータがコンバージェンスを加速し,リカバリエラーを広範囲に低減できることが明らかとなった。
論文 参考訳(メタデータ) (2021-04-04T07:52:34Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。