These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
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.