Post

I'm excited to share this paper. It answers a question that has bugged me for a long time: Can sample-and-aggregate be made more data-efficient? The answer is yes, but at a steep price in computational efficiency. See 🧵 for more details. Also, it was a fun opportunity to add a new coauthor. 😁

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).

The missing ingredient is a better aggregation method. Enter the shifted inverse mechanism cse.hkust.edu.hk/~yike/Shifte...

In this paper we showed that we can do this kind of versatile black-box estimation with only an *additive* cost of privacy, where sample-and-aggregate suffers a *multiplicative* cost. But this uses exponentially many subsamples - i.e., all subsets of size n-t instead of a partition into t parts.

OK, so can we get the best of both worlds? or at least trade off between the cost of privacy in terms of accuracy/data and the number of subsamples we need to evaluate on? That's what we address in our new paper. The answer is yes, but the tradeoff is quite steep (and we have a lower bound).