論文の概要: Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
- arxiv url: http://arxiv.org/abs/2506.10748v1
- Date: Thu, 12 Jun 2025 14:35:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 15:37:22.780102
- Title: Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
- Title（参考訳）: 統計学の計算複雑性:低次多項式からの新しい考察
- Authors: Alexander S. Wein,
- Abstract要約: これは、様々な平均的な計算問題における明らかな統計的・計算上のトレードオフを予測し、説明するために、低次の使用に関する調査である。
- 参考スコア（独自算出の注目度）: 57.377943721487966
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. In a nutshell, this framework measures the complexity of a statistical task by the minimum degree that a polynomial function must have in order to solve it. The main goals of this survey are to (1) describe the types of problems where the low-degree framework can be applied, encompassing questions of detection (hypothesis testing), recovery (estimation), and more; (2) discuss some philosophical questions surrounding the interpretation of low-degree lower bounds, and notably the extent to which they should be treated as evidence for inherent computational hardness; (3) explore the known connections between low-degree polynomials and other related approaches such as the sum-of-squares hierarchy and statistical query model; and (4) give an overview of the mathematical tools used to prove low-degree lower bounds. A list of open problems is also included.
- Abstract（参考訳）: これは、様々な平均的な計算問題における明らかな統計計算のトレードオフを予測し、説明するための低次多項式の使用に関する調査である。
簡単に言えば、このフレームワークは、多項式関数がそれを解決するために持たなければならない最小度で統計量の複雑性を測定する。
本調査の主な目的は,(1)低次フレームワークが適用可能な問題の種類,(2)低次低次境界の解釈にまつわるいくつかの哲学的問題,(3)低次多項式と低次多項式階層と統計的クエリモデルとの既知の関連性,(4)低次低次境界の証明に使用される数学的ツールの概要を考察することである。
オープンな問題のリストも含んでいる。
関連論文リスト
- From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
PCHのレベルによって, NPPP, PSPACE, NEXP完全満足度の問題が生じることを示す。
一方、完全言語の場合、すなわち加法、余分化、乗算が可能である場合、反事実レベルの満足度は確率的・因果的なレベルと同じであることを示す。
論文 参考訳（メタデータ） (2024-05-12T20:25:36Z) - The Franz-Parisi Criterion and Computational Trade-offs in High
Dimensional Statistics [73.1090889521313]
本稿では,低次と自由エネルギーの異なるアプローチの厳密な接続を実現することを目的とする。
我々は、自由エネルギーに基づく硬度基準を定義し、それを高次硬度の概念に正式に結び付ける。
結果は、異なる硬さの概念間のつながりに関する概念的な洞察と、具体的な技術ツールの両方を提供する。
論文 参考訳（メタデータ） (2022-05-19T17:39:29Z) - Average-Case Communication Complexity of Statistical Problems [48.03761288397421]
通信の複雑さは、ストリーミング、スケッチ、クエリベースのモデルにおける下位境界を証明する主要なツールである。
本稿では,ランダムグラフやマトリクスに植木構造を組み込んだ問題に対して,入力分布を保存する一般還元法を提案する。
我々は,植林した傾斜地を検知・発見するために,二者間・多者間通信の下限を導出する。
論文 参考訳（メタデータ） (2021-07-03T03:31:37Z) - Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。
テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。
提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
論文 参考訳（メタデータ） (2020-09-13T22:55:18Z) - Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文 参考訳（メタデータ） (2020-08-05T17:52:10Z) - Marginal likelihood computation for model selection and hypothesis
testing: an extensive review [66.37504201165159]
この記事では、このトピックの最先端に関する総合的な研究について紹介する。
さまざまなテクニックの制限、メリット、コネクション、差異を強調します。
また、不適切な事前利用の問題や解決法についても述べる。
論文 参考訳（メタデータ） (2020-05-17T18:31:58Z) - The empirical duality gap of constrained statistical learning [115.23598260228587]
本研究では,制約付き統計学習問題(制約なし版)について,ほぼ全ての現代情報処理のコアとなる研究を行った。
本稿では, 有限次元パラメータ化, サンプル平均, 双対性理論を利用して, 無限次元, 未知分布, 制約を克服する制約付き統計問題に取り組むことを提案する。
フェアラーニングアプリケーションにおいて,この制約付き定式化の有効性と有用性を示す。
論文 参考訳（メタデータ） (2020-02-12T19:12:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。