Research map / Federated learning and privacy / Differential privacy

Scalable Private Partition Selection via Adaptive Weighting

ICML 2025 · Federated learning and privacy › Differential privacy · approach: Differentially private clustering · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes MAD and MAD2R, scalable parallel weight-and-threshold algorithms for differentially private partition selection that reroute excess weight to light items, with stochastic dominance over the basic uniform weighting method.

Problem

User-level differentially private partition selection (private set union / key discovery): output as many items as possible from the union of users' sets, in a form that can run in massively parallel systems at very large scale.

Approach

An adaptive, non-uniform weighting that truncates weight above an adaptive threshold and reroutes the excess back to users' other items, with the same sensitivity (and hence noise and threshold) as uniform weighting; a two-round variant reuses noisy round-one weights to prune and bias round-two weights.

Key results

• MAD2R yields the best parallel output size on seven of nine datasets, e.g. 17785 items on Finance vs 16926 for DP-SIPS and 12412 for Basic.
• MAD always outperforms Basic on every dataset, consistent with the stochastic dominance proof (e.g. 35797 vs 35315 on Amazon).
• On Common Crawl (about 800 billion entries), MAD2R outputs 29,373,829 items versus 28,328,613 for DP-SIPS and 15,734,148 for Basic, with parallel runs finishing within 4 hours.

Measured effects reported in the paper

Surprising findings

• On the small datasets, the sequential PolicyGaussian and GreedyUpdate outperform all parallel methods, with GreedyUpdate's performance strongly dataset-dependent.
• On Clueweb, DP-SIPS outperforms the MAD variants, which the authors attribute to outlier statistics where the number of unique items is less than the number of users.

Limitations

• Sequential baselines (PolicyGaussian, GreedyUpdate) remain better on small datasets, with MAD2R reaching at least 86% of PolicyGaussian's output.
• Parameters such as d_max, beta, b_min, b_max and privacy splits were chosen by the authors, and DP-SIPS was given its best of two privacy splits.
• Experiments use delta=1e-5 for consistency with prior work, while production deployments usually need smaller delta.

Experimental setup

Datasets: Higgs IMDb Reddit Finance Wiki Twitter Amazon Clueweb Common Crawl

Benchmarks: Higgs IMDb Reddit Finance Wiki Twitter Amazon Clueweb Common Crawl

Metrics: output size (number of items released)

Baselines: Basic DP-SIPS PolicyGaussian GreedyUpdate

Builds on: DP-SIPS weight and threshold partition selection Gaussian mechanism PolicyGaussian GreedyUpdate

Closest papers by meaning

• On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)
• Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees (NeurIPS 2026 · similarity 0.85)
• Privacy Profiles for Private Selection (ICML 2024 · similarity 0.85)
• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.85)
• It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.85)
• Differentially Private Set Representations (NeurIPS 2024 · similarity 0.85)