論文の概要: Privately Learning Mixtures of Axis-Aligned Gaussians
- arxiv url: http://arxiv.org/abs/2106.02162v1
- Date: Thu, 3 Jun 2021 22:34:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 11:33:41.702914
- Title: Privately Learning Mixtures of Axis-Aligned Gaussians
- Title（参考訳）: 軸配向ガウスの私的学習混合
- Authors: Ishaq Aden-Ali, Hassan Ashtiani, Christopher Liaw
- Abstract要約: ここでは,$widetildeO(k2 d log3/2 (1/delta) / alpha2 varepsilon)$サンプルは,$k$軸整列ガウスの混合を学習するのに十分であることを示す。
混合分布をプライベートに学習する新しい手法を設計する。
- 参考スコア（独自算出の注目度）: 12.77304082363491
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of learning mixtures of Gaussians under the
constraint of approximate differential privacy. We prove that
$\widetilde{O}(k^2 d \log^{3/2}(1/\delta) / \alpha^2 \varepsilon)$ samples are
sufficient to learn a mixture of $k$ axis-aligned Gaussians in $\mathbb{R}^d$
to within total variation distance $\alpha$ while satisfying $(\varepsilon,
\delta)$-differential privacy. This is the first result for privately learning
mixtures of unbounded axis-aligned (or even unbounded univariate) Gaussians. If
the covariance matrices of each of the Gaussians is the identity matrix, we
show that $\widetilde{O}(kd/\alpha^2 + kd \log(1/\delta) / \alpha \varepsilon)$
samples are sufficient.
Recently, the "local covering" technique of Bun, Kamath, Steinke, and Wu has
been successfully used for privately learning high-dimensional Gaussians with a
known covariance matrix and extended to privately learning general
high-dimensional Gaussians by Aden-Ali, Ashtiani, and Kamath. Given these
positive results, this approach has been proposed as a promising direction for
privately learning mixtures of Gaussians. Unfortunately, we show that this is
not possible.
We design a new technique for privately learning mixture distributions. A
class of distributions $\mathcal{F}$ is said to be list-decodable if there is
an algorithm that, given "heavily corrupted" samples from $f\in \mathcal{F}$,
outputs a list of distributions, $\widehat{\mathcal{F}}$, such that one of the
distributions in $\widehat{\mathcal{F}}$ approximates $f$. We show that if
$\mathcal{F}$ is privately list-decodable, then we can privately learn mixtures
of distributions in $\mathcal{F}$. Finally, we show axis-aligned Gaussian
distributions are privately list-decodable, thereby proving mixtures of such
distributions are privately learnable.
- Abstract（参考訳）: 我々は、近似微分プライバシーの制約の下でガウスの混合を学習する問題を考察する。
我々は、$\widetilde{o}(k^2 d \log^{3/2}(1/\delta) / \alpha^2 \varepsilon)$サンプルは、$(\varepsilon, \delta)$-微分プライバシーを満たしながら、$\mathbb{r}^d$ から$k$軸整合ガウスの混合物を学ぶのに十分であることを証明する。
これは、非有界軸整列(あるいは非有界単変数)ガウスの混合を私的に学習する最初の結果である。
ガウス群の各共分散行列が同一行列であれば、$\widetilde{o}(kd/\alpha^2 + kd \log(1/\delta) / \alpha \varepsilon)$ のサンプルは十分である。
近年、Bun, Kamath, Steinke, Wu の「局所被覆」技術は、共分散行列を持つ高次元ガウスの私的学習に成功し、Aden-Ali, Ashtiani, Kamath による一般高次元ガウスの私的学習にも応用されている。
これらのポジティブな結果を考えると、このアプローチはガウスの個人学習混合物の有望な方向性として提案されている。
残念なことに、これは不可能である。
混合分布をプライベートに学習する新しい手法を設計する。
分布のクラス $\mathcal{f}$ がリスト決定可能(list-decodable)であるとは、$f\in \mathcal{f}$ のサンプルが与えられたとき、分布のリスト $\widehat{\mathcal{f}}$ を出力するアルゴリズムが存在して、$\widehat{\mathcal{f}}$ の分布の1つが$f$ に近似するときに言う。
もし$\mathcal{F}$がプライベートにリストデコダブルであれば、$\mathcal{F}$で分布の混合をプライベートに学ぶことができる。
最後に,軸方向のガウス分布がプライベートリスト決定可能であることを示し,これらの分布の混合がプライベート学習可能であることを示す。
関連論文リスト
- 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) - 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) - Learning Mixtures of Gaussians with Censored Data [9.053430799456587]
本稿では,ガウシアンと検閲データとの混合学習の問題点について考察する。
本稿では,$frac1varepsilonO(k)$サンプルだけで重量を$w_i$,平均$mu_i$を$varepsilon$エラーで推定するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-06T19:58:02Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。
具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
論文 参考訳（メタデータ） (2022-03-03T06:25:48Z) - 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) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。