論文の概要: Estimating the size of a set using cascading exclusion

• arxiv url: http://arxiv.org/abs/2508.05901v1
• Date: Thu, 07 Aug 2025 23:36:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.029491
• Title: Estimating the size of a set using cascading exclusion
• Title（参考訳）: カスケード排除を用いた集合の大きさの推定
• Authors: Sourav Chatterjee, Persi Diaconis, Susan Holmes,
• Abstract要約: 一般的な非漸近論が展開されている。 一般定理は、すべての場合において非パラメトリック有限$n$誤差境界を与える。
• 参考スコア（独自算出の注目度）: 5.052293146674794
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $S$ be a finite set, and $X_1,\ldots,X_n$ an i.i.d. uniform sample from $S$. To estimate the size $|S|$, without further structure, one can wait for repeats and use the birthday problem. This requires a sample size of the order $|S|^\frac{1}{2}$. On the other hand, if $S=\{1,2,\ldots,|S|\}$, the maximum of the sample blown up by $n/(n-1)$ gives an efficient estimator based on any growing sample size. This paper gives refinements that interpolate between these extremes. A general non-asymptotic theory is developed. This includes estimating the volume of a compact convex set, the unseen species problem, and a host of testing problems that follow from the question `Is this new observation a typical pick from a large prespecified population?' We also treat regression style predictors. A general theorem gives non-parametric finite $n$ error bounds in all cases.
• Abstract（参考訳）: S$ を有限集合とし、$X_1,\ldots,X_n$ を $S$ から i.i.d. の一様標本とする。 サイズを$|S|$と見積もるには、さらなる構造を使わずに、繰り返しを待つことができ、誕生日問題を使用することができる。 これは位数 $|S|^\frac{1}{2}$ のサンプルサイズを必要とする。 一方、$S=\{1,2,\ldots,|S|\}$ の場合、サンプルの最大値$n/(n-1)$ は、任意の増大するサンプルサイズに基づいて効率的な推定値を与える。 この論文は、これらの極端間を補間する精細化を与える。 一般的な非漸近論が展開されている。 これには、コンパクト凸集合の体積の推定、目に見えない種問題、そして「この新観測は、大集団の典型的な選択なのか?」という疑問から続く一連のテスト問題が含まれる。 また、回帰式予測器も扱う。 一般定理は、すべての場合において非パラメトリック有限$n$誤差境界を与える。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
  単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。 i) all $0 le alpha, beta le 1/8$ in the pre-free set, and (ii) all $delta le pi/4$ in the Bayesian set。
  論文  参考訳（メタデータ） (2024-03-25T17:42:32Z)
• Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes [5.00389879175348]
  実数値の幾何学的エルゴード的マルコフ過程の個々の$beta$-mixing係数を1つのサンプルパスから推定する。 予想される誤差率は$mathcal O(log(n) n-1/2)$である。
  論文  参考訳（メタデータ） (2024-02-11T20:17:10Z)
• On the Multidimensional Random Subset Sum Problem [0.9007371440329465]
  確率変数 $X_1, ..., X_n$ が与えられたランダム部分集合 Sum 問題では、任意の点 $z in [-1,1]$ を部分集合 $X_i_1(z), ..., X_i_s(z)$ の和として近似したい。 我々は、$d$次元において、$n = O(d3log frac 1varepsilon cdot
  論文  参考訳（メタデータ） (2022-07-28T08:10:43Z)
• 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)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。