Scalable Private Partition Selection via Adaptive Weighting
Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam · 2025
Read Scalable Private Partition Selection via Adaptive Weighting by Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-08878.txt.
Introduction
Justin Chen and co-authors tackle in 2025 a privacy puzzle. Many users each hold a set of items. The group wants to publish as much of the combined list as possible, without leaking who held what. This partition selection problem underlies private vocabulary building, category statistics, and learning on user supplied items. All of it sits under the shield of differential privacy.
Their algorithm, MaxAdaptiveDegree, shifts weight around cleverly. Items far above the safety threshold give up spare weight, and items with little support gain it, raising the odds that rare items make the cut. They prove the method beats the standard parallel approach in a strong stochastic sense. A two round variant uses round one's results to bias round two. In tests the methods led rival parallel algorithms and scaled to data sets with hundreds of billions of items, far beyond earlier sequential work.
Catalog record
| CREATOR | Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-08878
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Private Partition Selection via Adaptive Weighting Justin Y. Chen, Vincent Cohen-Addad, Alessandro Epasto, Morteza Zadimoghaddam Abstract In the differentially private partition selection problem (a.k.a. private set union, private 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 by prior sequential algorithms. 1 Introduction The availability of large amounts of user data has been one of the driving factors for the widespread adoption and rapid development of modern machine learning and data analytics. Consider the example of a system releasing information on the queries asked to a search engine over a period of time [ KKMN09 , BBD+21 ] . Such a system can provide valuable insights to researchers and the public (for instance on health concerns [ BBD+21 ] ) but care is needed in ensuring that the queries output do not leak private and sensitive user information. In this paper, we focus on the problem of private partition selection [ DVGM22 , GGK+20 ] which models the challenge of extracting as much data as possible from such a dataset while respecting user privacy. More formally, the setting of the problem (which is also known as private set union or private key discovery) is that each user has a private subset of items (e.g., the queries issued by the user) from an unknown and unbounded universe of items (e.g., all strings). The goal is to output as many of the items in the users’ sets as possible (i.e., the queries issues by the users), while providing a strong notion of privacy—User-level Differential Privacy (DP) [ DR14 ] . Private partition selection models many challenges beyond the example above, including the problem of extracting the vocabulary (words, tokens or n -gram) present in a private corpus [ ZHQ+22 , KGKY21 ] . This task is a fundamental prerequisite for many privacy-preserving natural language processing algorithms [ WZL+19 , GGK+20 ] , including for training language models for sentence completion and response generation for emails [ KGKY21 ] . Similarly, learning embedding models over categorical data often requires to identify the categories present in a private dataset [ GHK+23 , GGK+24 ] . Partition selection underpins many other applications including analyzing private streams [ CR22 , ZDK+23 ] , learning sparse histograms [ BBCG+21 ] , answering SQL queries [ DVGM22 ] and sparsifying the gradients in the DP SGD method [ GHK+23 ] . Unsurprisingly given these applications, private partition selection algorithms [ KKMN09 ] are a core building block of many standard differentially private libraries e.g., PyDP [ PyD24 ] , Google’s DP Libraries [ Goo24 , AGJ+22 ] , and OpenMined DP Library [ Ope24 ] . Real-world datasets for these applications can be massive, potentially containing hundreds of billions of data points, thus requiring algorithms for partition selection that can be efficiently run in large-scale data processing infrastructures—e.g., MapReduce [ DG04 ] , Hadoop [ Apa ] , Spark [ ZXW+16 ] . In our work, we design a highly parallelizable algorithm for this problem which requires constant parallel rounds in the Massively Parallel Computing model [ KSV10 ] and does not assume to fit the input in memory. This contrasts to prior algorithms such as [ GGK+20 , CWG22 ] which all require (with the key exception of the uniform weighting method described below) to process all the data sequentially on a single machine and assume storing the input in-memory thus precluding efficient parallelization. 1.1 Weight and Threshold Approach Before introducing our algorithm, we review the popular weighting-based approach to partition selection which is used in many algorithms [ KKMN09 , GGK+20 , CWG22 , SDH23 ] . This approach is of interest in the context of large-scale data as some of its variants can be parallelized efficiently [ KKMN09 , SDH23 ] . Notice that differential privacy imposes to not output any item which is owned by only a single user. However, it is possible for a private algorithm to output items which appear in many different sets. This intuition is at the basis of the weighting-based algorithms. Algorithms in this framework start by subsampling each user’s set to bound the maximum number of items per user. Then, these algorithms proceed by increasing, for each user, the weight associated the items present in the user data. Finally, the algorithm adds Gaussian (or Laplace) noise to the total accumulated weight of each item, and outputting all items with noised weight above a certain threshold [ KKMN09 , GGK+20 , CWG22 , SDH23 ] . The amount of noise and value of the threshold depends on the privacy parameters and crucially on the sensitivity of the weighting function to the addition or removal of any individual user’s set. Loosely speaking, the contribution of each user to the item weights must be bounded in order to achieve differential privacy. Algorithms within this framework differ in the choice of how to assign item weights, but in all designs the key goal is that of limiting the sensitivity of the weighting function. A basic strategy is uniform weighting [ KKMN09 ] where each user contributes equal weight to each of the items in their set. It is easy to bound the sensitivity of this basic weighting and thus to prove differential privacy. Because of its simplicity, the basic uniform weighting algorithm is extremely parallelizable requiring only basic counting operations over the items in the data. Unfortunately, however, uniform weighting is lossy in that it may overallocate weight far above the threshold to high frequency items, missing an opportunity to boost the weight of items closer to the decision boundary. This has inspired the design of greedy weighting schemes such as [ GGK+20 , CWG22 ] where each user’s allocations depend on data of previously analyzed users. All of these algorithms are inherently sequential and require memory proportional to the items present in the data. To our knowledge, the uniform weighting [ KKMN09 ] is essentially the only known solution to the private partition selection problem which is amenable to implementation in a massively parallel