The Limits of Differential Privacy in Online Learning
Authors: Bo Li
Wei Wang
Peng Ye
Venue: NeurIPS 2024 poster (2024)
Keywords: online learning
differential privacy
Primary area: privacy

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

The Limits of Differential Privacy in Online Learning
Bo Li Wei Wang Peng Ye Department of Computer Science and Engineering The Hong Kong University of Science and Technology
Hong Kong SAR, China bli0ust.hi hk, weiwa@cse ust hk, pyeac9connect. ust. hk
Abstract
Differential privacy (DP) is a formal notion that restricts the privacy leakage of an algorithm when running sensitive data, in which privacy-utility trade-off is 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 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 strong separation between private and non-private settings since finite mistake bound is always attainable (as long as the class is online learnable) when there is no privacy requirement.
Introduction
Machine learning has demonstrated extraordinary capabilities in various industries, from healthcare to finance. Yet, it could raise serious privacy concerns as it may require access to vast amount of personal data. The data used to train machine learning models may also contain sensitive information such medical records or financial transactions. Therefore, is crucial ensure that the private data is well-protected during the training process.
Differential privacy (DP) (24 23 is a rigorous mathematical definition that quantifies the level of personal data leakage. In a nutshell, an algorithm is said to be differentially private if the change of any individual's 's data won't 't make the output significantly different. DP has become the standard 2)
notion of privacy and has been broadly employed
However, privacy is not a free lunch and usually comes at cost. Simple tasks may become much harder or even intractable when privacy constraints are imposed. It crucial to understand the cost to pay for privacy. For probably approximately correct (PAC) learning 44] [T] 43), which is the standard theoretical model of machine learning, there have been many works investigating the cost associated with privacy, which demonstrate huge discrepancy in terms of the cost under non-private, pure private, and approximate private constraints.
One central requirement in PAC learning is that the data need to be i.i.d. generated and given in advance. Such assumptions fail to capture many scenarios in practice. For example, fraud detection in financial transactions often needs to be handled in real time, which prohibits access to the entire dataset. Moreover, fraudulent patterns can change over time, and new types of fraud can emerge. In such a scenario, the data are clearly not i.i.d. and can even be adaptive to the algorithm's 's prior predictions, which the online learning model should be adopted.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Separation between three types of constraints
Oblivious adversary
Adaptive adversary
Finite mistakes?
Learnable?
Learnable?
No DP constraints
(39
[139]
x (Theorem 4.3
Approximate DP
[30]
50
X
Pure DP
(Theorem 4.3
(Theorem 3.3
(Theorem 3.5
Compared with private PAC learning, the limits of private online learning are less understood. For approximate DP, algorithms for Littlestone classes were proposed [30]. But for pure DP, the only
known result is the one for point functions given by Dmitriev et al. [22]. They also suggested that
one could leverage existing tools of DP continual observation 26 34 to design algorithms for finite
hypothesis classes and asked if generic learners can be constructed for infinite hypothesis classes.
Going beyond qualitative learnability, it is worth quantitatively exploring the number of mistakes made by an online learner. Without privacy, it is possible to achieve a mistake bound of at most the Littlestone dimension of the hypothesis class [39], which is independent of the total rounds T. Therefore, the number of mistakes is always bounded as T - co. However, all existing private online learning algorithms suffer from an error count that grows at least logarithmically with T. was asked by Sanyal and Ramponi [41] whether such a cost is inevitable for DP online learning. In recent work of Cohen et al. (2N. they showed that any private online learning algorithm for the class of point functions over [7'] must incur 2(log 7') mistakes. However, it remains open whether such cost unavoidable for generic hypothesis classes, especially for those with a smaller cardinality.
1.1 Main Results
We obtain results that separate three types of constraints: no DP, pure DP, and approximate DP.
Separation between pure and approximate DP. We first perform a systematic study of online learning under pure DP. We prove that every pure privately PAC learnable class is also pure privately online learnable against oblivious adversaries. answering question raised by Dmitriev et al. [22]. For the stronger adaptive adversaries, we obtain an impossibility result that the class of point functions over N, which can be pure privately learned in the offline model, is not online learnable under pure DP. According to the result of Golowich and Livni [30,, online learnable under approximate DP. Thus, our conclusion reveals a strong separation between these two privacy definitions.
Separation between private and non-private settings. We next quantitatively investigate the dependence on in the mistake bound. We show that for any hypothesis class H. any private online learning algorithm must make 2(log 7') mistakes unless H contains only one single hypothesis or exactly two complementary hypotheses (see Section for the definition). This largely generalizes previous results and indicates that such separation indeed exists universally. We further improve the lower bound to (((D(H) log I',, where LD(H) represents the Littlestone dimension of H.
To better demonstrate our results, we consider the task of online learning point functions over N in the oblivious setting and summarize in Table [ the finiteness of mistakes and learnability under the three types of constraints. Note that for this hypothesis class, the impossibility of making finite mistakes in private online learning can also be derived from the result (1]. However, our conclusion (Theorem 4.3) is more general - it applies to a much broader family of hypothesis classes. We choose this hypothesis class for illustration because separates the learnability against adaptive adversaries under pure DP and approximate DP.

---

1.2
Related Work
The work of [88 initialized the study of PAC learning with differential privacy. A series of subsequent works then showed that privacy constraints have a distinctive impact on the learners. The most remarkable result is the equivalence between approximate private learning and (non-private) online learning 4
15 5 29]. For pure DP, the learnability is characterized by the so-called representation Both results suggest that private learning strictly harder than non-private learning. For some specific hypothesis class such as the one-dimensional threshold over finite domain, it was shown that learning with approximate DP enjoys a much lower sample complexity than with pure DP
dimension
37 20), separating these two types of privacy. Another separation result is the huge gap between properly and improperly learning point functions with pure DP 9 which does not exist in non-private and approximate private settings.
[9 19 28
13
14
The problem of private online learning Littlestone classes was first studied by Golowich and Livni 30 They proposed private online learning algorithms for hypothesis classes of finite Littlestone dimension in the realizable setting against oblivious and adaptive adversaries, further strengthening the connection between online learning and differential privacy. In contrast with the non-private setting where the mistake bound always finite, their algorithms exhibit cost of log 7 for data streams of length T. Recently, it was shown by Cohen et al. [2]] that this extra cost is unavoidable for point functions over [T'. Dmitriev et al. [22] also obtained similar results, but only for algorithms that satisfy certain properties. It was questioned by Sanyal and Ramponi [41] whether an unbounded number of mistakes is necessary for R /T (see Section 2.2 for the definition of E).
There were also great number of results on private parametric online learning tasks such as online predictions from experts (OPE) and online convex optimization (OCO) [36, 42
35 B [8. Most of
them focus on the agnostic setting. Asi et al. 7 developed algorithms for both problems in the realizable regime with oblivious adversaries, again with a log T overhead. Asi et al. [ obtained some hardness results for DP-OPE against adaptive adversaries, but they require the number of experts to be larger than T.
Another related field is differential privacy under continual observation (see, e.g., 26 18 34
While the techniques can be used to design online learning algorithms, it is unclear whether lower bounds for DP continual observation can be transformed any hardness results for private online learning (see (22 for a detailed discussion).
2 Preliminaries
Throughout this paper, use S (=1,-... ., 2 denote data stream of length T. We write S(t) to denote the data point comes at time-step 1, i.e., 2t. For an algorithm AA that runs on S, use A(S), denote the output of A at time-step
Notation.
2.1 Online Learning
We start by defining online learning as a sequential game played between learner and an adversary.
Let H C (0, 1 ) be a hypothesis class over domain X' and T be positive integer indicating the total number rounds. In the /-th round, the learner outputs a hypothesis h2 E (0. 1 (not required to be in H) while the adversary presents a pair (Iz, Bt). The performance of the learner is measured by the expected regret, which is the expected number of additive mistakes made by the learner compared to the best (in hindsight) hypothesis in H:
T
T Σ
[he(xx) # vd]
min K.
(a)) + vdl
The above setting is usually referred to as the agnostic setting, where we do not make any assumptions on the data. In the realizable setting, it is guaranteed that there is some h² E H. so that y1- = h* (xx) for all é E [7]. In this setting, the performance is directly measured by the expected number of mistakes made by the learner, which is called the mistake bound, defined as
E Σ
(1)) + vel
3

---

An online learning algorithm is considered successful if it attains a sublinear regret, i.e., the regret is o(T). In this paper, we mainly focus on the realizable setting. We say a hypothesis class H. online learnable if there is online learning algorithm for H that makes oTT) mistakes in expectation.
We consider two types of adversaries: oblivious adversary chooses the examples in advance (could depend on the learner's s strategy, but not on its internal randomness), and (It, yt is revealed to the learner in the t-th round. An adaptive adversary instead, can choose (Ze, Mr) based on past history, 1)-
i.e., ......,,--i and (II, ,..; (#t-1:
Without privacy, the mistake bound is exactly characterized by the Littlestone dimension [3 even with stronger adversaries that can choose (xt; y/) after seeing ht. To define the Littlestone dimension, we first introduce the notion of shattered tree.
Definition 2.1 (Shattered Tree). Consider full binary tree of depth d such that each node is labeled by some X. Every fyI...., yd) E {0, 1]dd defines root-to-leaf path ................................ .d obtained by starting at the root, then for each i = 2.... d choosing 2; to be the left child of z4-1 if V/-1 = and to be the right child otherwise. The tree is said to be shattered by H. if for every root-to-leaf path defined in this way, there exists E H such that = h((;;) for all E [d].
Definition 2.2 (Littlestone Dimension). The Littlestone dimension of H. denoted by LD(H), is the maximal such that there exists a full binary tree of depth d that is shattered by H.
The problem of online prediction from experts can be viewed as a parametric version of online learning. Let be the total number of experts. In the t-th round, the algorithm chooses an expert de E [d] while the adversary selects loss function & : [d] + [0, 1]. Then & is revealed and cost of (16) incurred. The goal is minimize the expected regret
T
T
E
Σ ((te))
min E
Σ
Similar online learning, an oblivious adversary chooses all & in advance, while an adaptive adversary determines & based on .t-.....-111.. and ......,,-1.. In the realizable setting, it is guaranteed that there exists E [d] such that (,(i*) = 0 for all / E (T].
2.2 Differential Privacy
We first recall the standard definition of differential privacy.
Definition 2.3 (Differential Privacy). An algorithm A is said to be (s, -idffeerrettial private if for any two sequences S₁ and S2 that differ in only one entry and any event O, we have
Pr[A(Si) E 0 S ef Pr[A(S2) E 0 +
When d 0, we also say A is s-differentially private.
Our proofs use the packing argument 332 91 which heavily relies on the following property of DP. Fact 2.4 (Group Privacy). Let A be an (e, 8) difffrrentialy private algorithm. Then for any two sequences S1 and S2 that differ in le entries and any event O, we have
Pr(A((i) E EO 5 ke Pr(A(S2) E 0]+
e
Privacy with adaptive adversaries. When interacting with adaptive adversaries, the notion of differential privacy becomes a bit trickier! We adopt the definition of adpative differential privacy from [30] 34 g Let A be an online algorithm, Adv be an adversary who generates two sequences Si and S. adaptively such that S and S, differ in only one entry, and b E 2} be global parameter that is unknown to A and Adv. The interactive process A Adv(b) works as follows: in each time-step t, Adv generates two data points S₁ [t). S2(t] based on the past history and A gets Sp(t). The output of A o Adv(b) is defined to be the entire output of .A. We say A satisfies (s, -addapive differential privacy if for any such adversary Adv and any event O, we have
Pr[A o Adv(1) E O < e Pr[A Adv(2) +
8
'It turns out that the standard differential privacy and adaptive differential privacy are equivalent when = 26 [2 But we will use the adaptive version our preof since is easier to work with.
Note that the adversary here is different from the one in the definition of online learning.

---

Choosing the privacy parameters. It is a commonly agreed principle that for the definition of differential privacy be meaningful, the parameter å should be much less than the inverse of the dataset size [27]_ In this paper, when we say an algorithm A is private without specifying the privacy parameters, we typically refer to the set-up that & a small constant (say 0.01) and ó = o(1/T).
Learning with Pure Differential Privacy
In this section, we study online learning under pure DP constraint. We first propose algorithms for privately offline learnable hypothesis classes against oblivious adversaries via a reduction to OPE using the tool of probabilistic representation. Then we turn to adaptive adversaries and present a hypothesis class that is privately offline learnable but not privately online learnable. Note that according the results of [30,, this class is online learnable under approximate DP with adaptive adversaries. Hence, we manifest strong separation between pure and approximate DP.
3.1 Learning Against Oblivious Adversaries
In this section, consider oblivious adversary. We first recall the notion of representation dimension, which was introduced by Beimel et al. [10] to characterize pure DP offline learnability, Let D be distribution over X' {0, 1} and {0, 11 be hypothesis. The error of with respect to 'D is defined as errorp (h) Pf(x.,)~D((((e (b(x) o u]-
Definition 3.1 (Representation Dimension). A probability distribution P over hypothesis classes is said to be an (a. 3) probabbilisti representation for H if for any h* E H and any distribution D over X' x {0, 1 that labeled by h", we have
Pr Bv E V s.t. (r) S sa 2 1 -B. V~P
Let size(P) = (supp(P) In Vl. The representation dimension of H. denoted by RepDim(H)) is defined as
RepDim(H) Pisa (1/4,1 prohallisiii representation
min
size (P).
The following lemma from 10 shows that a constant probabilistic representation can be boosted to an (a, B) one with logarithmic cost in 1/a and L/B. Lemma 3.2. There exists an (a, (c..@)-proaaillistic representation for H. with size(P) (log(1//a) (RepDim(H( + log log (og(1/)) + log log(1/3))).
We first consider the realizable setting. Let S { (i)ii,.)).. Vi)..... (IT, vr)) be the sequence chosen by the adversary and D be the empirical distribution of S (i.e., Pr y) [Ix, y) (x2, yt]] 1/T for all t E [T].. By sampling hypothesis class V from an (a. (e..3)--robabillite 1/a < 1/T, we know that it holds with probability at least 1 3 that errorps (v) S 1/a 1/T for some E V. This further implies that is consistent with all examples in S. By Lemma 3.2
representation with
V is finite as long as has a finite representation dimension. Thus, it suffices to run the DP-OPE algorithm in 7 with every E V as an expert.
Theorem 3.3. Let H. be a hypothesis class with HepDim(Hl- < co. In the realizable setting, there exists an online learning algorithm that e e-differentially private and has an expected mistake bound of O log T(RepDin( +log log T)2 with an oblivious adversary.
The above conclusion directly extends to the agnostic setting by replacing the DP-OPE algorithm with an agnostic one (8).
Theorem 3.4. Let H be hypothesis class with RepDim(H) < co. In the agnostic setting, there exists an online learning algorithu that is e-differentially private and achieves an expected regret of O /T log T (RepDin( H) Hoog T) with an oblivious adversary.
Note that every online learning algorithm can be transformed to PAC learner by the online-to-batch conversion [17. Our result reveals that pure private online learnability against oblivious adversaries is equivallntt to pure private PAC Icarnability in both realizable and agnostic settings.
5

---

3.2 Learning Against Adaptive Adversaries
We now turn to adaptive adversaries. For finite hypothesis classes, still feasible to employ techniques from DP-OPE 3 or DP continual observation 126 18 34 to devise online learning algorithms (in Appendix F. we give an algorithm with better mistake bound in the realizable setting). One may hope that this can be extended to hypothesis class with finite representation dimension, as we did in the oblivious setting. However, it turns out that our method for oblivious adversaries is not applicable here. Since the examples not fixed in advance, we cannot guarantee that the sampled hypothesis class V contains a consistent hypothesis. Moreover, the famous ablivious-to-adaptivv td-apite transformation (see, e.g.. (T6]), which was used by Golowich and Livni [30] to construct online learners under approximate DP, also fails to give a sublinear mistake bound. This is because pure DP only has the basic composition property, which yields mistake bound that scales linearly with T (for approximate DP, this can be improved to V by advanced composition). Therefore, it is not clear if every offline learnable hypothesis class can also be made online learnable against adaptive adversaries under pure DP.
We will show that this is an impossible mission. Let POINTa be the set of point functions over [d] and POINTs be the set of point functions over N. where a point function fa X' - {0, 1} is function that maps x to 1 and all other elements to O. Both POINT, and POINTy have a constant representation dimension and thus that for any pure DP online learning algorithm for POINT,, an adaptive adversary can force it to make Ammin (log d, T)) errors. As direct corollary, POINTN is not pure privately online learnable against adaptive adversaries.
offline learnable under pure DP [10]. In the rest of this section, we will prove
We now illustrate the idea of our proof. Let us start by considering a simplified version, where the algorithm is constrained to be proper, i.e., h, E H = POINT, for every E [T]. Then one can construct series of data streams S; {(i, 1).... I)..... (i, 1)} for every i E [d]. An accurate proper learner must output fi for most of the rounds. This allows us to use the packing argument to derive an (log d) lower bound for T = O(log d).
However, the above argument does not apply to the general case where the learner may be improper since learner can simply output an all-one function that makes O errors on each S,. Therefore, we have to insert S, some examples of the form (j. 0) where j A This prevents h2 from taking on elements other than i. But when should we insert (j. 0)? And how do we determine the value of j?
Note that till now, we have not used the adversary's adaptivity. It necessary to exploit this power since any oblivious construction can be solved by our algorithm in Theorem 3.3 When the adversary acts adaptively, the construction becomes dual online learning game: in each round, the learner outputs h as a "data point" and the adversary chooses (i. 1) or some (j, 0) as the "hypothesis". This inspires us to leverage tools from online learning construct the adversary.
We now sketch our idea. In each round, we choose (i. 1) as the data point with probability 1/2, and otherwise sample a (j, from some probability distribution. We maintain the distribution by the multiplicative update rule, which is a widely used method in online decision making. The weight of j is increased by a multiplicative factor whenever hi( 1, and the probability of selecting is proportional to its weight. We provide a detailed implementation in Algorithm []
Using the standard argument of multiplicative update, we can show that an accurate learner must predict (i) = for most rounds and he( = for very few rounds. This allows us to apply the packing argument to obtain the following hardness result.
Theorem 3.5. Lets < (1) and d 2 2. Any e-differentially private online learning algorithm for POINT, must incur mistake bound of Mm d/s,T") in the adaptive adversarial setting.
Since POINT, is a subset of POINTN for any d, the above result directly implies that POINTN is not online learnable with adaptive adversaries under pure DP. This shows a strong separation between pure DP and approximate DP.
Corollary 3.6. Let < O(1). In the adaptive adversarial setting, any e-differentially private online learning algorithm for POINTN must make Q(T)) mistakes.

---

Algorithm 1: Adaptive adversary for POINTa
Input: the number of rounds T; online learning algorithm A: input data stream S Output: hypotheses hi,...,,vy by outputted by A
wo(j) 1 for all j [d]
2 for f = I...., do
(Te, Mr) S[t]
Set p(j) < Exc(dN (k for E [d] \ {
(--1(1)
With probability 1/2, sample and set (It, Vi) +- (j.0) Present (It, Mr) to and receive h2 from A
6
Update wr(j) = w elllt) for all j E [d]
7
8
end
return h1,--., Nvr
General Lower Bound on the Number of Mistakes
In this section, prove (HLD((H) T) lower bound the number of mistakes made by any private learner for every hypothesis class H that contains a pair of non-complementary hypotheses This implies that - xc, any private algorithm will make an infinite number of mistakes. Note that without privacy, the Standard Optimal Algorithm always makes at most LD LD(H) mistakes (39] Thus, lower bound reveals a universal separation between non-private and private models.
Our proof proceeds in two steps. We first show an M(log T') lower bound in Section 4.1 Then based on this result, prove the QDLD log T)) lower bound in Section 4.2
4.1 A Lower Bound for Non-complementary Hypotheses
We first define the notion of complementary hypotheses.
Definition 4.1. We say two different hypotheses and f2 over X are complementary if fi()) 1 - [2( for all E X. Otherwise we say they are non-complementary.
is worth noticing the following important fact about conplemmlemyntrry hypotheses, where the first item directly comes from the above definition and the second is because fi and f2 are different.
Fact 4.2. Let fi and fz be two different hypotheses over that are ron-complementtrr Then:
1. There exists some un X such that fi fi())) f2(wu);
2. There exists some in X such that Si fi(1) f2(u1).
We remark that this fact is also used by Dmitriev et al. [22] to prove lower bound (in their work, they call it a "distinguishing tuple"). However. they make a strong assumption that when running on data stream containing (Mo, fi (ua)) only, with high probability, the algorithm predicts hy (u,) = fi (u1) simultaneously for all E [T]. This largely weakens their bound since most DP algorithms clearly do not have such property.
To how to Fact 4.2 consider hypothesis class that contains pair of non-complementary hypotheses. We will focus on No. ú, and fi, f2 only and ignore all other elements and hypotheses. In our proof, we will use (wo, (ua)) (wo- f2(w))) about which hypothesis is correct. Let So be sequence that contains the dummy input only and A be an online learning algorithm. Without loss of generality, we can assume that Pr Pr[A(Su)e(un) fi (u1)) 2 1/2 for all E [T] (we can make this hold for half of the rounds by swapping fi and f2. and ignore the rounds that does not hold). We will insert (1i, fe(u)))' 's make algorithm error.
dummy input that provides information
Our proof relies on the classical packing argument. For ease of presentation, we only consider pure DP here, but the proof strategy easily extends to approximate DP via group privacy under approximate DP. In the framework of packing argument, we will construct series of input sequences Si,..., "t,...,,.,, S...
'Such type of classes is equivalent to the notion of non- non-trivial classes in learning with data poisoning. See, e.g., [12 and (31].

---

from So and disjoint subsets of output O...... Om such that So and S; differ by at most k elements for every E [m], and any algorithm will make (2(k) mistakes on S. Then by group privacy, for any e-differentially private algorithm Alg we have
1
Pr Pr(Alg(So) E0,
Pr(Alg(S:) Oi).
Thus, a lower bound on Pr(All(S,) E O.] implies a lower bound on k by the above inequality.
The first challenge here is the construction of S. By our assumption, we can insert a (#1, f2((1) )) at any position of So to cause loss of 1/2. However, when inserting the second one, the loss may decrease by multiplicative factor of ef. Following this argument, no matter how many (u,, f2(u)))ss are inserted, we can only bound the expected number of mistakes by
(1 (1+e== + 2c +...) coonttatt
failing to give ((k) bound for k = log
We overcome this by constructing them according to the given algorithm A instead of arbitrary algorithms. We will assume A has mistake bound of Ollog T) and seek to derive contradiction. We now depict our construction. For Si, we let S = So be the initial data stream. We then go through every & [7] in an increasing order, insert (wI, (2w1)) at time-step L whenever Pr[A(S))(u)) = [1n)) 2 1/3, and let S = S at the end. By our assumption, the number of (u1. (21)))'s should not exceed ls- = 3 (log T). Hence, Si and S. differ by at most k O(log T) points. Morcover, by our construction, for each E [I'] such that [ = (uo. fi (uo)), we must have (M,))S)))())) (u,)] < 1/3.
Now let us construct S2. We find the earliest round 1 such that (r(A(S),, (u1) = [1 < 1/33. The property we mentioned above ensures the existence of such 1 as long as k < T. We then perform a similar procedure as in the construction of S,, but instead of starting from = 1 and going over the entire time span [7'. we start from ( = 4, The online nature of A allows us to use i to distinguish S and S2 (as well as S3...., Sm. which we will construct later) since
Pr(A(S))e, (u1) = (11) < 1/3 < 1/2 < Pr(A(S2),, (w1) (11))
In other words, A is more likely to predict (wı) = (u1) on S2 but is less likely to do so on Sj.
We repeat the construction for = 3,..., m. For each i, we first identify the minimal 4 such that Pr[A(S,) < 1/3 for every j < i. Then we insert (u1, fz fu())) 's starting from 1 By the same argument, - can be used to distinguish , S and S,...., Sm. We formally describe the construction procedure in Algorithm 2
At the end, we will have m sequences Si,..., S.n and m time-steps .1....,,hm, 1m-11 such that Pr[A(S;),, (u1) fi (11) < 1/3 for any j 2 i and Pr(A(S)),, (m1) fi (w1)) 1/2 for any j < i. It can be proved that m Q(T/k)) which is sufficiently large for A: = Ollog T). Now we run A on some S = S, Suppose we can figure out the index i, we can apply the packing argument to derive an M(log m) 22(log T) lower bound.
Here comes the second challenge. Though we can use the output of to estimate Pr(A(S),, (ui) = fu())] )} for given j. we only have a constant success probability. To make the estimate accurate for every j E [m - I]. one has to achieve a success probability of 1 - 1/m for each j. This requires running A for Olog m) = Olog T') times and taking the average, which is prohibited since the resulting algorithm would be ( log DDP, yielding a meaningless 52(1) lower bound.
We address this issue by using binary search. We start with {tz, ........ I' } and select the middle point mid in each iteration. By averaging over multiple copies of A(S)), we can figure out whether should go left go right. This can be done in O(log m) = Olog T) iterations, and we only require the decision made on each middle point to be correct. Thus, the number of independent copies can be reduced to Ologg log T), which leads lower bound of 22(log /lo log T).
The above approach is already sufficient to show an unbounded number of mistakes, but we can further refine method to achieve an T'log bound. The key observation here is that we do not need the probability of outputting i on S; to be constant. In fact, success probability of 1/m--f00 ((1) TT.
is enough to obtain & > (:llogmm/m--00//
8

---

Algorithm 2: Constructing So, Si.... Sm and , bm-1
Input: the number of rounds T: online learning algorithm A; threshold f1, f2 and uo, 41
Output: a single data stream S₁, or collection of m data streams Si,..., .,, Sm along with
m time-steps .1..... fm-1
1 So - {(ug, (uo)), .... (uo, fi(w)))
2 m [T/k]
3 for -l..... do
S. S
Find the smallest 4-11 such that Vj E Ii 1], 11, (m)) fi(wi)] < <1/3
for aort= ........ T do
if Pr())(
fi (w1)) 1/3 then
S.(d t f2(1))
end
end
11
if E [T] :5:14 = (2(1))(m))) > then
return S:
13
end
14 end
return , Sm and f1, ......,. tm-1
We thus "smooth" our binary search. In each iteration, instead going left or right deterministically, we to the side that is more likely to be correct with some probability > 1/2. We show that, by choosing appropriately, this approach will output i on S; with probability 1/m--900 1-1)11, Moreover, only requires running the online learning algorithm O(1) times, avoiding the log log I blow-up of privacy parameters. The S2 T) lower bound then follows by applying the packing argument. We illustrate this approach in Algorithm 3
Theorem 4.3. Let E (0,1) be some constant. Suppose T/T/Ti- and 8 < E/T. If is hypothesis class that contains two non-complementary hypotheses, then any (diffeiilryyy private online learning algorithm for H. must incur mistake bound of 12loo even in the oblivious adversarial setting.
One may ask whether the existence of non-complementtay pair is a necessary condition for the number of mistakes to unbounded. Note that there are only two cases that contains no non- complementary pairs: either | 1 or H = {S1, J2] such that fi = 1- f2. The former is definitely online learnable with zero mistakes. For the latter one, we give an algorithm with a finite expected mistake bound in Appendix F showing that the condition is indeed necessary and sufficient.
Algorithm 3: Distinguishing Si,..., Sm
Input: the number of rounds T;; online learning algorithm A; time-steps ti...., tm-mimii input data stream 5 (S1, Sm): :: f1, and up, un used in Algorithm
Output: an index E [m]
Run A on S for 360 times, obtain 360 copies of output (n( (w: ..... (w)
for (360]
2 <- 1, 4- m
while 1 < do
mid 1
if
(u1) (h) (iite
fi (ur) E [360]] < 150 then
Let + mid with probability 3/4, and + mid + otherwise
else
Let +- mid + with probability 3/4, and r +- mid otherwise
end
end return

---

4.2 Incorporating the Littlestone Dimension
Building upon the (loog T) lower bound, we are now ready to show an (H(L log T) lower bound
for general hypothesis classes. Let A be a private online learning algorithm for H. Consider shattered tree depth LD(H) 2 Let ug denote root and un
left child. By the definition of
shattered tree, there exists J1, f2 E H such that Si (1 f2((0) 0 and ( = (1()) * f2(11)
Note that fi, f2 and uo, #1 satisfy the property mentioned in Fact 4.2 We can thus apply Theorem
to find sequence S₁ of length 7" which A makes ([log T") mistakes.
Till now, only the labels of uo and in are revealed to the learner. Therefore, we can go into the corresponding subtree of in and reiterate the above operation. After repeating it LD(H)/2 times, we obtain a series of completely non-overlapping sequences Si...., SLD(H)/2 and on any one of them A makes 2loog T mistakes. By concatenating them together and setting T = T/LD(H), arrive the (HL log T) lower bound assuming 7 > LD(H) I+c.
Theorem 4.4. Let E (0, 1) and 0 be two constants. Suppose / and å S E/T. H is a hypothesis class that contains two non con-complementary hypotheses, then any (5,5) diiffeeifery private online learning algorithm for H must incur mistake bound of ((LD(H)) log T/E) even in the oblivious adversarial setting given that T > LD(H))++e) 1+02.
Note that the class of all hypotheses over [d] has Littlestone dimension of [log, dj. The above theorem directly implies the following lower bound for the OPE problem. This improves the lower bound 7 by a log? T factor.
Corollary 4.5. Let eι E (0,1) and 02 > 0 be two constants. Suppose 2 In InTT/T--eia//(ttee and 6 S e/T. In the realizable setting, any (a, diifferrentill private algorithm for OPE has regret of Mlog d log T/) even against oblivious adversaries given that > [log, d 1+0,
4.3 Comparing to the Upper Bounds
We have shown an 2g T) lower bound on the number of mistakes made by any private online learning algorithm. We now compare it to existing upper bounds.
For pure DP, we provide an upper bound of (Iol T (log log T) This is larger than our lower bound by a factor of log 7" (log TT)2. In Appendix F we show that Oz(log 7") is achievable for some specific hypothesis classes. Whether OHllog 7 attainable for generie hypothesis classes remains open.
For approximate DP, Golowich and Livni 30 proposed algorithm with Oz T) mistakes against oblivious adversaries. Thus, our lower bound is tight assuming a constant Littlestone dimension. However, their algorithm exhibits an Ox upper bound against upper bound against adaptive adversaries. Whether this also be improved to Ox(log T') is an interesting open question.
Acknowledgments and Disclosure of Funding
The research was supported part by an RGC RIF grant under the contract R6021-20, an RGC TRS grant under the contract T43-513/23N-2, RGC CRF grants under the contracts C7513, C7004- 22G, C1029-220 22G and C6015-23G, and RGC GRF grants under the contracts 16200221, 16207922 and 16207423. The authors would like to thank the anonymous reviewers for their feedback and suggestions.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 23rd ACM Conference on Computer and Communications Security, pages 308-318, 2016.
[2] John M Abowd. The U.S. Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, page 2867, 2018.
10

---

[3] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 32-40, 2017.
[4] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Proceedings of the 51 Annual ACM Symposium on Theory of Computing, pages 852-860, 2019.
[5] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability equivalent. Journal of the ACM, 69(4):1-34, 2022.
[6] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[7] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Near-optimal algorithms for private online optimization in the realizable regime. In Proceedings of the 40th International Conference on Machine Learning. volume 202, pages 1107-1120, 2023.
[8] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. In Proceedings of the 36th Annual Conference Learning Theory, volume 195, pages 674-699, 2023.
[9] Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine learning, 94(3): 401-437, 2014.
[10] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research, 20:1-33, 2019.
[11] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the Vapmik-Chervonenkis dimension. Journal of the ACM, 36(4):929-965, 1989.
[12] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2) 2002.
[13] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 634-649, 2015.
[14] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, pages 74 86, 2018.
[15] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Proceedings the 61 Annual IEEE Symposiun Foundations of Computer Science, pages 389-402, 2020.
[16] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[17] Nicolo Cesa- Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of online learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-2055 2004.
[18) T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security, 14(3):1-24, 2011.
[19] Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19, pages 155-186, 2011.
[20] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-coneave optimization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 472-482, 2023.

---

[21] Edith Cohen, Xin Lyu. Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Proceedings of the 37th Annual Conference on Learning Theory, volume 247, pages 1200-1222, 2024.
[22] Daniil Dmitriev, Kristóf Szabó, and Amartya Sanyal. On the growth of mistakes in differen- tially private online learning: A lower bound perspective. In Proceedings of the 37th Annual Conference on Learning Theory, volume 247, pages 1379- 2024.
[23] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503, 2006.
[24] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, pages 265-284, 2006.
[25] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 381-390, 2009.
[26] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy Rothblum. Differential privacy under continual observation. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pages 715-724, 2010.
[27] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):111-077, 2014.
[28] Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Proceedings of the 27th Annual Conference on Learning Theory, volume 35, pages 1000-1019, 2014.
[29] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, pages 183-196, 2021.
[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.
[31] Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran. On optimal learning under targeted data poisoning. In Advances in Neural Information Processing Systems, volume 35, pages 30770-30782, 2022.
[32] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pages 705-714, 2010.
[33] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[34] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In Proceedings of the 40th International Conference on Machine Learning, volume 202. pages 14678, 2023.
[35] Prateek Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differentially private learning. In Proceedings of the 31 International Conference on Machine Learning, volume 32, pages 476-484, 2014.
[36] Prateek Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 24.1-24.34 2012.
[37] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Proceedings of the 33rd Annual Conference on Learning Theory, volume 125, pages 2663-2285,400 2020.
12

---

[38] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing. 40(3):793-826 2011.
[39] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2:285-318, 1988.
[40] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 94-103. IEEE Computer Society, 2007.
[41] Amartya Sanyal and Giorgia Ramponi. Open problem: Do you pay for privacy in online learning? In Proceedings of the 35th Annual Conference on Learning Theory, volume 178, pages 5633-5637, 2022.
[42] Adam Smith and Abhradeep Thakurta. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems, volume 26, pages 2733-2741, 2013.
[43] Leslic Valiant. theory of the learnable. Communications of the ACM, 173111:1134-1142 1984.
[44] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264-280, 1971.
13

---

A Discussion
In this work, we investigate online learning with differential privacy and provide separation results that distinguish non-privee non-private, pure private, and approximate private constraints. Below, we discuss some limitations and future work.
Tighter dependence 7 under pure DP. Our algorithm for pure private online learning with oblivious adversaries exhibits log" T (log log T dependence T (Theorem D.1. We also provide algorithms for y (Theorem F.1 and Threshold, (Theorem F.3) that have a O T) mistake bound. It interesting to find out log T dependence is achievable for generic hypothesis classes.
lower bound requires 8 < 1/T (Theo- rem 4.3 for constant с, while the result in [2]] only needs 8 < 1//log' T. Although it is com- monly accepted criterion to select = o(/ we still wonder whether our bound also holds for 5 < log 7' Moreover, our results do not cover the cases where or T are extremely small. Is it possible to cover the entire range?
Broader range of privacy parameters. Our (log T)
Mistake bound against stochastic adversaries. One benefit of online learning is that it does require the data to be i.i.d. generated. But in some scenarios, we may still have i.i.d. data but have to make online predictions. Clearly, such stochastic adversaries weaker than oblivious ones. Our construction in Algorithm 2 does not apply to stochastic adversaries. Can we overcome the 22log T) barrier assuming stochastic adversaries?
Lower bound on learning with constant success probability. In Section 4.1 show that the expected number of mistakes incurred by any algorithm 22og T). unclear whether the O(log T) cost remains inevitable mistake bound of o(log T)) can be achieved if we only require the learner to succeed with a constant probability (e.g., 0.99).
B Broader Impacts
Privacy has become a fundamental concern in today's machine learning community. In this work, we show several lower bounds and upper bounds private online learning tasks. While contributions are theoretical in nature, and we do not see any direct societal implications, we hope that our results will reveal the intrinsic structures of the problems and provide insights for the development of practical online learning algorithms with better privacy-utility trade-offs.
C Additional Preliminaries
Theorem C.1 (Hoeffding's Inequality 33
Let Zi...., Zn be independent bounded random vari-
ables with Z; [a, b). Then
n
2nt²
Pr
74 ZZ) 2
exp
n2
(b a)
1=1
for all i
The Laplace mechanism ensures privacy by adding Laplace noise. Definition C.2 (Sensitivity). Let f Z -> R be function. The sensitivity of is defined by
A and S3 differ in one entry [f(S)) f(S2)..
Definition C.3 (Laplace Distribution). The Laplace distribution with parameter b and mean 0, denoted by Lap(b), defined by the following probability density function:
f(z)
exp( [x]l/b).
2b
14

---

Lemma CA4 (The Laplace Mechanism (24)). Let ~ Lap(A)/E) be a Laplace random variable. The algorithm that ouputs f(S) + r satisfies e-differential privacy, Moreover, with probability - it holds that |r| < 1n(1/3)A//e.
We also need the following T Threshold algorithm (aka the sparse vector technique)
25
Algorithm Above Throssool
Input: database S; privacy parameter e; threshold L; series of online and adaptively chosen sensitivity-1 queries QI....
Output: a stream of response di,... L < L Lap(2/E)
2 for = l...., do
4: (()) + Lap(4/e)
if q 2 i then
4
T
halt
7
else
1
end
end
Lemma C.5. Algorithm is E-differently private.
If we only want to identify query with large value instead of the values of all queries, the report- noisy-max mechanism gives much better utility guarantee. can be implemented by adding Laplace noise directly applying the exponential mechanism (40).
Theorem C.6 (Report-Noisy-Mert Let S a database and qı..... qa be d sensitivity- I queries. There exists an e-differentially private algorithm that outputs an index i such that
(:(S) 2 max (S) 2(In(d) + +n(1/))) sEld
C
with probability at least
B.
The composition property allows us to combine multiple differentially private algorithms into one, even if they executed adaptively.
Lei Ai 2" - Ri be an algorithm that satisfies (1,,5))-DP and for 2 < i let A R1 ... Ri-1 In Rr be an algorithm that satisfies (ci, D for any given (r1....,, 11-1) E R1 x ... Ri-1. Let A be an algorithm that
Lemma C.7 (Basic Composition
23
27
1. Computes T1 <- Ai(S);
2. For each i = ........ computes & Fi-1,...,
3. Outputs ri, rk-
Then Ais (Ei Ess Ek= 8.)
D Proofs from Section
D.1 Proof of Theorem 3,3
We use the following OP-OPE algorithm from 77
Theorem D.1. For any 0 < 3 < 1/2, there exists an c-differentially private algorithm such that with probability B has regret
( Log d + log(T/3) log(d/3)
o
against oblivious adversaries in the realizable setting.
15

---

Proof of Theorem 3.3 Let a 3 = 1/2T. By Lemma 3.2 there exists an (a, 3) probabilistic
representation of with
size(P) = (Tog (RepDim( ()) + log T)).
Let = ((11, yn),.... ...., (rr, yr)} be the sequence chosen by the adversary and Ds be the empirical distribution of S, namely, p (zr y) (Fz, ve)l 1/T for all [T]. Then have
Pr Be E V s.t. 1/+ v(x)) V [7]] Pr [Jv V s.l. errorps 1/aa 1/27]
V~P
1 1/2T.
Conditioning on this event, we then run the algorithm in Theorem D.I with V being the set of experts and (())) = [[x()))) + ut]. With probability 1 1/27, the number of mistakes is most
log 2 + log T log] V + log" T o
log (RepDDim + log log T)² )
By the union bound, the expected number of mistakes is bounded by
(log T(RepDimmH)) + log log 7)2
1/T T (1-11(1
D.2 Proof of Theorem 3.4
The proof follows the same steps the proof of Theorem 3.3
The only difference is that we use the following DP-OPE algorithm from B in the agnostic setting.
Theorem D.2. There exists an s-differentially private algorithm that has an expected regret of
VT logg
E
Σ ((i.
Σ 4(i) (E(d)
min
=0
against oblivious adversaries the agnostic setting.
We can use the same argument as in the proof of Theorem 3.3 to sample hypothesis class from P such that V ((log(T) (RepDim + log log T)) and
Proof of Theorem 3.4
Pr Ev E V s.t. v(x,) h" (x:)) > 1 1/2I,
where h* Thcorem D.2
(h) is minimizer of the error on Running the algorithm in gives an expected regret of at most
VT /oog
[VTlog T(RepDim(H)) + log log T)
(1 11-7/) o
1/2T 1/2T= =0
LI
D.3 Proof of Theorem 3.5
We start with the following claim, which states that Algorithm iis an adversary that preserves privacy. Claim D.3. Suppose A satisfies e-adaptive differential privacy. Let B be the algorithm that runs Algorithm 7 with A. Then B is e-differentially private.
Proof. Let S₁ and S2 be two input sequences that differ in only one entry. Consider an adversary Adv that runs Algorithm I on S, and Sn simultanously using the same randomness, and interacts with AA using S₁ for some E (1,2). Let S and Sy be the resulting sequences. Note that when Si [t] S2 [t). with the same randomness Thus, S and Sy also differ in only one entry. By the definition of adaptive differential privacy, holds that for any event O,
have S [t] S% [t] since the weights depend h1.-.., h only.
Pr[A o Adv(1) E O] s Pr[A Adv(2) E O).
The conclusion follows by observing that the output distributions of Adv(b) and B(S,) are identical.
16

---

Proof of Theorem 3.5 Let < 0.01. We first consider T E d and prove lower bound of (T(T) (/oo) To this end, we will assume that there exists an online learning algorithm A with an expected mistake bound of 0.017 that is e-adaptive DP and derive contradiction.
Let B be the algorithm that runs A with A. By Claim D.3) we know that B is s-differentially ....... ..., (1, for some i [d] Let c h, wx( e Φ, = Ejela {() We (j). and pr(j) wx(i)/ 2r- The expected number of mistakes made by A can be expressed as
private. Now suppose we are running B on S; {(i, .)......................
Σ
E
1
0]
Σ jEld|
Pt-1(i)-
S 0.017.
2
Now consider the potential Pr. At the beginning, we have P d We can upper bound $ by
D,- =
Σ
wr(i)
Σ
wt-1(j)che(1)
jE(dME
Φ1
Σ
Pt-1(j)
jE|dM(s
S 011
Σ Pt- +22((i)
Φ.-1
1+2 Σ (i-1(i)
jE(dM(()
S 11-1 exp
Σ Pr-1(j)M(())
jEldMii
where we use exh <1 + 2x for 0 < x I in the forth line and + x S eth for x E R in the last line.
Then it follows by induction that
T
T S 4 exp
2
Σ
(=1
Taking the logarithm on both sides, the linearity of expectation gives
Bln TT) < E
In t + 2
Σ
Pr-1()M+(0)
t=1
In(d - 1) 2 Σ
Σ
Elpt-
t=1 jeldM(
< 1n.d=1)+0.047
0.14T,
where the third line is due to and the last inequality uses the facts that 0.1 In d/d s T and < 0.01.
By Markov's incquality, with probability at least 5/6 we have In by - 0.84T. This implies that, for every j # i, have
cr( = In wr (j) & In Ty $ 0.847.
We then bound (i).. Note that by T we have
T
E[T - CT (1) E
(1) = 0] S 0.02T.
17

---

Applying Markov's inequality again, with probability at least 5/6 we have T - (ir S 0.12T, or equivalently, (r()) 0.88T. By the union bound, holds with probability 2/3 that cr 2 0.887 > 0.84T 2 er()) for every i..
Let O, be the event that cT (i) (j) for every j # i, then Oı,..., Oa are disjoint. Then by group privacy,
1 M
Pr(B(S)) E 0, 2 e- 7 Pr(B(S,) 0, 2/3 de Te
Rearranging the inequality yields T 2 (Ind In 1.5)// 0.2 when d 2 2, a contradiction.
Now, let us deal with the remaining range. When T' > 0.2 in d/e,, the algorithm must make 22 d/s) in the first [0.2 In d/e] rounds. For T < 0.1 In d/e, suppose A makes no more than 0.0057 mistakes in expectation. Then we can repeatedly initiate A after every T round to obtain an algorithm that makes most 0.005kF mistakes in expectation for a total of kT rounds, where
0.2 ln d/e
0.2 d/e 0.1 In
k
=
2 0.5
T
T
T
This contradicts our previous conclusion since kT E 1011 In d/e, 0.2 d/e]. We thus obtain the (2(7) lower bound as desired.
E Proofs from Section
E.1 Proof of Theorem 4.3
We start by analyzing Algorithm As we discussed in Section 4.1 it constructs series of data sequences and a list of time-steps that can be used to distinguish the sequences. We formalize this in the following lemma.
Lemma E.1. For any threshold is and online learning algorithm A such that Pr[[((So
fu()) 2 1/2 for all t E [T), where So = (wu. fi (ug)).... (ug, fi [uo))} and fI, f2, ug. u1 satiisyy the property listed in F.ct Algorithm S either outputs S which A makes more than k/3 mistakes in expectation, or Si....,
,.....,,. Sm and .m.... such that
1. m = [T/k]]
2. For each i E [m], we have Pr[A(S));,(u)) (u)) [i(w)) < 1/3 for all j 2 and Pr[A(S(),, (u1) = f(()) 2 f/r all 1i
Proof. If Algorithm 2 outputs a single S S, it inserts least k + (u1, f2(21))'s S,. By construction, each of them incurs a mistake with a probability of at least 1/3. Therefore, the expected number of mistakes made by A on S; is at least (k + 1)/3 > k/3. Now suppose Algorithm dooes does not output a single data stream, this means for every i, Algorithm replaces at most & elements when constructing S, from So-
For each i E [m], the algorithm will first find the minimal f--1 such that Pr(A(S,),. (w)) [u < 1/3 for all 1 S < 1, which is exactly the first half of item 2. Moreover, this also suggests that 4 < ... S lm. Due to the construction process, the first 4-1 entries of S, will be the same as Sg. Therefore, we have Pr[A(S:),,, (w)) (w])= (u,)) 2 1/2 for any 1 < j S i an online algorithm. This proves the second half of item 2.
since A is
Now it remains to show the construction actually runs for [T/k]] rounds, i.c., we can find 1 for any < [T/k]. Since S, and any one of SI....,,, S differ at most & entries, the pigeonhole principle suggests that there exists some E [i 1)k + 1] such that S = -... | (wo. fa (uo)). We next prove that > ty for every 1 S < <ii- For the sake of contradiction, assume that is the smallest index such that tú > t and j < i 1 (it is impossible for f to be equal to any ty since we always have S S = (11, (2(1)) by our construction). Then we have 4 - ... < 11-11 < I. This implies Pr Pr(A(S)):( = fi()) < 1/3 for every 1 S j. otherwise Algorithm 2 will put (un, f2(u1) ) at time-step when constructing St. By the minimality of L,, we should choose Ly to be t when constructing SJ+1. contradicting our assumption that t, t.
18

---

Therefore, we have > t, for every 1 S j < 1-1. As we just argued, it follows that (r(A(S()((1))) = fi(w)) )] 1/3 for all / - 1] otherwise Algorithm? [ will put a (2()) this location. Thus, we have 14-1 I t < (i 1)k < ([T/k] - 1)k++ +1
T by the minimality of 4-11. This completes
the proof.
The following lemma suggests that the condition in the Lemma E.1 can be assumed without loss of generality.
Lemma E.2. Given S1, f2 and uo, 11 as in Fact 442 Let A be a randomized online learning algorithm and Sq- {wuo fi (uo)).... (uo, fi (uo)))) There exists b {1,2] such that
I(e: (() = fu(w)) 2 1/2H 2 T/2.
Proof. Let n. [[t: (4) fu(u)) 2 1/23| for b E (1,2}. We have nn + n2 2 T. Therefore, either n1 2 T/2 12 2 2/2.
Proof of Theorem 4.3 Let A be an (e, d)ddiiffrrentallly private online learning algorithm and So- {(uo, fi (uo)), ... (wo, (wo))) By Lemma E.2. we can without loss of generality assume that Pr[A(So)((u1) = fi(u1)] 2 1/2 for all t E by ignoring all time-steps that do not have such property.
Let k [3ln2/33600e]]. We will assume that A makes no more than k/3 mistakes in ex- pectation and derive contradiction. By Lemma E.1 Algorithm P will output Si...., Sm and f1,..., 1m-1 with m = [T/k]. Moreover, Pr(A(SS),, (w1) (1n) 1/3 for every j 2 and (u))) 2 1/2 for every j 1
Pr[A(S.),,(u))
Let B be the algorithm that runs Algorithm] with A. The basic composition property immediately guarantees that 13 is (360s, 3605) -iffeerrrcee private.
We now examine the probability that B outputs on S,. so, B must go through a series of time-step tiy ... fr, in the binary search, where n I [log2 m]] I logz m + 1 X, be a random variable that takes 1 if
For each liy. let
T[K (i = (11) w E [360}} 150
T [ 2 i].
and takes 0 otherwise. Conditioning on Xyys ss the probability that B outputs i can be expressed as Pr(B(S.) = i X x,)= 1T (0.75X, + 0.25(1 X,)) = 0.75 0025 Ei X,
By Hoeffding's inequality, for each X, have
B[X,] Pr[X, = 1] 2 exp (-2 360 (30/360)²) = -5 0.99. then follows by the linearity of expectation and Markov's 's inequality that
Pr[X1 +... X, 2 0.97m] 2 2/3.
Putting it all together gives
Pr(B(S.) = i] 2 Pr[B(S.) = | + ... + X 2 0.97n] Pr[X, + ... + X, 2 0.97n]
2 2/3 0.97 0.03
0.97R
1
0.03n
2 2/3 22/2
2-1
2
= 2/3 3/3-2-* 2- (00.97 0.000)
2/3 2-0000000 -00.46m
2 2/3 (2m) 0.545
-0.540.44
19

---

We now apply the packing argument. Since B is (360s, 3606) differrrtile private, it follows by group privacy that
Pr(B(So) = =i]
-360ke
360kE Pr(B(S:) =
-360
e000c 1
1=1
360ke
> 2/3 2 -0.545
0.455
360ke
3600
e630
360ke
2 0.45m 0.455
360ke
m
-3606.
360c
300kE If 0.45m
2m
1-e 300ks
3600, then we have
0.225m 0.155
e 300ke
< 0.45m 0.155
360ks
m
360e
e
360ke
3608 - 1.
Rearranging the above gives
In 0.255 + 0.455 In
h:
360s
In 0.225 + 0.455 (T/k)
360s
In 0.225 + 0.455 In
36007's
cln T
360g
In 0.225 + 0.455c In T + 0.455 In
IV
360s
0.455c In
360s
where in the forth inequality we use the condition E 2 In 1 This contradicts our assumption
that & < e el T /3600e.
otherwise 0.45m 0.455
360kc < 2m
1-e SBOke
36006, we have
3000 -1
360c
360ke
In
00.255m
+ 1 -0.545
3606
360c
IV V
In
+ In 0.225
0.545 In
3606
In(e/0)
0.545 In T + 0.2.2
0.455 In + In 0.225
0.1 In
when 7' 2 100. Then it follows that k: > 0.1 1n 00027/(3600)) (360s) > T/36000 again contradiction.
In conclusion, any (s, -iiffereetiill private algorithm makes (k+1)/3 cln T/(1800s))) mistakes in expectation when T 2 100. This gives the 2(log T/s) lower bound.
E.2 Proof of Theorem 4.4
Proof. When LD(H)) 1, the result is directly implied by Theorem 4.3 From on, will assume LD(H)) 2 2.
Let m = [LD(H)/2] and T" = [T/m
[L > T/LD(H) 7 7r1-1/(1+ca) = (1++))
Pick a shattered tree for H of depth LD(H). Let un be its root and # be the left child of up- The definition of shattered tree indicates that there exists fi, H such that fi (wo) = f2(u0) = 0 and 0 (u1) * fe(u)) 1. By Theorem 4.3 for any (e, 8) diffferential private online learner with
20

---

2 InT/TTal- > /T and 6 < E/T < < we can construct sequence S1 such that it makes in expectation ([log /E) (/E) mistakes S₁. Moreover, S₁ only contains (wo, 0) and (u1, for some E (0.
Let H' (h. H h(ua) 0 and h(m)) b). If LD(H) > 4, then have LD(H)) > LD(H) 2 2 2 since the subtree rooted at the child (left if = 0, right = 1) of in is shattered by H' and has depth of LD(H) 2. Thus, we can similarly construct sequence S2 such that the algorithm makes Ollog Tee) errors. Importantly, the entries in S2 are completely different from those in S1.
We repeat the above process until we reach a hypothesis class with Littlestone dimension < 1 and construct series of sequences S1,..., , Sm that have non-overlapping entries. On each of them, the learner makes 12(log T/e) mistakes in expectation. Let S be the stream formed by concatenating S1, .......,.. Sm together. The length of S is at most mT" S T while the expected number of mistakes (LL((H) log 7)
F Additional Algorithms
In this section, we provide several algorithms for various tasks, Note that some of the upper bounds hold even against strong adaptive adversaries, i.e., adversaries that can see the prediction made by the learner the current round.
F. Learning Point Functions Against Oblivious Adversaries
We show how to improve the log T dependence in Theorem 3.3 log for POINTs. In the beginning, we keep outputting an all-zero function and use the sparse vector technique to monitor the mistakes. Then we sample hypotheses from the probabilistic representation constructed in [TO] and again apply the sparse vector technique to find one with low error on the past data. Following their argument, we can show that the construction guarantees that the hypothesis we found won't 't make many mistakes in the future. The result is stated as follows.
Theorem F1. In the realizable setting, there is an s-differentially private online learning algorithm for POINTy that makes in expectation Ollog T/e) mistakes against oblivious adversaries.
Proof. We run Algorithm| 5 Note that is in fact composed of two instances Above Above Threshold with privacy parameter e/ 2/2, the algorithm is c-DP.
Consider the first Above Threshold, there are T S 2T Laplace random variables. With probability 1- 1//3,, all of them have absolute values no larger than 4 In(67*)/s'. Thus, when it halts, there are least f. 4 In (n > 20 In ln(12T)) data points of the form (x: 1), where fz- is the target hypothesis. Moreover, it makes at most 20 (n(12T)) + (88n(672) + (
mistakes.
Now we show that the sampling won't 't last for too long. We consider the first 37 iterations. Then with probability - 1/3T, every random noise has an amplitude of at most I in the second AboveTTheshhole Note that Σ I(((x,) ) # yr and y,- = 1] 2 20 (1 /f and is if h(x') 1. Thus, the algorithm will exit the loop if and only if h(x=))))===))))))(())))))))))h = The probability
that this happens in the first 37 iterations is at least 1 (1 1/T)3T2 2 e- > 1 1/3T.
Moreover, this h makes in expectation less than (T - 1)/T < 1 mistakes on data points other than (x*, 1) in the sequence.
Putting it all together, the expected number of mistakes is less than
1/T T + (1/1/T) (20 + 8 (n + +1+ +11 Olog T/e).
F.2 Learning Point Functions Against Adaptive Adversaries
Theorem F.2. In the realizable setting, there is an e-differentially private online learning algo- rithm for P that makes expectation O(log d + log T)/ mistakes against strong adaptive adversaries.
21

---

Algorithm 5: Learning point functions over N
Input: the number of rounds T: privacy parameter e; sequence $ Output: hypotheses h1,...,,v
1 e' -/2
2 < (e 20
+ Lap(2/ee))
for I. = 1..... 7 do
Let h, be an all-zero function such that (x))) = 0 for all x e
(Ir, yr) S[t]
6
if " 1r Lap(4/e)) 2 then
+ 12 + Lap(2/e')
repeat
Sample an h such that Pr(h(z) = 1] = 1/T for every x E N independently until Σ [[b(x,)) # yr and yr 1] + Lap(4/e") <
11
Output h4+1 = =... hr h for the remaining rounds and halt
12
end
end
Proof. Let E/2. The algorithm works as follows: it keeps outputting an all-zero function and runs an E' e'-differentially private sparse vector technique (Algorithm 4 with L = 3(In In
8 ln(( to monitor the number of mistakes, Once the (noisy) number of mistakes exceeds L at round k, it computes c; = H[t E [k] (Iz, yr) = (i, 1)H and apply the report- noiinoooiaaaaa max mechanism with privacy parameter e' to find index with a large c. After that, it persistently outputs till the end. The privacy directly follows from the basic composition.
With probability - 1/27, the amplitude of every noise added in the sparse vector technique no larger than 1n(44"))/'' Thus, at round k, the number mistakes must the range [ - 4 1n(47))/E) (. 41 + have G; L 8 8/n(4T))/e = 3(mn In(2)))/e for some and oj for all # i. With probability - 1/2T, the report-noisy-mat algorithm will identify correctly.
1 -1)n(47))//e L 8I((47)) + 1]. Hence, we
Thus, the expected number of mistakes is bounded by
1/T T' + (1 1/T) (L 8 8l (1 1) O(llo d T)/s))
F33 Learning Threshold Functions
A threshold function over [d] is a function fs such that fi(x) = 0 for all x S i and f((z) = 1 for all x where E (d] U (0). The class of threshold functions over (d). denote by Thresholdg, the set (J: i E [d) (0)).
Theorem F.3. In the realizable setting, there is an e-differentially private online learning algo- rithm for Threshold, that makes in expectation Olog d log T/e) mistakes against strong adaptive adversaries.
Proof. We run Algorithm 6 Since the counters are refreshed once we switch the current hypothesis, we are actually running Above Threshold on disjoint datasets. Moreover, the comparisons of and e₁ are also performed on disjoint datasets. Therefore, the overall algorithm eDD..
Since the binary search runs for at most [log, (d + 1)] iterations, it follows by the privacy of AhresoTreehold and the basic composition that the overall algorithm is s-DP since the counters are refreshed once we switch the current hypothesis.
By the property of Laplace distribution and the union bound, with probability 1 - 1/T, every random noise that appears in the algorithm has an amplitude no larger than 4 In(47)) Conditioning on this event, once we change the current hypothesis, we must have + 2 7 - 4n 2 8 In in(472)/E and + c₁ < L 4 + 24 ln + 1. Therefore, we can identify
22

---

which one is zero. Since the binary search runs at most Olog d) iterations, we will make at most
Ollog d) (24 (1 +) OOlo log T/s)
mistakes with probability 1 1/T.. This implies an T (log log + bound in expectation.
(log d log T/e
Algorithm 6: Learning threshold functions over [d]
Input: the number of rounds T: privacy parameter E; sequence
Output: hypotheses hi,...,
1 =/2
2 <- 16 161n(479)/e' TTap2///)))))))
3 <- 0,r -- d, 4,mid + rr/2)
0,c +
5 for for(=l....,
h: - fmid
7
(II.31) + S[t]
Cy. F cy. + [[((x;;)) vol
if < r and co + ci + Lap(4/s") 2 Ż then
10
if co + Lap(1/e')
then
11
+ mid +
else
13
r 1-idd- 1
end
15
mid
<- [(| + r c 0,
Ż 16 /E' Lap(2/e)
17
18
end
end
E4 Online Prediction from Experts Against Adaptive Adversaries
is easy to come up with an algorithm with a regret of O(d T/E) even against strong adaptive adversaries. The idea is similar Algorithm 6 one instead of running& a binary search.
The only difference is that we try the experts one by
Theorem F.4. There is an e-differentially private algorithm that solves the OPE problem with an even against strong adaptive adversaries in the realizable setting.
expected regret of O doog T
Proof. We iterate over the set of experts. For each expert, we keep choosing it and run an E- differentially private sparse vector technique to monitor the loss incurred by the current expert. Once the sparse vector technique halts, we switch to the next expert and restart the sparse vector technique. Since all instances of the sparse vector technique
on disjoint data, the entire algorithm is e-DP.
With probability
1/T, all the Laplace noises added are bounded by 4 ln(22)) By choosing L In (n(2 will make at most Olog T/E)) mistakes each expert. Moreover, for an expert that makes no errors, we will not switch to the next one. Therefore, the overall expected regret
1/T T + (1-1-T11 d O(log T/e) = OOd
Note that there a multiplicative factor of on the log term. We will then show how to improve this dependence to log for (weak) adaptive adversaries. Due to Corollary 4.5 such a dependence is tight even for oblivious adversaries. It interesting to find out if this can also achieved for strong adaptive adversaries, and we leave this future work.
23

---

Moreover, our algorithm has regret of O (d d d+ log d T). Since it was shown by Asi et al. 8 that an (d)d) cost is inevitable, our algorithm near optimal.
The idea is to select uniformly random expert rather than keep choosing fixed one. Suppose are the beginning. Let (i) = Ei= (i) for expert i. The benefit of such random selection is that it only incurs a loss LiE(d (i)) which much less than the Eie(d) (1 loss we always choose the same expert since the adversary can let this expert make an error all the time.
We use the sparse vector technique to track the maximum of ct. Once it exceeds Ollog T + -dd dllog d). then apply the report-noisy-man algorithm to remove every expert with a (j) Ei= Cr(i) 2 (d log d) (we do not write y here since we will reset o to be later). After that, we reiterate the sampling and monitoring process using the remaining experts. Observe that if expert j is the i-th one being removed, the loss incurred by j is at most Oloo T + d log d)/i. This gives an upper bound of Oloo T + d dllog d) (1 1/2 + + 1/d) = Og + log dllog T). The details are depicted in Algorithm
Algorithm 7: DP-OPE against adaptive adversaries
Input: the number of rounds T; privacy parameter E; sequence $ Output: indices of experts i...... .7
Set (i)
and co(i) & for all [d]
2 E + [d]
3 E 8/ = <6d))
4 < 8ln )/1 + 3(nd In(3d) + Lap(2/e,)
for - l..... do
6
Sample in uniformly from E
+ S(1]
8
Update a + (((i and (i) + c1-1(i) + 4(i for all i [d]
if E| and maxic e (a + Lap(4/s1) 2 7 then
10
Run report-noisy-ma. with privacy parameter è2 on {ar(i))jeR and obtain some index
11
Update E E {i}
12
while i & E and [E] > 1 do
13
Run report-noisy-mat with privacy parameter on {ar(i))ee and obtain some index i
14
if (1) + Lap(1/eg) In 1/e2 then Update E + E {i} end end
15
16
+ 8ln + +3Ind le Lap(2/s1) (+) <- 0 for all i [d]
18
end
end
Here a subtle issue: the report-noisy-met mechanism only succeeds with probability 1/d. This does not imply upper bound in expectation. We cannot simply raise the success probability to 1 1-T/T. Otherwise, the d log² d term will become d log d log T, which is even higher than the brute force. To fix this, we run an extra sparse vector technique on top of the algorithm inspect the loss. Once the loss is greater than the upper bound, we then run the algorithm in Theorem F.4 for the rest of the rounds. This reduces the expected cost from T to Od T') when it fails, hence successfully bound the expected loss.
Theorem F.5. There is an e-differentially private algorithm that solves the OPE problem with an expected regret of dlogg d4log dlog T against adaptive adversaries in the realizable setting.
Proof. We first show the privacy and utility guarantee for Algorithm 7 For privacy, the sparse vector technique is e/2-DP. The report-noisy-mal outside the while loop will be executed most times, and the same for the one inside the while loop. Also, the if clause inside the while loop will also
24

---

be executed at most d times. All of these cost privacy budget of 3ds² = E/2. Thus, the overall algorithm is e-DP.
We next analyze the regret. With probability - 1/7, all the noises added by A Threshold are bounded by | Therefore, once (x 16 (el((22) + 31'n )+ for some i E, we must invoke the report-noisy-mat mechanism. On the other hand, once we invoke the report- noisy-max mechanism outside the while loop, we must have c2 > 3(lud-In(dd)) for some i. With
61
E2
probability 1 1/3d, it always identifies with ar (i) > 3(In ln(dd))
2(1n ((nd+in(3d))
0 and
52
62
delete it.
Now let us move into the while loop. With probability 1/3d the report-noisy-mon always returns an i with (i) 2 2l((d") 2(1n )) 2(In d+ (n(df)) 2 ln(3d") whenever max oe(j) 2(In (n 2In(3d")
22
E2
22
E2
Moreover, the noise added in the if clause is less than In(3d") for the entire 1 1/3d. Thus, expert é will be removed. Conversely, it identifies an i
62 time span with probability such that a (x) O, will not remove i and exit the loop.
d2
E2
Let Eg be the set E at the beginning of round and ET+I be the set after the algorithm terminates. Suppose is removed from É at time-step T; (if it still remains in E at the end, we define T; = T 1). From the above analysis, we know that with probability 1 - 1/d 1/T, for every expert we have Conditioning on the event that or, (t) S M for
3(In ) 2ln(3d") 16 16ln(2T")
aT, (i)
82
d2
E1
some M, we can bound the expected loss by
T
T
E
Σ Ei
E
Σ EE|d]
uli EAG())EEE
t=1
E
m E E.G(/EBB
1=1
E
103/EE
t=1
T
F0)/ETT
OT, (1) ET.
(E
M
Ex;
VE (M)
M
ln M
for d 2 2 (the case that d 1 trivial so we just ignore it).
We already have M = O d'lng dlg with probability 1 1- 1-1/d- 1/T'. However, this is not enough
to show an expected bound. To get an expected bound, we run Algorithm 7 with privacy parameter e' =/2 and an e' e'ddifferentially private Above Threshold to monitor maxee,, (r(1) (note that it won't affect the privacy and utility even if we release F., publicly) with threshold
2 ln(22) 3(In d + In(3d))
16 I2T
+1) + 4l
L
+
8¹
s
25

---

Once Above Threshold halts, we then stop Algorithm 7 and switch to the algorithm in Theorem F.4 with privacy parameter E,
not hard to see that the overall algorithm is e-DP. For utility, we have that with probability halts once E; (i) is greater than L L 4ln(T9) and never than L == L 4 1n( Conditioning this, with probability 1 - 1/d 1/T we have αT, - L for every i and thus
1 1/T AboveThresinn
halts if the value is always
never halts. In this case, the
expected loss is at most L In =
[Alog" d4 d log
If Above Threshold halts, the expected
loss incurred before that moment should be at most (L [L+1) 1) In d = O d [loog d+ log And
after that, the regret should be O dloo T expected regret of
by Theorem F.4 Putting these two cases together gives an
1 d T
7 ( 7) ( (L+1): 2nd
dllog I
2nndd
dlog" + log d dog
j + 7) 0
d dloog T
=0
E
=0 [dlog" d + log T
Thus, the expected regret of the entire algorithm is
1 (1- . ddlog" d + log d T')
1 T T = ( (dlog" d + log d log T
T
8
F5 Learning Two Complementary Hypotheses
Let H = f2) such that fi = 1 fz. We now give an algorithm that achieves a mistake bound of O(1/E).
It is not hard to come up with an algorithm that makes O(1/E) mistakes with constant probability. Since the incorrect hypothesis makes an error on every input sample, can output arbitrarily in the first (11/)) rounds. Then we use the ((1/s) data points to figure out which hypothesis is the correct one. This can be done using the Laplace mechanism.
However, a constant probability bound does not imply an expected bound. Note that once the Laplace mechanism fails, may make S?(T) errors the entire sequence. Thus, if we follow the above framework, we have to achieve success probability of 1/T. This requires Ollog T/e) samples, which exceed our target.
To reduce the expected number errors, we split the entire sequence into buckets length (11e)). We perform the Laplace mechanism every bucket. Then for the i-th bucket, instead of just using the result on the last bucket to predict, we take the majority over all previous buckets. This makes fail probability decrease exponentially. The mistake bound then converges to (11/s) as desired.
We describe the procedure in Algorithm aand provide formal statement of our result in the following theorem.
Theorem F.6. Let H = {Si, a hypothesis such that J1 and f2 are complementary. In the realizable setting, there exists an e-disferentially private algorithm that online learns H. with mistake bound of (1/e)) even against strong adaptive adversaries.
Proof. It is easy to see that Algorithm 8 is e-differentially private since add Laplace noise on disjoint buckets. For each bucket, with probability 2/3, the noise added to the counter is less than ln(3)/s s/2. This means we can identify the correct hypothesis with probability 2/3.
For the n-th bucket, we will make errors only if we wrongly identify the target hypothesis on at least half of the previous buckets. By Hoeffding's 's inequality, this happens with probability at most
exp (-2(n- 2)
exp(-(n 1)/18).
26

---

Thus, the expected number of mistakes is bounded by
exp(
- (000-(m-11118)
Algorithm Learning complementary hypotheses
Input: the number of rounds T; hypothesis class H = (fi, f2) such that fi and f2 are complementary; privacy parameter E; sequence
Output: hypotheses hi, /rr
1 + 0, 02 4 0
2 8 [3]
3 for -orl=10 (...=1...,,7 do
(fr, S[4]
if > then h
7
else
+ f2
end
if mod s then
if Σ - (x,, + Lap(1/e) 8/2 then c c
13
else
02 c2 c1
15
end
16
end
end
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, we state our main contributions: separation result between pure and approximate DP, and the other one between private and non-private settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations and future work Appendix A
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: The proofs of the results in Section and can be found in Appendix D and respectively. We also provide some additional results together with their formal proofs in Appendix F For each theorem the paper, we clearly state the assumptions that it relies on.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
29

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /utee//ggudddeeeedSuuuubmbibbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
30

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp:://euurpp:: http://rrrrpppp.oooooccccccccaaa
Answer: [Yes]
Justification: We have read the NeurlPS Code of Ethics and make sure that the research in this paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the potential impacts of this paper in Appendix B
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not have such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "Br4uXNR8SO", "reviewer": "Reviewer_ud1R", "summary": "Various results are proved about online learning of private learning algorithms, contrasting no DP, pure DP and approximate DP.", "questions": "No questions.", "limitations": "No potential negative societal impact.", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper present some interesting new results on online learning with DP. I read up to section 3 and the writing is very clear and the results are important and purportedly novel. (I don't have background or recent experience in the area of online learning so I cannot independently confirm their novelty.)", "weaknesses": "I can't point to any weaknesses, but this paper is outside of my area, and I was only able to follow up to Section 3, so it is certainly possible there is something I missed. I am basically taking the paper at its word on the claims made in Sections 1 and 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review and comments, and we have further clarified a few places to make it more accessible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sJD2Bs4nB7", "reviewer": "Reviewer_YzYS", "summary": "This paper studies limits of pure DP and approximate DP in the context of online learning (with oblivious and adaptive adversaries).", "questions": ".", "limitations": "The authors don't discuss limitations or societal impact.\nI believe there are no ethical concerns with this theoretical work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The research questions are interesting and the results may have fundamental value.\nI'm not an expert in all topics covered by the paper, but the contributions seem novel to me.\nThe text is in general well-written and understandable.", "weaknesses": "The paper has a lot of theorems and lemmas, which is interesting.  Still, the paper has no conclusions, discussion, further work, description of limitations or illustrative experiments or extensive examples.  This puts the task of understanding the value and applicability of the work to a large extent to the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments, and our detailed responses are listed below.\n\n> no conclusions, discussion, further work, limitations\n\nWe state our main conclusions in Section 1.1, which are the separation results between no DP, pure DP, and approximate DP online learning. \nThe discussion on the limitations and future work were put in Appendix A due to the space restrictions. \n\nWe will polish the structure of the paper to make it more accessible in the revision.\n\n> illustrative experiments or extensive examples.\n\nWe will provide some examples in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wlaq7GQgfH", "reviewer": "Reviewer_sPMY", "summary": "The paper demonstrates that any function class that is offline PAC learnable with pure DP is also online learnable with pure DP against an oblivious adversary. In this context, a hypothesis class is considered online learnable in the realizable setting if there exists an algorithm with a sublinear mistake bound.\n\nThe paper also establishes a distinction between online learning with pure privacy for oblivious and adaptive adversaries. Specifically, it shows that the hypothesis class $point_N$ is privately online learnable against an oblivious adversary but not against adaptive adversaries. This finding also indicates a separation between pure and approximate private online learnability, as $point_N$ is online learnable with approximate DP against an adaptive adversary.\n\nAdditionally, the paper presents a general lower bound on DP online learning against an oblivious adversary for non-complementary function classes.", "questions": "It looks like Lemma E.2 shows the concentration assumption in 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?", "limitations": "No significant limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper offers general results on private online learnability, identifying conditions under which a hypothesis class is online learnable with pure DP against an oblivious adversary. This connection to Representation Dimension links to existing results on DP PAC learnability.\n- It also explores different layers of separation using the function class $point_N$, contributing to a deeper understanding of the cost of privacy in online learning.", "weaknesses": "The proof of Theorem 4.3 is not clear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments, and our detailed responses are listed below.\n\n> The proof of Theorem 4.3 is not clear\n\nWe will polish the proof of Theorem 4.3 to make it more clear in the revision.\n\n> 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?\n\nOur Lemma E.2 is essentially different from their assumption.\n\n- 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$.\n- 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.\n\nA 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}$.\n\nOur 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k3DJVDxv1M", "reviewer": "Reviewer_kW4d", "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:\n1. If the adversary is oblivious, then PAC pure DP learnability implies online pure DP learnability.\n2. On the other hand, if the adversary is adaptive, then PAC pure DP learnability does not imply online pure DP learnability.\n3. In contrast with the standard online learning model, for every non-trivial hypothesis class, the mistake bound depends on $T$.", "questions": "Questions:\n1. 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]).\n2. What is the best known upper bound for the result of Section 4?\n\nSuggestions:\n1. Line 84: you wrote $\\epsilon$ before defining DP.\n2. 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.\n3. 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.\n4. 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...).\n\nTypos/english:\n1. line 146: \"not known by\" --> \"unknown to\"\n2. line 264: \"an lower\" --> \"a lower\"\n3. line 272: \"inpupt\"\n\n\n[1] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. TheoreticalComputer Science, 288(2):255–275, 2002.\n\n[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.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Assuming that the results are correct, the paper contains a significant improvement towards understanding mistake bounds in online learning under DP constraint.\n2. The questions and results are interesting and in the scope of NeurIPS.\n3. 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.\n\n2. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments, and our detailed responses are listed below.\n\n> figure/meta-theorem that neatly explains all the relationships.\n\nWe will add a figure to explain the relationships in the revision.\n\nOur main results imply that there exists a hypothesis class such that: \n\n|                | Oblivious adversary, finite mistakes | Oblivious adversary, learnable | Adaptive adversary, learnable |\n| -------------- | ------------------------------------ | ------------------------------ | ----------------------------- |\n| no DP          | Yes                                  | Yes                            | Yes                           |\n| approximate DP | No                                   | Yes                            | Yes                           |\n| pure DP        | No                                   | Yes                            | No                            |\n\n> the best known upper bound\n\nFor 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).\n\nFor 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})$.\n\nWe will include the above discussion in the revision.\n\n[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.\n\n> 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]).\n\nYes, 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.\n\n[1] Nader H Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255–275, 2002.\n\n[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.\n\n> Suggestions: Line 84: you wrote $\\epsilon$ before defining DP.\n\nWe will add a forward reference in the revision.\n\n> 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.\n\nYes, your interpretation is precise. We will clarify this sentence in the revision.\n\n> 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.\n\nWe 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.\n\n>Typos/English:\n\nWe will fix the typos in the revision. Thank you for pointing them out.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper derives basic results in online differentially private (DP) learning. I recommend acceptance.
Decision: Accept (poster)