Sample-Aggregate #59
Description
The sample-aggregate framework introduced in the paper "Smooth Sensitivity and Sampling in Private Data Analysis" (https://cs-people.bu.edu/ads22/pubs/NRS07/NRS07-full-draft-v1.pdf) is a powerful technique to create differentially private release mechanisms when the worst-case sensitivity is large or even unknown. It would be handy to have an implementation of this for a variety of aggregation functions. In particular, the median is well behaved and the smooth sensitivity is pretty easy to compute. An exisiting Python implementation can be found here: https://github.com/michaelpatrickpurcell/graph-dp/blob/master/edge_privacy_igraph.py.
A full-featured implementation would be compatible with multiple aggregation functions, possibly including user-defined functions, and would play nicely with Laplace, Gaussian, and Cauchy mechanisms.