論文の概要: Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

• arxiv url: http://arxiv.org/abs/2502.09832v1
• Date: Fri, 14 Feb 2025 00:24:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-17 14:46:49.648199
• Title: Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
• Title（参考訳）: 低次予想からのアルゴリズムの連続性と相関ランダムグラフへの応用
• Authors: Zhangsong Li,
• Abstract要約: 2つの問題に対して計算硬度を示す。 我々の証明の主な要素の1つは、2つの確率測度の間の近位関係を導出することである。 このフレームワークは、異なるタスク間のリダクションを実行するための便利なツールを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this paper, assuming a natural strengthening of the low-degree conjecture, we provide evidence of computational hardness for two problems: (1) the (partial) matching recovery problem in the sparse correlated Erd\H{o}s-R\'enyi graphs $\mathcal G(n,q;\rho)$ when the edge-density $q=n^{-1+o(1)}$ and the correlation $\rho<\sqrt{\alpha}$ lies below the Otter's threshold, solving a remaining problem in \cite{DDL23+}; (2) the detection problem between the correlated sparse stochastic block model $\mathcal S(n,\tfrac{\lambda}{n};k,\epsilon;s)$ and a pair of independent stochastic block models $\mathcal S(n,\tfrac{\lambda s}{n};k,\epsilon)$ when $\epsilon^2 \lambda s<1$ lies below the Kesten-Stigum (KS) threshold and $s<\sqrt{\alpha}$ lies below the Otter's threshold, solving a remaining problem in \cite{CDGL24+}. One of the main ingredient in our proof is to derive certain forms of \emph{algorithmic contiguity} between two probability measures based on bounds on their low-degree advantage. To be more precise, consider the high-dimensional hypothesis testing problem between two probability measures $\mathbb{P}$ and $\mathbb{Q}$ based on the sample $\mathsf Y$. We show that if the low-degree advantage $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$, then (assuming the low-degree conjecture) there is no efficient algorithm $\mathcal A$ such that $\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ and $\mathbb{P}(\mathcal A(\mathsf Y)=1)=\Omega(1)$. This framework provides a useful tool for performing reductions between different inference tasks.
• Abstract（参考訳）: 本稿では、低次予想の自然な強化を仮定し、(1) スパース相関式 Erd\H{o}s-R\enyi graphs $\mathcal G(n,q;\rho)$ と相関式 $q=n^{-1+o(1) と相関式 $\rho<\sqrt{\alpha}$ がオッタースしきい値以下にあるときの計算困難性の証明を与える。 我々の証明の主な要素の1つは、その低次優位性に基づく2つの確率測度の間の特定の形の \emph{algorithmic contiguity} を導出することである。 より正確には、2つの確率測度 $\mathbb{P}$ と $\mathbb{Q}$ の間の高次元仮説試験問題をサンプル $\mathsf Y$ に基づいて考える。 低次ゲイン $\mathsf{Adv}_{\leq D} \big( \frac{\mathrm{d}\mathbb{P}}{\mathrm{d}\mathbb{Q}} \big)=O(1)$ であるなら、(低次予想を仮定すると)効率的なアルゴリズム $\mathcal A$ が存在しなければ、$\mathbb{Q}(\mathcal A(\mathsf Y)=0)=1-o(1)$ と $\mathbb{P}(\mathcal A(\mathsf Y)=1)=\Omega(1)$ が成り立つ。 このフレームワークは、異なる推論タスク間の還元を実行するための有用なツールを提供する。

関連論文リスト

• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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