REVIEW 1 major objections 5 minor 33 references
Scalable Private Partition Selection via Adaptive Weighting
T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper proposes MAD, an adaptive weighting algorithm for private partition selection that provably matches the privacy parameters of uniform weighting while increasing output probability for rare items.
desk verdict A genuinely new adaptive weighting algorithm for private partition selection with a real scale-up, but the MAD2R privacy proof has a fixable conditioning gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the weight-and-threshold meta-algorithm: cap user degrees, compute item weights, add Gaussian noise, and output items whose noised weight exceeds a threshold $\rho$. MAD's weighting works by having adaptive users first send $1/|S_u|$ weight per item, truncating item weights above the adaptive threshold $\tau = \rho + \beta\sigma$, returning the excess to users in proportion to their contributions, and rerouting a discounted fraction $\alpha = b_{\min} - \frac{1}{2\sqrt{d_{\max}}}$ of that excess across their items; each user then adds a vector of $\ell_2$-norm-bounded weights. The delicate part is the sensitivity analysis, Lemmas 5.3 and 5.6, which keeps $\ell_2$ sensitivity at most $1$ and novel $\ell_\infty$ sensitivity at most $b_{\max}/\sqrt{t}$ despite the rerouting, so the same noise and threshold parameters as the basic algorithm still guarantee $(\varepsilon,\delta)$-DP.
What would settle it
Take MAD2R with $d_{\max}=4$, $b_{\min}=0.5$, $b_{\max}=2$, and two neighboring datasets that differ by one user whose items push several existing items above the adaptive threshold. Fix the first round's noisy weights to the same vector for both datasets, as the proof's conditional composition does, compute the bias vector, and directly compute the $\ell_2$ norm of the difference of the second-round MAD weights. If any such computation exceeds $1$, Theorem 5.1 is false; the theorem predicts the bound always holds.
Extended reading notes
Core claim
The central discovery is that adaptive, non-uniform weighting can be made free in the privacy budget. Its MaxAdaptiveDegree (MAD) weighting scheme has $\ell_2$ sensitivity at most $1$ and novel $\ell_\infty$ sensitivity at most $b_{\max}/\sqrt{t}$, the same bounds as uniform weighting, so within the weight-and-threshold meta-algorithm it uses exactly the same Gaussian noise scale and threshold while reallocating weight toward rare items. The corollary is Theorem 6.1: for every item in the union, MAD's output probability is at least the uniform algorithm's whenever the uniform algorithm is not already overwhelming, and otherwise at least $\Phi(\beta)$. A two-round variant, MAD2R, goes further by treating the first round's noisy weights as reusable data: it removes items whose upper-confidence weight is below the second threshold and biases down the weight of items whose lower-confidence weight is already above it.
Load-bearing premise
The load-bearing premise is that adding one user changes only that user's own contributions and the rerouting they trigger, so existing users' finalized weights never shift as a side effect; if a different first-round noisy vector could change existing users' weights, the $\ell_2$ sensitivity bound of Lemma 5.6 would break.
Editorial extensions
If this is right
- Because the noise scale and threshold are identical to Basic, MAD can replace Basic in any existing weight-and-threshold pipeline without re-tuning privacy parameters, and the utility gain is provably non-negative item-by-item.
- For every item that Basic outputs with probability below $\Phi(\beta)$, MAD outputs it with probability at least as high; items at or above $\Phi(\beta)$ keep at least probability $\Phi(\beta)$, so the output set stochastically dominates the baseline's.
- In MAD2R, the noisy weight vector from a first DP round can be treated as public information for a second round; pruning items with tiny upper bounds and biasing weights toward borderline items yields the best parallel results in the paper's experiments, improving on DP-SIPS by up to roughly 9.5%.
- Because every stage is a constant number of linear-work passes, the algorithm runs on datasets with hundreds of billions of user-item pairs in a massively parallel system, roughly three orders of magnitude beyond what earlier sequential algorithms could analyze.
- The same privacy accounting applies to both rounds of MAD2R through basic composition, so the two-round scheme scales with the same budget-splitting logic as DP-SIPS.
Reading between the lines
- A consequence the paper leaves implicit is that the same reuse of noisy weights might be iterated beyond two rounds, and whether the bias bounds and sensitivity analysis survive repeated reuse is a direct open question raised by its own technique.
- The conditional-composition reading of Lemma 5.6 suggests a general recipe: if each round's adaptive decisions depend only on previously released DP outputs, then per-round sensitivity analysis can be performed with those outputs fixed, potentially unlocking other parallel adaptive weighting schemes.
- The stochastic dominance theorem is ordinal rather than quantitative, so it does not measure how close MAD is to the best possible output; the paper explicitly leaves a competitive-ratio analysis open.
- On datasets with many singleton items, the privacy requirement itself sets an absolute ceiling, and the paper's frequency-bucket experiments imply that future gains will come from items near the decision boundary rather than from very rare items.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces MaxAdaptiveDegree (MAD), an adaptive weighting algorithm for differentially private partition selection that is claimed to achieve the same privacy parameters as the basic uniform weighting algorithm while rerouting excess weight from high-weight items to low-weight items. It also introduces a two-round variant, MAD2R, which uses first-round noisy weights to bias the second-round weighting, and presents a formal privacy proof based on novel ℓ2 and novel ℓ∞ sensitivity bounds, a per-item stochastic dominance theorem over Basic, and experiments on datasets up to 800 billion entries.
Significance. If the privacy proof is made fully rigorous, this is a significant result: it gives the first non-uniform adaptive weighting algorithm for partition selection that runs in constant parallel rounds and linear work, with a formal dominance guarantee over the standard parallel baseline and strong empirical performance at a scale previously inaccessible to sequential algorithms. The paper includes detailed sensitivity analyses, explicit pseudocode, an open-source implementation, and demonstrations on very large datasets, which are notable strengths.
major comments (1)
- [§5.2, Lemma 5.6 and Theorem 5.1] The statement and proof of Lemma 5.6 compare two runs of Algorithm 3 which, as the text explicitly allows, may use different bias vectors b and b′ on the common items; however, the proof's claim that Δuser is dv-sparse is valid only when b′ and b agree on all items of existing users. As stated, the lemma is false: for instance, with S containing one user u with Su = {a}, S′ = S ∪ {(v, {b})}, bmin = 0.5, τ = 1, dmax = 4, b(a) = 0.5 and b′(a) = 1, the ℓ2 difference exceeds 1 (difference 0.5 on a plus 1 on b). In the proof of Theorem 5.1, the bias vector is derived from the first-round noisy weights, whose distributions differ between neighboring datasets, so invoking Lemma 5.6 without further argument does not establish the claimed (ε1+ε2, δ1+δ2)-DP guarantee. The lemma should be restated under the hypothesis that both runs use the same bias vector on the common union, and the proof of Theorem 5.1 should explicitly perform the conditional-composition step: for every fixed first-round transcript, the bias vector and the removal sets are identical, so the second-round comparison reduces to the equal-bias case.
minor comments (5)
- [Algorithm 3, line 6] The formula for r(i) uses min{0, ...}, which would set the fraction to zero for all items with positive excess; the surrounding text and Lemma 5.3 both use the maximum with 0, so the pseudocode should be corrected to max{0, ...}.
- [Abstract and §1.2] The abstract and Section 1.2 state that MAD 'stochastically dominates' the basic algorithm, but Theorem 6.1 proves per-item output probability bounds rather than a set-wise coupling; the expected output size is still dominated, so the claim should be qualified accordingly.
- [Figure 4 and caption] The axis label and the caption refer to a parameter 'δ0'; this should be 'Δ0', the degree cap used throughout the paper.
- [Lemma 5.8 proof] The stationary-point condition should be an equality: setting the derivative of f to zero gives x(C√y − 1)/y = 2A(1 − A), not '<' as printed.
- [Informal Theorem 1.2] The informal theorem uses U both for the output set of the basic algorithm and for the union of user sets; consider using different symbols to avoid ambiguity.
Circularity Check
No significant circularity: the privacy and dominance results are derived from explicit sensitivity lemmas and pointwise weight comparisons; the flagged Lemma 5.6 issue is an omitted conditioning hypothesis, not a circular reduction.
full rationale
I followed the derivation chain from Algorithm 3 and Algorithm 4 through the privacy analysis. Theorem 3.3 is a generic meta-algorithm statement: it reduces the privacy of the weight-and-threshold framework to the two stated sensitivity properties, and it is proved directly via the Gaussian mechanism and a union bound over novel items. Lemma 5.3 bounds the novel ℓ∞ sensitivity from the algorithm's definitions, and Lemma 5.6 bounds the ℓ2 sensitivity by decomposing the difference into Δ_reroute and Δ_user and then choosing α algebraically (Equation 5) so that the final bound is at most 1. No equation in this chain is defined in terms of the theorem it proves, and no parameter is fitted to data and then relabeled as a prediction: the hyperparameters β, dmax, bmin, bmax, Clb, and Cub are algorithm knobs whose specific values are not used to establish the correctness theorems. Theorem 6.1 is a direct pointwise comparison of Basic weights and MAD weights: in Case 1 the item is never truncated and MAD only increases its weight, and in Case 2 the adaptive truncation guarantees the final weight is at least τ, so the output probability is at least Φ(β). There is no load-bearing self-citation: the algorithmic predecessors cited (KKMN09, GGK+20, CWG22, SDH23) share no authors with this paper, and the paper imports no 'uniqueness' claim from the authors' prior work. The one concern raised by the skeptical reading is real but non-circular: in Section 5.2, the proof of Lemma 5.6 asserts 'Δ_user is d_v-sparse and only has nonzero entries on S_v, the items of the new user' without stating the conditioning hypothesis that the bias vectors b and b′ agree on all common items; in MAD2R the biases are derived from the first-round noisy vector (Algorithm 4, line 14), whose distribution differs between neighboring datasets, so Theorem 5.1's double invocation of Theorem 3.3 plus basic composition needs the conditional-composition reading to be made explicit. That is a missing hypothesis or proof gap in the manuscript, not a circular derivation: the claimed bound is not obtained by assuming its own conclusion, by fitting any quantity to the target output, or by citing the authors' own prior work as the source of the result.
Assumptions & free parameters
free parameters (8)
- beta (adaptive threshold excess) =
2 in experiments
- dmax (maximum adaptive degree) =
50 in experiments; 3 in the Section 6.2 example
- bmin (minimum bias) =
0.5 in experiments
- bmax (maximum bias) =
2 in experiments
- Clb (lower confidence bound multiplier) =
1 in experiments
- Cub (upper confidence bound multiplier) =
3 in experiments
- privacy split for MAD2R =
[0.1, 0.9] in experiments
- Delta0 (degree cap) =
100 in experiments
assumptions (7)
- standard math Gaussian mechanism analytical calibration (Proposition 2.4, Balle-Wang)
- standard math Basic composition of differentially private mechanisms
- domain assumption Weight-and-threshold meta-algorithm privacy framework
- domain assumption User-level DP with neighboring datasets differing by adding or removing one user
- domain assumption Unbounded universe Sigma with Gaussian noise added to all items in the analysis
- domain assumption Subsampling user sets to cap cardinality at Delta0
- standard math Taylor expansion and derivative analysis in Lemma 5.8
Cite this review
Pith. "Pith review of Scalable Private Partition Selection via Adaptive Weighting." pith.science (2026). https://pith.science/paper/BWZCOCLM
@misc{pith2026250208878,
author = {Pith},
title = {Pith review of: Scalable Private Partition Selection via Adaptive Weighting},
year = {2026},
howpublished = {\url{https://pith.science/paper/BWZCOCLM}},
note = {Machine review of arXiv:2502.08878}
}
read the original 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.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Daily financial news for 6000+ stocks
Miguel Aenlle. Daily financial news for 6000+ stocks
-
[2]
Plume: Differential privacy at scale
Kareem Amin, Jennifer Gillenwater, Matthew Joseph, Alex Kulesza, and Sergei Vassilvitskii. Plume: Differential privacy at scale. arXiv preprint arXiv:2201.11603 , 2022
arXiv 2022
-
[3]
Apache Software Foundation . Hadoop
-
[4]
Customer support on twitter, 2017
Stuart Axelbrooke. Customer support on twitter, 2017
work page 2017
-
[5]
Lightweight techniques for private heavy hitters
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Lightweight techniques for private heavy hitters. In 2021 IEEE Symposium on Security and Privacy (SP) , pages 762--776. IEEE, 2021
work page 2021
-
[6]
Google covid-19 vaccination search insights: Anonymization process description
Shailesh Bavadekar, Adam Boulanger, John Davis, Damien Desfontaines, Evgeniy Gabrilovich, Krishna Gadepalli, Badih Ghazi, Tague Griffith, Jai Gupta, Chaitanya Kamath, et al. Google covid-19 vaccination search insights: Anonymization process description. arXiv preprint arXiv:2107.01179 , 2021
arXiv 2021
-
[7]
Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Sadagopan Srinivasan, Krithi Ramamritham, Arun Kumar, M. P. Ravindra, Elisa Bertino, and Ravi Kumar, editors, Proceedings of the 20th international conference on World Wide Web , pages 58...
work page 2011
-
[8]
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning . PMLR, 2018
work page 2018
Show all 33 references
-
[9]
Differentially private histograms under continual observation: Streaming selection into the unknown
Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In International Conference on Artificial Intelligence and Statistics , pages 2397--2419. PMLR, 2022
2022
-
[10]
Incorporating item frequency for differentially private set union
Ricardo Silva Carvalho, Ke Wang, and Lovedeep Singh Gondara. Incorporating item frequency for differentially private set union. In Proceedings of the AAAI Conference on Artificial Intelligence , 2022
2022
-
[11]
MapReduce: Simplified Data Processing on Large Clusters
Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters . In OSDI'04: Sixth Symposium on Operating System Design and Implementation , pages 137--150, San Francisco, CA, 2004
2004
-
[12]
The algorithmic foundations of differential privacy
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3--4):211--407, 2014
2014
-
[13]
Differentially private partition selection
Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. Differentially private partition selection. In Proceedings on Privacy Enhancing Technologies , 2022
2022
-
[14]
Differentially private set union
Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Differentially private set union. In Proceedings of the 37th International Conference on Machine Learning . PMLR, 2020
2020
-
[15]
Differentially private optimization with sparse gradients
Badih Ghazi, Crist \'o bal Guzm \'a n, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Differentially private optimization with sparse gradients. arXiv preprint arXiv:2404.10881 , 2024
2024 arXiv
-
[16]
Sparsity-preserving differentially private training of large embedding models
Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Sparsity-preserving differentially private training of large embedding models. In Thirty-seventh Conference on Neural Information Processing Systems , 2023
2023
-
[17]
differential-privacy Library
Google . differential-privacy Library . https://github.com/google/differential-privacy/blob/main/common_docs/partition_selection.md, May 2024
2024
-
[18]
Differentially private n-gram extraction
Kunho Kim, Sivakanth Gopi, Janardhan Kulkarni, and Sergey Yekhanin. Differentially private n-gram extraction. Advances in neural information processing systems , 34:5102--5111, 2021
2021
-
[19]
Releasing search queries and clicks privately
Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th international conference on World wide web , 2009
2009
-
[20]
A model of computation for mapreduce
Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages 938--948. SIAM, 2010
2010
-
[21]
SNAP Datasets : Stanford large network dataset collection
Jure Leskovec and Andrej Krevl. SNAP Datasets : Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014
2014
-
[22]
Maas, Raymond E
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies , pages 142--15...
2011
-
[23]
Hidden factors and hidden topics: understanding rating dimensions with review text
Julian McAuley and Jure Leskovec. Hidden factors and hidden topics: understanding rating dimensions with review text. Proceedings of the 7th ACM conference on Recommender systems , 2013
2013
-
[24]
OpenMined PipelineDP Library
OpenMined . OpenMined PipelineDP Library . https://github.com/OpenMined/PipelineDP, May 2024
2024
-
[25]
PyDP Library: Partition Selection
PyDP . PyDP Library: Partition Selection . https://pydp.readthedocs.io/en/stable/pydp.html\#partition-selection, May 2024
2024
-
[26]
DP-SIPS : A simpler, more scalable mechanism for differentially private partition selection
Marika Swanberg, Damien Desfontaines, and Samuel Haney. DP-SIPS : A simpler, more scalable mechanism for differentially private partition selection. In Proceedings on Privacy Enhancing Technologies , 2023
2023
-
[27]
Simple/normal wikipedia abstracts v1
Mark Wijkhuizen. Simple/normal wikipedia abstracts v1
-
[28]
Differentially private sql with bounded user contribution
Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. arXiv preprint arXiv:1909.01917 , 2019
1909 arXiv
-
[29]
Differentially private SQL with bounded user contribution
Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private SQL with bounded user contribution. In Proceedings on Privacy Enhancing Technologies , 2020
2020
-
[30]
Differentially private stream processing at scale
Bing Zhang, Vadym Doroshenko, Peter Kairouz, Thomas Steinke, Abhradeep Thakurta, Ziyin Ma, Himani Apte, and Jodi Spacek. Differentially private stream processing at scale. arXiv preprint arXiv:2303.18086 , 2023
2023 arXiv
-
[31]
Federated model decomposition with private vocabulary for text classification
Zhuo Zhang, Xiangjing Hu, Lizhen Qu, Qifan Wang, and Zenglin Xu. Federated model decomposition with private vocabulary for text classification. In Empirical Methods in Natural Language Processing 2022 , pages 6413--6425. Association for Computational Linguistics (ACL), 2022
2022
-
[32]
Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J
Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. Apache Spark: a unified engine for big data processin...
2016
-
[33]
Character-level convolutional networks for text classification
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 28. Curran Associates, Inc., 2015
2015
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.