論文の概要: Optimal Testing of Discrete Distributions with High Probability
- arxiv url: http://arxiv.org/abs/2009.06540v1
- Date: Mon, 14 Sep 2020 16:09:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 12:06:35.559685
- Title: Optimal Testing of Discrete Distributions with High Probability
- Title（参考訳）: 高確率離散分布の最適試験
- Authors: Ilias Diakonikolas and Themis Gouleakis and Daniel M. Kane and John
Peebles and Eric Price
- Abstract要約: 高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 49.19942805582874
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of testing discrete distributions with a focus on the
high probability regime. Specifically, given samples from one or more discrete
distributions, a property $\mathcal{P}$, and parameters $0< \epsilon, \delta
<1$, we want to distinguish {\em with probability at least $1-\delta$} whether
these distributions satisfy $\mathcal{P}$ or are $\epsilon$-far from
$\mathcal{P}$ in total variation distance. Most prior work in distribution
testing studied the constant confidence case (corresponding to $\delta =
\Omega(1)$), and provided sample-optimal testers for a range of properties.
While one can always boost the confidence probability of any such tester by
black-box amplification, this generic boosting method typically leads to
sub-optimal sample bounds.
Here we study the following broad question: For a given property
$\mathcal{P}$, can we {\em characterize} the sample complexity of testing
$\mathcal{P}$ as a function of all relevant problem parameters, including the
error probability $\delta$? Prior to this work, uniformity testing was the only
statistical task whose sample complexity had been characterized in this
setting. As our main results, we provide the first algorithms for closeness and
independence testing that are sample-optimal, within constant factors, as a
function of all relevant parameters. We also show matching
information-theoretic lower bounds on the sample complexity of these problems.
Our techniques naturally extend to give optimal testers for related problems.
To illustrate the generality of our methods, we give optimal algorithms for
testing collections of distributions and testing closeness with unequal sized
samples.
- Abstract（参考訳）: 本研究では,高確率分布に着目した離散分布テストの問題について検討する。
具体的には、1つ以上の離散分布のサンプルが与えられたとき、$\mathcal{P}$とパラメータ$0< \epsilon, \delta <1$とすると、これらの分布が$\mathcal{P}$を満足するか、または$\epsilon$-farを$\mathcal{P}$と$\mathcal{P}$を全変動距離で区別したい。
分散テストにおけるほとんどの以前の研究は、一定の信頼性ケース($\delta = \Omega(1)$)を研究し、様々な特性に対してサンプル最適化テスターを提供した。
ブラックボックス増幅により、常にそのようなテスターの信頼確率を高めることができるが、この一般的なブースティング法は、通常、準最適サンプル境界につながる。
与えられたプロパティ$\mathcal{P}$に対して、エラー確率$\delta$を含むすべての関連する問題パラメータの関数として$\mathcal{P}$をテストする際のサンプルの複雑さを特徴づけることができるか?
この研究に先立ち、一様性テストは、この設定でサンプルの複雑さを特徴付ける唯一の統計的タスクであった。
主な結果として,すべてのパラメータの関数として,サンプル最適であり,定数係数内に存在する近さと独立性テストのための最初のアルゴリズムを提供する。
また、これらの問題のサンプル複雑性について、マッチング情報理論の下限を示す。
我々のテクニックは自然に拡張され、関連する問題に対して最適なテスターを与えます。
提案手法の一般性を説明するため,分布の集合をテストし,不等サイズのサンプルを用いて近接性をテストするアルゴリズムを提案する。
関連論文リスト
- Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
論文 参考訳（メタデータ） (2022-07-14T01:24:01Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳（メタデータ） (2022-06-21T20:43:53Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - 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) - Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
論文 参考訳（メタデータ） (2020-07-15T02:46:44Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。