論文の概要: The Minimax Risk in Histogram-Based Uniformity Testing under Missing
Ball Alternatives
- arxiv url: http://arxiv.org/abs/2305.18111v5
- Date: Mon, 20 Nov 2023 07:52:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 19:24:02.339166
- Title: The Minimax Risk in Histogram-Based Uniformity Testing under Missing
Ball Alternatives
- Title(参考訳): ボール代替品におけるヒストグラムによる一様性検査におけるミニマックスリスク
- Authors: Alon Kipnis
- Abstract要約: そこで本研究では,多くのカテゴリから一様分布への離散サンプルの適合性テストの問題点について検討する。
ミニマックステストは、非常に小さなサンプル限界での衝突に大きく依存するが、それ以外はチフタッドテストのように振る舞う。
- 参考スコア(独自算出の注目度): 8.285441115330944
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of testing the goodness of fit of a discrete sample from
many categories to the uniform distribution over the categories. As a class of
alternative hypotheses, we consider the removal of an $\ell_p$ ball of radius
$\epsilon$ around the uniform rate sequence for $p \leq 2$. When the number of
samples $n$ and number of categories $N$ go to infinity while $\epsilon$ is
small, the minimax risk $R_\epsilon^*$ in testing based on the sample's
histogram (number of absent categories, singletons, collisions, ...) asymptotes
to $2\Phi(-n N^{2-2/p} \epsilon^2/\sqrt{8N})$; $\Phi(x)$ is the normal CDF.
This result allows the comparison of the many estimators previously proposed
for this problem at the constant level, rather than at the rate of convergence
of the risk or the scaling order of the sample complexity. The minimax test
mostly relies on collisions in the very small sample limit but otherwise
behaves like the chisquared test. Empirical studies over a range of problem
parameters show that our estimate is accurate in finite samples and that the
minimax test is significantly better than the chisquared test or a test that
only uses collisions. Our analysis relies on the asymptotic normality of
histogram ordinates, the equivalence between the minimax setting and a Bayesian
setting, and the characterization of the least favorable prior by reducing a
multi-dimensional optimization problem to a one-dimensional problem.
- Abstract(参考訳): 本研究では,多くのカテゴリからカテゴリ上の一様分布への離散サンプルの適合性をテストする問題について検討する。
代替仮説のクラスとして、半径$\epsilon$ の $\ell_p$ の球を、$p \leq 2$ の均一レート列の周りに取り除くことを考える。
サンプル数$n$とカテゴリ数$N$が無限大へ、$\epsilon$が小さければ、サンプルのヒストグラム(不備なカテゴリ数、シングルトン数、衝突数、...)に基づくテストにおいて、ミニマックスリスク$R_\epsilon^*$が2\Phi(-n N^{2-2/p} \epsilon^2/\sqrt{8N})$;$\Phi(x)$は通常のCDFである。
この結果により、リスクの収束率やサンプルの複雑さのスケーリング順序よりも、この問題に対して以前に提案された多くの推定器を一定レベルで比較することができる。
ミニマックステストは、非常に小さなサンプル限界での衝突に大きく依存するが、それ以外はチフタッドテストのように振る舞う。
種々の問題パラメータに関する実証的な研究により、我々の推定は有限標本において正確であり、最小値検定はチフタッド検定や衝突のみを用いる検定よりもはるかに優れていることが示された。
本解析は,ヒストグラム順序の漸近的正規性,ミニマックス設定とベイズ設定の等価性,および多次元最適化問題を1次元問題に還元することにより,最善の優先条件のキャラクタリゼーションに依存する。
関連論文リスト
- Minimax Optimality of Score-based Diffusion Models: Beyond the Density
Lower Bound Assumptions [12.260288510756796]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳(メタデータ) (2024-02-23T20:51:31Z) - Optimal minimax rate of learning interaction kernels [7.329333373512536]
広帯域の交換可能な分布に対して最適な収束率を得るための最小二乗推定器(tLSE)を導入する。
以上の結果から, 大きな試料限界の逆問題が保たれた場合, 左テール確率はバイアス分散トレードオフを変化させないことがわかった。
論文 参考訳(メタデータ) (2023-11-28T15:01:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳(メタデータ) (2022-06-21T20:43: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) - Dimension-agnostic inference using cross U-statistics [39.27033181001605]
本稿では,サンプル分割と自己正規化とともに,既存のテスト統計の変分表現を用いた手法を提案する。
結果の統計学は、縮退したU統計を慎重に修正し、対角ブロックを落とし、対角ブロックを外したままにすると見なすことができる。
論文 参考訳(メタデータ) (2020-11-10T12:21:34Z) - 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) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳(メタデータ) (2020-05-21T17:51:30Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。