mlsanityData to 7 Oct 2026

On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

arXiv 2402.16778 ↗First posted 26 Feb 2024cs.LG cs.CRcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, we provide lower bounds for Differentially Private (DP) Online Learning algorithms. Our result shows that, for a broad class of (varepsilon,δ)-DP online algorithms, for number of rounds T such that log T≤ O(1 / δ), the expected number of mistakes incurred by the algorithm grows as Omega(log fracTδ). This matches the upper bound obtained by Golowich and Livni (2021) and is in contrast to non-private online learning where the number of mistakes is independent of T. To the best of our knowledge, our work is the first result towards settling lower bounds for DP-Online learning and partially addresses the open question in Sanyal and Ramponi (2022).

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 13 of its 32 references that are in the map. First posted on arXiv 26 Feb 2024.

Builds on

13 of 32 references.

References · 13

  1. 2018Private PAC learning implies finite Littlestone dimensioncited by 73
  2. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 62
  3. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  4. 2018Privacy-preserving Predictioncited by 48
  5. 2021The Price of Differential Privacy under Continual Observationcited by 32
  6. 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
  7. 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
  8. 2014Characterizing the Sample Complexity of Private Learnerscited by 19
  9. 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
  10. 2021Littlestone Classes are Privately Online Learnablecited by 10
  11. 2015Robust Mediators in Large Gamescited by 6
  12. 2023Private Everlasting Predictioncited by 5
1 more
  1. 2022Do you pay for Privacy in Online learning?cited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queriescited by 11
  2. 2024The Limits of Differential Privacy in Online Learningcited by 5
  3. 2025Private Learning of Littlestone Classes, Revisitedcited by 3
  4. 2025Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settingscited by 1
  5. 2026Privately Learning Decision Lists and a Differentially Private Winnowcited by 0