Private Means and the Curious Incident of the Free Lunch

arXiv:2408.10438v2 Announce Type: new
Abstract: We show that the most well-known and fundamental building blocks of DP implementations — sum, mean, count (and many other linear queries) — can be released with substantially reduced noise for the same privacy guarantee. We achieve this by projecting individual data with worst-case sensitivity $R$ onto a simplex where all data now has a constant norm $R$. In this simplex, additional “free” queries can be run that are already covered by the privacy-loss of the original budgeted query, and which algebraically give additional estimates of counts or sums, and can be combined for lower final noise.