論文の概要: Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps

• arxiv url: http://arxiv.org/abs/2604.17410v1
• Date: Sun, 19 Apr 2026 12:34:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 21:52:52.511724
• Title: Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
• Title（参考訳）: 低層ヒューリスティックからのアルゴリズムの整合性II:検出-回復ギャップの予測
• Authors: Zhangsong Li,
• Abstract要約: 低次フレームワークは、高次元推論における統計的-計算的ギャップの証拠を提供する強力なツールとして登場した。 我々は,低次テストの優位性に対する軽度境界から,回復問題に対するエンプ計算の下限を求める一般的な手法を開発した。 この枠組みは, 植込み部分行列, 植込み高密度部分グラフ, ブロックモデル, 多周波角同期, グループ同期, 多層ブロックモデルなど, いくつかの標準的推論問題に適用する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, the standard approach bounds the low-degree advantage through an explicit orthonormal basis. However, this method does not extend naturally to estimation tasks, and thus fails to capture the \emph{detection-recovery gap phenomenon} that arises in many high-dimensional problems. Although several important advances have been made to overcome this limitation \cite{SW22, SW25, CGGV25+}, the existing approaches often rely on delicate, model-specific combinatorial arguments. In this work, we develop a general approach for obtaining \emph{conditional computational lower bounds} for recovery problems from mild bounds on low-degree testing advantage. Our method combines the notion of algorithmic contiguity in \cite{Li25} with a cross-validation reduction in \cite{DHSS25} that converts successful recovery into a hypothesis test with lopsided success probabilities. In contrast to prior unconditional lower bounds, our argument is conceptually simple, flexible, and largely model-independent. We apply this framework to several canonical inference problems, including planted submatrix, planted dense subgraph, stochastic block model, multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block model. In the first three settings, our method recovers existing low-degree lower bounds for recovery in \cite{SW22, SW25} via a substantially simpler argument. In the latter three, it gives new evidence for conjectured computational thresholds including the persistence of detection-recovery gaps. Together, these results suggest that mild control of low-degree advantage is often sufficient to explain computational barriers for recovery in high-dimensional statistical models.
• Abstract（参考訳）: 低次多項式フレームワークは、高次元推論における統計的-計算的ギャップの証拠を提供する強力なツールとして登場した。 検出問題に対して、標準的アプローチは明示的な正則基底を通じて低次優位性の境界を定めている。 しかし、この手法は自然に推定タスクに拡張されないため、多くの高次元問題で発生する 'emph{detection-recovery gap phenomenon' を捉えることができない。 この制限を克服するためにいくつかの重要な進歩がなされているが、既存のアプローチはしばしば繊細でモデル固有の組合せ論に依存している。 本研究では,低次テストの優位性に対する軽度バウンダリからリカバリ問題に対する 'emph{conditional compute lower bounds} を得るための一般的な手法を開発する。 提案手法は, アルゴリズムの整合性の概念と, 成功率を立方的成功確率に換算した仮説テストに変換する, クロスバリデーション還元法を組み合わせたものである。 以前の非条件下界とは対照的に、我々の議論は概念的には単純であり、柔軟であり、主にモデルに依存しない。 この枠組みは、植込み部分行列、植込み高密度部分グラフ、確率ブロックモデル、多周波角同期、直交群同期、多層確率ブロックモデルなど、いくつかの標準的推論問題に適用する。 最初の3つの設定において,本手法はより単純な引数を用いて,既存の低緯度下界を復元する。 後者の3つでは、検出-回復ギャップの持続性を含む予測された計算しきい値の新しい証拠を与える。 これらの結果は、高次元統計モデルにおいて、回復のための計算障壁を説明するのに、低次優位性の緩やかな制御が十分であることを示している。

関連論文リスト

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Low degree conjecture implies sharp computational thresholds in stochastic block model [3.7873597471903935]
  我々は(拡張)低次予想(対称ブロックモデルにおける[MW23]の最近の形式化)の影響について検討する。 我々は,Kesten-Stigum(KS)しきい値以下で,非リアルタイムアルゴリズムがコミュニティラベルを弱めに復元できることを確立した。 この結果から,ブロックモデルのパラメータの学習において,計算量と統計量との差があることが示唆された。
  論文  参考訳（メタデータ） (2025-02-20T20:21:03Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Convergence of uncertainty estimates in Ensemble and Bayesian sparse model discovery [4.446017969073817]
  ブートストラップに基づく逐次しきい値最小二乗推定器による雑音に対する精度と頑健性の観点から経験的成功を示す。 このブートストラップに基づくアンサンブル手法は,誤差率の指数収束率で,確率的に正しい可変選択を行うことができることを示す。
  論文  参考訳（メタデータ） (2023-01-30T04:07:59Z)
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics [73.1090889521313]
  本稿では,低次と自由エネルギーの異なるアプローチの厳密な接続を実現することを目的とする。 我々は、自由エネルギーに基づく硬度基準を定義し、それを高次硬度の概念に正式に結び付ける。 結果は、異なる硬さの概念間のつながりに関する概念的な洞察と、具体的な技術ツールの両方を提供する。
  論文  参考訳（メタデータ） (2022-05-19T17:39:29Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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