論文の概要: Precise Error Rates for Computationally Efficient Testing

• arxiv url: http://arxiv.org/abs/2311.00289v1
• Date: Wed, 1 Nov 2023 04:41:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 14:59:57.168578
• Title: Precise Error Rates for Computationally Efficient Testing
• Title（参考訳）: 計算効率テストのための高精度誤り率
• Authors: Ankur Moitra, Alexander S. Wein
• Abstract要約: 本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
• 参考スコア（独自算出の注目度）: 75.63895690909241
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the fundamental question of simple-versus-simple hypothesis testing with an eye towards computational complexity, as the statistically optimal likelihood ratio test is often computationally intractable in high-dimensional settings. In the classical spiked Wigner model (with a general i.i.d. spike prior) we show that an existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates among all computationally efficient tests, even though there are exponential-time tests that do better. This result is conditional on an appropriate complexity-theoretic conjecture, namely a natural strengthening of the well-established low-degree conjecture. Our result shows that the spectrum is a sufficient statistic for computationally bounded tests (but not for all tests). To our knowledge, our approach gives the first tool for reasoning about the precise asymptotic testing error achievable with efficient computation. The main ingredients required for our hardness result are a sharp bound on the norm of the low-degree likelihood ratio along with (counterintuitively) a positive result on achievability of testing. This strategy appears to be new even in the setting of unbounded computation, in which case it gives an alternate way to analyze the fundamental statistical limits of testing.
• Abstract（参考訳）: 統計学的に最適である確率比検定は高次元設定でしばしば計算可能であるため、計算複雑性に目を向けて、単純な対数-単純仮説検定の根本的な問題を再考する。 古典的なスパイクド・ウィグナーモデル(一般のスパイク先行)では、線形スペクトル統計に基づく既存のテストは、より優れた指数時間テストがあるにもかかわらず、全ての計算効率の良いテストの中で、タイプIとタイプIIのエラー率の間の最良のトレードオフ曲線を達成することを示した。 この結果は、適切な複雑性理論的予想、すなわち、確立された低次予想の自然な強化に条件づけられている。 その結果、スペクトルは計算的に有界なテストでは十分統計量である(全てのテストではそうではない)。 我々の知る限り、我々の手法は効率的な計算で達成可能な正確な漸近テスト誤差を推論するための最初のツールを提供する。 ハードネスの結果に必要な主な成分は、低次度度比の標準値と(直感的に)テストの達成可能性の正の結果に鋭い束縛である。 この戦略は、非有界計算の設定においても新しく、テストの基本的な統計的限界を分析する代替的な方法を提供する。

関連論文リスト

• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  我々は、一般的な非データ生成プロセスの下で、最初のタイプIエラーと予測リジェクション時間保証を提供する。 本研究では, 平均処理効果など, 方程式を推定することによって定義されるパラメータの推測に, 結果を適用する方法を示す。
  論文  参考訳（メタデータ） (2022-12-29T18:37:08Z)
• Learning to Increase the Power of Conditional Randomization Tests [8.883733362171032]
  モデル-X条件ランダム化テストは、条件独立性テストのための一般的なフレームワークである。 本稿では,モデルXテストのパワー向上を目的とした新しいモデル適合方式を提案する。
  論文  参考訳（メタデータ） (2022-07-03T12:29:25Z)
• Statistical and Computational Phase Transitions in Group Testing [73.55361918807883]
  本研究の目的は、希少な疾患を患っているk人の集団を同定することである。 個々人のテストを割り当てるための2つの異なる単純なランダムな手順を考える。
  論文  参考訳（メタデータ） (2022-06-15T16:38:50Z)
• Sequential Permutation Testing of Random Forest Variable Importance Measures [68.8204255655161]
  そこで本研究では、逐次置換テストと逐次p値推定を用いて、従来の置換テストに関連する高い計算コストを削減することを提案する。 シミュレーション研究の結果、シーケンシャルテストの理論的性質が当てはまることを確認した。 本手法の数値安定性を2つの応用研究で検討した。
  論文  参考訳（メタデータ） (2022-06-02T20:16:50Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• Significance tests of feature relevance for a blackbox learner [6.72450543613463]
  ブラックボックス学習者の特徴関連性に関する2つの一貫した試験を導出する。 第1は、推論サンプルの摂動による損失差を評価する。 2つ目は推論サンプルを2つに分割するが、データの摂動は必要ない。
  論文  参考訳（メタデータ） (2021-03-02T00:59:19Z)
• Cross-validation Confidence Intervals for Test Error [83.67415139421448]
  この研究は、クロスバリデーションのための中心極限定理と、学習アルゴリズムの弱い安定性条件下での分散の一貫した推定器を開発する。 結果は、一般的な1対1のクロスバリデーションの選択にとって、初めてのものだ。
  論文  参考訳（メタデータ） (2020-07-24T17:40:06Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• The Chi-Square Test of Distance Correlation [7.748852202364896]
  チ二乗検定は非パラメトリックであり、非常に高速であり、強い負のタイプ計量または特徴核を用いてバイアス補正された距離相関に適用できる。 基礎となるカイ二乗分布は上尾部の制限零分布をよく近似し支配しており、カイ二乗試験が独立性テストに有効で一貫性があることを証明している。
  論文  参考訳（メタデータ） (2019-12-27T15:16:40Z)

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

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