Research map / Federated learning and privacy / Differential privacy
It's My Data Too: Private ML for Datasets with Multi-User Training Examples
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.
Introduces multi-attribution user-level DP (fixed-graph DP) for training where examples are attributed to multiple users, and a greedy contribution-bounding baseline with DP-SGD/DP-MF variants evaluated on arXiv abstracts and synthetic logistic regression.
Problem
User-level differential privacy for model training when each training example can be attributed to multiple users (e.g., emails with several senders/receivers), where standard single-attribution reductions fail and selecting a contribution-bounded subset is NP-hard.
Approach
Defines fixed-graph (fixed-hypergraph) DP that protects all examples attributed to one user while the attribution hypergraph is fixed, reduces training to contribution bounding (selecting a subset with at most k examples per user), and proposes greedy contribution-bounding algorithms for DP-SGD (with/without duplicates) and DP-MF (min-separation), empirically studying their suboptimality and bias-
Key results
- Greedy contribution bounding retrieves about 98.7% of the ILP-optimal number of examples on arXiv for k=2,3, with at most 1.25% larger noise multiplier and at most 0.25% test loss increase.
- On arXiv, DP-SGD with duplicates outperforms DP-MF at all epsilon values tested.
- On arXiv, greedy contribution bounding performs noticeably worse than training on a random subset of equal size, with the gap comparable to reducing epsilon by a factor of sqrt(2) or more, indicating bias towards examples with fewer users matters.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allow duplicate examples in greedy contribution bounding (ablation) | DP-SGD contribution bounding on arXiv · arXiv test set | loss | Helped |
| allow duplicate examples in greedy contribution bounding (ablation) | DP-SGD contribution bounding on synthetic logistic regression · Synthetic logistic regression test set | accuracy | Mixed |
| use DP-MF instead of DP-SGD (ablation) | Training on arXiv · arXiv test set | loss | Hurt |
| use DP-MF instead of DP-SGD (ablation) | Training on synthetic logistic regression · Synthetic logistic regression test set | accuracy | Mixed |
| use greedy contribution bounding instead of the ILP solution (ablation) | DP-SGD contribution bounding without duplicates · arXiv | number of selected examples: ≈ 98.7% of the ILP solution value | Hurt |
| use greedy contribution bounding instead of the ILP solution (ablation) | DP-SGD contribution bounding without duplicates · arXiv test set | loss: at most $.25% | Hurt |
| use greedy contribution bounding instead of the ILP solution (ablation) | DP-SGD contribution bounding without duplicates · arXiv | noise multiplier: at worst a 1.25% larger noise multiplier | Hurt |
| use the ILP rather than greedy contribution bounding while allowing duplicates (ablation) | DP-SGD contribution bounding · arXiv test set | training outcome | Hurt |
| select examples with greedy contribution bounding rather than a random subset of equal size (ablation) | Contribution-bounded training · arXiv test set | loss | Hurt |
| select examples with greedy contribution bounding rather than a random subset of equal size (ablation) | Contribution-bounded training · Synthetic logistic regression test set | accuracy | Hurt |
| select random examples with more than the median number of users rather than a random subset of all data (ablation) | Random-subset training · arXiv test set | loss | Helped |
| mitigate selection bias by alternating between low- and high-user-count examples (ablation) | Greedy contribution bounding · Synthetic logistic regression test set | accuracy | Helped |
Surprising findings
- Training on a random subset of examples with more users outperforms the greedy subset of equal size, showing that examples with more attributed users tend to be higher quality.
- Allowing duplicates helps for arXiv at all epsilon values, implying noise reduction matters more than bias reduction for transformer training, while for logistic regression duplication helps only below a threshold epsilon.
Limitations
- Contribution bounding maximizing subset size is NP-hard, so the greedy baseline has no approximation guarantee in general.
- Min-separation DP-MF lacks tight amplification guarantees, forcing a choice between DP-SGD with amplification and DP-MF without it.
- Fixed-graph DP is weaker than node DP; the hypergraph structure must be treated as public or independent of contents.
Experimental setup
Datasets: arXiv abstracts with author attribution synthetic hypergraph logistic regression data
Benchmarks: arXiv masked language modeling test loss synthetic logistic regression test accuracy
Metrics: test loss test accuracy dataset size noise multiplier
Baselines: DP-SGD with duplicates greedy contribution bounding DP-SGD without duplicates greedy ILP-optimal contribution bounding random subset selection
Builds on: DP-SGD DP-FTRL / DP matrix factorization (BandMF) node-level DP
Closest papers by meaning
- Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy (ICML 2019 · similarity 0.92)
- Optimal Algorithms for Fixed-Graph Multi-Attribution Privacy (NeurIPS 2026 · similarity 0.90)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.89)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.87)
- Differentially Private Model Merging (NeurIPS 2026 · similarity 0.87)
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.