論文の概要: Near-Optimal Bounds for Testing Histogram Distributions
- arxiv url: http://arxiv.org/abs/2207.06596v1
- Date: Thu, 14 Jul 2022 01:24:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-15 14:50:59.465546
- Title: Near-Optimal Bounds for Testing Histogram Distributions
- Title（参考訳）: ヒストグラム分布試験のための近接最適境界
- Authors: Cl\'ement L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Sihan
Liu
- Abstract要約: ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
- 参考スコア（独自算出の注目度）: 35.18069719489173
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of testing whether a discrete probability
distribution over an ordered domain is a histogram on a specified number of
bins. One of the most common tools for the succinct approximation of data,
$k$-histograms over $[n]$, are probability distributions that are piecewise
constant over a set of $k$ intervals. The histogram testing problem is the
following: Given samples from an unknown distribution $\mathbf{p}$ on $[n]$, we
want to distinguish between the cases that $\mathbf{p}$ is a $k$-histogram
versus $\varepsilon$-far from any $k$-histogram, in total variation distance.
Our main result is a sample near-optimal and computationally efficient
algorithm for this testing problem, and a nearly-matching (within logarithmic
factors) sample complexity lower bound. Specifically, we show that the
histogram testing problem has sample complexity $\widetilde \Theta (\sqrt{nk} /
\varepsilon + k / \varepsilon^2 + \sqrt{n} / \varepsilon^2)$.
- Abstract（参考訳）: 本研究では,順序領域上の離散確率分布が,指定された数のビンのヒストグラムであるかどうかを調べる。
データの簡潔な近似のための最も一般的なツールの1つ、$[n]$ に対する $k$-histograms は、一連の $k$ 間隔に対して区分的に定数な確率分布である。
未知分布のサンプル$\mathbf{p}$ on $[n]$を与えられた場合、$\mathbf{p}$が$k$-histogramであるのに対して$\varepsilon$-farが$k$-histogramである場合を、全変動距離で区別したい。
私たちの主な結果は、このテスト問題に対して、ほぼ最適で計算効率のよいサンプルアルゴリズムと、(対数係数を含む)サンプル複雑性を低く抑えることです。
具体的には、ヒストグラム検定問題はサンプル複雑性$\widetilde \Theta (\sqrt{nk} / \varepsilon + k / \varepsilon^2 + \sqrt{n} / \varepsilon^2)$であることを示す。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space [1.2277343096128712]
本稿では、ストリーミング設定において、空間$O(log4 varepsilon-1)$を使用するアルゴリズムを提供する。
また、私たちは9つの関連するオープンな問題を述べ、それと関連した問題への関心を喚起することを望んでいます。
論文 参考訳（メタデータ） (2024-10-29T15:24:27Z) - Testing Support Size More Efficiently Than Learning Histograms [0.18416014644193066]
分布のヒストグラムを$p$で学習するよりも, より効率的にテストを行うことができることを示す。
この証明は、チェビシェフ近似が良い近似であるように設計されている範囲外の分析に依存する。
論文 参考訳（メタデータ） (2024-10-24T17:05:34Z) - Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。
具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。
本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
論文 参考訳（メタデータ） (2023-11-22T04:34:09Z) - 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) - Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。
我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
論文 参考訳（メタデータ） (2022-10-27T05:11:00Z) - Gaussian Mean Testing Made Simple [46.03021473600576]
a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。
一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-25T01:59:13Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳（メタデータ） (2021-09-01T06:22:53Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。