論文の概要: On the Limits of Stochastic Push-Pull over Time-Varying Digraphs

• arxiv url: http://arxiv.org/abs/2610.32422v1
• Date: Fri, 23 Oct 2026 09:50:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.485808
• Title: On the Limits of Stochastic Push-Pull over Time-Varying Digraphs
• Title（参考訳）: 時間変化ダイグラフ上の確率的プッシュパルスの極限について
• Abstract要約: 二次的なPush-Pullは、静的に連結されたダイグラフ上のネットワークサイズ$n$に対して線形スピードアップを達成する。 本稿では,Push-Pullが時間変化ダイグラフ上で線形スピードアップを達成できないことを示す。
• 参考スコア（独自算出の注目度）: 9.639131147505173
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic Push-Pull achieves linear speedup with respect to the network size $n$ on static strongly connected digraphs, but whether this speedup persists on time-varying networks remains unclear. In this work, we construct a quadratic decentralized problem on period-two networks showing that stochastic Push-Pull may fail to attain linear speedup over time-varying digraphs. For $p$-periodic networks, we identify an effective node count $n_{\mathrm{eff}}\le n$ that governs the leading stochastic term. Specifically, for smooth nonconvex objectives, we establish convergence upper bounds and matching lower bounds for stochastic Push-Pull with constant stepsizes, both exhibiting the leading-order dependence $Θ(1/\sqrt{n_{\mathrm{eff}} T})$. When $p=1$, the identity $n_{\mathrm{eff}}=n$ recovers the usual linear speedup for static digraphs. However, periodic networks can have $n_{\mathrm{eff}}=o(n)$, demonstrating the loss of linear speedup under temporal variation. Numerical experiments illustrate effective-count scaling and the separation between static and periodic networks, consistent with our theoretical findings.
• Abstract（参考訳）: Stochastic Push-Pullは、静的な強結合ダイグラフ上でのネットワークサイズ$n$の線形スピードアップを実現するが、このスピードアップが時間変化のネットワーク上で持続するかどうかは不明である。 本研究では、周期2ネットワーク上の二次分散問題を構築し、確率的なPush-Pullが時間変化ダイグラフ上で線形スピードアップを達成できないことを示す。 p$-周期ネットワークに対して、主確率項を支配している実効ノード数 $n_{\mathrm{eff}}\le n$ を同定する。 具体的には、滑らかな非凸対象に対して、収束上界と、確率的プッシュプルに対する下界を定常的な段数で整合させ、それぞれが先行階依存(英語版)$ 1/\sqrt{n_{\mathrm{eff}} T}) を示す。 p=1$のとき、$n_{\mathrm{eff}}=n$は静的グラフの通常の線形スピードアップを回復する。 しかし、周期的ネットワークは$n_{\mathrm{eff}}=o(n)$を持つことができ、時間的変動の下での線形スピードアップの損失を示す。 数値実験では, 静的ネットワークと周期ネットワークの分離と有効カウントスケーリングを理論的に検証した。

関連論文リスト

• A Queueing-Stability Criterion for Causal IPD-QIM Network Flow Watermarking [9.96318277344866]
  因果性(Causality)は、埋め込み装置が遅延パケットを遅延させるが前進しないので、各量子化-インデックス-変調アライメントは非負のドウェルを遅延バッファに注入する。 我々は、固定された双格子、等確率ビット規則の下で、埋め込みを反射ダウエルキューとしてモデル化する。 因果QIMネットワーク・フロー・ウォーターマーキングのための検証可能な安定な組込み性基準と量子化ステップ構成ベースラインを提供する。
  論文  参考訳（メタデータ） (2026-07-16T13:04:21Z)
• Scalable Training of Continuous-Time Spiking Neural Networks with Differentiable Spike-Time Discretization [1.489944824637277]
  連続時間スパイクニューラルネットワーク(SNN)のためのメモリ効率のトレーニングフレームワークを提案する。 微分可能なスパイク時間離散化は、不規則なシナプス前スパイクを一定時間点における微分可能な重み付き事象にマッピングする。 密度の高いLIF層では、DSTDはスパイク時間計算と比較してピークメモリの消費を最大100倍に減らし、トレーニング時間を最大20倍に減らした。
  論文  参考訳（メタデータ） (2026-07-16T07:38:24Z)
• Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling [55.388363730120325]
  本研究では,CTMC(Continuous-Time Markov Chain)フレームワークにおいて,離散拡散を吸収するための$-leapingアルゴリズムを並列化する。 我々は,$$-leapingアルゴリズムとPicard法の連続時間積分形式を利用して,並列時間サンプリング高速化を実現する。 本研究は, 分子構造や言語生成などの応用において, 効率的な並列推論のための離散拡散モデルの可能性を広げるものである。
  論文  参考訳（メタデータ） (2026-07-01T10:59:33Z)
• Generating pairwise entanglement in periodically driven quantum spin chains with stochastic resetting [0.0]
  安定状態の対の絡み合わさった臨界リセットレート $r_c$ の存在は、コンカレンス $C$ によって測定され、消滅する。 また、$C$が最大となる最適リセット率$r_m$も同定する。
  論文  参考訳（メタデータ） (2026-04-21T11:05:06Z)
• Time Is All It Takes: Spike-Retiming Attacks on Event-Driven Spiking Neural Networks [87.16809558673403]
  スパイキングニューラルネットワーク(SNN)は離散スパイクで計算し、時間構造を利用する。 イベント駆動SNNにおけるスパイク数と振幅を保存しながら、既存のスパイクを繰り返すタイミングのみの敵について検討する。
  論文  参考訳（メタデータ） (2026-02-03T09:06:53Z)
• Efficient Parallel Training Methods for Spiking Neural Networks with Constant Time Complexity [63.56009745101597]
  スパイキングニューラルネットワーク (SNN) はしばしば、$T$スパイクのシーケンシャル処理のために、高い時間複雑性の$O(T)$に悩まされる。 本稿では,ネットワークアーキテクチャを変更することなく,SNNトレーニングを高速化するFPT法を提案する。
  論文  参考訳（メタデータ） (2025-06-10T13:27:27Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。 ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
  論文  参考訳（メタデータ） (2020-03-01T08:12:08Z)

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

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