論文の概要: 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)を含まないことを示す既知の障壁を回避している。
関連論文リスト
- 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) - Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance
Estimation for Subgaussian Distributions [8.40077201352607]
我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。
我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
論文 参考訳(メタデータ) (2023-01-28T16:57:46Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳(メタデータ) (2022-05-17T17:55:10Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。