論文の概要: Low-degree lower bounds via almost orthonormal bases

• arxiv url: http://arxiv.org/abs/2509.09353v1
• Date: Thu, 11 Sep 2025 11:07:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-12 16:52:24.349344
• Title: Low-degree lower bounds via almost orthonormal bases
• Title（参考訳）: ほぼ正則基底による低次下界
• Authors: Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud, Nicolas Verzelen,
• Abstract要約: 低次数は、様々な高次元統計モデルにまたがる統計的-計算的ギャップの証拠を提供するための強力なパラダイムとして現れてきた。 本研究では,より直接的な証明戦略を提案する。
• 参考スコア（独自算出の注目度）: 47.83594448785856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models [Wein25]. For detection problems -- where the goal is to test a planted distribution $\mathbb{P}'$ against a null distribution $\mathbb{P}$ with independent components -- the standard approach is to bound the advantage using an $\mathbb{L}^2(\mathbb{P})$-orthonormal family of polynomials. However, this method breaks down for estimation tasks or more complex testing problems where $\mathbb{P}$ has some planted structures, so that no simple $\mathbb{L}^2(\mathbb{P})$-orthogonal polynomial family is available. To address this challenge, several technical workarounds have been proposed [SW22,SW25], though their implementation can be delicate. In this work, we propose a more direct proof strategy. Focusing on random graph models, we construct a basis of polynomials that is almost orthonormal under $\mathbb{P}$, in precisely those regimes where statistical--computational gaps arise. This almost orthonormal basis not only yields a direct route to establishing low-degree lower bounds, but also allows us to explicitly identify the polynomials that optimize the low-degree criterion. This, in turn, provides insights into the design of optimal polynomial-time algorithms. We illustrate the effectiveness of our approach by recovering known low-degree lower bounds, and establishing new ones for problems such as hidden subcliques, stochastic block models, and seriation models.
• Abstract（参考訳）: 低次多項式は、様々な高次元統計モデルにわたる統計的-計算的ギャップの証拠を提供するための強力なパラダイムとして現れてきた[Wein25]。 検出問題 -- 固定分布 $\mathbb{P}'$ を、独立成分を持つヌル分布 $\mathbb{P}$ に対してテストすること -- に対して、標準的なアプローチは、多項式の非正規族である $\mathbb{L}^2(\mathbb{P})$-orthonormal family を使って利点を束縛することである。 しかし、この手法は、推定タスクやより複雑なテスト問題に対して分解されるので、$\mathbb{P}$がいくつかの植込み構造を持つので、単純な$\mathbb{L}^2(\mathbb{P})$-orthogonal polynomial familyが利用できない。 この課題に対処するために、いくつかの技術的回避策(SW22,SW25)が提案されているが、その実装は繊細である。 本研究では,より直接的な証明戦略を提案する。 ランダムグラフモデルに着目し、$\mathbb{P}$ でほぼ正則な多項式の基底を構築する。 このほぼ正則基底は、低次下界を確立する直接的な経路を与えるだけでなく、低次基準を最適化する多項式を明示的に特定することを可能にする。 これにより、最適多項式時間アルゴリズムの設計に関する洞察が得られる。 本稿では, 既知の低次下界を復元し, 隠れ斜め, 確率ブロックモデル, セレーションモデルなどの問題に対して, 新たな手法を確立することによるアプローチの有効性について述べる。

関連論文リスト

• $p$-Adic Polynomial Regression as Alternative to Neural Network for Approximating $p$-Adic Functions of Many Variables [55.2480439325792]
  任意の精度で連続関数を近似できる回帰モデルを構築している。 提案モデルは、ニューラルネットワークアーキテクチャに基づく$p$-adicモデルの簡単な代替と見なすことができる。
  論文  参考訳（メタデータ） (2025-03-30T15:42:08Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Resilience of Rademacher chaos of low degree [5.3390449198644445]
  ラデマッハカオスのレジリエンスは、カオスが持続できる敵のサインフリップの最大数である。 我々はRadecherカオスの弾力性に関する確率的低バウンド保証を提供する。 次数2のラデマッハカオスと次数2のラデマッハカオスは,同じ概念的枠組みで確立されているが,大きな違いがある。
  論文  参考訳（メタデータ） (2024-02-16T08:27:55Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。 本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。 私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
  論文  参考訳（メタデータ） (2021-01-13T15:14:31Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  変分法による離散的グラフィカルモデルの推論は困難である。 エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。 Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。 選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T05:04:38Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Learning the Hypotheses Space from data: Learning Space and U-curve Property [0.0]
  本稿では、学習問題を仮説空間$mathcalH$だけでなく、学習空間$mathbbL(mathcalH)$でモデル化する古典的なPAC学習モデルの拡張について述べる。 我々の主な貢献は、$mathbbL(mathcalH)$で正規化モデル選択を行うデータ駆動の一般学習アルゴリズムである。
  論文  参考訳（メタデータ） (2020-01-26T22:29:33Z)

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

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