論文の概要: Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction

• arxiv url: http://arxiv.org/abs/2506.23836v1
• Date: Mon, 30 Jun 2025 13:27:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-01 21:27:54.075454
• Title: Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction
• Title（参考訳）: 新しい下界構成による集中分散最適化の限界スケーラビリティの証明
• Authors: Alexander Tyurin,
• Abstract要約: 我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
• 参考スコア（独自算出の注目度）: 57.93371273485736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider centralized distributed optimization in the classical federated learning setup, where $n$ workers jointly find an $\varepsilon$-stationary point of an $L$-smooth, $d$-dimensional nonconvex function $f$, having access only to unbiased stochastic gradients with variance $\sigma^2$. Each worker requires at most $h$ seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are $\tau_{s}$ and $\tau_{w}$ seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to $n$. For instance, it is well known that the distributed version of SGD has a variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{n \varepsilon^2},$ which improves with the number of workers $n,$ where $\Delta = f(x^0) - f^*,$ and $x^0 \in R^d$ is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce both the variance-dependent runtime term and the communication runtime term. However, once we account for the communication from the server to the workers $\tau_{s}$, we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term $\tau_{s} d \frac{L \Delta}{\varepsilon}$ and the variance-dependent runtime term $\frac{h \sigma^2 L \Delta}{\varepsilon^2},$ better than poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution. To establish this result, we construct a new "worst-case" function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous assumption.
• Abstract（参考訳）: 古典的なフェデレーション学習では、$n$Workersが$\varepsilon$-stationary point of a $L$-smooth, $d$-dimensional nonconvex function $f$を共同で見つける。 各ワーカーは確率勾配を計算するのに最低で$h$秒を必要とし、サーバからワーカーへの通信時間は、それぞれ$\tau_{s}$と$\tau_{w}$秒である。 分散最適化の主な動機の1つは、$n$に関してスケーラビリティを達成することである。 例えば、分散バージョン SGD の分散ランタイム項 $\frac{h \sigma^2 L \Delta}{n \varepsilon^2},$ は労働者数$n,$ で改善され、$\Delta = f(x^0) - f^*,$ と $x^0 \in R^d$ が始点であることが知られている。 同様に、バイアスのないスパーシフィケーション圧縮機を使用することで、分散依存ランタイム項と通信ランタイム項の両方を削減することができる。 しかし、サーバからワーカーへの通信を$\tau_{s}$とすると、サーバ側通信ランタイムの$\tau_{s} d \frac{L \Delta}{\varepsilon}$と分散依存ランタイムの$\frac{h \sigma^2 L \Delta}{\varepsilon^2}の両方をスケールする非バイアスランダムなスペーシ圧縮器を使った手法を設計することは不可能になる。 この結果を確立するために、我々は新しい"Worst-case"関数を構築し、ランダム和の濃度に解析を還元する新しい下界フレームワークを開発し、そこで集中束を証明した。 これらの結果は、均質な仮定の下でも、分散最適化のスケーリングにおける基本的な制限を明らかにしている。

関連論文リスト

• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
  DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。 我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-07-26T08:47:54Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)

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

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