Littlestone Classes are Privately Online Learnable
Authors: Noah Golowich
Roi Livni
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: differential privacy
online classification
online learning

Abstract:     We consider the problem of online classification under a privacy constraint. In this setting a learner observes sequentially a stream of labelled examples $(x_t, y_t)$, for $1 \leq t \leq T$, and returns at each iteration $t$ a hypothesis $h_t$ which is used to predict the label of each new example $x_t$. The learner's performance is measured by her regret against a known hypothesis class $\mathcal{H}$. We require that the algorithm satisfies the following privacy constraint: the sequence $h_1, \ldots, h_T$ of hypotheses output by the algorithm needs to be an $(\epsilon, \delta)$-differentially private function of the whole input sequence $(x_1, y_1), \ldots, (x_T, y_T)$.

We provide the first non-trivial regret bound for the realizable setting. Specifically, we show that if the class $\mathcal{H}$ has constant Littlestone dimension then, given an oblivious sequence of labelled examples, there is a private learner that makes in expectation at most $O(\log T)$ mistakes -- comparable to the optimal mistake bound in the non-private case, up to a logarithmic factor. Moreover, for general values of the Littlestone dimension $d$, the same mistake bound holds but with a doubly-exponential in $d$ factor. 

    A recent line of work has demonstrated a strong connection between classes that are online learnable and those that are differentially-private learnable. Our results strengthen this connection and show that an online learning algorithm can in fact be directly privatized (in the realizable setting).

We also discuss an adaptive setting and provide a sublinear regret bound of $O(\sqrt{T})$.

