論文の概要: Row-stochastic matrices can provably outperform doubly stochastic matrices in decentralized learning

• arxiv url: http://arxiv.org/abs/2511.19513v1
• Date: Mon, 24 Nov 2025 02:58:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.059672
• Title: Row-stochastic matrices can provably outperform doubly stochastic matrices in decentralized learning
• Title（参考訳）: Row-stochastic matricesは、分散学習における二重確率行列を確実に上回る
• Authors: Bing Liu, Boao Kong, Limin Lu, Kun Yuan, Chengcheng Zhao,
• Abstract要約: 分散学習は、不均一ノード重みが$$の重み付きグローバル損失を伴うことが多い。 重み付きヒルベルト空間フレームワーク $L2(mathbbRd)$ を開発し、ユークリッド解析より厳密な収束率を得る。 そして、より小さなスペクトルギャップであっても、行確率的設計がより高速に収束する十分な条件を導出する。
• 参考スコア（独自算出の注目度）: 10.686669655748702
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized learning often involves a weighted global loss with heterogeneous node weights $λ$. We revisit two natural strategies for incorporating these weights: (i) embedding them into the local losses to retain a uniform weight (and thus a doubly stochastic matrix), and (ii) keeping the original losses while employing a $λ$-induced row-stochastic matrix. Although prior work shows that both strategies yield the same expected descent direction for the global loss, it remains unclear whether the Euclidean-space guarantees are tight and what fundamentally differentiates their behaviors. To clarify this, we develop a weighted Hilbert-space framework $L^2(λ;\mathbb{R}^d)$ and obtain convergence rates that are strictly tighter than those from Euclidean analysis. In this geometry, the row-stochastic matrix becomes self-adjoint whereas the doubly stochastic one does not, creating additional penalty terms that amplify consensus error, thereby slowing convergence. Consequently, the difference in convergence arises not only from spectral gaps but also from these penalty terms. We then derive sufficient conditions under which the row-stochastic design converges faster even with a smaller spectral gap. Finally, by using a Rayleigh-quotient and Loewner-order eigenvalue comparison, we further obtain topology conditions that guarantee this advantage and yield practical topology-design guidelines.
• Abstract（参考訳）: 分散学習は、不均一ノード重みが$λ$の重み付き大域的損失を伴うことが多い。 我々は、これらの重みを取り入れるための2つの自然な戦略を再考する。 (i)一様重量を保持するために局所的な損失に埋め込む(従って二重確率行列) (ii)$λ$で誘導される行確率行列を使用しながら、元の損失を維持する。 以前の研究は、どちらの戦略も、世界的損失に対して同じ予想される降下方向を導いていることを示しているが、ユークリッド空間の保証が厳密なのか、その振る舞いを根本的に区別するかは定かではない。 これを明らかにするために、重み付きヒルベルト空間フレームワーク $L^2(λ;\mathbb{R}^d)$ を開発し、ユークリッド解析より厳密な収束率を得る。 この幾何学において、行確率行列は自己随伴となるが、二重確率行列はそうでないので、コンセンサス誤差を増幅する追加のペナルティ項を生成し、収束を遅くする。 その結果、収束の差はスペクトルギャップだけでなく、これらのペナルティ項からも生じる。 そして、より小さなスペクトルギャップであっても、行確率的設計がより高速に収束する十分な条件を導出する。 最後に、Rayleigh-quotient と Loewner-order の固有値比較を用いて、この利点を保証し、実用的なトポロジー設計ガイドラインを得るトポロジー条件を得る。

関連論文リスト

• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。 収束解析の主な課題は、領域の非有界性に起因する。 制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
  論文  参考訳（メタデータ） (2025-05-05T12:33:18Z)
• Implicit Bias and Fast Convergence Rates for Self-attention [26.766649949420746]
  本稿では,変圧器の定義機構である自己注意の基本的な最適化原理について考察する。 線形分類におけるデコーダを用いた自己アテンション層における勾配ベースの暗黙バイアスを解析する。
  論文  参考訳（メタデータ） (2024-02-08T15:15:09Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  ガウス空間の任意のクラスの線型予測器を示す新しい一般化境界を証明した。 私たちは、Zhou et al. (2021) の「最適化率」を直接回復するために、有限サンプルバウンドを使用します。 ローカライズされたガウス幅を用いた有界一般化の適用は、一般に経験的リスク最小化に対してシャープであることを示す。
  論文  参考訳（メタデータ） (2022-10-21T16:16:55Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance [14.06947898164194]
  ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。 SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。 その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
  論文  参考訳（メタデータ） (2021-02-20T13:45:11Z)

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

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