論文の概要: Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits
- arxiv url: http://arxiv.org/abs/2602.03970v1
- Date: Tue, 03 Feb 2026 19:39:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-05 19:45:11.251456
- Title: Statistical Guarantees for Reasoning Probes on Looped Boolean Circuits
- Title（参考訳）: ループ型ブール回路における共振プローブの統計的保証
- Authors: Anastasis Kratsios, Giulia Livieri, A. Martina Neuman,
- Abstract要約: ループ型推論モデルにおける推論プローブの統計的挙動について検討した。
推論プローブは、おそらくグラフ全体をカバーすることなく、内部ノードのサンプリングされたサブセットにアクセスする。
グラフ畳み込みネットワーク(GCN)ベースの仮説クラスによって推論プローブがパラメータ化され、$N$ノードを問うと、最悪の一般化誤差が最適値に達することを示す。
- 参考スコア（独自算出の注目度）: 10.292476979020522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the statistical behaviour of reasoning probes in a stylized model of looped reasoning, given by Boolean circuits whose computational graph is a perfect $ν$-ary tree ($ν\ge 2$) and whose output is appended to the input and fed back iteratively for subsequent computation rounds. A reasoning probe has access to a sampled subset of internal computation nodes, possibly without covering the entire graph, and seeks to infer which $ν$-ary Boolean gate is executed at each queried node, representing uncertainty via a probability distribution over a fixed collection of $\mathtt{m}$ admissible $ν$-ary gates. This partial observability induces a generalization problem, which we analyze in a realizable, transductive setting. We show that, when the reasoning probe is parameterized by a graph convolutional network (GCN)-based hypothesis class and queries $N$ nodes, the worst-case generalization error attains the optimal rate $\mathcal{O}(\sqrt{\log(2/δ)}/\sqrt{N})$ with probability at least $1-δ$, for $δ\in (0,1)$. Our analysis combines snowflake metric embedding techniques with tools from statistical optimal transport. A key insight is that this optimal rate is achievable independently of graph size, owing to the existence of a low-distortion one-dimensional snowflake embedding of the induced graph metric. As a consequence, our results provide a sharp characterization of how structural properties of the computational graph govern the statistical efficiency of reasoning under partial access.
- Abstract（参考訳）: 計算グラフが完全$ν$-ary tree(ν\ge 2$)であり、出力が入力に付加され、その後の計算ラウンドに反復的にフィードバックされるBoolean回路によって与えられるループ推論のスタイリングモデルにおける推論プローブの統計的挙動について検討する。
推論プローブは、おそらくグラフ全体をカバーせずに、内部計算ノードのサンプリングされた部分集合にアクセスでき、各クエリノードで、$ν$-ary Boolean ゲートが実行されるかを推測し、$\mathtt{m}$許容$ν$-ary ゲートの固定コレクション上の確率分布を介して不確実性を表す。
この部分可観測性は一般化問題を誘導し、それが実現可能でトランスダクティブな設定で解析する。
推論プローブがグラフ畳み込みネットワーク(GCN)ベースの仮説クラスでパラメータ化され、$N$ノードを問うと、最悪の一般化誤差は、$δ\in (0,1)$に対して少なくとも1-δ$の確率で$\mathcal{O}(\sqrt{\log(2/δ)}/\sqrt{N})$に達する。
本分析では, 積雪量計の埋込み技術と, 統計学的最適輸送のツールを組み合わせる。
重要な洞察は、この最適速度は、誘導グラフ計量の低歪み1次元雪片埋め込みの存在により、グラフサイズとは独立に達成可能であることである。
その結果,計算グラフの構造的特性が,部分的アクセス下での推論の統計的効率をどのように制御するかを,より鮮明に評価した。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。
このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。
次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳（メタデータ） (2020-08-23T19:19:45Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。