論文の概要: Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples

• arxiv url: http://arxiv.org/abs/2309.03847v3
• Date: Tue, 23 Apr 2024 14:54:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-24 20:04:56.879394
• Title: Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
• Title（参考訳）: ガウスの混合はポリノミアルなサンプル数でプライベートに学習できる
• Authors: Mohammad Afzali, Hassan Ashtiani, Christopher Liaw,
• Abstract要約: 差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。 主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
• 参考スコア（独自算出の注目度）: 9.649879910148854
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of estimating mixtures of Gaussians under the constraint of differential privacy (DP). Our main result is that $\text{poly}(k,d,1/\alpha,1/\varepsilon,\log(1/\delta))$ samples are sufficient to estimate a mixture of $k$ Gaussians in $\mathbb{R}^d$ up to total variation distance $\alpha$ while satisfying $(\varepsilon, \delta)$-DP. This is the first finite sample complexity upper bound for the problem that does not make any structural assumptions on the GMMs. To solve the problem, we devise a new framework which may be useful for other tasks. On a high level, we show that if a class of distributions (such as Gaussians) is (1) list decodable and (2) admits a "locally small'' cover (Bun et al., 2021) with respect to total variation distance, then the class of its mixtures is privately learnable. The proof circumvents a known barrier indicating that, unlike Gaussians, GMMs do not admit a locally small cover (Aden-Ali et al., 2021b).
• Abstract（参考訳）: 本稿では,差分プライバシー(DP)の制約下でのガウスの混合度を推定する問題について検討する。 我々の主な結果は、$\text{poly}(k,d,1/\alpha,1/\varepsilon,\log(1/\delta))$サンプルが$k$ Gaussians in $\mathbb{R}^d$から$(\varepsilon, \delta)$-DPを満足しながら全変動距離$\alpha$を推定するのに十分であるということである。 これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。 この問題を解決するために、他のタスクに有用な新しいフレームワークを考案する。 高いレベルでは、(1)分布の類(ガウス類など)がデコッド可能なリストであり、(2)「局所的に小さい」被覆(Bun et al , 2021)が全変動距離に関して認められる場合、その混合の類はプライベートに学習可能である。 この証明は、ガウスとは異なり、GMMが局所的な小さな被覆(Aden-Ali et al , 2021b)を含まないことを示す既知の障壁を回避している。

関連論文リスト

• Sample-Efficient Private Learning of Mixtures of Gaussians [11.392841244701605]
  およそ$kd2 + k1.5 d1.75 + k2 d$サンプルは、$k$任意の$d$次元ガウスの混合を学ぶのに十分である。 我々の作業は、以前の最高の結果 [AAL24b] よりも改善され、$d$が$k2$よりもはるかに大きい場合、確実に最適です。
  論文  参考訳（メタデータ） (2024-11-04T17:23:52Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
  我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。 我々は、下層の混合成分について分離を前提としない。 我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-29T17:30:36Z)
• 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)
• Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
  任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。 本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-03T17:54:03Z)
• 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)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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