論文の概要: The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian
Mixtures
- arxiv url: http://arxiv.org/abs/2103.15653v1
- Date: Mon, 29 Mar 2021 14:28:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-30 14:31:34.607692
- Title: The EM Algorithm is Adaptively-Optimal for Unbalanced Symmetric Gaussian
Mixtures
- Title（参考訳）: 非平衡対称ガウス混合に対するEMアルゴリズムの適応最適性
- Authors: Nir Weinberger and Guy Bresler
- Abstract要約: EMアルゴリズムは、$tildeOBig(minBigfrac1(1-2delta_*)sqrtfracdn,frac1|theta_*|sqrtfracdn,left(fracdnright)1/4BigBig)$を$OBig(frac1|theta_*|2Big以下で適応的に達成することを示した。
- 参考スコア（独自算出の注目度）: 36.91281862322494
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the problem of estimating the means
$\pm\theta_{*}\in\mathbb{R}^{d}$ of a symmetric two-component Gaussian mixture
$\delta_{*}\cdot N(\theta_{*},I)+(1-\delta_{*})\cdot N(-\theta_{*},I)$ where
the weights $\delta_{*}$ and $1-\delta_{*}$ are unequal. Assuming that
$\delta_{*}$ is known, we show that the population version of the EM algorithm
globally converges if the initial estimate has non-negative inner product with
the mean of the larger weight component. This can be achieved by the trivial
initialization $\theta_{0}=0$. For the empirical iteration based on $n$
samples, we show that when initialized at $\theta_{0}=0$, the EM algorithm
adaptively achieves the minimax error rate
$\tilde{O}\Big(\min\Big\{\frac{1}{(1-2\delta_{*})}\sqrt{\frac{d}{n}},\frac{1}{\|\theta_{*}\|}\sqrt{\frac{d}{n}},\left(\frac{d}{n}\right)^{1/4}\Big\}\Big)$
in no more than $O\Big(\frac{1}{\|\theta_{*}\|(1-2\delta_{*})}\Big)$ iterations
(with high probability). We also consider the EM iteration for estimating the
weight $\delta_{*}$, assuming a fixed mean $\theta$ (which is possibly
mismatched to $\theta_{*}$). For the empirical iteration of $n$ samples, we
show that the minimax error rate
$\tilde{O}\Big(\frac{1}{\|\theta_{*}\|}\sqrt{\frac{d}{n}}\Big)$ is achieved in
no more than $O\Big(\frac{1}{\|\theta_{*}\|^{2}}\Big)$ iterations. These
results robustify and complement recent results of Wu and Zhou obtained for the
equal weights case $\delta_{*}=1/2$.
- Abstract（参考訳）: 本稿では,対称な2成分ガウス混合系である$\delta_{*}\cdot n(\theta_{*},i)+(1-\delta_{*})\cdot n(-\theta_{*},i)$ の$\pm\theta_{*}\in\mathbb{r}^{d}$ を推定する問題について検討する。
$\delta_{*}$ が知られていると仮定すると、初期推定値がより大きい重み成分の平均を持つ非負の内積を持つ場合、EMアルゴリズムの集団バージョンは全世界的に収束する。
これは自明な初期化 $\theta_{0}=0$ によって達成できる。
n$のサンプルに基づく経験的反復に対して、$\theta_{0}=0$で初期化されると、EMアルゴリズムはミニマックス誤差率$\tilde{O}\Big(\min\Big\{\frac{1}{(1-2\delta_{*})}\sqrt {\frac{d}{n}},\frac{1}{\|\theta_{*}\|}\sqrt{\frac{d}{n}},\left(\frac{d}{n}\right)^{1/4}\\\\\Big)$が$O\Big(\frac{1}{\|\theta_{*}\|(1-2\delta_{*})}\sqrt{\frac{d}{n}},\left(\frac{d}{n}\right)^{1/4}\\\\Big)$を適応的に達成していることを示す。
また、固定平均$\theta$(これはおそらく$\theta_{*}$と一致している)を仮定して、重量を$\delta_{*}$と見積もるEM反復を考える。
n$サンプルの実証的な反復について、ミニマックス誤差率$\tilde{O}\Big(\frac{1}{\|\theta_{*}\|}\sqrt {\frac{d}{n}}\Big)$が$O\Big(\frac{1}{\|\theta_{*}\|^{2}}\Big)$反復で達成されることを示す。
これらの結果は、等しい重みが$\delta_{*}=1/2$である場合、Wu と Zhou の最近の結果をしっかりと補う。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture
Models [12.746888269949407]
2進隠れマルコフモデルに対する高次元平均推定問題を考える。
ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
論文 参考訳（メタデータ） (2022-06-06T09:34:04Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
ランダム集合 $mathcalS の部分集合 U(d)$ に対して、$mathcalS$ が $delta$-approximate $t$-design となる確率の有界性を与える。
正確な$t$-designから引き出された$mathcalS$に対して、$delta$-approximate $t$-designが不等式$mathbbPleft(delta geq x right)leq 2D_tを満たす確率を示す。
論文 参考訳（メタデータ） (2022-02-10T23:44:09Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
我々は、ほとんどの方向において$bfu$と$nu=mathrmpoly(k)$に対して、$n=mathrmpoly(k)$測定を用いて、高い精度で$bfu$を推定するアルゴリズムを開発し、分析する。
数値実験により,非漸近的条件下でも良好な性能が得られた。
論文 参考訳（メタデータ） (2021-10-04T02:10:47Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。