論文の概要: Detection of Dense Subhypergraphs by Low-Degree Polynomials

• arxiv url: http://arxiv.org/abs/2304.08135v1
• Date: Mon, 17 Apr 2023 10:38:08 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-18 15:47:01.860349
• Title: Detection of Dense Subhypergraphs by Low-Degree Polynomials
• Title（参考訳）: 低次多項式による高密度部分グラフの検出
• Authors: Abhishek Dhawan, Cheng Mao, Alexander S. Wein
• Abstract要約: ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
• 参考スコア（独自算出の注目度）: 72.4451045270967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergraph version of the problem. Let $G^r(n,p)$ denote the $r$-uniform Erd\H{o}s-R\'enyi hypergraph model with $n$ vertices and edge density $p$. We consider detecting the presence of a planted $G^r(n^\gamma, n^{-\alpha})$ subhypergraph in a $G^r(n, n^{-\beta})$ hypergraph, where $0< \alpha < \beta < r-1$ and $0 < \gamma < 1$. Focusing on tests that are degree-$n^{o(1)}$ polynomials of the entries of the adjacency tensor, we determine the threshold between the easy and hard regimes for the detection problem. More precisely, for $0 < \gamma < 1/2$, the threshold is given by $\alpha = \beta \gamma$, and for $1/2 \le \gamma < 1$, the threshold is given by $\alpha = \beta/2 + r(\gamma - 1/2)$. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known. Our proof of low-degree hardness is based on a conditional variant of the standard low-degree likelihood calculation.
• Abstract（参考訳）: ランダムグラフにおける植込み高密度部分グラフの検出は、近年広く研究されている基本的な統計的および計算上の問題である。 我々は問題のハイパーグラフ版を研究している。 G^r(n,p)$ は$r$-ユニフォーム Erd\H{o}s-R\'enyi ハイパーグラフモデルで$n$頂点とエッジ密度 $p$ を表す。 我々は,$g^r(n^\gamma,n^{-\alpha})$部分超グラフを$g^r(n,n^{-\beta})$ハイパーグラフで検出し,$0< \alpha < \beta < r-1$ および $0 < \gamma < 1$ とする。 隣接テンソルの成分の次数-$n^{o(1)}$多項式の試験に焦点をあて、検出問題に対する易度と硬度の間のしきい値を決定する。 より正確には、$0 < \gamma < 1/2$の場合、閾値は$\alpha = \beta \gamma$、$1/2 \le \gamma < 1$の場合は$\alpha = \beta/2 + r(\gamma - 1/2)$である。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。 低次硬さの証明は、標準低次度度計算の条件付き変種に基づいている。

関連論文リスト

• A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
  一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。 一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。 隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
  論文  参考訳（メタデータ） (2024-09-02T06:14:05Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• 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)
• Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
  我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。 我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
  論文  参考訳（メタデータ） (2022-05-31T17:59:09Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
  本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。 低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
  論文  参考訳（メタデータ） (2021-03-17T18:18:57Z)
• Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
  重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。 我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
  論文  参考訳（メタデータ） (2020-10-30T14:42:17Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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