Research map / Federated learning and privacy / Differential privacy
Private Prediction via Shrinkage
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 differentially private prediction can answer super-polynomially many adversarially streamed queries with polylog-in-T labeled samples, via subsample-and-aggregate plus BetweenThresholds with a shrinking version space.
Problem
Differentially private prediction (Dwork and Feldman) with T adversarially streamed queries: standard composition needs sample size growing as sqrt(T); the question is whether this can be reduced to polylog T under oblivious or adaptive online adversaries.
Approach
Run BetweenThresholds over a noisy majority vote of hypotheses learned on disjoint blocks; each "hard" query (⊤ output) shrinks the version space (random label guess halves label patterns for oblivious adversaries; hyperplane intersection for halfspaces), so only O(VC·log T) or O(d) hard queries occur, instead of sqrt(T) composition.
Key results
- Oblivious online adversary: private predictor answers T queries with |S| = Õ(VC^3.5 log^3.5 T) labeled examples.
- Adaptive online adversary for halfspaces over R^d: |S| = Õ(d^5.5 log T).
- Hard-query count bounded by O(VC·log T) (oblivious) and d+1 (halfspaces), so BetweenThresholds outputs ⊤ only that many times.
Surprising findings
- The polynomial dependence on VC dimension is larger than the sqrt(T) composition baseline for moderate T, trading VC-dependence for polylog T dependence.
Limitations
- Polynomial dependence on VC dimension (VC^3.5) is much worse than the O(VC) of offline/stochastic settings.
- Adaptive result only for halfspaces; general VC classes against adaptive adversaries remain open.
- Only privacy of the labeled sample is protected, not of the query stream.
Experimental setup
Metrics: labeled sample complexity
Baselines: Standard composition O(VC*sqrt(T)) Beimel et al. offline O(VC log T) Nandi and Bassily stochastic Naor et al. query privacy
Builds on: Dwork and Feldman private prediction Naor et al. private prediction BetweenThresholds (Bun et al.) Kaplan et al. halfspace cdepth Nissim et al. halfspace learning
Closest papers by meaning
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.89)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.89)
- Private Truly-Everlasting Robust-Prediction (ICML 2024 · similarity 0.87)
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.87)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.86)
- Auditing Private Prediction (ICML 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.