論文の概要: On the Structure of Replicable Hypothesis Testers

• arxiv url: http://arxiv.org/abs/2507.02842v1
• Date: Thu, 03 Jul 2025 17:51:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.455153
• Title: On the Structure of Replicable Hypothesis Testers
• Title（参考訳）: Replicable hypothesis Testerの構造について
• Authors: Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Shyam Narayanan, Sandeep Silwal,
• Abstract要約: 仮説テストアルゴリズムは、同じ分布から2つの異なるサンプルを走らせると、高い確率で同じ出力を生成する場合に複製可能である。 レプリカ可能なテスタのサンプル複雑性に対して,下限と上限を証明するための一般的なツールを構築します。 正準特性の集合を同定し、これらの特性を満たすために任意のレプリカブルなテストアルゴリズムを変更可能であることを証明する。
• 参考スコア（独自算出の注目度）: 19.10307834463581
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results. We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in $[0,1]$. It is invariant to the order in which the samples are received, and, if the testing problem is ``symmetric,'' then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties. We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free in a large parameter regime for uniformity testing. We also give state-of-the-art bounds for replicable Gaussian mean testing, and, unlike prior work, our algorithm runs in polynomial time.
• Abstract（参考訳）: 仮説テストアルゴリズムは、同じ分布から2つの異なるサンプルを走らせると、高い確率で同じ出力を生成する場合に複製可能である。 Impagliazzo, Lei, Pitassi, Sorell (STOC'22) によって定義されたこの概念は、テスト手順に対する信頼を高め、アルゴリズムの安定性、一般化、プライバシーに深く関係している。 我々は、複製可能なテスタのサンプルの複雑さを下限と上限で証明し、既存の結果を統一し、定量的に改善する一般的なツールを構築します。 標準特性の集合を同定し、これらの特性を満たすために複製可能なテストアルゴリズムを、精度やサンプルの複雑さを悪化させることなく変更できることを証明する。 正準レプリカブルアルゴリズムは、入力の確定関数(すなわち、テスト統計)と、一様ランダムな値に対する閾値を$[0,1]$で計算する。 サンプルが受信される順序に不変であり、もしテスト問題が ''対称' であれば、アルゴリズムはドメイン要素のラベル付けにも不変であり、Liu と Ye [NeurIPS'24] によって解かれる。 レプリカブルアルゴリズムがこれらの標準特性を満たす場合に限って、均一性、同一性、近接性テストのための新しい下限を証明した。 我々は、既知の期待値と有界分散値を持つテスト統計に基づいて、複製可能なアルゴリズム設計のための共通戦略を体系化し、改善する。 当社のフレームワークでは、リプライ不可能な設定で広範囲に分析されたテスタを、最小限のオーバーヘッドでレプリカ化することが可能です。 本フレームワークの直接的応用として,コインテストとクローズネステストのための定数係数最適境界を求め,一様性テストのための大きなパラメータ構造において,レプリカ性を無償で取得する。 我々はまた、複製可能なガウス平均テストの最先端境界を与え、以前の研究とは異なり、我々のアルゴリズムは多項式時間で実行される。

関連論文リスト

• Replicable Distribution Testing [38.76577965182225]
  独立したサンプルが与えられた場合、その目的は、基礎となる分布の自然特性を複製的にテストするサンプルの複雑さを特徴づけることである。 アルゴリズム面では、離散分布の近接性と独立性をテストするための新しいアルゴリズムを開発する。 低境界面上では、レプリカブルテストのためのサンプル複雑性の低い境界を証明するための新しい方法論を開発する。
  論文  参考訳（メタデータ） (2025-07-03T17:27:11Z)
• Minimax Optimal Kernel Two-Sample Tests with Random Features [8.030917052755195]
  ランダムフーリエ特徴量(RFF)近似に基づくスペクトル正規化2サンプル試験を提案する。 RFFの近似順序が十分に大きい場合、提案した試験が最小限最適であることを示す。 そこで本研究では,正規化パラメータとカーネルを選択するためのデータ適応型戦略を用いて,提案したテストの実用的実装可能な置換型バージョンを開発する。
  論文  参考訳（メタデータ） (2025-02-28T06:12:00Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Replicability in High Dimensional Statistics [18.543059748500358]
  本稿では,いくつかの基本的高次元統計課題に対する再現性の計算的および統計的コストについて検討する。 我々の主な貢献は、最適なレプリカブルアルゴリズムと高次元等尺波の計算的および統計的等価性を確立することである。
  論文  参考訳（メタデータ） (2024-06-04T00:06:42Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization [26.4468964378511]
  複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。 データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。 我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
  論文  参考訳（メタデータ） (2023-03-22T21:35:50Z)
• Sequential Permutation Testing of Random Forest Variable Importance Measures [68.8204255655161]
  そこで本研究では、逐次置換テストと逐次p値推定を用いて、従来の置換テストに関連する高い計算コストを削減することを提案する。 シミュレーション研究の結果、シーケンシャルテストの理論的性質が当てはまることを確認した。 本手法の数値安定性を2つの応用研究で検討した。
  論文  参考訳（メタデータ） (2022-06-02T20:16:50Z)
• Group Testing with Non-identical Infection Probabilities [59.96266198512243]
  そこで我々は,集合形成法を用いた適応型グループテストアルゴリズムを開発した。 提案アルゴリズムは, エントロピー下界に近い性能を示す。
  論文  参考訳（メタデータ） (2021-08-27T17:53:25Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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