論文の概要: Replicable Distribution Testing
- arxiv url: http://arxiv.org/abs/2507.02814v1
- Date: Thu, 03 Jul 2025 17:27:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-04 15:37:16.77032
- Title: Replicable Distribution Testing
- Title（参考訳）: レプリケーション可能な分散テスト
- Authors: Ilias Diakonikolas, Jingyi Gao, Daniel Kane, Sihan Liu, Christopher Ye,
- Abstract要約: 独立したサンプルが与えられた場合、その目的は、基礎となる分布の自然特性を複製的にテストするサンプルの複雑さを特徴づけることである。
アルゴリズム面では、離散分布の近接性と独立性をテストするための新しいアルゴリズムを開発する。
低境界面上では、レプリカブルテストのためのサンプル複雑性の低い境界を証明するための新しい方法論を開発する。
- 参考スコア（独自算出の注目度）: 38.76577965182225
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, we develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity testing -- answering an open question from prior work -- and closeness testing.
- Abstract（参考訳）: 我々は,アルゴリズムの複製可能性の枠組みにおける分布試験の体系的な研究を開始する。
具体的には、確率分布の集合から独立したサンプルが与えられた場合、その目的は、基礎となる分布の自然特性を複製的にテストするサンプルの複雑さを特徴づけることである。
アルゴリズム面では、離散分布の近接性と独立性をテストするための新しいレプリカブルアルゴリズムを開発する。
低境界面では、より広い関心を持つであろうレプリカブルテストにおいて、サンプル複雑性の低い境界を証明するための新しい方法論を開発する。
この手法の適用例として、複製可能な均一性テスト -- 以前の作業からのオープンな質問に答える -- とクローズネステスト -- において、ほぼ最適なサンプル複雑性の低い境界を確立する。
関連論文リスト
- Optimal Algorithms for Augmented Testing of Discrete Distributions [25.818433126197036]
予測器は3つのプロパティテストタスクすべてに必要なサンプル数を実際に削減できることを示す。
我々のアルゴリズムの重要な利点は、予測の精度への適応性である。
アルゴリズムによって達成されるサンプルの複雑さの改善は、情報理論的に最適であることを示すために、より低い境界を提供する。
論文 参考訳（メタデータ） (2024-12-01T21:31:22Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization [26.4468964378511]
複製可能なアルゴリズムは、そのランダム性が固定されたときに高い確率で同じ出力を与える。
データ解析にレプリカブルアルゴリズムを使用することで、公開結果の検証が容易になる。
我々は、複製性とアルゴリズム安定性の標準概念との新たな接続と分離を確立する。
論文 参考訳（メタデータ） (2023-03-22T21:35:50Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Communication-constrained hypothesis testing: Optimality, robustness,
and reverse data processing inequalities [8.010966370223985]
通信制約下での単純な二項仮説テストのサンプルの複雑さは、少なくとも制約のない設定よりも大きい対数係数であることが示される。
我々のフレームワークは、分布が全変動距離で破壊されるような頑健な仮説テストにまで拡張する。
論文 参考訳（メタデータ） (2022-06-06T17:42:11Z) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。
我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文 参考訳（メタデータ） (2020-11-17T05:41:50Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳（メタデータ） (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。