論文の概要: SpatialPC: Deep Computation with Sublinear Local Credit Propagation
- arxiv url: http://arxiv.org/abs/2610.36139v1
- Date: Mon, 26 Oct 2026 18:47:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-29 04:15:49.192787
- Title: SpatialPC: Deep Computation with Sublinear Local Credit Propagation
- Title（参考訳）: SpacePC: サブリニア・ローカル・クレジット・プロパゲーションによるディープ・コンピューティング
- Abstract要約: N$状態の連鎖において、境界通信範囲を持つ任意の局所学習規則は、損失が最初期のパラメータに影響を与える前に$(N)$ラウンドを必要とする。
深度というよりは通信幾何学の特質であることを示す。
N=md$ 状態が$d$次元の一定の密度に置かれる場合、光錐の議論は、有界なラウンドの数で$(N1/d)$下界を与える。
- 参考スコア（独自算出の注目度）: 3.3339672829516687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: On a chain of $N$ states, any local learning rule with bounded communication range needs $Θ(N)$ rounds before the loss can influence the earliest parameters, and this latency is usually attributed to depth. We show that it is a property of the communication geometry rather than of depth. For $N=m^d$ states placed at constant density in $d$ dimensions, a light-cone argument gives an $Ω(N^{1/d})$ lower bound on the number of bounded-range rounds that any local algorithm needs before its gradient estimates can be sign-correct at every parameter. We construct a unit-range, degree-$2d$ directed acyclic graph that contains a Hamiltonian computation of length $N-1$ and in which every state lies within directed distance $d(m-1)=Θ(N^{1/d})$ of the output, matching the lower bound. In the realizable-circuit model, depth and credit depth are therefore independent parameters: represented depth $Θ(N)$ and causal credit latency $Θ(N^{1/d})$ coexist, with a separation of order $N^{1-1/d}$. SpatialPC realizes this separation within predictive coding. Credit is propagated by adjoint prediction dynamics (APD), a local update whose $K$-round state on a settled acyclic graph is the truncated reverse-path sum $a^K=\sum_{k<K}(J^\top)^k b$, with error exactly $(J^\top)^K a^\star$. Graph geometry fixes when credit can first arrive at a state; the Jacobian-weighted path tail fixes how many further rounds accurate credit requires. A sparse two-dimensional Moore compiler retains the $N-1$ backbone with $\tfrac32N-2$ unit-range edges and has measured worst-node reachability $\sqrt N+2$ up to $N=65{,}536$, where a 65,535-edge backbone is reached in 258 local hops. With $T=2\sqrt N$ rounds, SpatialPC keeps finite-round task gradients aligned with settled gradients (cosine $0.93$ on MNIST and $0.97$ on Fashion-MNIST at $N=256$) and reaches $97.6\%$ and $88.1\%$ test accuracy after 20 epochs.
- Abstract（参考訳）: N$状態の連鎖では、損失が最初期のパラメータに影響を及ぼす前に、有界な通信範囲を持つ任意の局所学習規則は、$(N)$ラウンドを必要とする。
深度というよりは通信幾何学の特質であることを示す。
N=m^d$ 状態が$d$次元の一定の密度に置かれる場合、光錐論法は、任意の局所アルゴリズムがその勾配推定の前に必要とする有界範囲のラウンドの数に$Ω(N^{1/d})$下界を与える。
我々は、長さ$N-1$のハミルトニアン計算を含む単位範囲の次数$2d$非巡回グラフを構築し、全ての状態が出力の有向距離$d(m-1)=(N^{1/d})$の範囲内にあり、下界と一致する。
既約回路モデルでは、深さとクレジット深度は独立なパラメータである: 表される深さは$(N)$と因果信用遅延は$(N^{1/d})$共存し、オーダーは$N^{1-1/d}$である。
SpacePCはこの分離を予測符号化内で実現している。
固定された非巡回グラフ上の$K$ラウンド状態が、正確には$(J^\top)^K a^\star$である逆パス和$a^K=\sum_{k<K}(J^\top)^k b$であるような局所的な更新である。
ジャコビアン重み付きパステールは、正確なクレジットに必要なラウンド数を修正する。
スパースな2次元ムーアコンパイラは、$N-1$のバックボーンを$\tfrac32N-2$のユニットレンジエッジに保持し、最悪のノード到達可能性$\sqrt N+2$から$N=65{,}536$まで測定した。
T=2\sqrt N$ラウンドでは、SpatialPCは有限ラウンドのタスク勾配をMNIST上の0.93ドル、Fashion-MNIST上の0.97ドル(N=256ドル)に整合させ、20時間後に9.7.6\%、テスト精度8.1\%に到達させる。
関連論文リスト
- Instance-Adaptive Online Multiclass Multicalibration [11.377412007104363]
我々は、T$ラウンド以上のオンラインマルチクラス多重校正について研究し、余計な保証付きアルゴリズムを提供する。
逆選択された結果の列が次元$s$のアフィン部分空間にある場合、高い確率でエラー$widetilde O(n1/(s+2)T(s+1)/(s+2))$を得る。
論文 参考訳（メタデータ） (2026-10-11T22:21:57Z) - Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization [55.29259818039367]
支持領域がより均一な選択を許すにつれて、認証された近似係数がどのように改善されるかを示す。
明示的なパラメータの選択は、非遅延認証プロファイルに$underline_k()$を与える。
値保持丸めは、これらの保証をマトロイドとクナプサックの制約に転送する。
論文 参考訳（メタデータ） (2026-10-02T20:52:38Z) - Approximation Property of Dropout Neural Networks: Sobolev Rates and Confidence Bounds [1.0152838128195467]
定数深さとサイズ$widetilde O_n,d(p-9varepsilon-maxd/n,2 log (1/)$。
この構成は、有界な局所ワーク、成功した近似事象の局所化、およびマルチスケールのテイラー分解を組み合わせたものである。
論文 参考訳（メタデータ） (2026-09-30T19:19:07Z) - Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。
学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。
定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文 参考訳（メタデータ） (2026-09-30T18:26:29Z) - Bias-Induced Crossover in Absolute Capacity of Dense Associative Memory [0.0]
漸近マッチングは1-2q=O(N/Nl n/2rfloor-1)$でバイアスによって引き起こされる交叉を予測する。
条件付きクロストークをキャンセルするアクティビティ依存制御電位は、固定された$0q1/2$に対して$Nn-1/ln N$キャパシティを復元する。
論文 参考訳（メタデータ） (2026-09-15T17:16:38Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy [0.0]
グラフニューラルネットワークがスパースグラフにどの程度の深さを持つ必要があるかを研究する。
深さの値は、Kesten-Stigum比$=2$である。
任意の深さの局所分類器は、孤立根によって設定された普遍床 $e-(-)$ を破ることはない。
論文 参考訳（メタデータ） (2026-07-18T07:11:45Z) - Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。
We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。
また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
論文 参考訳（メタデータ） (2025-03-26T03:36:36Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。