PLAN: Variance-Aware Private Mean Estimation

• URL: http://arxiv.org/abs/2306.08745v3
• Date: Wed, 10 Apr 2024 14:30:58 GMT
• Title: PLAN: Variance-Aware Private Mean Estimation
• Authors: Martin Aumüller, Christian Janos Lebeda, Boel Nelson, Rasmus Pagh,
• Abstract summary: Differentially private mean estimation is an important building block in privacy-preserving algorithms for data analysis and machine learning. We show how to exploit skew in the vector $boldsymbolsigma$, obtaining a (zero-digma) differentially private mean estimate with $ell$ error. To verify the effectiveness of PLAN, we empirically evaluate accuracy on both synthetic and real world data.
• Score: 12.452663855242344
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentially private mean estimation is an important building block in privacy-preserving algorithms for data analysis and machine learning. Though the trade-off between privacy and utility is well understood in the worst case, many datasets exhibit structure that could potentially be exploited to yield better algorithms. In this paper we present $\textit{Private Limit Adapted Noise}$ (PLAN), a family of differentially private algorithms for mean estimation in the setting where inputs are independently sampled from a distribution $\mathcal{D}$ over $\mathbf{R}^d$, with coordinate-wise standard deviations $\boldsymbol{\sigma} \in \mathbf{R}^d$. Similar to mean estimation under Mahalanobis distance, PLAN tailors the shape of the noise to the shape of the data, but unlike previous algorithms the privacy budget is spent non-uniformly over the coordinates. Under a concentration assumption on $\mathcal{D}$, we show how to exploit skew in the vector $\boldsymbol{\sigma}$, obtaining a (zero-concentrated) differentially private mean estimate with $\ell_2$ error proportional to $\|\boldsymbol{\sigma}\|_1$. Previous work has either not taken $\boldsymbol{\sigma}$ into account, or measured error in Mahalanobis distance $\unicode{x2013}$ in both cases resulting in $\ell_2$ error proportional to $\sqrt{d}\|\boldsymbol{\sigma}\|_2$, which can be up to a factor $\sqrt{d}$ larger. To verify the effectiveness of PLAN, we empirically evaluate accuracy on both synthetic and real world data.

Related papers

• 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)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  We study person-level differentially private mean estimation in the case where each person holds multiple samples. We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
  arXiv  Detail & Related papers  (2024-05-30T18:20:35Z)
• Online Robust Mean Estimation [37.746091744197656]
  We study the problem of high-dimensional robust mean estimation in an online setting. We prove two main results about online robust mean estimation in this model.
  arXiv  Detail & Related papers  (2023-10-24T15:28:43Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  We revisit the problem of sparse linear regression in the local differential privacy (LDP) model. We propose an innovative NLDP algorithm, the very first of its kind for the problem. Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.
  arXiv  Detail & Related papers  (2023-10-11T10:34:52Z)
• Data Structures for Density Estimation [66.36971978162461]
  Given a sublinear (in $n$) number of samples from $p$, our main result is the first data structure that identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. that reports $v_i$ in time linear in $k$.
  arXiv  Detail & Related papers  (2023-06-20T06:13:56Z)
• Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
  We provide an algorithm with a nearly matching error guarantee of $tildeO_varepsilon(sqrtn)$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram.
  arXiv  Detail & Related papers  (2022-10-27T05:11:00Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCA is a single-pass algorithm that overcomes both limitations. For sub-Gaussian data, we provide nearly optimal statistical error rates even for $n=tilde O(d)$.
  arXiv  Detail & Related papers  (2022-05-27T02:02:17Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.