論文の概要: The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds

• arxiv url: http://arxiv.org/abs/2603.20070v1
• Date: Fri, 20 Mar 2026 15:53:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 19:48:39.215477
• Title: The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
• Title（参考訳）: フランツ・パリポテンシャルの単調性は低次MMSE下界と同値である
• Authors: Konstantinos Tsirkas, Leda Wang, Ilias Zadik,
• Abstract要約: 低次推定のパワーは、幅広い加法モデルの族に対するFPポテンシャルの単調性と同値であることを示す。 以上の結果から,これらのモデルの限界は熱処理されたFP電位の単調性によって直接的に示唆されることが明らかとなった。
• 参考スコア（独自算出の注目度）: 5.6738617521792145
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz--Parisi (FP) potential \cite{franz1995recipes,franz1997phase}, while the mathematically rigorous literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators \cite{hopkins2017efficient}. For many inference models, these two perspectives yield strikingly consistent predictions, giving rise to a long-standing open problem of establishing a precise mathematical relationship between them. In this work, we show that for estimation problems the power of low-degree polynomials is equivalent to the monotonicity of the annealed FP potential for a broad family of Gaussian additive models (GAMs) with signal-to-noise ratio $λ$. In particular, subject to a low-degree conjecture for GAMs, our results imply that the polynomial-time limits of these models are directly implied by the monotonicity of the annealed FP potential, in conceptual agreement with predictions from the physics literature dating back to the 1990s.
• Abstract（参考訳）: 過去数十年間、統計的推定の計算複雑性の理解に、2つの異なるアプローチが役立っている。 統計物理学の文献は、フランツ-パリ(FP)ポテンシャル \cite{franz 1995recipes,franz 1997phase} の局所安定性と単調性によるアルゴリズムの硬さを予測し、数学的に厳密な文献は制限されたアルゴリズムクラス、特に低次多項式推定器 \cite{hopkins2017efficient} の制限によって硬さを特徴づける。 多くの推論モデルにおいて、これらの2つの観点は驚くほど一貫した予測をもたらし、それらの間の正確な数学的関係を確立するという長年のオープンな問題を引き起こす。 本研究では、推定問題に対して、低次多項式のパワーは、信号対雑音比$λ$のガウス加法モデル(GAM)の広い族に対する熱処理されたFPポテンシャルの単調性と同値であることを示す。 特に、GAMの低次予想では、これらのモデルの多項式時間限界は1990年代までさかのぼる物理学文献の予測と概念的に一致して、熱処理されたFPポテンシャルの単調性によって直接示唆される。

関連論文リスト

• Asymptotic breakdown point analysis of the minimum density power divergence estimator under independent non-homogeneous setups [2.449909275410287]
  最低密度パワー分散推定器 (MDPDE) は、ロバスト推論の文献において大きな注目を集めている。 独立系や非均一系(INH)の観測など、様々な装置でうまく応用されている。 INH設定下におけるこの推定器のグローバルな信頼性や破壊挙動に関する一般的な結果は分かっていない。
  論文  参考訳（メタデータ） (2025-08-17T16:33:58Z)
• Computational Complexity of Statistics: New Insights from Low-Degree Polynomials [57.377943721487966]
  これは、様々な平均的な計算問題における明らかな統計的・計算上のトレードオフを予測し、説明するために、低次の使用に関する調査である。
  論文  参考訳（メタデータ） (2025-06-12T14:35:26Z)
• An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds [24.13557931882888]
  統計的検出問題において,Franz-Parisi基準を最適化し,計算ハードフェーズを特徴付ける。 この等価性は、幅広い統計モデルによって満たされる穏やかな仮定の下で成り立つ。 我々の同値性は、いくつかの既知の SQ の下界の導出を統一し、単純化する。
  論文  参考訳（メタデータ） (2025-06-06T17:39:32Z)
• Hyperscaling of Fidelity and Operator Estimations in the Critical Manifold [0.0]
  本研究では, 減速運動量モードで支持される観測値の基底状態予測値を, QFTが流れる固定点理論に基づく平均値で近似できることを示す。 以上の結果から,予測値の計算において,QFTをスケール不変の制限で置き換えることが可能なケースの明確化が可能となった。
  論文  参考訳（メタデータ） (2025-05-21T14:20:54Z)
• Algebraic and Statistical Properties of the Ordinary Least Squares Interpolator [3.4320157633663064]
  我々は最小$ell$-norm OLS補間器について結果を提供する。 ガウス・マルコフの定理の拡張のような統計的結果を示す。 我々はOLS補間器の特性をさらに探求するシミュレーションを行う。
  論文  参考訳（メタデータ） (2023-09-27T16:41:10Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics [73.1090889521313]
  本稿では,低次と自由エネルギーの異なるアプローチの厳密な接続を実現することを目的とする。 我々は、自由エネルギーに基づく硬度基準を定義し、それを高次硬度の概念に正式に結び付ける。 結果は、異なる硬さの概念間のつながりに関する概念的な洞察と、具体的な技術ツールの両方を提供する。
  論文  参考訳（メタデータ） (2022-05-19T17:39:29Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Divergence Frontiers for Generative Models: Sample Complexity, Quantization Level, and Frontier Integral [58.434753643798224]
  多様性フロンティアは生成モデルの評価フレームワークとして提案されている。 分岐フロンティアのプラグイン推定器のサンプル複雑性の非漸近的境界を確立する。 また,スムーズな分布推定器の統計的性能を調べることにより,分散フロンティアの枠組みも強化する。
  論文  参考訳（メタデータ） (2021-06-15T06:26:25Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。 問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。 我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
  論文  参考訳（メタデータ） (2020-06-18T17:18:02Z)

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

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