Scalable Private Partition Selection via Adaptive Weighting

In the differentially private partition selection problem (a.k.a. set union, key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy. Solutions to this problem are a core building block for many privacy-preserving ML applications including vocabulary extraction in a private corpus, computing statistics over categorical data and learning embeddings over user-provided items. We propose an algorithm for this problem, MaxAdaptiveDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight, thereby increasing the probability that less frequent items are output. Our algorithm can be efficiently implemented in massively parallel computation systems allowing scalability to very large datasets. We prove that our algorithm stochastically dominates the standard parallel algorithm for this problem. We also develop a two-round version of our algorithm, MAD2R, where results of the computation in the first round are used to bias the weighting in the second round to maximize the number of items output. In experiments, our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed in prior works.

When dealing with sensitive data, protecting individual privacy is of paramount importance. A fundamental data processing task is to output the set of items in a database, for example, the words that people use in a corpus of messages. However, this vocabulary may leak sensitive information, especially if some words are only ever used by one or a few individuals. There is an inherent tradeoff between privacy and the number of items one can output. We develop new, highly scalable algorithms which improve this tradeoff, allowing for more items to be released while maintaining the same level of privacy. Our algorithms can be run in parallel across many computers, allowing us to process datasets with hundreds of billions of entries.