論文の概要: Sharp Constants in Uniformity Testing via the Huber Statistic
- arxiv url: http://arxiv.org/abs/2206.10722v1
- Date: Tue, 21 Jun 2022 20:43:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-24 08:55:40.021514
- Title: Sharp Constants in Uniformity Testing via the Huber Statistic
- Title（参考訳）: Huber Statisticによる一様性テストのシャープ定数
- Authors: Shivam Gupta, Eric Price
- Abstract要約: 一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
- 参考スコア（独自算出の注目度）: 16.384142529375435
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Uniformity testing is one of the most well-studied problems in property
testing, with many known test statistics, including ones based on counting
collisions, singletons, and the empirical TV distance. It is known that the
optimal sample complexity to distinguish the uniform distribution on $m$
elements from any $\epsilon$-far distribution with $1-\delta$ probability is $n
= \Theta\left(\frac{\sqrt{m \log (1/\delta)}}{\epsilon^2} + \frac{\log
(1/\delta)}{\epsilon^2}\right)$, which is achieved by the empirical TV tester.
Yet in simulation, these theoretical analyses are misleading: in many cases,
they do not correctly rank order the performance of existing testers, even in
an asymptotic regime of all parameters tending to $0$ or $\infty$.
We explain this discrepancy by studying the \emph{constant factors} required
by the algorithms. We show that the collisions tester achieves a sharp maximal
constant in the number of standard deviations of separation between uniform and
non-uniform inputs. We then introduce a new tester based on the Huber loss, and
show that it not only matches this separation, but also has tails corresponding
to a Gaussian with this separation. This leads to a sample complexity of $(1 +
o(1))\frac{\sqrt{m \log (1/\delta)}}{\epsilon^2}$ in the regime where this term
is dominant, unlike all other existing testers.
- Abstract（参考訳）: 均一性テストはプロパティテストにおいて最もよく研究されている問題の1つであり、数え上げ衝突、シングルトン、経験的テレビ距離に基づくものなど、多くの既知のテスト統計がある。
1-\delta$確率の任意の$\epsilon$-far分布と$m$要素の均一分布を区別する最適なサンプル複雑性は、経験的テレビテスタによって達成される$n = \theta\left(\frac{\sqrt{m \log (1/\delta)}}{\epsilon^2} + \frac{\log (1/\delta)}{\epsilon^2}\right)$であることが知られている。
多くの場合、それらは、0$または$\infty$である傾向のあるパラメータの漸近的なシステムでさえも、既存のテスターのパフォーマンスを正しくランク付けしていない。
この不一致を,アルゴリズムが要求する非定常因子の研究によって説明する。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
次に、Huberの損失に基づく新しいテスタを導入し、この分離と一致するだけでなく、この分離とガウスに対応する尾を持つことを示す。
これは、他の既存のテスターとは異なり、この用語が支配的な体制において、サンプルの複雑さは$(1 + o(1))\frac{\sqrt{m \log (1/\delta)}}{\epsilon^2}$となる。
関連論文リスト
- Replicable Uniformity Testing [1.5883812630616523]
この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。
我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
論文 参考訳（メタデータ） (2024-10-12T02:55:17Z) - The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。
この問題は、$alpha = beta$ (prior-free) または $alpha = 1/2$ (Bayesian) でのみ研究されている。
論文 参考訳（メタデータ） (2024-03-25T17:42:32Z) - Testing with Non-identically Distributed Samples [20.74768558932617]
本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。
それぞれのディストリビューションから$Theta(k/varepsilon2)$サンプルをサンプリングしても、$textbfp_mathrmavg$は、テレビ距離で$textbfp_mathrmavg$をエラー$varepsilon$内で学習するのに十分である。
論文 参考訳（メタデータ） (2023-11-19T01:25:50Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。