論文の概要: Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking

• arxiv url: http://arxiv.org/abs/2509.18129v1
• Date: Thu, 11 Sep 2025 21:47:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-28 15:30:14.394477
• Title: Pareto-optimal Tradeoffs Between Communication and Computation with Flexible Gradient Tracking
• Title（参考訳）: フレキシブル・グラディエント・トラッキングを用いた通信と計算のパレ-最適トレードオフ
• Authors: Yan Huang, Jinming Xu, Li Chai, Jiming Chen, Karl H. Johansson,
• Abstract要約: 本稿では,非rho-convexi.d.シナリオにおける分散最適化問題に対処する。 そこで我々はFlexFlexGTを提案する。FlexFlexGTはフレキシブルなスナップショット追跡手法で、各イテレーションのローカル更新回数を計測する。 我々は,Acc-GTと呼ばれる高速化されたゴシップベースの変種を導入し,通信と計算の間の調整可能な最適トレードオフを実現することを示す。
• 参考スコア（独自算出の注目度）: 20.36100343422038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses distributed optimization problems in non-i.i.d. scenarios, focusing on the interplay between communication and computation efficiency. To this end, we propose FlexGT, a flexible snapshot gradient tracking method with tunable numbers of local updates and neighboring communications in each round. Leveraging a unified convergence analysis framework, we prove that FlexGT achieves a linear or sublinear convergence rate depending on objective-specific properties--from (strongly) convex to nonconvex--and the above-mentioned tunable parameters. FlexGT is provably robust to the heterogeneity across nodes and attains the best-known communication and computation complexity among existing results. Moreover, we introduce an accelerated gossip-based variant, termed Acc-FlexGT, and show that with prior knowledge of the graph, it achieves a Pareto-optimal trade-off between communication and computation. Particularly, Acc-FlexGT achieves the optimal iteration complexity of $\tilde{\mathcal{O}} \left( L/\epsilon +L\sigma ^2/\left( n\epsilon^2 \sqrt{1-\sqrt{\rho _W}} \right) \right) $ for the nonconvex case, matching the existing lower bound up to a logarithmic factor, and improves the existing results for the strongly convex case by a factor of $\tilde{\mathcal{O}} \left( 1/\sqrt{\epsilon} \right)$, where $\epsilon$ is the targeted accuracy, $n$ the number of nodes, $L$ the Lipschitz constant, $\rho_W$ the spectrum gap of the graph, and $\sigma$ the stochastic gradient variance. Numerical examples are provided to demonstrate the effectiveness of the proposed methods.
• Abstract（参考訳）: 本稿では,コミュニケーションと計算効率の相互作用に着目し,分散最適化の問題に対処する。 そこで本研究では,各ラウンドにおける局所的な更新数と近接通信数を調整可能なフレキシブルなスナップショット勾配追跡手法であるFlexGTを提案する。 統合収束解析フレームワークを活用することで、FlexGTは、(強く)凸から非凸へ、および上記のチューナブルパラメータから、客観的な特性に応じて線形あるいはサブ線形収束率を達成することを証明した。 FlexGTはノード間の不均一性に対して確実に堅牢であり、既存の結果の中で最もよく知られた通信と計算の複雑さを達成する。 さらに、Acc-FlexGTと呼ばれる高速化されたゴシップベースの変種を導入し、グラフの事前知識により、通信と計算の間のパレート最適トレードオフを実現することを示す。 特に、Acc-FlexGTは、非凸ケースに対して$\tilde{\mathcal{O}} \left(L/\epsilon +L\sigma ^2/\left(n\epsilon^2 \sqrt{1-\sqrt{\rho _W}} \right)$の最適反復複雑性を達成し、既存の下限を対数係数に一致させ、強い凸ケースに対する既存の結果を$\tilde{\mathcal{O}} \left(1/\sqrt{\epsilon} \right)$の係数で改善する。 提案手法の有効性を示す数値的な例を示す。

関連論文リスト

• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。 非滑らかな正規化はしばしば機械学習タスクに組み込まれる。 本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-17T08:32:25Z)
• Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time [3.1789549088190414]
  本研究では, ピアツーピア通信によるローカルコスト関数の和を協調的に共有する分散学習問題について検討する。 本稿では、一般的な通信グラフから抽出した2本の木を用いて、モデルパラメータと位相パラメータの両方を分散する新しいEmph Tree PushPull-(STPP)を提案する。
  論文  参考訳（メタデータ） (2025-03-20T13:11:44Z)
• Byzantine-resilient Federated Learning Employing Normalized Gradients on Non-IID Datasets [23.640506243685863]
  実践的連合学習(FLNGA)では、悪意のある攻撃やデータ不均一性の存在が学習プロセスにバイアスをもたらすことが多い。 本稿では、アップロードされた局所勾配をアグリゲーションの前に正規化する正規化勾配単位(Fed-M)モデルを提案し、$mathcalO(pM)$を達成した。
  論文  参考訳（メタデータ） (2024-08-18T16:50:39Z)
• Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach [32.36073823372713]
  機械学習モデルでは、アルゴリズムはその勾配のためにデータセンターとサンプルデータに通信する必要がある。 これにより、通信効率が良く、勾配計算の数を最小限に抑える分散最適化アルゴリズムの必要性が生じる。 通信効率が高く,$varepsilon$-approximate のソリューションを実現する。
  論文  参考訳（メタデータ） (2024-04-03T06:55:59Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Improving the Transient Times for Distributed Stochastic Gradient Methods [5.215491794707911]
  拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。 EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。 我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
  論文  参考訳（メタデータ） (2021-05-11T08:09:31Z)

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

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