Private Means and the Curious Incident of the Free Lunch
<|reference_start|>Private Means and the Curious Incident of the Free Lunch: 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.<|reference_end|>
@article{fitzsimons2024private,
    title={Private Means and the Curious Incident of the Free Lunch},
    author={Jack Fitzsimons, James Honaker, Michael Shoemate, Vikrant Singhal},
    journal={arXiv preprint arXiv:2408.10438},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.10438},
    primaryClass={cs.CR}
}