論文の概要: What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness

• arxiv url: http://arxiv.org/abs/2507.00195v1
• Date: Mon, 30 Jun 2025 19:06:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-03 14:22:58.647612
• Title: What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness
• Title（参考訳）: ローカルアップデートの有効性 - データ不均一性と平滑性の役割
• Authors: Kumar Kshitij Patel,
• Abstract要約: この論文は、異種環境における局所SGDの分析のための自己完結型ガイドに寄与する。 この論文はオンライン学習にも拡張され、ファーストオーダーとバンディットの両方のフィードバックの下で基本的な境界を提供する。
• 参考スコア（独自算出の注目度）: 5.357435119431715
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This thesis contributes to the theoretical understanding of local update algorithms, especially Local SGD, in distributed and federated optimization under realistic models of data heterogeneity. A central focus is on the bounded second-order heterogeneity assumption, which is shown to be both necessary and sufficient for local updates to outperform centralized or mini-batch methods in convex and non-convex settings. The thesis establishes tight upper and lower bounds in several regimes for various local update algorithms and characterizes the min-max complexity of multiple problem classes. At its core is a fine-grained consensus-error-based analysis framework that yields sharper finite-time convergence bounds under third-order smoothness and relaxed heterogeneity assumptions. The thesis also extends to online federated learning, providing fundamental regret bounds under both first-order and bandit feedback. Together, these results clarify when and why local updates offer provable advantages, and the thesis serves as a self-contained guide for analyzing Local SGD in heterogeneous environments.
• Abstract（参考訳）: この論文は局所更新アルゴリズム、特にローカルSGDの理論的理解に寄与し、実際のデータ不均一性のモデルの下での分散最適化とフェデレーション最適化に寄与する。 中心となるのは有界二階不均一性仮定(bounded two-order heterogeneity assumption)であり、凸や非凸の設定において、局所的な更新が集中的あるいはミニバッチメソッドよりも優れていることが示される。 この論文は、様々なローカル更新アルゴリズムのためのいくつかのレギュレーションにおいて、厳しい上と下の境界を確立し、複数の問題クラスのmin-max複雑性を特徴づける。 中心となるのは、よりシャープな有限時間収束境界を3次の滑らかさと緩和された不均一性仮定の下で生成する、微細なコンセンサス・エラーに基づく分析フレームワークである。 この論文はオンライン・フェデレーション・ラーニングにも拡張され、一階と盗賊の両方のフィードバックの下で根本的な後悔の種となる。 これらの結果から, 局所的なSGD分析のための自己完結型ガイドとして, 局所的な更新が有効である理由が明らかとなった。

関連論文リスト

• Convergence of Distributed Adaptive Optimization with Local Updates [3.895864050325129]
  局所的な更新(間欠的通信)による分散適応アルゴリズムの研究 初めて、Em Local SGD em with momentum (em Local em SGDM) と em Local em Adam が、convex と弱凸設定でミニバッチよりも優れていることを証明した。
  論文  参考訳（メタデータ） (2024-09-20T01:45:10Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Federated Minimax Optimization: Improved Convergence Analyses and Algorithms [32.062312674333775]
  我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。 我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-09T16:21:31Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。 我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。 理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
  論文  参考訳（メタデータ） (2021-06-15T17:45:51Z)
• Learning Invariant Representations and Risks for Semi-supervised Domain Adaptation [109.73983088432364]
  半教師付きドメイン適応(Semi-DA)の設定の下で不変表現とリスクを同時に学習することを目的とした最初の手法を提案する。 共同で textbfLearning textbfInvariant textbfRepresentations と textbfRisks の LIRR アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2020-10-09T15:42:35Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  分散通信方式の統一収束解析を導入する。 いくつかの応用に対して普遍収束率を導出する。 私たちの証明は弱い仮定に依存している。
  論文  参考訳（メタデータ） (2020-03-23T17:49:15Z)

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

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