論文の概要: Extrapolating the profile of a finite population
- arxiv url: http://arxiv.org/abs/2005.10561v1
- Date: Thu, 21 May 2020 10:39:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 00:06:18.267553
- Title: Extrapolating the profile of a finite population
- Title(参考訳): 有限集団のプロファイルを外挿する
- Authors: Soham Jana, Yury Polyanskiy and Yihong Wu
- Abstract要約: 経験的ベイズにおける原型的問題を考察する。すなわち、$k$の個体群は、それぞれ$k$の個体群である。
我々は、$m =omega(k/log k)$ の部分線型状態において、集団の自明な全変動を一貫して見積もることができることを示す。
- 参考スコア(独自算出の注目度): 35.69057741775438
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a prototypical problem in empirical Bayes. Namely, consider a
population consisting of $k$ individuals each belonging to one of $k$ types
(some types can be empty). Without any structural restrictions, it is
impossible to learn the composition of the full population having observed only
a small (random) subsample of size $m = o(k)$. Nevertheless, we show that in
the sublinear regime of $m =\omega(k/\log k)$, it is possible to consistently
estimate in total variation the \emph{profile} of the population, defined as
the empirical distribution of the sizes of each type, which determines many
symmetric properties of the population. We also prove that in the linear regime
of $m=c k$ for any constant $c$ the optimal rate is $\Theta(1/\log k)$. Our
estimator is based on Wolfowitz's minimum distance method, which entails
solving a linear program (LP) of size $k$. We show that there is a single
infinite-dimensional LP whose value simultaneously characterizes the risk of
the minimum distance estimator and certifies its minimax optimality. The sharp
convergence rate is obtained by evaluating this LP using complex-analytic
techniques.
- Abstract(参考訳): 我々は経験ベイズにおける原型的問題を研究する。
すなわち、$k$の個人からなる集団は、それぞれ$k$のタイプに属する(いくつかの型は空である)。
構造的な制限がなければ、m = o(k)$ の小さな(ランダムな)サブサンプルしか観測していない全人口の構成を知ることは不可能である。
それにもかかわらず、$m =\omega(k/\log k)$ の部分線型状態において、各タイプのサイズの経験的分布として定義される集団の全体の変動を一貫して推定することができ、その集団の多くの対称特性を決定することができる。
また、任意の定数 $c$ に対して $m=c k$ の線形レジームにおいて、最適レートは $\theta(1/\log k)$ であることが証明される。
我々の推定器は、Wolfowitzの最小距離法に基づいており、これは、長さ$k$の線形プログラム(LP)を解くことを必要とする。
最小距離推定器のリスクを同時に特徴づけ、その最小値の最適性を証明した単一の無限次元LPが存在することを示す。
このLPを複素解析法を用いて評価することにより, 鋭収束率を得る。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Debiasing and a local analysis for population clustering using
semidefinite programming [1.9761774213809036]
サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
論文 参考訳(メタデータ) (2024-01-16T03:14:24Z) - Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation [7.693388437377614]
任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
論文 参考訳(メタデータ) (2023-10-10T04:02:43Z) - On Computationally Efficient Learning of Exponential Family
Distributions [33.229944519289795]
我々は、サポートと自然なパラメータが適切にバウンドされている設定に焦点を当てる。
本手法は,ノードワイズ・スパースランダムフィールドに適した場合,$O(sf log(k)/alpha2)$のオーダー最適サンプル複雑性を実現する。
論文 参考訳(メタデータ) (2023-09-12T17:25:32Z) - Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。
両課題を適度な条件下で克服する簡易平均推定器を提案する。
私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
論文 参考訳(メタデータ) (2023-05-24T16:02:28Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。
準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
論文 参考訳(メタデータ) (2022-05-27T02:02:17Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。