Ripple Mechanisms for Discrete and Private Statistics

Matthew Joseph, Alex Kulesza, Yuyan Wang, Alexander Yu
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3856-3903, 2026.

Abstract

We study \emph{ripple mechanisms} for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-joseph26a, title = {Ripple Mechanisms for Discrete and Private Statistics}, author = {Joseph, Matthew and Kulesza, Alex and Wang, Yuyan and Yu, Alexander}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3856--3903}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/joseph26a/joseph26a.pdf}, url = {https://proceedings.mlr.press/v336/joseph26a.html}, abstract = {We study \emph{ripple mechanisms} for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.} }
Endnote
%0 Conference Paper %T Ripple Mechanisms for Discrete and Private Statistics %A Matthew Joseph %A Alex Kulesza %A Yuyan Wang %A Alexander Yu %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-joseph26a %I PMLR %P 3856--3903 %U https://proceedings.mlr.press/v336/joseph26a.html %V 336 %X We study \emph{ripple mechanisms} for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.
APA
Joseph, M., Kulesza, A., Wang, Y. & Yu, A.. (2026). Ripple Mechanisms for Discrete and Private Statistics. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3856-3903 Available from https://proceedings.mlr.press/v336/joseph26a.html.

Related Material