Research map / Federated learning and privacy / Differential privacy
The Limits of Differential Privacy in Online Learning
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 private online learning under pure DP cannot achieve finite mistakes for point functions against adaptive adversaries, and that any private learner for a non-trivial class makes Omega(LD(H) log T / epsilon) mistakes, separating no-DP, pure DP, and approximate DP.
Problem
Characterizing the fundamental limits (learnability and mistake counts) of online learning under differential privacy, separating no DP, pure DP, and approximate DP.
Approach
Uses a multiplicative-weights adaptive adversary to force pure-DP online learners on point functions to err Omega(min(log d, T)) times, and a packing argument with a smoothed binary search over time-steps to show Omega(LD(H) log T) mistakes for any non-trivial class under (epsilon, delta)-DP.
Key results
- Pure DP online learner for point functions over N must make Omega(T) mistakes against adaptive adversaries (corollary), while approximate DP can learn it.
- Any (epsilon,delta)-DP online learner for a class with two non-complementary hypotheses incurs Omega(log T / epsilon) expected mistakes even against oblivious adversaries, and Omega(LD(H) log T / epsilon) in general.
- Pure DP oblivious-adversary upper bound O(log^2 T (RepDim + log log T)^2 / epsilon), with a log T algorithm for POINT_N achieved in the appendix.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require pure differential privacy instead of no privacy | Online learning for classes containing non-complementary hypotheses · Oblivious adversary | mistakes: \mathtt{LD}(\mathcal{H}) -> \Omega(\mathtt{LD}(\mathcal{H})\log T/\varepsilon) | Hurt |
| Use pure instead of approximate differential privacy | Online learning for POINT_N · Adaptive adversary | learnability | Hurt |
| Use approximate differential privacy instead of pure differential privacy | Online learning · Oblivious adversary | mistakes: O_{\mathcal{H}}(\log^2 T\cdot (\log\log T)^2) -> O_{\mathcal{H}}(\log T) | Helped |
| Use approximate differential privacy instead of pure differential privacy | Online learning for POINT_N · Adaptive adversary | learnability | Helped |
| Use the POINT_N-specific pure-DP algorithm instead of the general pure-DP upper-bound construction | Pure-DP online learning for POINT_N · Realizable, oblivious adversary | expected mistakes: O\left(\frac{\log^2T(\mathtt{RepDim}(\mathcal{H}) + \log\log T)^2}{\varepsilon}\right) -> O(\log T/\varepsilon) | Helped |
| Impose privacy rather than allowing a non-private learner | Online learning for classes containing non-complementary hypotheses · Oblivious adversary, as T grows | finiteness of mistakes: \mathtt{LD}(\mathcal{H}) -> \Omega(\mathtt{LD}(\mathcal{H})\log T/\varepsilon) | Hurt |
Surprising findings
- Pure DP online learnability fails against adaptive adversaries even for point functions over N, which are offline learnable under pure DP.
Limitations
- Upper bounds under pure DP are log^2 T scale, not matching the log T lower bound for generic classes.
- Lower bound requires delta = o(1/T) for constant epsilon.
- Results do not cover stochastic adversaries or constant-probability success.
Experimental setup
Metrics: expected mistake bound regret
Baselines: Standard Optimal Algorithm DP-OPE algorithm approximate DP online learner for Littlestone classes
Builds on: Littlestone dimension representation dimension DP-OPE packing argument AboveThreshold
Closest papers by meaning
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.91)
- Auditing Private Prediction (ICML 2024 · similarity 0.90)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.90)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.89)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.89)
- A Unified Framework for Adversary-Aware Differential Privacy Bounds (NeurIPS 2026 · similarity 0.88)
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.