論文の概要: High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking
- arxiv url: http://arxiv.org/abs/2605.00281v1
- Date: Thu, 30 Apr 2026 22:45:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-04 17:43:28.783963
- Title: High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking
- Title（参考訳）: 勾配追従を用いた分散確率最適化における高確率収束
- Abstract要約: 分散最適化における高確率収束保証について検討する。
その結果, 地平線上の条件は, 比較時間と同一であることがわかった。
- 参考スコア（独自算出の注目度）: 69.90407799170687
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study high-probability (HP) convergence guarantees in decentralized stochastic optimization, where multiple agents collaborate to jointly train a model over a network. Existing HP results in decentralized settings almost exclusively focus on the Decentralized Stochastic Gradient Descent ($\mathtt{DSGD}$) algorithm, which requires strong assumptions, such as bounded data heterogeneity, or strong convexity of each agent's cost. This is contrary to the mean-squared error (MSE) results, where methods incorporating bias-correction techniques are known to converge under relaxed assumptions and achieve better practical performance. In this paper we provide the first step toward bridging the gap, by studying HP convergence of $\mathtt{DSGD}$ incorporating the gradient tracking technique, in the presence of noise satisfying a relaxed sub-Gaussian condition. We show that the resulting method, dubbed $\mathtt{GT-DSGD}$, achieves order-optimal HP convergence rates for both non-convex and Polyak-Łojasiewicz costs, of order $\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big)$ and $\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big)$, respectively, where $n$ is the number of agents, $T$ is the time horizon and $δ\in (0,1)$ is the confidence parameter. Our results establish that $\mathtt{GT-DSGD}$ converges in the HP sense under the same conditions on the cost as in the MSE sense, while achieving comparable transient times. To the best of our knowledge, these are the first HP guarantees for decentralized optimization methods incorporating bias-correction. Numerical experiments on real and synthetic data verify our theoretical findings, underlining the superior performance of $\mathtt{GT-DSGD}$ and highlighting that the benefits of incorporating bias-correction are also maintained in the HP sense.
- Abstract（参考訳）: 本稿では,複数のエージェントが協調してネットワーク上でモデルをトレーニングする分散確率最適化における高確率収束保証について検討する。
既存のHPは、分散化確率勾配(Decentralized Stochastic Gradient Descent)(\mathtt{DSGD}$)アルゴリズムにのみ焦点をあてており、これは有界データの不均一性や各エージェントのコストの強い凸性といった強い仮定を必要とする。
これは平均二乗誤差(MSE)の結果とは逆で、バイアス補正手法を取り入れた手法は緩和された仮定の下で収束し、より実用的な性能を達成することが知られている。
本稿では,緩やかな準ガウス条件を満たす雑音の存在下で,勾配追跡手法を取り入れたHP収束について検討し,ギャップを埋める第一歩を示す。
結果の方法である$\matht{GT-DSGD}$は,非凸およびポリアック・ジョジャシエヴィチ費用の順序最適HP収束率,および$\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big)$と$\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big)$をそれぞれ達成し,$n$はエージェント数,$T$は時間軸,$δ\in(0,1)$は信頼性パラメータであることを示す。
この結果から,$\mathtt{GT-DSGD}$ は MSE の値と同じ条件下で HP の値に収束することがわかった。
我々の知る限り、これらはバイアス補正を取り入れた分散最適化手法に対する最初のHP保証である。
実データおよび合成データに関する数値実験により、この理論的な知見を検証し、$\mathtt{GT-DSGD}$の優れた性能を概説し、バイアス補正を組み込むことの利点もHPの意味で維持されていることを強調した。
関連論文リスト
- Improved High-probability Convergence Guarantees of Decentralized SGD [74.39742894097348]
平均二乗誤差(MSE)と同じ条件下で,$mathttDSGD$がHPに収束することを示す。
改良された分析によりユーザ数が線形アップし,$mathttDSGD$がHPの意味で性能を維持していることを示す。
論文 参考訳（メタデータ） (2025-10-07T17:15:08Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients [27.433334322019675]
Federated Learning (FL)は、クライアントが生データを共有せずに、協力的にモデルをトレーニングすることを可能にする。
FLはByzantine攻撃やデータ不均一性の反復に弱いため、パフォーマンスが著しく低下する可能性がある。
フェデレート正規化勾配アルゴリズム (Federated Normalized Gradients Algorithm, NGA) を提案する。
既存手法に対するベンチマーク収束の実験結果
論文 参考訳（メタデータ） (2024-08-18T16:50:39Z) - Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - DFedADMM: Dual Constraints Controlled Model Inconsistency for
Decentralized Federated Learning [52.83811558753284]
分散学習(DFL)は、中央サーバーを捨て、分散通信ネットワークを確立する。
既存のDFL手法は依然として、局所的な矛盾と局所的な過度なオーバーフィッティングという2つの大きな課題に悩まされている。
論文 参考訳（メタデータ） (2023-08-16T11:22:36Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
本稿では,通信制限条件下で分散最適化問題を解くことを検討する。
CEDASと呼ばれる圧縮精密拡散法について述べる。
特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
論文 参考訳（メタデータ） (2023-01-14T09:49:15Z) - Provably Efficient Convergence of Primal-Dual Actor-Critic with
Nonlinear Function Approximation [15.319335698574932]
The first efficient convergence result with primal-dual actor-critic with a convergence of $mathcalOleft ascent(Nright)Nright)$ under Polyian sample。
Open GymAI連続制御タスクの結果。
論文 参考訳（メタデータ） (2022-02-28T15:16:23Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。