論文の概要: Near-Optimal Decentralized Stochastic Convex Optimization over Networks

• arxiv url: http://arxiv.org/abs/2606.04757v1
• Date: Wed, 03 Jun 2026 11:42:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.71253
• Title: Near-Optimal Decentralized Stochastic Convex Optimization over Networks
• Title（参考訳）: ネットワーク上のほぼ最適分散確率凸最適化
• Authors: Nitai Kluger, Amit Attia, Tomer Koren,
• Abstract要約: 我々は分散スムーズな凸最適化について研究し、そこでは労働者が固定ゴシップネットワーク上で通信する。 我々は、このレートを最大$smashMlesssim sqrt,N3/4$ワーカーに保存する、高速化された分散化手法を導入する。 線形スパン分散一階法に一致する下界を定め, 対数係数に最適であることを示す。
• 参考スコア（独自算出の注目度）: 25.69933113941911
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study decentralized stochastic smooth convex optimization, where $M$ workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of $N$ gradient samples while still preserving the centralized $O(1/\sqrt N)$ statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to $\smash{M\lesssim \sqrtρ\,N^{3/4}}$ workers, where $ρ$ is the spectral gap of the gossip network, improving the best prior maximal scaling of $\smash{M\lesssim ρ\sqrt N}$. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.
• Abstract（参考訳）: 固定ゴシップネットワーク上での局所確率勾配と近接通信を用いて,M$Workerが平均目標を最小化する分散確率的滑らかな凸最適化について検討した。 この設定の中心的な問題は、中央集権的な$O(1/\sqrt N)$統計率を維持しながら、合計で$N$の勾配サンプルで使用できる最大の労働者数を決定することである。 我々は、この速度を最大$\smash{M\lesssim \sqrtρ\,N^{3/4}}$ワーカーで保ち、$ρ$はゴシップネットワークのスペクトルギャップであり、$\smash{M\lesssim ρ\sqrt N}$の最適な事前スケーリングを改善する。 この手法は,残差不一致を制御しながら,作業者が加速ゴシップによる最小バッチをインターリーブできる1ステップ遅れ確率加速度方式に基づいており,その保証は局所的局所的不均一性にのみ対数的に依存する。 また,線形スパン分散一階法において,この手法が対数係数に最適であることを示すために,一致した下界を定式化する。

関連論文リスト

• High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking [69.90407799170687]
  分散最適化における高確率収束保証について検討する。 その結果, 地平線上の条件は, 比較時間と同一であることがわかった。
  論文  参考訳（メタデータ） (2026-04-30T22:45:21Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
  分散環境下での非平滑な非平滑な目的に対する(delta,,ilon$)-定常点の有限時間解析について検討する。 $Oは分散非滑らかな最適化のための最初の有限時間保証である。
  論文  参考訳（メタデータ） (2024-06-03T16:09:34Z)
• PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds [9.47030623916154]
  そこで本研究では,分散化による勾配プッシュを応用し,各ノードのプライバシを保証する,差分プライベートな分散学習手法(PrivSGPVR)を提案する。 この理論解析により, DP雑音下では, PrivGPS-VR は$mathcalO (1/sqrtnK)$のサブ線形収束速度を達成できることがわかった。
  論文  参考訳（メタデータ） (2024-05-04T11:22:53Z)
• Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomness [9.731329071569018]
  我々はN$エージェントが未知の報酬関数を協調的に最大化する分散カーネルの帯域を考える。 我々は,通信コストが$N$と$T$に比例する,最適な後悔順序を達成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-20T17:49:10Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)

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

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