Littlestone Classes are Privately Online Learnable
Noah Golowich
Roi Livni Tel Aviv University rl rlivni@tauen tau. ac. i1
MIT CSAII nzg@mit edu
Abstract
We consider the problem of online classification under a privacy constraint. this setting learner observes sequentially stream of labelled examples Vr). for S S T. and returns at each iteration r a hypothesis h, which is used to predict the label of each new example Xy- The learner's performance is measured by her regret against a known hypothesis class H. We require that the algorithm satisfies the following privacy constraint: the sequence It,.... hy of hypotheses output by the algorithm needs to be an (c, dcife-iiferretiially private function the whole input sequence (x1. (1),))),... ................................ Yr). We provide the first non-trivial regret bound for the realizable setting. Specifically, we show that if the class H has constant Littlestone dimension then, given an oblivious sequence of labelled examples, there is a private learner that makes in expectation at most O (log 7) mistakes comparable to the optimal mistake bound in the non-private case, up a logarithmic factor. Moreover, for general values of the Littlestone dimension d. the same mistake bound holds but with line of work has demonstrated strong connection between classes that are online learnable and those that are differentially--riiee this connection and show that an online learning algorithm can in fact be directly privatized (in the realizable setting). We also discuss an adaptive setting and provide sublinear regret bound of O(VT).
in d factor. A recent
learnable. Our results strengthen
Introduction
machine learning has attracted considerable attention in recent years, motivated by the fact that individuals' data often collected to train statistical models, and such models can leak sensitive data about those individuals [13, 32]. The notion of differential privacy has emerged as a central tool which can be used formally reason about the privacy-accuracy tradeoffs one must make in the process of analyzing and learning from data. A considerable body of literature on differentially private machine learning has resulted, ranging from empirical works which train deep neural networks with a differentially private form of stochastic gradient descent [1]. to recent line of theoretical works which aim to characterize the optimal sample complexity privately learning an arbitrary hypothesis class [3. 11, 20].
Nearly all of these prior works on differentially private learning, however, are limited to the statistical learning setting (also known as the offtine setting): this is the setting where the labeled data, (x,, y,), are assumed to be drawn i.i.d. from some unknown population distribution. This setting, while very well-understod and readily amenable to analysis, is unlikely to hold in practice. Indeed, the data (x,, yr) fed as input into the learning algorithm may shift over time (e.g., as consequence of demographic changes in population), or may be subject to more drastic changes which are adaptive to the algorithm's 's prior predictions (e.g., drivers' reactions to the recommendations route-planning apps may affect traffic patterns, which influence the input data to those apps). For this reason, it is desirable to develop provable algorithms which make fewer assumptions on the data.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

In this work, we do so by studying the setting of (private) online learning, in which the sequence of data (x,, yr) is allowed be arbitrary, and we also discuss a certain notion of privacy in a setting where it is even allowed to adapt to the algorithm's is predictions in prior rounds. We additionally restrict our attention to the problem of classification, namely where the labels y; E {0. 1); thus we introduce the problem of differentially private online classification, and prove the following results (see Section for the exact setup):
In the realizable setting with an oblivious adversary, we introduce a private learning algo- rithm which, for hypothesis classes of Littlestone dimension d (see Section 2.1) and time horizon T, achieves mistake bound of Ō(20 log T), ignoring the dependence privacy parameters (Theorem 4.1).
In the realizable setting with an adaptive adversary, we show that a slight modification of the above algorithm achieves a mistake bound of Ō(20(2)) VT) (Theorem 4.2).
We remark that no algorithm (even without privacy, allowing randomization, and in the oblivious adversary setting) can achieve mistake bound of smaller than (d(d) for classes of Littlestone dimension d [30, 33]. Therefore, a class of infinite Littlestone dimension cannot have any finite mistake bound, and the regret for any algorithm, for any time horizon T, is (T)). Thus, our results listed above, which show a mistake-boune (which also the regret in the realizable setting) of Oa(V7) for classes of Littlestone dimension d. establish that in the realizable setting, finiteness of the Littlestone dimension necessary and sufficient for online learnability ([31)) with differential privacy.
Recently it was shown by Alon al. [3] and Bun et al. [11] (later to be improved by Ghazi et al. (20]) that finiteness of the Littlestone dimension is necessary and sufficient for private learnability in the offfine setting. namely with i.i.d. data (and both in the realizable and agnostic settings). Since, as remarked above, the Littlestone dimension characterizes online learnability (even without privacy), this means that binary hypothesis class is privately (offline) learnable if and only if it is online learnable. Our result thus strengthens this connection, showing that the equivalence also includes private online learnability (in the realizable setting).
1.1 Related work
A series of papers [15, 25, 21, 17, 2] has studied the problem of diferentially private online convex optimization, which includes specific cases such private prediction from expert advice and, when one assumes imperfect feedback, private non-stochastic multi-armed bandits [35, 36, 18, 24]. These results show that in many regimes privacy is free for such problems: for instance, for the problem of prediction from the expert advice (with N experts), Agarwal and Singh [2] shows that an e-differentially private algorithm (based on bolow-the-reeullrizee regulerizze--eedde)))) achieves regret of O [VT+ N log'T" which matches the non-private regret bound of O(v'T log when T Z (((/()))) Our results can be seen extending such "privacy is (nearly) free" results to the nonparametric setting where we instead optimize over an arbitrary class of finite Littlestone dimension. Our techniques are different from those of the above papers.
In addition to [11, 20] which establish private learning algorithms for classes with finite Littlestone dimension in the i.i.d. (offline) setting, there has been an extensive line of work private learning algorithms the offline setting: [29, 7, 5, 19] study the complexity of private learning with pure differential privacy, [26, 9, 10, 4] study the sample complexity of privately learning thresholds, and [27, 28, 6] study the sample complexity of privately learning halfspaces.
Preliminaries
In this section we introduce some background concepts used in the paper.
2.1 Online Learning
We begin by revisiting the standard setting of online-learning: We consider a sequential game between learner and an adversary. Both learner and adversary know the sets X and HC The game

---

proceeds for T rounds (again 7 is known) and at each round r I T. the adversary chooses pair (x,, (r) and presents the learner with the example X2. The learner then must present the adversary with a hypothesis (perhaps randomly) h, X - {0. 1). h, is not required to lie in H Finally the adversary presents the learner with y,, which the learner uses to update its internal state. The performance of the learner is measured by its regret which is its number of mistake vs. the optimal decision in hindsight:
E
Σ
(x,, # y.l F=1
Σ (x)) C
min
+
(I)
The adversary is said to realizable if presents the learner with a sequence of examples (x,, yr) so that there is some h+ E H so that for each / E [7], (*xxx, yr. In the realizable setting, the regret simply counts the number of mistakes the learner makes. And we measure the performance by its mistake bound, namely the maximum, over all possible realizable adversaries, of
E Σ (x) # yrl
In the setting with an agnostic adversary, we do not require such ht* to exist; and we measure the learner by its (worst-case) regret, as in Eq. (1). In this paper we focus on the realizable setting; the (private) agnostic setting is left as an interesting direction for future work.
Additionally, we normally make a distinction between two types of adversaries: An oblivious adversary chooses its sequence in advance and at each iteration (x) is revealed the learner. In the adversarial setting, the adversary may choose (x,,), as a function of the learner's 's previous choices: i.e. ....... h1-1- This definition follows the standard setup of online learning (see [12] for example). We note though, that in the non-private setting of online binary classification, one can obtain results against adversary that even gets to observe the learner's prediction time-step However, we will simplify here by considering the more standard setting. It is interesting to find out if we can compete against such a strong adversary in the private setup.
Littlestone dimension We next turn to introduce the Littlestone dimension which a combinatorial measure that turns out to characterize learnability in the above setting.
Let H be class of hypotheses h X {0, 1}. To define the Littlestone dimension of HC, we first introduce mistake trees: a mistake tree of depth d is a complete binary tree, each of whose non-leaf nodes is labeled by point x, E X, and so that the two out-edges of v are labeled by 0 and 1. We associate each root-to-leaf path in a mistake tree with a sequence (I), yi),.... (xa. ya), where for each i [d], the ith node in the path is labeled x; and the path takes the out-edge from that node labeled y;. A mistake tree is said to be shattered by FC if for any root-to-leaf path whose corresponding sequence is y1,........ i E [d]. The Littlestone dimension of HC, denoted Ldim(H(, is the depth of the largest mistake tree that is shattered by JC.
Ya). there is some
H so that hxxx,) yr for all
The Standard Optimal Algorithm (SOA) Suppose H is binary hypothesis class with Littlestone dimension d. Littlestone [30] showed that there is an algorithm, called the Standard Optimal Algorithm (SOA), which, against an adaptive and realizable adversary, has a mistake bound of d: moreover, this is the best possible mistake bound. We will access the SOA as a black box. The underlying assumption we make is that given a realizable sequence (X1, yI)...., (XT. )r), the SOA makes at most Ldim(?() mistakes. We will also assume that whenever the algorithm SOA makes mistake then it changes it state: namely, if the algorithm makes mistake on example / then h,+1 # h,, this is in fact true for the SOA algorithm, but it can be seen that any algorithm with mistake bound can be modified to make sure this holds (simply by reiterating the mistake until the algorithm does change state). We refer the reader to [30, 33] for the specifics of it.
2.2 Differential Privacy
We next recall the standard notion of (c, d)ddiferrenta privacy:
This setup is known as the improper learning problem. In the proper version of the problem, it is required that h; E H and we leave study of proper private online learning for future work. (see [22] for a discssion on proper online learning in the non- non-private case
3

---

Definition 2.1 (Differential privacy). Let n be positive integer, c. (0. 1), and W be set. A randomized algorithm A (Xxx x {0, 13)" W defined to be (e, ō) differeentall private if for any two datasets S,S' E (Xx (0. 13)" differing in a single example, and any event & c &, it holds that
Pr(A(S) E &] S e" Pr(A(S") E &] +
Adaptive Composition The online nature of the problem naturally requires us to deal with adaptive mechanisms that query the data-base. We thus depict here the standard framework of adaptive querying, and we refer the reader to Dwork and Roth [13] for more detailed exposition.
In this framework we assume sequential setting, where step r an adversary chooses two adjacent datasets S and sy, and a mechanism M, (S) from a class F and receives z = M,( for some b E {0. 1} (where b does not depend on r).
Definition 2.2. We say that the family IF of algorithms over databases satisfies (c, 8) -)-ffferrett privacy under T T-fold adaptive composition if for every adversary A and event E, we have
Pr((E)...... 27)) E) e' Pr((E).......d 6.
3 Problem Setup
We now formally introduce the main problem considered this paper, namely that of private online learning. Let X be set, and let H be a set of hypotheses, namely of functions h X - {0, 1}. We consider the setting depicted in Section 2.1 and in this framework we want to study the learnability of private learners which are defined next. We make a distinction between the case of an oblivious and an adaptive adversary:
Private online learning vs. an oblivious adversary As discussed, in this setting the adversary must choose the entire sequence (x1. (Xy, yr) before its interaction with the learner (though it may use knowledge of the learner's s algorithm). In particular, the samples (x,, yr) do not depend on any random bits used by the learner. Thus, in the private online learning problem we merely require that the sequence of hypotheses (hi.... h7) output by the learner (c. di-ffferrent private as function of the entire input sequence (1). (x
Private online learning vs. an adaptive adversary: In the adaptive setting, the adversary may choose each example (x,, yz) as a function of all of the learner's hypotheses up to 1. This makes need to carefully define what mean here by
the notion of privacy little bit more subtle, (e, 0)-privacy. We consider then the following scenario:
At each round 1, the adversary outputs two outcomes (xf, y:)) and (f/,))). The learner then outputs he and (x².y²)) is revealed to the learner where b E (0, 1} is independent of 1. We require that the sequences st = {(x.. } and S ((x/.>)) y/)} differ in, at most, a single example. We will say that an adaptive online classification algorithm is 6) differentially private, if for any event and any adversary, it holds that
Pr[ hb) E] s P
Pr[(A....... ................................ b.) E] 8.
The notion is similar to privacy under foodd adaptive composition. Normally, though, for mecha- nism to be (e, -)ddifferentiallyy private under T-fold adaptive compositions, Dwork et al. [16] requires to be private under an adversary that may choose at each iteration any two adjacent datasets, 5%. S/. Note, however that, in the online setup, the utility is dependent only on a single point at each iteration, hence such requirement will be too strong (in fact, the learner will then be tested on two arbitrary sequences).
4
Main Results
We next state the main results of this paper, we start with logarithmic regret bound for realizable oblivious learning.
Theorem 4.1 (Private Oblivious online-learning) For choice of k Ō(2dtl), and
28
k2 =
T/

