論文の概要: Private and polynomial time algorithms for learning Gaussians and beyond
- arxiv url: http://arxiv.org/abs/2111.11320v1
- Date: Mon, 22 Nov 2021 16:25:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-23 19:39:15.097069
- Title: Private and polynomial time algorithms for learning Gaussians and beyond
- Title(参考訳): ガウスおよびそれ以上の学習のための私的および多項式時間アルゴリズム
- Authors: Hassan Ashtiani, Christopher Liaw
- Abstract要約: 本稿では,$(varepsilon, delta)$differentially private (DP) 統計的推定を非私的推定に還元する枠組みを提案する。
我々は、(制限のない)ガウスの堅牢な学習のための$(varepsilon, delta)$-DPアルゴリズムを初めて提供する。
- 参考スコア(独自算出の注目度): 13.947461378608525
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We present a fairly general framework for reducing $(\varepsilon, \delta)$
differentially private (DP) statistical estimation to its non-private
counterpart. As the main application of this framework, we give a polynomial
time and $(\varepsilon,\delta)$-DP algorithm for learning (unrestricted)
Gaussian distributions in $\mathbb{R}^d$. The sample complexity of our approach
for learning the Gaussian up to total variation distance $\alpha$ is
$\widetilde{O}\left(\frac{d^2}{\alpha^2}+\frac{d^2
\sqrt{\ln{1/\delta}}}{\alpha\varepsilon} \right)$, matching (up to logarithmic
factors) the best known information-theoretic (non-efficient) sample complexity
upper bound of Aden-Ali, Ashtiani, Kamath~(ALT'21). In an independent work,
Kamath, Mouzakis, Singhal, Steinke, and Ullman~(arXiv:2111.04609) proved a
similar result using a different approach and with $O(d^{5/2})$ sample
complexity dependence on $d$.
As another application of our framework, we provide the first polynomial time
$(\varepsilon, \delta)$-DP algorithm for robust learning of (unrestricted)
Gaussians.
- Abstract(参考訳): 我々は、$(\varepsilon, \delta)$differentially private (DP) 統計的推定を非私的推定に還元する、かなり一般的なフレームワークを提案する。
このフレームワークの主な応用として、多項式時間と$(\varepsilon,\delta)$-dpアルゴリズムを与えて、$\mathbb{r}^d$ でガウス分布を学習する。
我々のアプローチのサンプル複雑性は、全変分距離$\alpha$は$\widetilde{O}\left(\frac{d^2}{\alpha^2}+\frac{d^2 \sqrt{\ln{1/\delta}}}{\alpha\varepsilon} \right)$, matching (対数因子まで) the most known information-theoretic (non- efficient) sample complexity upper bound of Aden-Ali, Ashtiani, Kamath~(ALT'21)である。
独立した研究で、Kamath, Mouzakis, Singhal, Steinke, Ullman~(arXiv:2111.04609) は異なるアプローチと$O(d^{5/2})$$$d$のサンプル複雑性依存性を用いて同様の結果を示した。
フレームワークの別の応用として、(制限のない)ガウスの堅牢な学習のための最初の多項式時間$(\varepsilon, \delta)$-DPアルゴリズムを提供する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - 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 a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳(メタデータ) (2022-06-17T17:55:43Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。
具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
論文 参考訳(メタデータ) (2022-03-03T06:25:48Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。