Post

First, what is sample-and-aggregate? It's a generic method for differentially private estimation. Partition your data into 1/ε subsamples; evaluate your function on each subsample; then combine the values in a ε-differentially private manner. It's flexible - it works for *any* function - but...

...it's inefficient in terms of data. You only get accuracy from evaluating on a subsample & each subsample gets treated like one datapoint for the privacy analysis. In terms of sample complexity, the cost of privacy is multiplicative, when it _should_ be additive. But it can be practical e.g.:

So the obvious question is *can sample-and-aggregate can be made more data-efficient?* 🤔 E.g., instead of partitioning the dataset, can we use overlapping subsamples? Unfortunately, using standard aggregation methods, this doesn't work (because overlapping subsamples means higher sensitivity).