The Limits of Differential Privacy in Online Learning

We thank the reviewer for the constructive comments, and our detailed responses are listed below.

figure/meta-theorem that neatly explains all the relationships.

We will add a figure to explain the relationships in the revision.

Our main results imply that there exists a hypothesis class such that:

the best known upper bound

For pure DP, the best known upper bound is $O_{\mathcal{H}}(\log^2 T)$ as in our Theorem 3.3. This is larger than our lower bound by a factor of $\log T$. We show that $O_{\mathcal{H}}(\log T)$ is achievable for some specific hypothesis classes (Appendix F, page 20-21). Whether the $\log T$ dependence is attainable for generic hypothesis classes remains open (page 12, line 480-483).

For approximate DP, Golowich and Livni [30] proposed an algorithm with $O_{\mathcal{H}}(\log T)$ mistakes against oblivious adversaries. Thus, our lower bound is tight assuming a constant Littlestone dimension. However, their algorithm exhibits an $O_{\mathcal{H}}(\sqrt{T})$ upper bound against adaptive adversaries. It remains open whether this can be improved to $O_{\mathcal{H}}(\log{T})$.

We will include the above discussion in the revision.

[30] Noah Golowich and Roi Livni. Littlestone classes are privately online learnable. In Advances in Neural Information Processing Systems, volume 34, pages 11462–11473, 2021.

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]).

Yes, the type of classes we require in Section 4 is equivalent to the notion of non-trivial classes in [1, 2]. We will add some comments and related works on this in the revision. Thanks for pointing this out.

[1] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255–275, 2002.

[2] S. Hanneke, A. Karbasi, M. Mahmoody, I. Mehalel, and S. Moran. On optimal learning under targeted data poisoning. In Advances in Neural Information Processing Systems36, 2022.

Suggestions: Line 84: you wrote $\epsilon$ before defining DP.

We will add a forward reference in the revision.

Suggestions: 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.

Yes, your interpretation is precise. We will clarify this sentence in the revision.

Suggestions: 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.

We will rewrite the paragraph to make it more accessible and move it to an appropriate place in the revision. The paragraph is about the gap between our upper bound ($O_{\mathcal{H}}(\log^2 T)$) and lower bound ($O_{\mathcal{H}}(\log T)$) on pure DP online learning.

Typos/English:

We will fix the typos in the revision. Thank you for pointing them out.

We thank the reviewer for the constructive comments, and our detailed responses are listed below.

The proof of Theorem 4.3 is not clear

We will polish the proof of Theorem 4.3 to make it more clear in the revision.

It looks like Lemma E.2 shows the concentration assumption in Dmitriev et al. Can you give some intuition on how the proof of Theorem 4.3 get rid of this assumption? Also, are there examples of DP online learning algorithms that do not satisfy their concentration assumption?

Our Lemma E.2 is essentially different from their assumption.

• In their assumption, it is required that $\Pr[\forall t\in[T], A(S_0)_t(u_1) = f_1(u_1)]\ge 1 - \beta$. Roughly speaking, they require that with high probability, the predictions (on $u_1$) are the same for the entire time span when running on $S_0$.
• In our Lemma E.2, we only require that $\Pr[A(S_0)_t(u_1) = f_1(u_1)]\ge 1/2$ for each $t$. We allow the predictions to be different at different rounds, which is more general.

A straightforward example is an algorithm that predicts uniformly randomly at each time-step. The algorithm is $(0, 0)$-DP, and satisfies our Lemma E.2. But it does not fit the assumption made by Dmitriev et al. since the probability that all predictions are the same is only $1/2^{T-1}$.

Our proof strategy is also completely different from theirs and does not rely on the assumption. In our proof, we first construct a series of sequences $S_1, \dots, S_m$, where each of them is obtained from $S_0$ by replacing $\log T$ (Algorithm 2 on page 8) data points. By the property of DP, any DP algorithm should output similarly on every $S_i$. We then use a binary search approach (Algorithm 3 on page 9) to show that the outputs cannot be too similar if the algorithm makes less than $\log T$ mistakes. Combining the two steps leads to the desired lower bound.

We thank the reviewer for the constructive comments, and our detailed responses are listed below.

no conclusions, discussion, further work, limitations

We state our main conclusions in Section 1.1, which are the separation results between no DP, pure DP, and approximate DP online learning. The discussion on the limitations and future work were put in Appendix A due to the space restrictions.

We will polish the structure of the paper to make it more accessible in the revision.

illustrative experiments or extensive examples.

We will provide some examples in the revision.

Thanks for the review and comments, and we have further clarified a few places to make it more accessible.