論文の概要: A Private and Computationally-Efficient Estimator for Unbounded
Gaussians
- arxiv url: http://arxiv.org/abs/2111.04609v1
- Date: Mon, 8 Nov 2021 16:26:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-09 15:27:23.558148
- Title: A Private and Computationally-Efficient Estimator for Unbounded
Gaussians
- Title(参考訳): 非有界ガウスに対するプライベートかつ計算効率の良い推定器
- Authors: Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke,
Jonathan Ullman
- Abstract要約: 任意のガウス分布 $mathcalN(mu,Sigma)$ in $mathbbRd$ の平均と共分散に対する、初めて微分プライベートな推定器を与える。
我々のアルゴリズムにおける主要な新しい技術ツールは、任意のガウス$mathcalN(0,Sigma)$からサンプルを取り出し、$A$を返却して、$A Sigma AT$が一定の条件数を持つような新しい微分プライベートプレコンディショナーである。
- 参考スコア(独自算出の注目度): 18.758545721600196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first polynomial-time, polynomial-sample, differentially private
estimator for the mean and covariance of an arbitrary Gaussian distribution
$\mathcal{N}(\mu,\Sigma)$ in $\mathbb{R}^d$. All previous estimators are either
nonconstructive, with unbounded running time, or require the user to specify a
priori bounds on the parameters $\mu$ and $\Sigma$. The primary new technical
tool in our algorithm is a new differentially private preconditioner that takes
samples from an arbitrary Gaussian $\mathcal{N}(0,\Sigma)$ and returns a matrix
$A$ such that $A \Sigma A^T$ has constant condition number.
- Abstract(参考訳): 任意のガウス分布 $\mathcal{N}(\mu,\Sigma)$ in $\mathbb{R}^d$ の平均と共分散に対する最初の多項式時間、多項式サンプル、微分プライベート推定器を与える。
以前の推定値はすべて非コンストラクティブで、ランニング時間がないか、パラメータ $\mu$ と $\Sigma$ の優先度境界を指定する必要がある。
我々のアルゴリズムにおける主要な新しい技術ツールは、任意のガウス$\mathcal{N}(0,\Sigma)$からサンプルを取り出し、$A \Sigma A^T$が一定条件数を持つような行列$A$を返す新しい微分プライベートプレコンディショナーである。
関連論文リスト
- Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time [2.311583680973075]
我々はフロベニウスノルムで次元非依存誤差を実現する時間アルゴリズムを設計する。
散乱行列 $Sigma$, for every $t in mathbbN$, we design an estimator that, given $n = dO(t)$ sample, in time $nO(t)$ finds $hatSigma。
論文 参考訳(メタデータ) (2025-02-10T15:31:57Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-11-01T17:59:53Z) - Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。
我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文 参考訳(メタデータ) (2024-10-02T15:21:07Z) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳(メタデータ) (2023-01-17T18:44:41Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Gaussian Mean Testing Made Simple [46.03021473600576]
a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。
一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-25T01:59:13Z) - 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) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。