論文の概要: Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

• arxiv url: http://arxiv.org/abs/2009.06107v3
• Date: Sat, 26 Jun 2021 17:06:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2022-10-19 02:59:47.654121
• Title: Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Title（参考訳）: 統計的クエリアルゴリズムと低次テストはほぼ等価である
• Authors: Matthew Brennan and Guy Bresler and Samuel B. Hopkins and Jerry Li and Tselil Schramm
• Abstract要約: 我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。 テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。 提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
• 参考スコア（独自算出の注目度）: 29.684442397855197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.
• Abstract（参考訳）: 研究者は現在、高次元統計的推定問題において、情報計算ギャップを予測し、裏付けるために多くのアプローチを使っている。 顕著なアプローチは、制限された計算モデルの限界を特徴づけることである。一方、アルゴリズムの強力なクラスに対して強力な計算下界を生じさせ、一方、効率的なアルゴリズムの開発を導くのに役立つ。 本稿では,高次元仮説検定の文脈において,統計クエリフレームワークと低次多項式という,最も一般的な制限付き計算モデルについて検討する。 私たちの主な結果は、テスト問題における穏やかな条件下において、アルゴリズムの2つのクラスは本質的に等価であるということです。 そこで我々は,スパルスPCA,テンソルPCA,および植木クリッド問題のいくつかの変種について,新しい統計的検索下界を求める。

関連論文リスト

• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity [19.939448881052453]
  本稿では,PCAにおける通信複雑性を用いたメモリバウンドアルゴリズムの実行時間に対する計算的低バウンドを導出する。 下限は反復時間アルゴリズムを除外しないが、勾配降下法やパワー法のような多くのよく使われるアルゴリズムは、サンプルサイズが十分に大きくない場合、より高いカウントを持つ必要があることを示唆している。
  論文  参考訳（メタデータ） (2022-04-15T15:59:43Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。 本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
  論文  参考訳（メタデータ） (2020-05-22T22:30:52Z)
• Marginal likelihood computation for model selection and hypothesis testing: an extensive review [66.37504201165159]
  この記事では、このトピックの最先端に関する総合的な研究について紹介する。 さまざまなテクニックの制限、メリット、コネクション、差異を強調します。 また、不適切な事前利用の問題や解決法についても述べる。
  論文  参考訳（メタデータ） (2020-05-17T18:31:58Z)
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix [2.345015036605934]
  統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。 第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。 第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
  論文  参考訳（メタデータ） (2020-03-17T19:12:21Z)

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

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