Research map / Federated learning and privacy / Differential privacy
Oracle-Efficient Differentially Private Learning with Public Data
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.
Gives the first computationally efficient (oracle-efficient, poly many ERM calls) semi-private learners that leverage unlabeled public data under bounded density-ratio shift, with improved sample complexity for convex classes and binary classification.
Problem
Semi-private learning with public unlabeled data was statistically tractable but computationally inefficient (exponential-size covers); the paper asks whether this overhead is necessary when non-private ERM is efficient.
Approach
Use ERM on Gaussian-process-perturbed (or regularized) private objectives to get a stable estimator, then output-perturb the function on public points by minimizing a noisy empirical norm; for classification, perturb the ERM objective with Laplace-weighted public labels so the projection onto public data is private without a second perturbation.
Key results
- Generic oracle-efficient semi-private learner needs poly(d) private samples with only poly many ERM oracle calls, under bounded density ratio between public and private marginals.
- Convex-class regularization variant improves private sample complexity to roughly (sup_m Gbar_m)^2 * eps^-1 * alpha^-5, versus alpha^-14 for the general algorithm.
- Binary classification algorithm (RRSPM) attains O(alpha^-5) sample complexity for pure DP (O(alpha^-4) for approximate DP), using only 2 ERM calls.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Gaussian-process perturbations and averaging with regularization for convex classes (ablation) | Oracle Efficient Private Learner · Semi-private learning, convex function classes | private labeled sample complexity dependence on accuracy: O\left( \mathsf{vc}(\cF) \cdot \varepsilon^{-3} \cdot \alpha^{-14} \right) -> (\sup_m \overline{\cG}_m(\cF))^2 \cdot \va | Helped |
| Use RRSPM instead of the general perturbation algorithm | Oracle-efficient private binary classification · Binary classification, agnostic | private labeled sample complexity dependence on accuracy: O(\alpha^{-14}) -> O(\alpha^{-5}) | Helped |
| Use Gaussian perturbations instead of Laplace perturbations (ablation) | RRSPM · Binary classification, agnostic | private labeled sample complexity dependence on accuracy: \alpha^{-5} -> \alpha^{-4} | Helped |
| Assume realizability (ablation) | RRSPM · Binary classification, pure DP | private labeled sample complexity dependence on accuracy: \alpha^{-5} -> \alpha^{-3} | Helped |
| Assume realizability (ablation) | RRSPM with Gaussian perturbations · Binary classification, approximate DP | private labeled sample complexity dependence on accuracy: \alpha^{-4} -> \alpha^{-2.5} | Helped |
Limitations
- Sample complexity remains far from the optimal alpha^-2 rate achieved by inefficient public-data methods.
- The general algorithm's sample complexity is a large polynomial in accuracy parameters.
- Convexity of the loss is essential for privacy in the regularization variant but not needed for the learning guarantee, leaving the role of such assumptions open.
Experimental setup
Metrics: sample complexity excess loss
Baselines: Exponential-mechanism semi-private learner (Bassily et al.) Oracle-efficient perturbation learner (Algorithm 1) Oracle-efficient regularization learner (Algorithm 2)
Builds on: exponential mechanism follow-the-perturbed-leader follow-the-regularized-leader separator sets universal identification sets
Closest papers by meaning
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.89)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.89)
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · similarity 0.88)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.88)
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.88)
- Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy (ICML 2024 · 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.