論文の概要: 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$を返す新しい微分プライベートプレコンディショナーである。
関連論文リスト
- $L^1$ Estimation: On the Optimality of Linear Estimators [70.75102576909295]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳(メタデータ) (2023-09-17T01:45:13Z) - A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm [41.03423042792559]
我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
論文 参考訳(メタデータ) (2023-05-01T17:54:35Z) - 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) - 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) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳(メタデータ) (2020-06-23T20:21:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。