Research map / Federated learning and privacy / Differential privacy
Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy
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.
Improves sample and user complexity bounds for pure differentially private agnostic learning under item-level and user-level privacy, including a nearly tight user complexity for thresholds.
Problem
Determining the sample complexity of pure private agnostic learning under item-level DP and the user complexity under user-level DP, where gaps existed between upper and lower bounds.
Approach
Replace the empirical error score in the representation-based exponential mechanism learner with a surrogate score (min over concepts of empirical error plus disagreement), so only agnostic generalization for C (VC-based) and realizable generalization for disagreements are needed; extend to user-level via user-level error amplified by sqrt(m), and for thresholds use median-based binary search expl
Key results
- Item-level pure private agnostic learner with sample complexity O~(RepD(C)/(alpha*eps) + VC(C)/alpha^2), matching the lower bound up to polylog factors (Theorem on item-level).
- User-level generic learner with user complexity O~(RepD/eps + RepD/(sqrt(m) alpha eps) + VC/(m alpha^2)), improving the third term from RepD/(m alpha^2) to VC/(m alpha^2).
- For thresholds under user-level DP, user complexity O~(log|X|/eps + log|X|/(m alpha eps) + 1/(sqrt(m) alpha eps) + 1/(m alpha^2)), which is nearly tight, matching the lower bound up to polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the surrogate score based on minimum concept error plus disagreement instead of the hypothesis empirical error | Pure-private item-level agnostic learner for arbitrary concept classes · Agnostic learning, item-level privacy | sample complexity: \widetilde{O}\left(\frac{\mathrm{RepD}(\mathcal{C})}{\alpha\varepsilon} + \frac{\mathrm{VC}(\mathcal{C})}{\alpha^2}\righ | Helped |
| Replace item-level error and disagreement with user-level analogues | Pure-private user-level agnostic learner for arbitrary concept classes · Agnostic learning, user-level privacy | user complexity: \widetilde{O}\left(\frac{\mathrm{RepD}(\mathcal{C})}{\varepsilon}+\frac{\mathrm{RepD}(\mathcal{C})}{\sqrt{m}\alpha\varep | Helped |
| Use distribution-median splitting with a private median selection procedure instead of midpoint splitting | Pure-private threshold learner · Thresholds over X, user-level privacy | user complexity: \widetilde{O}\left(\frac{\log|X|}{\sqrt{m}\alpha\varepsilon}\right) vs. \widetilde{O}\left(\frac{\log|X|}{m\alpha\vareps | Helped |
Surprising findings
- The authors found that the prior threshold user-level upper bound claimed by Ghazi et al. was incorrect; their algorithm does not achieve the claimed complexity and has a suboptimal term.
Limitations
- Gap remains between upper and lower bounds for the second term of the general user-level bound (RepD/(sqrt(m) alpha eps)).
- Assumes each user holds the same number of examples m.
- Thresholds result is the only fully tight user-level case; general concept classes remain open.
Experimental setup
Metrics: sample complexity user complexity
Baselines: Beimel et al. agnostic learner Ghazi et al. user-level learner Alon et al. realizable-to-agnostic transformation
Builds on: probabilistic representation dimension exponential mechanism user-level private learning (Ghazi et al.) realizable-to-agnostic transformation
Closest papers by meaning
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.88)
- Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.87)
- Provable Privacy with Non-Private Pre-Processing (ICML 2024 · similarity 0.87)
- It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.86)
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.86)
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · 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.