論文の概要: The minimax risk in testing the histogram of discrete distributions for
uniformity under missing ball alternatives
- arxiv url: http://arxiv.org/abs/2305.18111v1
- Date: Mon, 29 May 2023 14:26:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 14:52:04.522753
- Title: The minimax risk in testing the histogram of discrete distributions for
uniformity under missing ball alternatives
- Title（参考訳）: ボールオルタナティブが欠如する一様性に対する離散分布ヒストグラムの試験におけるミニマックスリスク
- Authors: Alon Kipnis
- Abstract要約: 本論では,多くのカテゴリから一様分布に至るまでの項目の離散的なサンプルの適合性をテストすることの問題点を考察する。
サンプルの数と次元の数が無限に近づくにつれて、$epsilon が 0$ になるときのミニマックスリスクを鋭く特徴づける。
様々な問題パラメータに関する実証的研究は、この推定が有限標本において正確であることを示している。
- 参考スコア（独自算出の注目度）: 10.926992035470372
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of testing the fit of a discrete sample of items 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$. We deliver a sharp
characterization of the asymptotic minimax risk when $\epsilon \to 0$ as the
number of samples and number of dimensions go to infinity, for testing based on
the occurrences' histogram (number of absent categories, singletons,
collisions, ...). For example, for $p=1$ and in the limit of a small expected
number of samples $n$ compared to the number of categories $N$ (aka
"sub-linear" regime), the minimax risk $R^*_\epsilon$ asymptotes to $2
\bar{\Phi}\left(n \epsilon^2/\sqrt{8N}\right) $, with $\bar{\Phi}(x)$ the
normal survival function. Empirical studies over a range of problem parameters
show that this estimate is accurate in finite samples, and that our test is
significantly better than the chisquared test or a test that only uses
collisions. Our analysis is based on the asymptotic normality of histogram
ordinates, the equivalence between the minimax setting to a Bayesian one, and
the reduction of a multi-dimensional optimization problem to a one-dimensional
problem.
- Abstract（参考訳）: 我々は,多くのカテゴリからカテゴリ上の一様分布への離散的サンプルの適合性をテストする問題を考える。
代替仮説のクラスとして、半径$\epsilon$ の $\ell_p$ の球を、$p \leq 2$ の均一レート列の周りに取り除くことを考える。
標本の数と次元の数が無限になるに従って$\epsilon \to 0$のとき、漸近的ミニマックスのリスクを鋭く特徴づけ、発生のヒストグラム(不在のカテゴリ、シングルトン、衝突、...)に基づいてテストする。
例えば、$p=1$ と、期待されるサンプル数の制限で$n$ は、カテゴリー数$n$ (別名 "sub-linear" regime) と比較して、minimax リスク $r^*_\epsilon$ asymptotes to $2 \bar{\phi}\left(n \epsilon^2/\sqrt{8n}\right) $, with $\bar{\phi}(x)$ は通常の生存関数である。
種々の問題パラメータに関する実証的な研究により、この推定は有限標本において正確であり、我々のテストは衝突のみを用いるチフタッドテストやテストよりもはるかに優れていることが示された。
本解析は,ヒストグラム順序の漸近正規性,ミニマックス設定とベイズ設定の等価性,多次元最適化問題の1次元問題への還元に基づく。
関連論文リスト
- Wasserstein F-tests for Fréchet regression on Bures-Wasserstein manifolds [0.9514940899499753]
ビュール・ワッサーシュタイン多様体上のフレシェレグレッションが発展する。
非関連性の零仮説のテストが提案されている。
結果は,提案した試験が所望の有意な程度に有意であることを示している。
論文 参考訳（メタデータ） (2024-04-05T04:01:51Z) - Optimal minimax rate of learning interaction kernels [7.329333373512536]
広帯域の交換可能な分布に対して最適な収束率を得るための最小二乗推定器(tLSE)を導入する。
以上の結果から, 大きな試料限界の逆問題が保たれた場合, 左テール確率はバイアス分散トレードオフを変化させないことがわかった。
論文 参考訳（メタデータ） (2023-11-28T15:01:58Z) - Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳（メタデータ） (2022-06-21T20:43:53Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - 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) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。