---

Running DP-SOA (Algoritim 1) for T iterations on any realizable sequence (x1, y1), (xT, yr),
the algorithm outputs a sequence of predictors hy...., hr such that
The algorithm is (c, 6) differentially private.
The expected number of mistakes the algorithm makes is
28.2 In 1/
h, # yrl =
E
Theorem 4.1 shows that, up logarithmic factor, the number of mistakes in the private case is comparable with the number of mistakes in the non-private case, when d the Littlestone dimension of the class constant. We obtain, though, strong deterioration in terms of the Littlestone dimension sublinear dependece vs. double exponential dependence. As discussed, Ghazi et al. [20] improved the dependence in the batch case to polynomial, and remains an open question similar improvement is applicable in the online case. We next turn to the adversarial case
Theorem 4.2 (Private Adaptive online-learning), There exists an adaptive online classification realizble seqeunce:
algorithm that is (c, diiifeerenttill private with expected regret
2002 VT log 1/(6)
EL
h (x,) # yrl Ō =
Theorem 4.2 provides a sublinear regret bound, which is in fact optimal for the agnostic case. However, in the non-private (realizable) case it is known that constant regret can be obtained2. We leave it as an open problem whether one can achieve logarithmic regret in the realizable adaptive setting.
5 Algorithm
We next present our main algorithm for an oblivious, realizable online private learning algorithm. The algorithm, DP-SOA, assumes access to mistake bound algorithm for the class H (not necessarily private) such as SOA as in [30], which we denote by A, as well as call a procedure Hi HistSparse that depicted below (Algorithm 2). We can think of DP-SOA as an algorithm that runs several copies of the same procedure, where each copy is working on its own subsequence of (1). (xy, yr ) and the sub sequences form random partition of the entire sequence.
Each process can be described by a tree whose vertices are labelled by samples that are iteratively constructed. Each tree outputs a predictor according to the state of its vertices. Hence, overall the algorithm can be depicted as a forest, where at each iteration an example randomly assigned to one of the trees, and that tree, in turn, makes update.
At each time step, we maintain set vertices V,, which we will call pertinent vertices. Each pertinent vertex holds sample S,, At time 1 only the leaves are in Vi, and each leaf is assigned the sample S, = 0. Then, at every time-step where an example (xr, is assigned to tree, it is randomly assigned a Ieaf and then propagated to a pertinent ancestor), and the sample S, is updated to (Sp. (Xy, yr)). next describe, process starts that updates the set of pertinent vertices; this process
pertinent vertex in V (in detail, it is first randomly assigned to
After that, follows the idea of the tournament examples presented in [11].
Whenever two siblings v, s(v) are pertinent and assigned with sequences S, and Ss(v), respectively, they stay pertinent as long as A(S,) = A(Ss(v)), and samples are assigned to them their turn via the process depicted above. Whenever it becomes the case that A(S,) A(Sa(v)), let v denote the parent v, S(v); we consider an example xy on which A(S,), A(Ss(v)) disagree, and guess its label yv. Then, s(v) are removed from the set of pertinent vertices, their parent F becomes pertinent, and we set S. to equal (S,. (x)) if ((,
yv, and (Ss(y) (x)) otherwise. Once this
Zand as discussed, the adversary may even depend on h, at round *In particular, A is required to be an algorithm that achieves a mistake bound of at most on hypothesis classes of Littlestone dimension d. We will use the following (easily verified) fact about such an algorithm: after making mistake, the algorithm must change the hypothesis it outputs for the following round.
5

---

Algorithm DP-SOA
Input (c. (), k1, k2.
Set 1) = 4k, and 4k1n1
2-41
Let G = EV be a forest of 22 full binary trees, each with kj leaves.
Let 7 - Leaves(V) be random mapping that maps [T] to a random leaf.
Set S, = for each leaf v and S, =1 for each non-leaf vertex u (where we define A(1) =1).
Initialize V to be the set of all leaves in the forest.
set $1 (6) be arbitrary leaf from the tree Gj, for each i [k2]
for t=1 to T do
Run HistSparse (h4-1, L4) the List L, {A(S, y
(o)) and receive h,
Predict h, (x₂) = =f,. and observe yr-
Choose V1 E V, be an antecedent of leaf T() lothre exists unique antecedent V, Set 122 = s(p1) (if y1 is the root, continue to the next iteration).
Set (S,, (X,, yy)) Sny
while ASS,,) * A(,,,) AND v1, V2 V, do
Set 7 be the parent of v1.
Choose an arbitrary such that A(S,, [xo] # A and yv randomly
Set (S., yz)) - S; where such that ASS,) [x,] yv. Remove v1,22 from V, and add F to V,. Let V1 be V
if is not the root then
Set v2 to be the sibling of V1 else
Set V1 12 (and hence exit the loop.)
end if
end while
if The While loop was executed at least once then
Let i be the tree for which (() belongs to.
Choose randomly vertex in tree i such that s(v) V, and A(S,) A(Ss(v)) (break ties by choosing randomly).
(If no such exists, let be the root and S, be some sample for which AS,,) =1, add the root to V, and remove all other vertices that belong to tree i).
(1') Set
i=
c+]
11
i
else
Set [+] = v
for all s k2.
end if
Set V,+1 V,-
end for
procedure finishes, the tree outputs (randomly) some hypothesis A(S,) where v is a pertinent vertex. The hypothesis will change only when the state of the tree changes (note that initialization, the tree outputs A()).
5.1 Technical Overview
We next give high level overview of our proof techniques. We focus until the end of this section the oblivious realizable case. The main procedure of the algorithm, DP-SOA, is Algorithm I.
Our proof strategy is similar to the approach of Bun et al. [11] for learning privately in the stochastic setting, which we next briefly describe. In the stochastic setup, the idea was rely on global stability. In a nutshell, randomized algorithm is called globally stable if it outputs certain function with constant probability (over the random bits of algorithm as well as the random i.i.d sample). Once we can construct such algorithm (with sufficiently small error) we run several copies of the algorithm on separate samples, and then we can use any mechanism, such as the one Theorem 5.1 below, that publishes (privately) an estimated histogram of the frequency of appearance of each

---

Algorithm 2 Hist:Spars:: Receives a sequence of --sensitive lists
Initialize: parameters C,
Let o = (ke(k)), 0 = 3n/32
Let On + LAP(o).
Let counter =
For list L1 41 hisle/(2c.8fc.n) (L1).
for f = ,,, do
T:
Define query: Q, = freqi, (1)-
Let v, (2)
if T + v; counter then
Set h, = (iste//(c).8/c..t) ( L.)
counter counter
Counter = 0 + LAP(o).
else
Set h, h4-1 end if
if counter then
ABORT end if end for
function. detail, given a list L = xx) we denote by freq, the mapping
Σ 1[x fl. K XEL
1
freqı (f)
Theorem 5.1 (18) essentially Proposition 2.20). For every e, and n, there exists (e, 8D- mechanism histe.ō. that given list L = {xI..... outputs a mapping freq, X [0. 1] such that if
log 1/)
log 1/788
k 2 (1. = 4/n+
(2)
1/6
1/c
then with probability (1 ():
If ffreq, (x) > 0 then freq,, (x) > 4.
For every x such that freq,, (x) > 17, we have that freq, (x)
Our algorithm follows similar strategy but certain distribution-free nature of the data, as well as the fact that using hist procedure T times may be prohibitive (if we wish to obtain logarithmic regret). We next review these challenges:
needs taken due the sequential (and
Global Stability Our first task is to construct an online version of globally stable algorithm, which roughly means that different copies of the same algorithm run on disjoint subsequences of (x1, y1)...., (Xy, yr). and output fixed hypothesis which may depend on the whole sequence but not on the disjoint subsequences. DP-SDA does so by assigning each subsequence to a tree which running the procedure described in Section We now explain how this procedure induces the
desired stability.
As in Section recall that vertex is pertinent if the set V,. We will refer to the distance of a vertex to any of its leaves as that vertex's 's depth. Note that for each pertinent vertex at depth k, the algorithm makes mistakes on the sequence S, indeed, whenever vertex is made pertinent, we always append to S; an example which forces a mistake for the sequence of child of V. Also, notice that with probability 2 2-2k; where k the number of leaves in the tree, all sequences assigned to each pertinent vertex are consistent with the realized hypothesis h* (recall that we are considering here the oblivious realizable case, hence h* is well-defined). Indeed, this is true as as long as we guessed the label to equal h² (xx)) at each round; the number of guesses is bounded by the number of vertices, which 2k < 2kj. Ultimately, this allows two cases: in the first case vertex of depth d is pertinent: in this case the vertex must identify /** (indeed, if there are two different
7

---

hypotheses that are consistent on sample with d mistakes, then we can force a (d + 1)th mistake). So, if there are "many" trees with a d-depth pertinent vertex, then fraction of 2 2-2k) of them, are outputting h*, hence we found a frequent hypothesis. The second case is that in "many" of the trees, for some k < d, there are many pairs v. s(v) of pertinent vertices at depth & so that A(S,) A(Ss(v)); we will refer to such a pair v, (P) as a collision.
In the batch case the latter case immediately implies that some hypothesis is outputted frequently (i.e., we get global stability) through standard concentration inequality that relates the number of collisions between i.i.d random variables, and the frequency of the most probable hypothesis. In the online case it is a little bit more subtle as the examples are not i.id, hence the sequences for the pertinent vertices are not i.i.d copies of some random variable. However, suppose that there are many collisions at depth k. and that we now reassign the data by randomly permuting the k k-depth subtree (i.e. we reassign a random parent to each vertex at depth k, order to form a new complete binary tree, and we don't change relations at other depths). Since the assignment of the data (xx yr) to the leaves is invariant under permutation, we can think of this process as randomly picking a new assignment, conditioning on the k-th level structure of the trees. Alternatively, we can also think of this process as randomly picking without replacement the different hypotheses outputed by the k k-depth vertices, and counting collisions of siblings.
We now want to relate the number of collisions to their expected mean and obtain bound on the most frequent hypothesis. We can do this using a variant of Mcdiarmid's 's inequality for permutations or sampling without replacement. The observation for this inequality was found in [23] which attributes it to Talagrand [34]. For completeness we provide the proof in the full version.
Lemma 5.2 (Mediarmid's s without replacement). Suppose 7. = (Z1,..., .7)) are random variables sampled uniformly from some universe 2 = [z(")...., ..... (N)) without replacement (in particular n S N). Let F Z" - [0. I] be a mapping such that for 2 (Zi..... 2n) and E' (Zfp...., 2/n) that are of Hamming distance at most 1, IF( - F(2)) c. Then:
2
( 2202262 26 se 9nc
We use Lemma 5.2 as follows: our function F' counts the number of collisions between depth vertices after a random permutation (where we think here of permutation as sampling without replacement), this function is I-sensitive to changing single element, as required. We thus obtain an estimate of the number of collisions for a random permutation, which we can relate to the appearance of the most frequent hypothesis.
The above calculation can be used to obtain guarantee that there exists an hypothesis that appears at frequency 2 (k)( (this frequency is roughly the probability that the tree remains consistent with ht). Since the number of leaves is exponential in the depth, and the depth needs to be at least d (the upper bound on the level at which the algorithm stabilizes for sure), we overall obtain doubly exponential dependence of the frequency on the Littlestone dimension.
Mistake Bound We next turn bound the number of mistakes. The crucial observation is that every time the algorithm makes a mistake, if example is assigned to tree i then with some positive probability (specifically, the frequency of h,, lower bounded by 2 2-0(2") tree i outputs h, Moreover, with probability 1/k] > 0, x, is assigned to the pertinent vertex that made the mistake. Once the example is assigned to this vertex, we have A((S,, (X,, yx))) A(S,()). In particular, the two siblings are taken out of the list of pertinent vertices, and their parent becomes pertinent. In other words, every time the algorithm makes a mistake with some constant probability (roughly 2 2-0(2")) the set of pertinent vertices diminishes by one. Since we start with finite number of leaves as pertinent vertices, the expected number of mistakes is bounded by the number of leaves in the forest.
It remains to show that the number of leaves in the forest is logarithmic in the sequence size (but doubly exponential in the Littlestone dimension). The number of leaves is roughly kj (which is roughly ))2 times the number of trees in the forest; this number of trees depends on the sample complexity of the private process in which we output the frequent hypothesis. We now explain why roughly 0(20(2 In 7) trees is sufficient.
Online publishing of a globally stable hypothesis The next challenge we meet is to output the frequent hypothesis. The most straightforward method to do that is to repeat the idea in the batch
8

---

setting and use procedure hist. We can guarantee a ((VT) factor of deterioration in the privacy parameter (see Lemma 5.4) due the repeated use of the hist procedure times.
Our main observation though, is that in most rounds, the frequent hypothesis does not change, allowing us exploit the sparse vector technique [14], (see also [13]). The sparse vector technique is a method to answer, adaptively, a stream of queries where: whenever the answer to the query does exceed certain threshold the algorithm returns negative result but without any cost in privacy. We pay, though, in each round where the query exceed the threshold.
We will exploit this idea in the following setting: Namely, each list L, is derived from the data = ((11))))........
receive stream of 1-sensitive lists
yr)), and L, changes by at most element, given change in single (x,Yrr). We assume that each iteration / we want to output an element h, E L,, with high frequency. Our key assumption is that the lists are related and very frequent element h, is also frequent at step + 1. Thus in most rounds we just verify that freqz, (1) is large, and only in rounds where it is too small do we use the stable histogram mechanism, paying for privacy.
Indeed, in our setting, the appearance of the frequent hypothesis may diminish by at most one each round. Once its frequency has diminished by a certain factor, then have already made a certain fraction of the maximum possible number of mistakes. Thus, in general we only need to verify that the frequency of h in L, is sufficiently large each round, which can be done via the sparse vector technique without loss of privacy. We next state the result more formally, the proof is provided in the full version
Lemma 5.3. Consider, the procedure HistSparse q,e,s depicted in Algorithm Given a sample S, suppose Algorithm 2 receives stream of lists, where each list is a function of to an array of elements and each list is 1-sensitive. Then Algorithm 2 is (c, 8) differentially private and: Set
@,s,c.a.B.e.a) = 8c(In T + In ln/p)B)
and suppose:
k O == ma a, B.e. a) O O2) B.e. = c In cI
(4)
17C
The procedure then outputs sequence {h, {hr) I where h, L, such that if for each list L, there exists such that freq,, (h) 2 n then with probability at least (1 2B), for all T, either the algorithm aborted before step I or
* ffrerr, (h,) n/16. 16.
. hf # h1:
freqt, (h,-1) s n/8 and freqz, (h₂) 2 n/4
Adaptive adversaries The proof for the oblivious case relies the existence of an h* that is consistent with the data (and independent of the random bits of the algorithm). In the adaptive case, while the sequence has to be consistent, h+ need not be determined, and the consistent hypothesis may depend on the algorithm's 's choices.
However, to obtain regret bound, we rely on the standard reduction that shows that randomized learner against oblivious adversary, can attain a similar regret against an adaptive adversary ([12), Lemma 4.1). One issue, though, is that DP-SOA uses random bits that are shared through time. Hence for the reduction to work we need to reinitialize the algorithm at every time-step. In this case, though, the assumptions we make for using the sparse vector technique longer hold. Thus we can run DP-SOA, using hist (as we no longer obtain any guarantee from HistSparse), and we require that each output hypothesis will be O (e/ (8 The privacy of the whole mechanism now follows from 7'lold composition:
Lemma 5.4. (see for example Dwork and Roth [13]) Suppose (c',8') satisfy:
8' 8/2T, and é' 2 In 1/8)
(5)
Then, the class (c', ('',8')_-2)")""""" d''-differentially private mechanisms satisfies (c, 8) -)differrential privacy under T-fold adaptive composition.
Unfortunately though, the above strategy leads to vI factor in the regret.

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Uri Stemmer for helpful discussions. N.G is supported by a Fannie & John Hertz Foundation Fellowship and an NSF Graduate Fellowship: R.L is supported by ISF grant no. 2 2188/20 and by a grant from Tel Aviv University Center for Al and Data Science (TAD) in collaboration with Google, as part of the initiative of Al and DS for social good.
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 16, page 308-318, New York, NY, USA, 2016.
Association for Computing Machinery. ISBN 978 4784430341
[2] N. Agarwal and K. Singh. The price of differential privacy for online learning. In Proceedings of the 34th International Conference on Machine Learning, pages 32-40, 2017.
[3] N. Alon, R. Livni, M. Malliaris, and S. Moran. Private PAC learning implies finite Littlestone dimension. In STOC, page 852-860, 2019. ISBN 978 1403367059.
[4] A. Beimel. K. Nissim, and U. Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In APPROX-RANDOM, pages 363-378, 2013.
[5] A. Beimel, H. Brenner, S. P. Kasiviswanathan, and K. Nissim. Bounds on the sample complexity for private learning and private data release. Machine Learning, 94:401-437, 2014.
[6] A. Beimel, S. Moran, K. Nissim, and U. Stemmer. Private center points and learning of halfspaces, In COLT, pages 269-282, 2019.
[7] A. Beimel, K. Nissim, and U. Stemmer. Characterizing the sample complexity of pure private learners. JMLR, 20( 133,,, 2019.
[8] M. Bun, K. Nissim, and U. Stemmer. Simultaneous private learning of multiple concepts. arXiv preprint arXiv: 11:.:5111..8000 1.05552, 2015.
[9] M. Bun, K. Nissim, U. Stemmer, and S. P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634 649, 2015.
[10] M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. Composable and versatile privacy via truncated CDP. In STOC, page 74-86, 2018.
[11] M. Bun, R. Livni, and Moran. equivalence between private classification and online prediction. arXiv preprint WxXi::2033005633 2020.
[12] N. Cesa- besa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[13] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014.
[14] C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 38 381-390, 2009.
[15] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 10, page 715-724, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 978 1450300506.
[16] C. Dwork, A. Roth, et The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 93-4):221 1-0077, 2014.
[17] C. C.Dorrk, K. Talwar, A. Thakurta, and L. Zhang. Analyze gauss: Optimal bounds for privacy- preserving principal component analysis. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, page 11-20, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107.
[18] A. Ene, L. Nguyen, and A. Vladu. Projection bandit optimization with privacy guaran- tees. CORR, abs/2012. 2020.
10

---

[19] V. Feldman and D. Xiao. Sample complexity bounds on differentially private learning via communication complexity. In COLT, pages 1-20, 2014.
[20] B. Ghazi, N. Golowich, R. Kumar, and P. Manurangsi. Sample-efficient proper pac learning with approximate differential privacy. arXiv preprint arXiv:2012.03893, 2020.
[21] A. Guha Thakurta and A. Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. In J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 26.
Curran Associates, Inc., 2013.
[22] S. Hanneke, R. Livni, and S. Moran. Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games. arXiv preprini arXiv:2102.0164p 2021.
[23] K. P. C. of random variables permutations. MathOverflow, 2013. URL https: / thoverflow.
costello). Concentration bounds for sums
net/q/ / UBL.:htsss/mmattovrrloowdd/// wwtp:rerwwwwwwee//////e//// (version: 2013-01-29).
[24] B. Hu. Z. Huang. and N. A. Meta. Optimal algorithms for private online learning in stochastic environment. CoRR, abs/2 0022200.07700 102.07929, 2021.
[25] P. Jain, P. Kothari, and A. Thakurta. Differentially private online learning. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 24.1-24.34 2012.
[26] H. Kaplan, K. Ligett, Y. Mansour, M. Naor, and U. Stemmer. Privately learning thresholds: Closing the exponential gap. COLT, pages 2263-2285, 2020.
[27] H. Kaplan, Y. Mansour, U. Stemmer, and E. Tsfadia. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. In NeurIPS, 2020.
[28] H. Kaplan, M. Sharir, and Stemmer. How to Find Point in the Convex Hull Privately. In SoCG, pages 52:1-52:15, 15, 2020.
[29] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Rashkodnikova, and A. Smith. What can we learn privately? In FOCS, pages 531-540, 2008
[30] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285-318, 1988.
[31] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning via sequential complexities. JMLR, 16:155-186, 2015.
[32] A. Roth and M. Kearns, The Ethical Algorithm: The Science of Socially Aware Algorithm Design. Oxford University Press, 2019.
[33] S. Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 1(2):107-194, 2011.
[34] M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de I'Isstitut des Hautes Etudes Scientifiques, 81(1):73-205, 1995.
[35] A. C. Y. Tossou and C. Dimitrakakis. Algorithms for differentially private multi-armed bandits. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI' 16, page
2087-2093. AAAI Press, 2016.
[36] A. C. Y. Tossou and C. Dimitrakakis. Achieving privacy in the adversarial multi-armed bandit. In Proceedings of the Thirty-Fir First AAAI Conference on Artificial Intelligence, AAAI'17, page 2653 26599. AAAI Press, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
11

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "anF11MWuiSM", "reviewer": "Reviewer_pd6C", "summary": "The paper presents an on line classification algorithm which satisfies the differential privacy property. In the realizable setting,  if the Littlestone dimension of the hyothesis space is constant, against oblivious adversary the regret (mistake bound) is equivalent (up to logarithmic factor) to that achieved in the non-differential privacy setting. The loss is in general significant (doubly exponential) in terms of Littlestone dimension. For constant Littlestone dimension,  and against adaptive adversary, the regret obtained is sublinear but grows to order of square root of the time horizon T.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strength: the work strengthens recent results connecting differential privacy and on line learnability by showing scenarios where on line learning can be directly endowed with differential privacy property.\nWeakness: the regret grown doubly exponentially with the Littlestone dimension of the hypotheses class.\nOriginality: the main proof tool bears similarity with recent analogous results for the stochastic setting, however the authors have to overcome some specific new problems to adapt it to the on line setting. \nOverall, I think the results are solid and consistute a significant contribution. \nClarity and presentation: The main algorithmic elements and proof techniques are well explained and the paper is easy to read. However, there are several syntactic errors (words and parts of sentences are swapped, prepositions are missing, verbs are not properly inflected, etc.) and the paper would benefit from a thorough proofreading  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper sufficiently discusses the limitations and does not present potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "aKASkplLp8j", "reviewer": "Reviewer_YBsr", "summary": "The paper considers the problem of online learning hypothesis class $H$ under an additional privacy constraint: The sequence of hypotheses $h_1, h_2, \\ldots, h_T \\in H$ chosen by the learner must be differentially private w.r.t. the data sequence $(x_1, y_1)$ through $(x_T, y_T)$. \n\nIt is well-known that a hypothesis class $H$ is online-learnable if and only if its Littlestone dimension $d$ is finite. A sequence of recent breakthrough proved that $d < +\\infty$ is also sufficient and necessary for $H$ to be privately learnable (in the offline/batch setting). This work makes a further and stronger connection: online learnability is equivalent to private online learnability (albeit this is only proved for the realizable setting).\n\nAssuming the realizable setting, the following quantitative results are given:\n- When $H$ has Littlestone dimension $d$ and the adversary is oblivious, $\\tilde O(2^{O(2^d)}\\log T)$ regret is possible. In particular, for $d = O(1)$, this is comparable to the non-private setting (in which $O(d)$ regret is achievable) up to a log factor.\n- For adaptive adversaries, a modification of the algorithm gives a regret bound of $\\tilde O(2^{O(2^d)}\\log \\sqrt{T})$.\n\nThe analysis follows the following steps:\n- Achieve an online version of \"global stability\", meaning that some hypothesis $h^* \\in H$ is returned with an $\\Omega(1)$ probability. This step is roughly done by randomly allocating the data points to the leaves in a forest structure, and then propagate the data upwards whenever two sibling nodes disagree.\n- In the batch setting, the analysis of the above scheme relies on the i.i.d. property, which no longer holds for the online setting. Nevertheless, the authors showed that the random allocation is sufficient to achieve a similar guarantee, using a version of Mcdiarmid's inequality.\n- Finally, in the batch setting we can publish a model by running a private version of heavy hitters. To publish $T$ models in the online setting, however, leads to severe ($\\sqrt{T}$) degradation of the privacy parameters. To address this issue, it is noted that the frequent hypothesis tends to be stable over time, which enables the use of the sparse vector technique.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The authors gave a clear introduction of the setting of interest, background on online learning and differential privacy, and the results are clearly stated. On the other hand, I found the technical sections (5 and 6) harder to follow as the proofs are quite involved. That said, I think the authors in general did a good job in presenting the algorithm, sketching the analyses, and explaining why the adaptive setting becomes more challenging.\n\nThis work adds on to a series of exciting recent results on the private learnability of binary hypothesis classes. While being built on some ideas/tools from previous work, both the algorithm and its analysis are nontrivial. Although the paper leaves a few important questions open (e.g., improving the dependence on both $d$ and $T$, and extending to the more challenging agnostic case), I found the current results quite solid and should be published. Therefore, I recommend acceptance.\n\nMinor comments:\n- Line 99: \"(private )\"\n- Line 206: Should all $(x_v, y_v)$ on this line be $(x_{\\overline{v}}, y_{\\overline{v}})$ instead?\n\n===Added After Author Response===\n\nI have read the authors' response as well as the other reviews. My overall evaluation of the paper remains the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "HSczmaY0MKE", "reviewer": "Reviewer_wJX6", "summary": "The submission considers the problem of online classification, in which a learner is provided with a stream of labeled examples and must return a hypothesis at each iteration. In particular, the authors look at online learning in a differentially private setting for both the case of oblivious adversaries as well as that of adaptive adversaries (in the realizable setting) and prove mistake bounds.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is a strong submission and makes progress on an important question. Private learnability in the offline setting has been well-studied in recent years, with the results of Alon et al, Bun et al., and Ghazi et al. that have established the connection between finite Littlestone dimension and private learnability. How such a result extends to private *online* learnability is a natural question, and some works have studied regret bounds for private online convex optimization. This submission considers arbitrary hypothesis classes of finite Littlestone dimension and shows that a hypothesis class with Littlestone dimension d can be learned privately with a mistake bound that scales as 2^(O(2^d)).\n\nThe paper is fairly easy to follow, although some more inuition could improve the readability of Algorithm 1. There are some minor typos (e.g., the word \"adversarial\" was misspelled numerous times on page 3).\n\nIn terms of novelty: The techniques are based on ideas that have been explored in other works. The DP-SOA algorithm, for instances, relies on using copies of a non-private SOA algorithm on different subsequences. Moreover, the mistake bounds proceed via construction of an online version of a globally stable algorithm, which draws upon ideas from Bun et al. However, the way in which these ideas are tied together is nontrivial, which merits originality.\n\nThe paper appears to be technically sound, although I have not verified all the details of the proofs (e.g., material in the supplementary material).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "DUTA5Va_Eoj", "reviewer": "Reviewer_aXPb", "summary": "The paper introduces the problem of online classification under a differential privacy constraint. There is a learner and an adversary. Specifically, it is required that the sequence of hypotheses outputted by the learner is (epsilon,delta)-differentially private in the sequence of examples presented by the adversary.\n\nThe paper focuses on the realizable setting, where the sequence of examples chosen by the adversary is consistent with some unknown hypothesis that lies in a hypothesis class known to both the learner and the adversary.\n\nTwo cases are studied. The adversary can be oblivious or adaptive. For oblivious adversaries, the paper proposes an algorithm with regret that is doubly exponential in Littlestone dimension and log(T) factor. For adaptive adversaries, an upper bound doubly exponential in Littlestone dimension times sqrt{T} regret is achieved.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think this is a solid contribution to the area of differentially-private learning. While quantitatively the bounds are not great, e.g. the doubly-exponential dependence on the Littlestone dimension, I think formulating the problem and proving the first non-trivial upper bounds is substantial. \n\nThe paper is very well-written and easy to follow. \n\nTechnically, the paper relies on the property of global stability introduced in prior work. The authors show how to construct an online version of a globally stable algorithm to obtain the log(T) factor in the oblivious case with a novel application of the sparse vector technique. The adaptive case is achieved via a reduction to the oblivious case and using T-fold composition, but this incurs a sqrt{T} factor. \n\nIt might be helpful for readers of Section 6 if the authors could separate how an online version of a globally stable learner implies the online private learner, and how they construct this globally stable learner from SOA. \n\nI would appreciate it if the authors could clarify the following. The authors considered requiring the sequence of hypotheses h_1,...,h_T to be differentially-private, but what about requiring only the sequence of predictions h_1(x_1),...,h_T(x_T) to be differentially-private? Is this notion of privacy different? is it useful? \n\nIn Theorem 4.1 and Theorem 4.2, the upper bounds on the mistake bound of the proposed algorithms incur some dependence on T (log(T) and sqrt{T}). We know that in standard online classification, in the realizable setting, no such dependence is incurred. Can the authors comment on whether such dependence on T is necessary in private online classification?\n\nCan the authors clarify if their algorithm can be made to work with any black-box online learner? Is knowledge of the class H required or is having a black-box online learner sufficient?\n\nSimilar to online-to-batch conversions in standard classification, can private online learners be leveraged to construct private learners in the stochastic setting? This could be further motivation for studying the problem of private online learning.\n\nMinor comments.\n- Line 128: event E \\subseteq W?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In my opinion, the authors have adequately addressed the limitations of their work. I would encourage the authors to discuss societal impacts of their work even if it’s currently of theoretical nature.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A very nice paper that does what it title says: gives a differentially-private online algorithm for classes of finite Littlestone dimension.  The paper is clearly written and gives a good background of the problem, and while the paper mostly makes use of known techniques, it still gives a nontrivial and interesting result.
Decision: Accept (Spotlight)