Research map / Federated learning and privacy / Differential privacy
Differentially Private Submodular Maximization: Data Summarization in Disguise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exponential mechanism greedy vs large margin mechanism greedy (cardinality constraint) | Private greedy for location selection · Uber pickups, Manhattan | utility | No clear effect |
| Replace exponential mechanism with large margin mechanism in greedy (ablation) | Private greedy for location selection · Uber pickups, Manhattan | utility | Hurt |
| Private greedy (EM or LMM) vs fully random selection at small epsilon | Private greedy for location selection · Uber pickups, Manhattan | utility | Helped |
| Private mechanisms vs non-private greedy on feature selection | Private greedy for feature selection · NHANES diabetes features | mutual information utility | No clear effect |
| Subsample-greedy (1/k fraction per round) for non-monotone objectives, guarantee 1/e(1-1/e) with |V| evaluations | Non-monotone cardinality-constrained submodular maximization · theory | approximation ratio: 0.2325 guarantee vs no constant before | Helped |
| Plain greedy used for non-monotone objectives | Non-monotone submodular maximization · theory | approximation | Hurt |
| Privacy budget split across k iterations via basic composition (eps0 = eps/k) instead of advanced composition | EM-based greedy on location privacy · Uber pickups, Manhattan | utility | No clear effect |
Closest papers by meaning
- Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints (ICML 2018 · similarity 0.94)
- Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints (ICML 2020 · similarity 0.93)
- Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization (ICML 2024 · similarity 0.87)
- Improved Algorithms for Fair Matroid Submodular Maximization (NeurIPS 2025 · similarity 0.87)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.87)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.86)
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.