論文の概要: Low-degree phase transitions for detecting a planted clique in sublinear
time
- arxiv url: http://arxiv.org/abs/2402.05451v1
- Date: Thu, 8 Feb 2024 07:08:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 16:06:30.199305
- Title: Low-degree phase transitions for detecting a planted clique in sublinear
time
- Title（参考訳）: 亜線形時間における植込みクランク検出のための低次相転移
- Authors: Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
- Abstract要約: 我々は、n$上のランダムグラフにおいて、サイズ$k$の植込みクリムを検出する問題を考える。
我々は、$k = Theta(n1/2 + delta)$のとき、高信号状態のアルゴリズムをより高速に研究する。
適応的でない全てのクエリパターンに対して、少なくとも有効である同じサイズの高度に構造化されたクエリパターンが存在することを示す。
- 参考スコア（独自算出の注目度）: 47.38306674755808
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of detecting a planted clique of size $k$ in a random
graph on $n$ vertices. When the size of the clique exceeds $\Theta(\sqrt{n})$,
polynomial-time algorithms for detection proliferate. We study faster --
namely, sublinear time -- algorithms in the high-signal regime when $k =
\Theta(n^{1/2 + \delta})$, for some $\delta > 0$. To this end, we consider
algorithms that non-adaptively query a subset $M$ of entries of the adjacency
matrix and then compute a low-degree polynomial function of the revealed
entries. We prove a computational phase transition for this class of
non-adaptive low-degree algorithms: under the scaling $\lvert M \rvert =
\Theta(n^{\gamma})$, the clique can be detected when $\gamma > 3(1/2 - \delta)$
but not when $\gamma < 3(1/2 - \delta)$. As a result, the best known runtime
for detecting a planted clique, $\widetilde{O}(n^{3(1/2-\delta)})$, cannot be
improved without looking beyond the non-adaptive low-degree class.
Our proof of the lower bound -- based on bounding the conditional low-degree
likelihood ratio -- reveals further structure in non-adaptive detection of a
planted clique. Using (a bound on) the conditional low-degree likelihood ratio
as a potential function, we show that for every non-adaptive query pattern,
there is a highly structured query pattern of the same size that is at least as
effective.
- Abstract（参考訳）: 我々は、$n$頂点上のランダムグラフにおいて、サイズ$k$の植込みクリムを検出する問題を考察する。
clique のサイズが $\Theta(\sqrt{n})$ を超えると、検出のための多項式時間アルゴリズムが増殖する。
k = \theta(n^{1/2 + \delta})$ の場合、いくつかの$\delta > 0$ に対して、より高速で、すなわち、サブリニアな時間 -- アルゴリズムを研究する。
この目的のために、隣接行列のエントリのサブセット $m$ を非適応的にクエリし、明快なエントリの低次多項式関数を計算するアルゴリズムを考える。
スケーリング $\lvert M \rvert = \Theta(n^{\gamma})$ では、clique は $\gamma > 3(1/2 - \delta)$ では検出できるが、$\gamma < 3(1/2 - \delta)$ では検出できない。
その結果、植林された傾斜角を検出する最もよく知られたランタイムである$\widetilde{O}(n^{3(1/2-\delta)})$は、非適応的な低次クラスを超越せずには改善できない。
条件付き低度度比のバウンドに基づく下限の証明は、植栽されたクランクの非適応検出におけるさらなる構造を明らかにする。
条件付き低次度度比をポテンシャル関数として用いることで、非適応的なクエリパターンに対して、少なくとも有効である同じサイズの高度に構造化されたクエリパターンが存在することを示す。
関連論文リスト
- Truncated Variance Reduced Value Iteration [23.282578280033622]
我々は、割引マルコフ決定プロセスにおいて、$epsilon$-optimal Policyを計算するための高速なランダム化アルゴリズムを提供する。
この結果から,モデルフリー法とモデルベース法とでは,サンプル・複雑さのギャップを埋めることができた。
論文 参考訳（メタデータ） (2024-05-21T17:28:06Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Agnostic proper learning of monotone functions: beyond the black-box
correction barrier [6.47243430672461]
2tildeO(sqrtn/varepsilon)$ 未知関数 $f:pm 1n rightarrow pm 1$ の一様ランダムな例を与えられたとき、我々のアルゴリズムは仮説 $g:pm 1n rightarrow pm 1$ を出力する。
また,2tildeO(sqrt)の実行時間を用いて,未知関数$f$からモノトンへの距離を加算誤差$varepsilon$まで推定するアルゴリズムも提供する。
論文 参考訳（メタデータ） (2023-04-05T18:52:10Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。