論文の概要: An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

• arxiv url: http://arxiv.org/abs/2506.06259v1
• Date: Fri, 06 Jun 2025 17:39:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 21:34:56.78168
• Title: An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
• Title（参考訳）: 最適化Franz-Parisi基準とSQ下界の等価性
• Authors: Siyu Chen, Theodor Misiakiewicz, Ilias Zadik, Peiyuan Zhang,
• Abstract要約: 統計的検出問題において,Franz-Parisi基準を最適化し,計算ハードフェーズを特徴付ける。 この等価性は、幅広い統計モデルによって満たされる穏やかな仮定の下で成り立つ。 我々の同値性は、いくつかの既知の SQ の下界の導出を統一し、単純化する。
• 参考スコア（独自算出の注目度）: 24.13557931882888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an annealed version of the celebrated Franz-Parisi potential from statistical physics, was shown to be equivalent to low-degree polynomial (LDP) lower bounds for Gaussian additive models, thereby connecting two distinct approaches to understanding the computational hardness in statistical inference. In this paper, we propose a refined FP criterion that aims to better capture the geometric ``overlap" structure of statistical models. Our main result establishes that this optimized FP criterion is equivalent to Statistical Query (SQ) lower bounds -- another foundational framework in computational complexity of statistical inference. Crucially, this equivalence holds under a mild, verifiable assumption satisfied by a broad class of statistical models, including Gaussian additive models, planted sparse models, as well as non-Gaussian component analysis (NGCA), single-index (SI) models, and convex truncation detection settings. For instance, in the case of convex truncation tasks, the assumption is equivalent with the Gaussian correlation inequality (Royen, 2014) from convex geometry. In addition to the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds -- such as for the NGCA model (Diakonikolas et al., 2017) and the SI model (Damian et al., 2024) -- but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (Arpino et al., 2023) and convex truncation (De et al., 2023).
• Abstract（参考訳）: Bandeira et al (2022) は、統計的検出問題において計算ハードフェーズを特徴づけるためのフランツ・パリ(FP)基準を導入した。 統計物理学による有名なフランツ・パリポテンシャルのアニール版に基づくFP基準は、ガウス加法モデルに対する低次多項式(LDP)下限と等価であることが示され、統計的推論における計算硬度を理解するために2つの異なるアプローチが結合された。 本稿では,統計モデルの幾何的「オーバーラップ」構造をよりよく捉えることを目的とした,洗練されたFP基準を提案する。 我々の主な結果は、この最適化されたFP基準が、統計的推論の計算複雑性のもう1つの基礎的な枠組みである統計的クエリ(SQ)下位境界と等価であることを証明している。 この等価性は、ガウス加法モデル、植込みスパースモデル、非ガウス成分分析(NGCA)、単一インデックス(SI)モデル、凸トランケーション検出設定など、幅広い種類の統計モデルによって満たされる軽度で検証可能な仮定の下で維持される。 例えば、凸トランケーションタスクの場合、仮定は凸幾何学からのガウス相関不等式(Royen, 2014)と等価である。 これらに加えて、NGCAモデル(Diakonikolas et al , 2017)やSIモデル(Damian et al , 2024)など、既知のいくつかのSQ下限の導出を統一し、単純化するだけでなく、混合スパース線形回帰(Arpino et al , 2023)や凸トランケーション(De et al , 2023)の計算ギャップを含む、新たな独立性を持つSQ下限の導出も行う。

関連論文リスト

• T-Rex: Fitting a Robust Factor Model via Expectation-Maximization [0.0]
  統計的因子モデルに頑健に適合する新しい予測最大化(EM)アルゴリズムを提案する。 我々のアプローチは、楕円分布に対する散乱行列のタイラーのM-推定器に基づいている。 合成例と実例の両方について数値実験を行った。
  論文  参考訳（メタデータ） (2025-05-17T18:53:06Z)
• Transition of $α$-mixing in Random Iterations with Applications in Queuing Theory [0.0]
  本研究では, 混合特性を外因性回帰器から結合論による応答へ伝達することを示す。 また,非定常環境下においても,ドリフトおよびマイノライズ条件のランダム環境におけるマルコフ連鎖について検討した。
  論文  参考訳（メタデータ） (2024-10-07T14:13:37Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• State and parameter learning with PaRIS particle Gibbs [11.290331898505594]
  非線形状態空間モデルは統計機械学習においてユビキタスである。 PaRISはモンテカルロのシーケンシャルな手法であり、加算関数の期待値の効率的なオンライン近似を可能にする。 我々はパリの粒子Gibbs PPGサンプリングアルゴリズムを,条件付きSMC移動によって駆動されるPaRISアルゴリズムとして設計する。
  論文  参考訳（メタデータ） (2023-01-02T23:27:33Z)
• 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)
• A non-asymptotic model selection in block-diagonal mixture of polynomial experts models [1.491109220586182]
  回帰モデルの未知条件密度を推定するために, ペナル化最大選択基準を導入する。 我々は、Jensen-Kullback-Leibler型損失によるペナル化極大確率で満たされる有限サンプルオラクルを含む強力な理論的保証を提供する。
  論文  参考訳（メタデータ） (2021-04-18T21:32:20Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  変分法による離散的グラフィカルモデルの推論は困難である。 エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。 Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。 選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T05:04:38Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  本稿では,低ランクテンソル推定問題に対するフレキシブルなフレームワークについて述べる。 計算画像、ゲノミクス、ネットワーク解析の応用から多くの重要な例を含む。
  論文  参考訳（メタデータ） (2020-02-26T01:54:35Z)

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

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