論文の概要: PTF Testing Lower Bounds for Non-Gaussian Component Analysis

• arxiv url: http://arxiv.org/abs/2511.19398v1
• Date: Mon, 24 Nov 2025 18:35:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:25.366556
• Title: PTF Testing Lower Bounds for Non-Gaussian Component Analysis
• Title（参考訳）: 非ガウス成分分析のためのPTF試験
• Authors: Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas,
• Abstract要約: 本研究は,統計的問題に対する情報計算ギャップについて研究する。 非ガウス成分分析(NGCA)におけるほぼ自明な PTF 検定の下限を証明した。 我々のNGCAローバウンドは、他の多くの統計問題に対して同様のローバウンドを意味する。
• 参考スコア（独自算出の注目度）: 45.24757440014651
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are stronger than the information-theoretic optimum) against natural models of computation. A popular such model in the literature is the family of low-degree polynomial tests. While these tests are defined in such a way that make them easy to analyze, the class of algorithms that they rule out is somewhat restricted. An important goal in this context has been to obtain lower bounds against the stronger and more natural class of low-degree Polynomial Threshold Function (PTF) tests, i.e., any test that can be expressed as comparing some low-degree polynomial of the data to a threshold. Proving lower bounds against PTF tests has turned out to be challenging. Indeed, we are not aware of any non-trivial PTF testing lower bounds in the literature. In this paper, we establish the first non-trivial PTF testing lower bounds for a range of statistical tasks. Specifically, we prove a near-optimal PTF testing lower bound for Non-Gaussian Component Analysis (NGCA). Our NGCA lower bound implies similar lower bounds for a number of other statistical problems. Our proof leverages a connection to recent work on pseudorandom generators for PTFs and recent techniques developed in that context. At the technical level, we develop several tools of independent interest, including novel structural results for analyzing the behavior of low-degree polynomials restricted to random directions.
• Abstract（参考訳）: 本研究は,統計的問題に対する情報計算ギャップについて研究する。 このようなギャップを証明するための一般的なアプローチは、計算の自然なモデルに対して、サンプルの複雑さの低い境界(情報理論の最適値よりも強い)を示すことである。 文学におけるそのようなモデルは、低次多項式テストの族である。 これらのテストは分析を容易にする方法で定義されているが、それらが除外するアルゴリズムのクラスは多少制限されている。 この文脈における重要なゴールは、より強い、より自然な低次多項式閾値関数(PTF)テスト(すなわち、データの低次多項式をしきい値と比較できるようなテスト)に対する下界を得ることである。 PTFテストに対する低いバウンダリの証明は困難であることが判明した。 実際、文献の下位境界を検査する非自明な PTF は知らない。 本稿では,統計的タスクの下位境界をテストする非自明な PTF を初めて確立する。 具体的には,非ガウス成分分析 (NGCA) において, ほぼ最適 PTF 試験を行う。 我々のNGCAローバウンドは、他の多くの統計問題に対して同様のローバウンドを意味する。 提案手法は, PTF用擬似乱数発生器の最近の研究と, その文脈で開発された最近の技術とのつながりを生かしたものである。 技術的レベルでは、ランダムな方向に制限された低次多項式の挙動を解析するための新しい構造的結果を含む、いくつかの独立した興味を持つツールを開発する。

関連論文リスト

• Low degree conjecture implies sharp computational thresholds in stochastic block model [3.7873597471903935]
  我々は(拡張)低次予想(対称ブロックモデルにおける[MW23]の最近の形式化)の影響について検討する。 我々は,Kesten-Stigum(KS)しきい値以下で,非リアルタイムアルゴリズムがコミュニティラベルを弱めに復元できることを確立した。 この結果から,ブロックモデルのパラメータの学習において,計算量と統計量との差があることが示唆された。
  論文  参考訳（メタデータ） (2025-02-20T20:21:03Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)

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

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