Summary
The paper studies online learning of concept classes under DP (differential privacy) constraint. The paper makes progress towards understanding mistake bounds (mostly) in the realizable case in a few settings. Concretely, The paper shows that:
1. If the adversary is oblivious, then PAC pure DP learnability implies online pure DP learnability.
2. On the other hand, if the adversary is adaptive, then PAC pure DP learnability does not imply online pure DP learnability.
3. In contrast with the standard online learning model, for every non-trivial hypothesis class, the mistake bound depends on $T$.
Strengths
1. Assuming that the results are correct, the paper contains a significant improvement towards understanding mistake bounds in online learning under DP constraint.
2. The questions and results are interesting and in the scope of NeurIPS.
3. The proof techniques are explained in detail.
Weaknesses
1.It is a bit hard to digest the results and understand the remaining gaps, because there are many settings considered in the paper (DP/non-DP, oblivious/adaptive, approximate/pure...), and no figure/meta-theorem that neatly explains all the relationships. Such a figure/meta-theorem would significantly improve the presentation of the paper.
2. As a consequence of the above, it is not exactly clear how tight the results are. If you prove a lower bound (as in Section 4), I think it is better to formally state, right after it, the best known lower bound (and the dual statement for proving a lower bound).
Questions
Questions:
1. I think that the type of classes you require in Section 4 is related (or equivalent?) to the notion of "non-trivial classes" which is used in lower bounds for learning with data poisoning. See, e.g., [1,2]. This setting is also related to some notions of "stability", like DP (see [2]).
2. What is the best known upper bound for the result of Section 4?
Suggestions:
1. Line 84: you wrote $\epsilon$ before defining DP.
2. If I understand correctly, the sentence in line 190 is supposed to say: "Our result reveals that, against oblivious adversaries, pure private online learnability is equivalent to pure private offline learnability in both realizable and agnostic settings." If so, I would recommend clarifying it.
3. The whole paragraph that begins at line 192 is unclear. It involves not yet stated results and definitions. Either remove it or move it to a suitable place.
4. It could be helpful to add a figure of the landscape of separations between the many settings discussed in the paper (DP/non-DP, oblivious/adaptive, approximate/pure...).
Typos/english:
1. line 146: "not known by" --> "unknown to"
2. line 264: "an lower" --> "a lower"
3. line 272: "inpupt"
[1] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. TheoreticalComputer Science, 288(2):255–275, 2002.
[2] S. Hanneke, A. Karbasi, M. Mahmoody, I. Mehalel, and S. Moran. On optimal learningunder targeted data poisoning. In Advances in Neural Information Processing Systems36, 2022.