論文の概要: Improved High-probability Convergence Guarantees of Decentralized SGD

• arxiv url: http://arxiv.org/abs/2510.06141v1
• Date: Tue, 07 Oct 2025 17:15:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-08 17:57:08.377016
• Title: Improved High-probability Convergence Guarantees of Decentralized SGD
• Title（参考訳）: 分散型SGDの高確率収束保証の改善
• Authors: Aleksandar Armacki, Ali H. Sayed,
• Abstract要約: 平均二乗誤差(MSE)と同じ条件下で,$mathttDSGD$がHPに収束することを示す。 改良された分析によりユーザ数が線形アップし,$mathttDSGD$がHPの意味で性能を維持していることを示す。
• 参考スコア（独自算出の注目度）: 74.39742894097348
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convergence in high-probability (HP) has been receiving increasing interest, due to its attractive properties, such as exponentially decaying tail bounds and strong guarantees for each individual run of an algorithm. While HP guarantees are extensively studied in centralized settings, much less is understood in the decentralized, networked setup. Existing HP studies in decentralized settings impose strong assumptions, like uniformly bounded gradients, or asymptotically vanishing noise, resulting in a significant gap between assumptions used to establish convergence in the HP and the mean-squared error (MSE) sense, even for vanilla Decentralized Stochastic Gradient Descent ($\mathtt{DSGD}$) algorithm. This is contrary to centralized settings, where it is known that $\mathtt{SGD}$ converges in HP under the same conditions on the cost function as needed to guarantee MSE convergence. Motivated by this observation, we revisit HP guarantees for $\mathtt{DSGD}$ in the presence of light-tailed noise. We show that $\mathtt{DSGD}$ converges in HP under the same conditions on the cost as in the MSE sense, removing uniformly bounded gradients and other restrictive assumptions, while simultaneously achieving order-optimal rates for both non-convex and strongly convex costs. Moreover, our improved analysis yields linear speed-up in the number of users, demonstrating that $\mathtt{DSGD}$ maintains strong performance in the HP sense and matches existing MSE guarantees. Our improved results stem from a careful analysis of the MGF of quantities of interest (norm-squared of gradient or optimality gap) and the MGF of the consensus gap between users' models. To achieve linear speed-up, we provide a novel result on the variance-reduction effect of decentralized methods in the HP sense and more fine-grained bounds on the MGF for strongly convex costs, which are both of independent interest.
• Abstract（参考訳）: 高確率(HP)の収束は、指数関数的に減衰する尾の境界やアルゴリズムの個々の実行に対する強い保証など、その魅力的な性質のために、ますます関心を集めている。 HPの保証は集中的な設定で広く研究されているが、分散化されたネットワーク設定では理解されていない。 分散化された環境における既存のHP研究は、一様有界勾配や漸近的に消えるノイズのような強い仮定を課し、その結果、HPの収束を確立するために使われる仮定と平均二乗誤差(MSE)の感覚の間には、バニラの分散確率勾配(英語版)(\mathtt{DSGD}$)アルゴリズムでさえ大きなギャップがある。 これは集中的な設定とは逆で、$\mathtt{SGD}$ が MSE 収束を保証するために必要なコスト関数の条件で HP に収束することが知られている。 この観測により、光尾ノイズの存在下でHPが保証する$\mathtt{DSGD}$を再検討した。 We show that $\mathtt{DSGD}$ converges in HP under the same conditions on the cost as the MSE sense, remove a uniformly bounded gradients and other limitive assumptions, while a simultaneously to order-timal rate for non-convex and strongly convex cost。 さらに,改良された解析により,ユーザ数の線形スピードアップが実現し,HP 感覚の強い性能を維持し,既存の MSE 保証と一致していることを示す。 改良された結果は、興味の量(勾配または最適性ギャップのノーム二乗)のMGFと、ユーザのモデル間のコンセンサスギャップのMGFを慎重に分析することに起因する。 線形速度アップを実現するために,HP の意味での分散化手法の分散還元効果と,MGF 上のよりきめ細かな境界を,双方の利害関係の強い凸コストで実現した。

関連論文リスト

• Differentially Private Clipped-SGD: High-Probability Convergence with Arbitrary Clipping Level [18.723330586196997]
  本研究では,DPのクリッピングレベルが固定された最初の高確率収束解析法を提案する。 提案手法は,固定クリッピングレベルにおいて,既存の方法よりも高速に近傍最適解に収束することを示す。 この地区は、DPが導入した騒音とバランスが取れており、収束速度とプライバシー保証のトレードオフが洗練されている。
  論文  参考訳（メタデータ） (2025-07-31T12:48:29Z)
• Theory of Decentralized Robust Kernel-Based Learning [8.407288892993703]
  我々は、カーネルヒルベルト空間を再現する枠組みの中で、新しい堅牢なカーネルベース学習アルゴリズムを提案する。 分散化アルゴリズムから生成された各局所ロバスト推定器を用いて回帰関数を近似することができることを示す。 局所的なサンプルサイズに対する厳密な選択ルールを提供し、適切に選択されたステップサイズとスケーリングパラメータ$sigma$では、分散化されたロバストアルゴリズムが最適な学習率を達成することができることを示す。
  論文  参考訳（メタデータ） (2025-06-05T16:30:05Z)
• Federated PCA and Estimation for Spiked Covariance Matrices: Optimal Rates and Efficient Algorithm [19.673557166734977]
  フェデレートラーニング(FL)は、プライバシとデータセキュリティの強化により、機械学習において、近年大きな注目を集めている。 本稿では,分散差分プライバシー制約下でのフェデレーションPCAとスパイク共分散行列の推定について検討する。 我々は、集中サーバの最適レートがローカルクライアントのミニマックスレートの調和平均であることから、収束のミニマックスレートを確立する。
  論文  参考訳（メタデータ） (2024-11-23T21:57:50Z)
• 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)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learning [52.83811558753284]
  分散学習(DFL)は、中央サーバーを捨て、分散通信ネットワークを確立する。 既存のDFL手法は依然として、局所的な矛盾と局所的な過度なオーバーフィッティングという2つの大きな課題に悩まされている。
  論文  参考訳（メタデータ） (2023-08-16T11:22:36Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
  経験値関数の新しい正規化器を導入し、ワッサーシュタイン分布のロバストな値関数を下限とすることを示す。 強化学習における$textitexternalな不確実性に対処するための実用的なツールとして正規化を使用することを提案する。
  論文  参考訳（メタデータ） (2020-03-05T19:56:23Z)

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

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