論文の概要: 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（参考訳）: 勾配追従を用いた分散確率最適化における高確率収束
• Authors: Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed,
• 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)
• 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)
• 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)

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

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