論文の概要: Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem

• arxiv url: http://arxiv.org/abs/2011.11500v2
• Date: Thu, 28 Jan 2021 13:21:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 03:31:43.303619
• Title: Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem
• Title（参考訳）: k$-densest sub-hypergraph問題に対する統計的および計算的しきい値
• Authors: Luca Corinzia and Paolo Penna and Wojciech Szpankowski and Joachim M. Buhmann
• Abstract要約: 我々は,$d$-uniform ハイパーグラフ上に$k$-densest サブハイパーグラフを植え付けることで回復する問題を考察する。 この根本的な問題は、例えば、コミュニティの検出、平均ケースの複雑さ、神経科学の応用など、様々な文脈に現れる。
• 参考スコア（独自算出の注目度）: 13.808053718325635
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we consider the problem of recovery a planted $k$-densest sub-hypergraph on $d$-uniform hypergraphs. This fundamental problem appears in different contexts, e.g., community detection, average-case complexity, and neuroscience applications as a structural variant of tensor-PCA problem. We provide tight \emph{information-theoretic} upper and lower bounds for the exact recovery threshold by the maximum-likelihood estimator, as well as \emph{algorithmic} bounds based on approximate message passing algorithms. The problem exhibits a typical statistical-to-computational gap observed in analogous sparse settings that widen with increasing sparsity of the problem. The bounds show that the signal structure impacts the location of the statistical and computational phase transition that the known existing bounds for the tensor-PCA model do not capture. This effect is due to the generic planted signal prior that this latter model addresses.
• Abstract（参考訳）: 本研究では,$d$-uniformハイパーグラフ上の$k$-densestサブハイパーグラフのリカバリ問題について考察する。 この根本的な問題は、例えば、コミュニティ検出、平均ケースの複雑さ、神経科学の応用など、テンソルPCA問題の構造的変種として異なる文脈に現れる。 近似メッセージパッシングアルゴリズムに基づいて,最大類似度推定器による正確な回復しきい値の上限と下限の厳密な \emph{information-theoretic} と \emph{algorithmic} 境界を与える。 この問題は、問題の範囲が拡大するにつれて広がる類似のスパース設定で観測される典型的な統計的-計算的ギャップを示す。 境界は、信号構造がテンソルPCAモデルに対する既知の有界が捉えない統計的および計算的相転移の位置に影響を与えることを示している。 この効果は、後者のモデルが参照する前の一般的な植込み信号によるものである。

関連論文リスト

• High-dimensional optimization for multi-spiked tensor PCA [8.435118770300999]
  本研究では,2つの局所最適化アルゴリズム,オンライン勾配勾配(SGD)と勾配流のダイナミクスについて検討する。 勾配流の場合、第1のスパイクを効率的に回収するアルゴリズムしきい値も$Np-2$である。 この結果は, 推定器とスパイクの相関関係を記述した低次元系の詳細な解析によって得られた。
  論文  参考訳（メタデータ） (2024-08-12T12:09:25Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。 植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
  論文  参考訳（メタデータ） (2024-02-01T03:39:01Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。 広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
  論文  参考訳（メタデータ） (2022-05-26T17:47:35Z)
• Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity [19.939448881052453]
  本稿では,PCAにおける通信複雑性を用いたメモリバウンドアルゴリズムの実行時間に対する計算的低バウンドを導出する。 下限は反復時間アルゴリズムを除外しないが、勾配降下法やパワー法のような多くのよく使われるアルゴリズムは、サンプルサイズが十分に大きくない場合、より高いカウントを持つ必要があることを示唆している。
  論文  参考訳（メタデータ） (2022-04-15T15:59:43Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。 この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。 本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。 我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
  論文  参考訳（メタデータ） (2021-05-27T23:41:01Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits [9.427635404752936]
  我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。 我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。 信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-21T15:53:44Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  本稿では,低ランクテンソル推定問題に対するフレキシブルなフレームワークについて述べる。 計算画像、ゲノミクス、ネットワーク解析の応用から多くの重要な例を含む。
  論文  参考訳（メタデータ） (2020-02-26T01:54:35Z)

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

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