論文の概要: Decentralized Optimization with Topology-Independent Communication

• arxiv url: http://arxiv.org/abs/2509.14488v1
• Date: Wed, 17 Sep 2025 23:42:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:53.004541
• Title: Decentralized Optimization with Topology-Independent Communication
• Title（参考訳）: トポロジ非依存通信を用いた分散最適化
• Authors: Ying Lin, Yao Kuang, Ahmet Alacaoglu, Michael P. Friedlander,
• Abstract要約: 分散最適化にはノードの調整が必要ですが、完全な同期スケールは不十分です。 本稿では,各ノードが一意に1つの正規化器をサンプリングし,その項を共有するノードのみを協調するランダム化局所調整を提案する。 実験は、合成データセットと実世界のデータセット間の収束率と通信効率の両方を検証する。
• 参考スコア（独自算出の注目度）: 9.348335671378424
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed optimization requires nodes to coordinate, yet full synchronization scales poorly. When $n$ nodes collaborate through $m$ pairwise regularizers, standard methods demand $\mathcal{O}(m)$ communications per iteration. This paper proposes randomized local coordination: each node independently samples one regularizer uniformly and coordinates only with nodes sharing that term. This exploits partial separability, where each regularizer $G_j$ depends on a subset $S_j \subseteq \{1,\ldots,n\}$ of nodes. For graph-guided regularizers where $|S_j|=2$, expected communication drops to exactly 2 messages per iteration. This method achieves $\tilde{\mathcal{O}}(\varepsilon^{-2})$ iterations for convex objectives and under strong convexity, $\mathcal{O}(\varepsilon^{-1})$ to an $\varepsilon$-solution and $\mathcal{O}(\log(1/\varepsilon))$ to a neighborhood. Replacing the proximal map of the sum $\sum_j G_j$ with the proximal map of a single randomly selected regularizer $G_j$ preserves convergence while eliminating global coordination. Experiments validate both convergence rates and communication efficiency across synthetic and real-world datasets.
• Abstract（参考訳）: 分散最適化にはノードの調整が必要ですが、完全な同期スケールは不十分です。 n$ノードが$m$ペアワイズ正規化子を介して協調する場合、標準メソッドはイテレーション毎に$\mathcal{O}(m)$通信を要求する。 本稿では,各ノードが一意に1つの正規化器をサンプリングし,その項を共有するノードのみを座標とするランダム化局所調整を提案する。 これは部分分離性を利用し、各正規化子$G_j$はノードのサブセット$S_j \subseteq \{1,\ldots,n\}$に依存する。 グラフ誘導正規化器の場合、$|S_j|=2$の通信は、イテレーション毎に正確に2つのメッセージに減少する。 この方法は、凸目的および強い凸の下での反復を$\tilde{\mathcal{O}}(\varepsilon^{-2})$で、$\mathcal{O}(\varepsilon^{-1})$で$\varepsilon$-solutionと$\mathcal{O}(\log(1/\varepsilon))$で実現する。 和 $\sum_j G_j$ の近位写像を 1 つのランダムに選択された正則化子 $G_j$ の近位写像に置き換えると、大域的調整を排除しながら収束が保たれる。 実験は、合成データセットと実世界のデータセット間の収束率と通信効率の両方を検証する。

関連論文リスト

• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• 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)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Supervised Training of Conditional Monge Maps [107.78770597815242]
  最適輸送(OT)理論は、多くの可能な選択の中から確率測度を他のものにマッピングする最も効率的な方法を定義し、選択する一般的な原理を記述している。 本研究では,コンテキスト変数に条件付きOTマップの族を推定するマルチタスク手法であるCondOTを紹介する。 本研究では,CondOTの遺伝的・治療的摂動の任意の組み合わせが単一細胞に与える影響を推測する能力を示す。
  論文  参考訳（メタデータ） (2022-06-28T19:34:44Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)

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

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