Research map / Federated learning and privacy / Differential privacy
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
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.
Shows that subsampling a one-sided (add) DP mechanism yields two-sided pure DP, and applies this to get pure-DP algorithms for decomposable submodular maximization, set cover, metric k-median/means, and shifting heavy hitters.
Problem
Pure-DP algorithms for private combinatorial optimization (decomposable submodular maximization, set cover, metric clustering) and shifting heavy hitters, where prior good-error algorithms were only approximate-DP.
Approach
If a mechanism is one-sided add-DP, its Poisson-subsampled version is two-sided pure DP with epsilon = ln(max{1/(1-p), 1+p(e^{eps0}-1)}); combined with individualized privacy accounting for repeated exponential mechanism and repeated above threshold, this yields pure-DP algorithms with tight errors.
Key results
- Pure-DP monotone submodular maximization under cardinality constraint achieves (1-1/e-eta)-approximation with O(k log(m/beta)/(eta eps)) error, improving prior approx-DP error by O(log(1/delta)) and matching the Omega(k log m / eps) lower bound.
- Pure-DP set cover achieves O(log n + log(m/beta)/eps) approximation, improving prior approx-DP O(log n + log m log(1/delta)/eps) by a log(1/delta) factor.
- Pure-DP shifting heavy hitters achieves error O(k log(T|Y|/beta)/eps), with a matching packing lower bound up to constants for pure DP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Poisson subsampling to repeated exponential mechanism | DPSubmodGreedy · Monotone submodular maximization, cardinality constraint | error: O\left(\frac{k \log (m/\beta)}{\eta \varepsilon}\right) | Helped |
| Apply Poisson subsampling to the private continuous greedy algorithm | PrivContGreedy · Monotone submodular maximization, matroid constraint | error: O\left(\frac{k \log\left(\frac{m}{\eta\beta}\right)}{\eta \varepsilon}\right) | Helped |
| Use repeated above threshold with subsampling | DPGreedyScaling · Set Cover | approximation ratio: O\left(\log n + \frac{\log(m/\beta)}{\varepsilon}\right) | Helped |
| Apply Poisson subsampling to the one-sided-DP clustering algorithm | Private metric k-median and k-means algorithm · Metric k-median and k-means | error: O\left(\frac{k \log(mn)}{\varepsilon}\right) | Helped |
| Use pure-DP subsampled ThreshMonitor instead of the approximate-DP heavy-hitter algorithm | Shifting heavy hitters algorithm · Shifting heavy hitters | error: O\left(\frac{k \log(T|\mathcal{Y}|/\beta)}{\varepsilon}\right); \tilde{O}\left(\frac{\sqrt{k} \log(1/\delta) \log(T|\mat | Mixed |
| Subsample a one-sided-DP mechanism to obtain two-sided DP | One-sided add-DP mechanisms · Privacy accounting | privacy guarantee: \varepsilon | Helped |
Surprising findings
- Basic composition-free repeated exponential mechanism is not pure-DP with epsilon = o(L eps0) without subsampling, showing the naive two-sided analysis fails.
Limitations
- Requires monotonicity of scoring functions, so does not apply to non-monotone submodular maximization.
- Does not extend to general low-sensitivity submodular functions; technique relies on decomposability.
Experimental setup
Metrics: approximation ratio additive error
Baselines: Gupta et al. 2010 DP submodular greedy (approx-DP) Chaturvedi et al. matroid submodular (approx-DP) Gupta et al. private set cover approx-DP private k-median Upadhyay/Bun-style shifting heavy hitters (approx-DP)
Builds on: Gupta et al. repeated exponential mechanism for private submodular maximization Poisson subsampling amplification AboveThreshold / sparse vector technique greedy scaling set cover
Closest papers by meaning
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.87)
- Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification (NeurIPS 2024 · similarity 0.86)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.86)
- Scalable DP-SGD: Shuffling vs. Poisson Subsampling (NeurIPS 2024 · similarity 0.85)
- Privacy Profiles for Private Selection (ICML 2024 · similarity 0.85)
- How Private are DP-SGD Implementations? (ICML 2024 · similarity 0.85)
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.