論文の概要: Polynomial Time and Private Learning of Unbounded Gaussian Mixture
Models
- arxiv url: http://arxiv.org/abs/2303.04288v2
- Date: Wed, 7 Jun 2023 23:35:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-09 19:21:02.063216
- Title: Polynomial Time and Private Learning of Unbounded Gaussian Mixture
Models
- Title（参考訳）: 非有界ガウス混合モデルの多項式時間とプライベート学習
- Authors: Jamil Arbas, Hassan Ashtiani and Christopher Liaw
- Abstract要約: 本稿では,$d$-dimensional Gaussian Mixture Models (GMM) のパラメータを$k$コンポーネントでプライベートに推定する問題について検討する。
我々はその問題を非私的な問題に還元する手法を開発した。
我々は,Moitra Valiant と[MV10] の非プライベートアルゴリズムを用いて,GMM をブラックボックスとして学習するための$(varepsilon, delta)$-differentially privateアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 9.679150363410471
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study the problem of privately estimating the parameters of
$d$-dimensional Gaussian Mixture Models (GMMs) with $k$ components. For this,
we develop a technique to reduce the problem to its non-private counterpart.
This allows us to privatize existing non-private algorithms in a blackbox
manner, while incurring only a small overhead in the sample complexity and
running time. As the main application of our framework, we develop an
$(\varepsilon, \delta)$-differentially private algorithm to learn GMMs using
the non-private algorithm of Moitra and Valiant [MV10] as a blackbox.
Consequently, this gives the first sample complexity upper bound and first
polynomial time algorithm for privately learning GMMs without any boundedness
assumptions on the parameters. As part of our analysis, we prove a tight (up to
a constant factor) lower bound on the total variation distance of
high-dimensional Gaussians which can be of independent interest.
- Abstract（参考訳）: 本稿では,$d$-dimensional Gaussian Mixture Models (GMM) のパラメータを$k$コンポーネントでプライベートに推定する問題について検討する。
そこで我々は,この問題を非民間企業に還元する手法を開発した。
これにより、既存の非プライベートなアルゴリズムをブラックボックス方式で民営化できますが、サンプルの複雑さと実行時間のオーバーヘッドは少なくなります。
本フレームワークの主な応用例として,Moitra と Valiant [MV10] の非プライベートアルゴリズムをブラックボックスとして,GMM を学習するための$(\varepsilon, \delta)$-differentially privateアルゴリズムを開発した。
これにより、パラメータの有界性を仮定せずにgmmをプライベートに学習する最初のサンプル複雑性上限時間と1次多項式時間アルゴリズムが得られる。
解析の一環として、独立な興味を持つことができる高次元ガウスの総変分距離に対して(定数係数まで)厳密な下界を証明した。
関連論文リスト
- An Efficient 1 Iteration Learning Algorithm for Gaussian Mixture Model
And Gaussian Mixture Embedding For Neural Network [2.261786383673667]
新しいアルゴリズムは、古典的な期待最大化(EM)アルゴリズムよりも頑丈さと単純さをもたらす。
また、精度も向上し、学習に1回しかかからない。
論文 参考訳（メタデータ） (2023-08-18T10:17:59Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-28T16:53:41Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳（メタデータ） (2021-11-25T09:31:15Z) - Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
論文 参考訳（メタデータ） (2021-06-05T01:58:40Z) - Differentially Private ADMM Algorithms for Machine Learning [38.648113004535155]
勾配摂動による乗算器(ADMM)の高効率な個人交互方向法について検討した。
差分型ADMM(DP-ADMM)アルゴリズムを提案し,性能保証を$(epsilon,delta)$-differential privacy とする。
論文 参考訳（メタデータ） (2020-10-31T01:37:24Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。