論文の概要: Sample-Efficient Private Learning of Mixtures of Gaussians

• arxiv url: http://arxiv.org/abs/2411.02298v1
• Date: Mon, 04 Nov 2024 17:23:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:48:53.699106
• Title: Sample-Efficient Private Learning of Mixtures of Gaussians
• Title（参考訳）: ガウスの混合のサンプル効率の良い私的学習
• Authors: Hassan Ashtiani, Mahbod Majid, Shyam Narayanan,
• Abstract要約: およそ$kd2 + k1.5 d1.75 + k2 d$サンプルは、$k$任意の$d$次元ガウスの混合を学ぶのに十分である。 我々の作業は、以前の最高の結果 [AAL24b] よりも改善され、$d$が$k2$よりもはるかに大きい場合、確実に最適です。
• 参考スコア（独自算出の注目度）: 11.392841244701605
• License:
• Abstract: We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $kd^2 + k^{1.5} d^{1.75} + k^2 d$ samples suffice to learn a mixture of $k$ arbitrary $d$-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result [AAL24b] (which required roughly $k^2 d^4$ samples) and is provably optimal when $d$ is much larger than $k^2$. Moreover, we give the first optimal bound for privately learning mixtures of $k$ univariate (i.e., $1$-dimensional) Gaussians. Importantly, we show that the sample complexity for privately learning mixtures of univariate Gaussians is linear in the number of components $k$, whereas the previous best sample complexity [AAL21] was quadratic in $k$. Our algorithms utilize various techniques, including the inverse sensitivity mechanism [AD20b, AD20a, HKMN23], sample compression for distributions [ABDH+20], and methods for bounding volumes of sumsets.
• Abstract（参考訳）: ガウシアンと近似微分プライバシーの混合を学習する問題について検討する。 約$kd^2 + k^{1.5} d^{1.75} + k^2 d$サンプルは、任意の$k$$$d$次元ガウスアンと差分プライバシーとの混合を学習するのに十分であることを示す。 AAL24b](およそ$k^2 d^4$サンプルが必要)よりも改善され、$d$が$k^2$よりもはるかに大きい場合、確実に最適である。 さらに、単変数(つまり1$次元)ガウス多様体の私的学習混合物に対する最初の最適境界を与える。 重要なことは、単変量ガウスの混合体をプライベートに学習する際のサンプルの複雑さが$k$の成分数で線形であることを示し、前回のベストサンプルの複雑さは$k$の2乗である。 本アルゴリズムでは, 逆感度機構 [AD20b, AD20a, HKMN23] , 分布のサンプル圧縮 [ABDH+20] , 総和を束縛する方法など, 様々な手法を用いる。

関連論文リスト

• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
  差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。 主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
  論文  参考訳（メタデータ） (2023-09-07T17:02:32Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Privately Learning Mixtures of Axis-Aligned Gaussians [12.77304082363491]
  ここでは,$widetildeO(k2 d log3/2 (1/delta) / alpha2 varepsilon)$サンプルは,$k$軸整列ガウスの混合を学習するのに十分であることを示す。 混合分布をプライベートに学習する新しい手法を設計する。
  論文  参考訳（メタデータ） (2021-06-03T22:34:23Z)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• 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)
• Robust Learning of Mixtures of Gaussians [13.173307471333617]
  我々は、$X$が任意の$d$-次元ガウス多様体の均等な重み付け混合であるときに、$poly(eps)$を総変量で誤りを犯すことを学ぶ。 特に、$X$ が 2 つの任意の$d$次元ガウス多様体の均等な重み付き混合であれば、$X$ a $eps$-fraction からサンプルにアクセスする時間アルゴリズムを考案する。
  論文  参考訳（メタデータ） (2020-07-12T05:15:50Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians [21.780375994511324]
  我々は、期待最大化(EM)に対する新しい結果を証明する: EMは、分離された$Omega(sqrtlog k)$の下で局所的に収束することを示す。 我々の結果は、(潜在的に異なる)ガウス成分の事前の知識を前提としない。
  論文  参考訳（メタデータ） (2020-02-02T05:09:26Z)

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

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