A Private and Computationally-Efficient Estimator for Unbounded Gaussians

• URL: http://arxiv.org/abs/2111.04609v1
• Date: Mon, 8 Nov 2021 16:26:10 GMT
• Title: A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Authors: Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, Jonathan Ullman
• Abstract summary: We give the first-time, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution $mathcalN(mu,Sigma)$ in $mathbbRd$. The primary new technical tool in our algorithm is a new differentially private preconditioner that takes samples from an arbitrary Gaussian $mathcalN(0,Sigma)$ and returns a matrix $A$ such that $A Sigma AT$ has constant condition number.
• Score: 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.

Related papers

• Allocating Variance to Maximize Expectation [2.25491649634702]
  We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. Such expectation problems occur in diverse applications, ranging from utility auctions to learning mixture models in quantitative genetics.
  arXiv  Detail & Related papers  (2025-02-25T18:59:46Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
  We study the estimation of distributional parameters when samples are shown only if they fall in some unknown set. We develop tools that may be of independent interest, including a reduction from PAC learning with positive and unlabeled samples to PAC learning with positive and negative samples.
  arXiv  Detail & Related papers  (2024-10-02T15:21:07Z)
• A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm [41.03423042792559]
  We produce a list of hypotheses that are close to $Sigma$ in relative Frobenius norm. As a corollary, we obtain an efficient spectral algorithm for robust partial clustering of Gaussian mixture models. Our new method yields the first Sum-of-Squares-free algorithm for robustly learning GMMs.
  arXiv  Detail & Related papers  (2023-05-01T17:54:35Z)
• A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
  We design an $(varepsilon, delta)$-differentially private algorithm that is adaptive to $Sigma$. The estimator achieves optimal rates of convergence with respect to the induced Mahalanobis norm $||cdot||_Sigma$.
  arXiv  Detail & Related papers  (2023-01-17T18:44:41Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Gaussian Mean Testing Made Simple [46.03021473600576]
  Given i.i.d. samples from a distribution $p$ on $mathbbRd$, the task is to distinguish, with high probability, between the following cases. We give an extremely simple algorithm for Gaussian mean testing with a one-page analysis.
  arXiv  Detail & Related papers  (2022-10-25T01:59:13Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.