論文の概要: Fast Decoding for Non-Adaptive Learning of Erdős--Rényi Random Graphs

• arxiv url: http://arxiv.org/abs/2511.17240v1
• Date: Fri, 21 Nov 2025 13:34:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-24 18:08:19.04277
• Title: Fast Decoding for Non-Adaptive Learning of Erdős--Rényi Random Graphs
• Title（参考訳）: Erdés-Rényiランダムグラフの非適応学習のための高速復号法
• Authors: Hoang Ta, Jonathan Scarlett,
• Abstract要約: ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討する。 一般に、 (n) ノードと (k) エッジを持つ任意のグラフを学ぶことは、非適応的な設定では難しい。
• 参考スコア（独自算出の注目度）: 33.51066694357509
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with \(n\) nodes and \(k\) edges is hard in the non-adaptive setting, requiring \(Ω\big(\min\{k^2\log n,\,n^2\}\big)\) tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs \(G\sim\ER(n,q)\) in the non-adaptive setting, where the expected number of edges is \(\bar{k}=q\binom{n}{2}\), and we aim to design an efficient testing--decoding scheme achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests \(O(\bar{k}\log n)\) but incurs \(Ω(n^2)\) decoding time, whereas their proposed sublinear-time algorithm incurs an extra \((\log \bar{k})(\log n)\) factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using \(O(\bar{k}\log n)\) tests while attaining decoding time \(O(\bar{k}^{1+δ}\log n)\) for any fixed \(δ>0\).
• Abstract（参考訳）: ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。 一般に、任意のグラフを \(n\) ノードと \(k\) エッジで学習することは非適応的な設定では困難であり、小さな誤差確率が許される場合でも \(Ω\big(\min\{k^2\log n,\,n^2\}\big)\) テストを必要とする。 予測されるエッジの数が \(\bar{k}=q\binom{n}{2}\) となる非適応的条件下でのエルデシュ-レーニ (ER) グラフ \(G\sim\ER(n,q)\) の学習に集中し、漸近的にエラー確率を減少させる効率的なテスト-デコードスキームを設計することを目指している。 我々は最近、非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ学習設定に拡張し、任意の固定された \(δ>0\ に対して復号時間 \(O(\bar{k}^{1+δ}\log n)\) を確保しながら、 \(O(\bar{k}\log n)\) テストを用いてエッジセットを高い確率で復元できることを証明する。

関連論文リスト

• Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point [3.793609515750114]
  我々は、ErdHos-R'enyiランダムグラフのエッジ密度を強く推定する問題を、$G(n, dcirc/n)$で検討する。 我々のアルゴリズムは2乗の総和階層に基づいている。
  論文  参考訳（メタデータ） (2025-03-05T21:45:17Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Optimal network online change point localisation [73.93301212629231]
  オンラインネットワーク変化点検出の問題点について検討する。 この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。 目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
  論文  参考訳（メタデータ） (2021-01-14T07:24:39Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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