mlsanityData to 14 Oct 2026

The Limits of Differential Privacy in Online Learning

arXiv 2411.05483 ↗First posted 8 Nov 2024cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Differential privacy (DP) is a formal notion that restricts the privacy leakage of an algorithm when running on sensitive data, in which privacy-utility trade-off is one of the central problems in private data analysis. In this work, we investigate the fundamental limits of differential privacy in online learning algorithms and present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. This indicates that approximate DP must be adopted when dealing with adaptive adversaries. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes. This essentially generalizes previous results and shows a strong separation between private and non-private settings since a finite mistake bound is always attainable (as long as the class is online learnable) when there is no privacy requirement.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 18 of its 46 references that are in the map. First posted on arXiv 8 Nov 2024.

Builds on

18 of 46 references.

References · 18

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  3. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  4. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  5. 2017The Price of Differential Privacy For Online Learningcited by 45
  6. 2021The Price of Differential Privacy under Continual Observationcited by 34
  7. 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
  8. 2019Privately Learning Thresholds: Closing the Exponential Gapcited by 31
  9. 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
  10. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  11. 2022~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimizationcited by 18
  12. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
6 more
  1. 2022On Optimal Learning Under Targeted Data Poisoningcited by 14
  2. 2024Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queriescited by 12
  3. 2021Littlestone Classes are Privately Online Learnablecited by 10
  4. 2023Near-Optimal Algorithms for Private Online Optimization in the Realizable Regimecited by 9
  5. 2024On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspectivecited by 5
  6. 2022Do you pay for Privacy in Online learning?cited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025Private Learning of Littlestone Classes, Revisitedcited by 3
  2. 2025Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settingscited by 1
  3. 2026Privately Learning Decision Lists and a Differentially Private Winnowcited by 1
  4. 2025Hierarchical Dual-Strategy Unlearning for Biomedical and Healthcare Intelligence Using Imperfect and Privacy-Sensitive Medical Datacited by 0
  5. 2026Balancing Fairness, Privacy, and Accuracy: A Multitask Adversarial Framework for Centralized Data-Driven Systemscited by 0