論文の概要: Replicable Uniformity Testing

• arxiv url: http://arxiv.org/abs/2410.10892v1
• Date: Sat, 12 Oct 2024 02:55:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-16 14:03:27.795980
• Title: Replicable Uniformity Testing
• Title（参考訳）: Replicable Uniformity Testing
• Authors: Sihan Liu, Christopher Ye,
• Abstract要約: この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。 我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
• 参考スコア（独自算出の注目度）: 1.5883812630616523
• License:
• Abstract: Uniformity testing is arguably one of the most fundamental distribution testing problems. Given sample access to an unknown distribution $\mathbf{p}$ on $[n]$, one must decide if $\mathbf{p}$ is uniform or $\varepsilon$-far from uniform (in total variation distance). A long line of work established that uniformity testing has sample complexity $\Theta(\sqrt{n}\varepsilon^{-2})$. However, when the input distribution is neither uniform nor far from uniform, known algorithms may have highly non-replicable behavior. Consequently, if these algorithms are applied in scientific studies, they may lead to contradictory results that erode public trust in science. In this work, we revisit uniformity testing under the framework of algorithmic replicability [STOC '22], requiring the algorithm to be replicable under arbitrary distributions. While replicability typically incurs a $\rho^{-2}$ factor overhead in sample complexity, we obtain a replicable uniformity tester using only $\tilde{O}(\sqrt{n} \varepsilon^{-2} \rho^{-1})$ samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on $\rho$. Lastly, we consider a class of ``symmetric" algorithms [FOCS '00] whose outputs are invariant under relabeling of the domain $[n]$, which includes all existing uniformity testers (including ours). For this natural class of algorithms, we prove a nearly matching sample complexity lower bound for replicable uniformity testing.
• Abstract（参考訳）: 均一性テストは間違いなく最も基本的な分散テスト問題の1つである。 未知分布へのサンプルアクセス $\mathbf{p}$ on $[n]$ が与えられたとき、$\mathbf{p}$ が一様であるか、あるいは一様(全変動距離)から$\varepsilon$-far かを決定する必要がある。 一様性テストはサンプル複雑性$\Theta(\sqrt{n}\varepsilon^{-2})$である。 しかし、入力分布が一様でも一様でもない場合、既知のアルゴリズムは非常に再現不能な振る舞いを持つ可能性がある。 したがって、これらのアルゴリズムが科学研究に応用されれば、科学に対する一般の信頼を損なう矛盾した結果につながる可能性がある。 本研究では,アルゴリズムの複製性(STOC '22] の枠組みの下で一様性テストを再検討し,任意の分布下ではアルゴリズムを複製可能であることを要求した。 レプリカ性は通常、サンプルの複雑さにおいて$\rho^{-2}$因子のオーバーヘッドを生じるが、$\tilde{O}(\sqrt{n} \varepsilon^{-2} \rho^{-1})$サンプルのみを用いてレプリカ可能な均一性テスターを得る。 我々の知る限り、これは(ほぼ)$\rho$への線形依存を持つ最初のレプリカブル学習アルゴリズムである。 最後に, [FOCS '00] の出力が領域$[n]$の緩和の下で不変であるような, ``symmetric' アルゴリズムのクラスを考える。 この自然なアルゴリズムのクラスに対して、複製可能な一様性検定のために、ほぼ一致するサンプルの複雑さを低く証明する。

関連論文リスト

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  生成モデルにアクセス可能なディスカウント型MDPの基本設定に焦点をあてる。 ImpagliazzoらにインスパイアされたRLアルゴリズムは、高い確率で2回の実行後に全く同じポリシーを出力した場合、複製可能である。
  論文  参考訳（メタデータ） (2023-05-31T05:16:23Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling [5.3098033683382155]
  本研究では,高次元分布におけるアイデンティティテスト問題について検討する。 私たちは、$mathsfCoordinate Oracle$という、非常に弱い条件付きサンプリングオラクルを考えています。 エントロピーの近似テンソル化(英語版)として知られる解析的性質が$n$-次元可視分布$mu$に対して成り立つならば、$tildeO(n/varepsilon)$クエリを使用して、隠れ分布$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
  論文  参考訳（メタデータ） (2022-07-19T06:49:24Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。 1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。 衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-21T20:43:53Z)
• Private High-Dimensional Hypothesis Testing [4.133655523622441]
  我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。 具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
  論文  参考訳（メタデータ） (2022-03-03T06:25:48Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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