論文の概要: Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior
- arxiv url: http://arxiv.org/abs/2503.20193v1
- Date: Wed, 26 Mar 2025 03:36:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-27 13:18:06.641792
- Title: Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior
- Title(参考訳): ガウス的位置混合のための非パラメトリックMLE:認証計算とジェネリック挙動
- Authors: Yury Polyanskiy, Mark Sellke,
- Abstract要約: 一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。
We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。
また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
- 参考スコア(独自算出の注目度): 28.71736321665378
- License:
- Abstract: We study the nonparametric maximum likelihood estimator $\widehat{\pi}$ for Gaussian location mixtures in one dimension. It has been known since (Lindsay, 1983) that given an $n$-point dataset, this estimator always returns a mixture with at most $n$ components, and more recently (Wu-Polyanskiy, 2020) gave a sharp $O(\log n)$ bound for subgaussian data. In this work we study computational aspects of $\widehat{\pi}$. We provide an algorithm which for small enough $\varepsilon>0$ computes an $\varepsilon$-approximation of $\widehat\pi$ in Wasserstein distance in time $K+Cnk^2\log\log(1/\varepsilon)$. Here $K$ is data-dependent but independent of $\varepsilon$, while $C$ is an absolute constant and $k=|supp(\widehat{\pi})|\leq n$ is the number of atoms in $\widehat\pi$. We also certifiably compute the exact value of $|supp(\widehat\pi)|$ in finite time. These guarantees hold almost surely whenever the dataset $(x_1,\dots,x_n)\in [-cn^{1/4},cn^{1/4}]$ consists of independent points from a probability distribution with a density (relative to Lebesgue measure). We also show the distribution of $\widehat\pi$ conditioned to be $k$-atomic admits a density on the associated $2k-1$ dimensional parameter space for all $k\leq \sqrt{n}/3$, and almost sure locally linear convergence of the EM algorithm. One key tool is a classical Fourier analytic estimate for non-degenerate curves.
- Abstract(参考訳): 一次元のガウス的位置混合に対して、非パラメトリック最大度推定器 $\widehat{\pi}$ について検討する。
Lndsay, 1983) 以降、この推定器は常に$n$の成分の混合物を返し、より最近の (Wu-Polyanskiy, 2020) ではサブガウスデータに対して鋭い$O(\log n)$バウンドを与えたことが知られている。
本研究では,$\widehat{\pi}$の計算面について検討する。
我々は,小さければ$\varepsilon>0$が$\varepsilon$-approximation of $\widehat\pi$ in time $K+Cnk^2\log\log(1/\varepsilon)$を計算できるアルゴリズムを提供する。
ここで、$K$は$\varepsilon$とは独立であるが、$C$は絶対定数であり、$k=|supp(\widehat{\pi})|\leq n$は$\widehat\pi$の原子の数である。
また、f|supp(\widehat\pi)|$の正確な値を有限時間で計算する。
これらの保証は、データセット $(x_1,\dots,x_n)\in [-cn^{1/4},cn^{1/4}]$ が密度を持つ確率分布からの独立な点からなる場合、ほぼ確実に保持される。
また、$k$-atomicと条件付けられた$\widehat\pi$の分布は、すべての$k\leq \sqrt{n}/3$に対して、関連する2k-1$次元パラメータ空間上の密度を認め、EMアルゴリズムの局所線型収束をほぼ確実にすることを示す。
鍵となるツールの1つは、非退化曲線に対する古典的なフーリエ解析推定である。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-11-01T17:59:53Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳(メタデータ) (2023-03-30T02:50:49Z) - 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) - A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。
我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文 参考訳(メタデータ) (2022-10-05T17:35:46Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳(メタデータ) (2022-09-06T23:37:31Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳(メタデータ) (2021-11-07T13:44:50Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。
点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
論文 参考訳(メタデータ) (2021-05-11T02:29:33Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳(メタデータ) (2021-01-11T17:23:24Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。