Black-Box Differential Privacy for Interactive ML
Authors: Haim Kaplan
Yishay Mansour
Shay Moran
Kobbi Nissim
Uri Stemmer
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
online learning

Abstract: In this work we revisit an interactive variant of joint differential privacy, recently introduced by Naor et al. [2023], and generalize it towards handling online processes in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing.

In order to demonstrate the advantages of this privacy definition compared to traditional forms of differential privacy,
we consider the basic setting of online classification. We show that any (possibly non-private) learning rule can be effectively transformed to a private learning rule with only a polynomial overhead in the mistake bound. This demonstrates a stark difference with traditional forms of differential privacy, such as the one studied  by Golowich and Livni [2021], where only a double exponential overhead in the mistake bound is known (via an information theoretic upper bound).

Black-Box Differential Privacy for Interactive ML
Haim Kaplan"
Yishay Mansouri
Shay Moran Kobbi Nissim
Uri Stemmer'
Abstract
In this work we revisit an interactive variant of joint differential privacy, recently introduced by Naor et al. [2023], and generalize towards handling online pro- cesses in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing.
In order to demonstrate the advantages of this privacy definition compared to traditional forms of differential privacy, we consider the basic setting of online classification. We show that any (possibly non non-private) learning rule can be effec- tively transformed to a private learning rule with only a polynomial overhead the mistake bound. This demonstrates stark difference with traditional forms of differential privacy, such as the one studied by Golowich and Livni [2021], where only double exponential overhead in the mistake bound is known (via an information theoretic upper bound).
Introduction
In this work we study privacy of interactive machine learning processes. As motivating story, consider a chatbot that continuously improves itself by learning from the conversations it conducts with users. As these conversations might contain sensitive information, we would like to provide privacy guarantees to the users, in the sense that the content of their conversations with the chatbot would not leak. This setting fleshes out the following two requirements.
(1) Clearly, the answers given by the chatbot to user must depend on the queries made by user u4. For example, the chatbot should provide different answers when asked by user u, for the weather forecast in Antarctica, and when asked by 24 for pasta recipe.
This is in contrast to the plain formulation of differential privacy, where it is required that all of the mechanism outputs would be (almost) independent any single user input. Therefore, the privacy requirement from other users, and would not leak through the other users' interactions with chatbot. Moreover, this should remain true even if "privacy attacker" (aiming to extract information about the conversation user u, had) conducts many different conversations with the chatbot.
aiming for is that the conversation of user u, will remain "hidden"
(2) The interaction with the chatbot is, by design, interactive and adaptive, it aims conduct dialogues with the users. This allows the privacy attacker (mentioned above) to choose its queries to the chatbot adaptively. Privacy, hence, needs to be preserved even in the presence of adaptive attackers.
While each of these two requirements was studied in isolation, the best of knowledge, they have not been (explicitly) unified into a combined privacy framework. Requirement (1) was formalized
Aviv University and Google Research. haimk@tau. ac. il.
TTl Aviv University and Google Research. mansour aissha@@mmil..omm
$ Technnon and Google Research. smoran@technion.c
8 Georgetown University. kobbi missim@georgetoon..cm edu.
1 Tel Aviv University and Google Research. u@uri. i1.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

by Kearns et al. [2015] as joint differential privacy (JDP). It provides privacy against non-adaptive attackers. Intuitively, the chatbot example, JDP aims to hide the conversation of user u, from any privacy attacker that chooses in advance all the queries it poses to the chatbot. This is unsatisfactory since the adaptive nature of this process invites adaptive attackers.
Requirement (2) was studied in many different settings, but to the best of our knowledge, only w.r.t. the plain formulation of DP, where the (adaptive) privacy attacker sees all of the outputs of the
mechanism. Works in this vein include [Dwork et al., 2009 Chan et al.) 2010 Hardt and Rothblum 2010 Dwork et al.) 2010b Bun et al., 2017 Kaplan et al. 2021 Jain al.) 2021]. In the chatbot example, plain DP would require, in particular, that even the messages sent from the chatbot to user u, reveals (almost) no information about uy. In theory, this could be obtained by making sure that the entire chatbot model is computed in privacy preserving manner, such that even its full description leaks almost no information about any single user. Then, when user u, comes, we can "simply" share the model with her, and let her query it locally on her device. But this is likely unrealistic with large models involving hundreds of billions of parameters.
In this work we use challenge differential privacy, which was recently introduced by Naor et al. [2023 in the context of PAC learning [ As discussed below, challenge differential privacy particularly suitable for addressing interactive and adaptive learning processes, such as the one illustrated above. Challenge DP can be viewed as an interactive variant of JDP, aimed maintaining privacy against adaptive privacy attackers. Intuitively, in the chatbot example, this definition would guarantee that even an adaptive attacker that controls all of the users except for user Ui learns (almost) no information about the conversation user uy had with the chathot.
1.1 Private Online Classification
We initiate the study of challenge differential privacy in the basic setting of online classification. Let X be the domain, y be the label space, and 2 = X x y be set of labeled examples. An online learner is (possibly randomized) mapping A: Z x X y. That is, it is mapping that maps a finite sequence E I* (the past examples), and an unlabeled example x (the current query point) to a label y, which is denoted by y S).
Let H S y be a hypothesis class. A sequence 5 E 2 said to be realizable by H if there exists h E H such that h(z;) = yi for every (I,, 1k) E S. For a sequence S = {( 3+) 2* we write M(A: S) for the random variable denoting the number of mistakes makes during the execution on S. That is (): = Σt ( + }, where ÿt- = A(Tx; Sex) is the (randomized) prediction of A on Tic-
Definition 1.1 (Online Learnability: Realizable Case). We say that a hypothesis class H is online learnable if there exists learning rule A such that IE [M] = o(T) for every sequence S which is realizable by H.
Remark 1.2. Notice that Definition 1.1 corresponds to an oblivious adversary, as it quantifies over the input sequence in advance. This should not be confused with the adversaries considered in the context of privacy which are always adaptive in this work. In the non-private setting, focusing on oblivious adversaries does not affect generality in terms of utility. This less clear when privacy constraints are involved We emphasize that our results (our mistake bounds) continue to hold even when the realizuble sequence is chosen by an adaptive (stateful) adversary, that at every point in time chooses the next inpul to the algorithm based on all of the previous outputs of the algorithm.
A classical result due to Littlestone 1988 characterizes online learnability (without privacy con- straints) in terms of the Littlestone dimension. The latter is a combinatorial parameter of H which was named after Littlestone by Ben- David et al. [2009]
In particular, Littlestone's 's characterization implies the following dichotomy: if H. has finite Littlestone dimension d then there exists a (deterministic) learning rule which makes at most d mistakes on
Thhe privacy notion we study, Challenge DP, is generalization of the privacy notion presented by Naor et al. 2023) They facused on a special case in which there is no interaction with individual users. In the chatbot example, this corresponds to having each user submitting only single query to the chatbot without conducting an adaptive dialog with it. In addition, we analyze useful properties of Challenge DP, such composition, These properties were not studied by Naor et al. [2023].
post pros-processing. and
In particular, Golowich Gollowch and Livni 2021 studied both oblivious and adaptive adversaries, and obtained very different results in these two cases.
2

---

every realizable input sequence. In the complementing case, when the Littlestone dimension of H. is infinite, for every learning rule A and every T E N there exists a realizable sequence S of length T such that IF. (M::)) 2 7/2. /. In other words, as a function of T, the optimal mistake bound is either uniformly bounded by the Littlestone dimension, or it is 2 T/2. Because of this dichotomy, in some places online learnability defined with respect to uniform bound the number of mistakes (and not just sublinear one as in the above definition). In this work we follow the more general definition.
We investigate the following questions: Can every online learnable class be learned by an algorithm which satisfies challenge differential privacy? What is the optimal mistake bound attainable by private learners?
Our main result in this part provides an affirmative answer to the first question. We show that for any class H with Littlestone dimension there exists an (e, challeenne DP learning rule which makes most Ô ( log" (#) log² (b)) mistakes, with probability
3. on every realizable sequence of length T. Remarkably, our proof provides an efficient transformation taking non-private learner to a private one: that is, given a black box access a learning rule A which makes at most M mistakes in the realizable case, we efficiently construct an (e, d)-chlllenge-DP learning rule A'' which makes at most Ô M 23 log" (1) log" (G)
mistakes.
1.1.1 Construction overview
We now give a simplified overview of our construction, called POP, which transforms a non-private online learning algorithm into a private one (while maintaining computational efficiency). Let A be non-private algorithm, guaranteed to make at most d mistakes in the realizable setting. We maintain k copies of A. Informally, in every round i E (T) we do the following:
1. Obtain an input point xz.
2. Give x; to each of the & copies of A to obtain predicted labels Ui, Bi.k-
3. Output a "privacy preserving" aggregation ý of [0r.1..... ke,k which is some variant of noisy majority. This step will only satisfy challenge-DP, rather than (standard) DP.
4. Obtain the "true" label y:-
5. Let & E [k] be chosen at random.
6. Rewind all copies of algorithm A except for the 9th copy, so that they "forget" ever seeing
7. Give the true label yı to the éth copy of A.
As we aggregate the predictions given by the copies of A using (noisy) majority, we know that if the algorithm then least constant fraction of the copies of A err. As we feed the true label ya to a random copy, with constant probability, the copy which we do not rewind incurs a mistake at this moment. That is, whenever we make a mistake then with constant probability one of the copies we maintain incurs a mistake. This can happen at most R k d times, since we have k copies and each of them makes most d mistakes. This allows to bound the number of mistakes made by our algorithm (w.h.p.). The privacy analysis is more involved. Intuitively, by rewinding all of the copies of A (except one) in every round, we make sure that a single user can affect the inner state of at most one of the copies. This allows us to efficiently aggregate the predictions given by the copies in privacy preserving manner. The subtle point is that the prediction we release in time i does require querying all the experts on the current example (before rewinding them). Nevertheless, we show that this algorithm is private.
1.1.2 Comparison with Golowich and Livni 2021
The closest prior work to this manuscript is by Golowich and Livni who also studied the problem of private online classification, but under a more restrictive notion of privacy than challenge- In particular their definition requires that the sequence of predictors which the learner uses to predict other words,
in each round does not compromise privacy. publishes the entire truth-table of its predictor, rather than just its current prediction. This might be too prohibitive certain applications such as the chatbot example illustrated above. Golowich and Livni show that even with respect to their more restrictive notion of privacy it is possible to online
as if at each round the learner
3

---

learn every Littlestone class. However, their mistake bound is doubly exponential in the Littlestone dimension (whereas ours is quadratic), and their construction requires more elaborate access to the non-private learner. In particular, it is not clear whether their construction can be implemented efficiently (while our construction is efficient).
1.2 Additional Related Work
Several works studied the related problem of private learning from expert advice (Dwork et al. 22010a Jain et al. 2012 Thakurta and Smith 2013 Dwork and Roth 2014 Jain and Thakurtal [014 Agarwal and Singh 2017 Asi et al. 2022]. These works study a variant of the experts problem in which the learning algorithm has access ls experts; on every time step the learning algorithm chooses one of the experts to follow, and then observes the loss of each expert. The goal of the learning algorithm is that its accumulated loss will be competitive with the loss of the best expert in hindsight. In this setting the private data is the sequence of losses observed throughout the execution, and the privacy requirement is that the sequence of experts chosen by the algorithm should not compromise the privacy of the sequence of losses 8 When applying these results to our context, the set of experts the set of hypotheses in the class H. which means that the outcome of the learner (on every time step) is a complete model (i.e., a hypothesis). That is, in our context, applying prior works on private prediction from expert advice would result in a privacy definition similar to that of Golowich and Livni [022] that accounts (in the privacy analysis) for releasing complete models, rather than just the predictions, which is significantly more restrictive.
There were few works that studied private learning in online settings under the constraint of JDP. For example. Shariff and Sheffei [2018] studied the stochastic contextual linear bandits problem under JDP. Here, in every round & the learner receives a context C,, then it selects an action a (from a fixed set of actions), and finaly it receives a reward y/ which depends on (ct, a,) in a linear way. The learner's 's objective is to maximize cumulative reward. The inon-adaptive) definition of JDP means that action a is revealed only to user uy Furthermore, it guarantees that the inputs of user up (specifically the context and the reward yr) do not leak to the other users via the actions they are given, provided that all these other users fix their data advance. This non-adaptive privacy notion fits the stochastic setting of Shariff and Sheffet (2018), but (we believe) is less suited for adversarial processes like the ones we consider in this work. We also note that the algorithm of (Shariff and Sheffet [2018) in fact satisfies the more restrictive privacy definition which applies to the sequence of predictors (rather than the sequence of predictions), similarly to the that of Golowich and Livni [202T]
2 Preliminaries
Notation. Two datasets S and S' are called neighboring if one is obtained from the other by adding or deleting one element, e.g., S = 5 U {z'}. For two random variables Y, Z we write X ()) Y mean that for every event F it holds that Pr[X E F] S e Pr(Y F] + 5, and Pr[Y F] < e Pr[[ E F] + 8. Throughout the paper assume that the privacy parameter satisfies E = (1), but our analyses trivially extend to larger values of epsilon.
The standard definition of differential privacy is, Definition 2.1 ([workk et al. 2006)). Let M be randomized algorithm that operates on datasets. Algorithum M is (e, (c,0) -)d private (DP) for any two neighboring datasets S, we have M(S) (c,8)) M(S)..
The Laplace mechanism. The most basic constructions of differentially private algorithms are via the Laplace mechanism as follows.
Definition 2.2. A random variable has probability distribution Tap(7) if its probability density 1 exp(-lar//)), where E RR.
function is f(x) = 22
Definition 2.3 (Sensitivity). A function f that maps datasets to the reals has sensitivity A ffr every two neighboring datasets S and S' it holds that [f(S) - f(S)) < A.
Asi et al. 2222) study a more general framework of adaptive privacy in which the private data is an auxiliary sequence (ZI,..., 27). During the interaction with the learner, these 2, are used (possibly in an adaptive way) choose the sequence of loss functions.

---

Theorem 2.4 (The Laplace Mechanism Dwork et al. 2006), Let f be a function that maps datasets to the reals with sensitivity A. The mechanism A that on input S adds noise with distribution Lap( to the output of ((S) preserves (e, O)-differretl privacy.
Joint differential privacy. The standard definition of differential privacy (Definition 2.1 captures setting in which the entire output of the computation may be publicly released without compromising privacy. While this is a very desirable requirement, it is sometimes too restrictive. Indeed, Kearns ct al. 2015) considered a relaxed setting in which we aim to analyze a dataset S = (Z1,... )n)) where every T, represents the information of user i, and to obtain vector of outcomes (y1 ........ yv) This vector, however, is not made public. Instead, every user i only receives its "corresponding outcome" V:- This setting potentially allows the outcome y/ to strongly depend the the input vi,, without compromising the privacy of the ith user from the view point of the other users.
Definition 2.5 ([earrs et al. 2015). Let M: X" + Y be a randomized algorithm that takes dataset S X" and outputs vector ÿ Y". Algorithm M satisfies (s, 8'-joint disferential privacy (JDP) if for every i E [n) and every two datasets S, E X differing only on their ith point it holds that M(S) (c.8) M(S') Here M(S) denotes the (random) vector of length n 1 obtained by ranning (y1, (y1,-.., Vn) < M(S) and returning (y). (yn..... 1/-1 Di+l, ...................... Un)
In words, consider an algorithm M that operates the data of n individuals and outputs outcomes y1..... Vn. This algorithm is JDP if changing only the ith input point x; has almost no affect on the outcome distribution of the other outputs (but the outcome distribution of y is allowed to strongly depend on æz). Kearns et al. [2015] showed that this fits a wide range of problems in economic environments.
Example 2.6 ([Nahmias et al.] 2019 Suppose that city waler corporation is interested in promoting water conservation. To do so, the corporation decided to send each household a customized report indicating whether their water consumption is above below the median consumption in the neighborhood. Of course, this must be done in a way that protects the privacy of the neighbors. One way tackle this would be to compute a privacy preserving estimation z for the median consumption (satisfying Definition 2. Then, in each report, we could safely indicate whether the household's 's water consumption is bigger or smaller than z. While this solution is natural and intuitive, turns out to be sub-optimal: We can obtain better utility by designing JDP algorithm that directly computes a different outcome for each user (" ("above" or "below"). which is what we really aimed for, without going through private median compulation.
Algorithm AboveThreshold. Consider a large number of low sensitivity functions fi, f2..... fT which are given (one by one) to a data curator (holding a dataset S). Algorithm AboveThreshold allows for privately identifying the queries fo whose value fi) is (roughly) greater than some threshold t.
Algorithm 1 AboveThreshold [Dwork et al.) 2009, Hardt and Rothblum, [2010]
Input: Dataset 5 E X", privacy parameters E, 6, threshold f, number of positive reports r, and an adaptively chosen stream of queries f: X* IR with sensitivity A
1. Denote 7 = 0 è /f (n()))
2. In each round i, when receiving query fi E Q, do the following:
(a) Let f. < fi(5) + Lap(7)
(b) If f 2 f, then let o; = and otherwise let or = 0
(c) Output
(d) If Σ o; 2 r then HALT
Even though the number of possible rounds is unbounded, algorithm AboveThreshold preserves differential privacy. Note, however, that AboveThreshold is an interactive mechanism, while the standard definition of differential privacy (Definition 2 1 stated for non-interactive mechanisms, that process their input dataset, release an output, and halt. The adaptation of DP to such interactive settings is done via game between the (interactive) mechanism and an adversary that specifies the inputs to the mechanism and observes its outputs. Intuitively, the privacy requirement is that the view
5

---

of the adversary at the end of the execution should be differentially private w.r.t the inputs given to the mechanism. Formally,
Definition 2.7 (DP under adaptive queries (Dwork al. 2006 Bun et al. 2017)) ). Let M be a mechanism that takes an input dataset and answers a sequence of adaptively chosen queries (specified by an adversary B and chosen from some family Q of possible queries). Mechanism M is (e, 8) --diffferentially private for every adversary B we have that Adap t iiveueryy, (defined below) is (e, -)diifferentially private (w.r.t. its input bit b).
Algorithm AdaptiveQuurry M,B. [Bun et al. 2017]
Input: A bit b E 10. (The bit is unknown to M and B.)
1. The adversary B chooses two neighboring datasets So and St.
2. The dataset St, given the mechanism M.
3. For i 1,2....
(a) The adversary B chooses a query qi E Q.
(b) The mechanism .M is given qi and returns
(c) a, is given to B.
4. When M or B halts, output Hss view of the interaction.
Theorem 2.8 (Dwork et al. 2009 Hardt and Rothblum, 2010 Kaplan et al. 2021 Algorithm AboveThresho ld is (s, --)-)-iffrrenttllll private.
private counter. In the setting of algorithm AboveThreshold, the dataset fixed in the begin- ning of the execution, and the queries arrive sequentially one by one. Dwork et al. [2000a] and Chan et al. [20T0) considered different setting, in which the data arrives sequentially. In particular, they considered the counter problem where in every time step E [T] obtain input bit 2; {0, 1) (representing the data of user i) and must immediately respond with an approximation for the current sum of the bits. That is, at time i we wish to release approximation for 21 + x2 + + Z4.
Similarly our previous discussion, this is an interactive setting, and privacy is defined via a game between mechanism M and an adversary B that adaptively determines the inputs for the mechanism.
Definition 2.9 (DP under adaptive inputs (Dwork et al. 2006 2010a Chan et al. 2010 Kaplan et al. 2021 Jain et al. 2021]). Let M be mechanism that in every round obtains imput point I; (representing the information of user i) and outputs a response az. Mechanism M is (c, 6)- differentially private if for every adversary B we have that A Adapt Ceapttivenpppt... M.B (defined below) is (e, 8) diffferrenti private (w.rt. its input bit b).
Algorithm 3 AdaptiveInput [Jain et al. 2021
Input: A bit b E 10, (The bit is unknown to M and B.)
1. For 1,2, (a) The adversary B outputs bit c {0, 1}. under the restriction that Ej=r Cj S 1.
% The round in which c, = is called the challenge round. Note that there could be at most one challenge round throughout the game.
(b) The adversary B chooses two input points 24,0 and 24,1, under the restriction that if = 0) then 24,0 = ø4,1-
(c) Algorithm M obtains Fi,b and outputs a;,
(d) a is given to B.
2. When M or B halts, output B's view of the interaction.
Theorem 2.10 (Private counter [Dwork et al. 2010a Chan et al. 2010 Jain et al. 2021 )) There
exists an (E, differrentill private mechanism M (as in Definition 2.9 that in each round i [T] obtains an input bit x, E {0. 1) and outputs a response a; E N with the following properties. Let
denote the random coins of M. Then there exists an event E, such that: (1) Pr(s E E) 2 1 - B, and (2) Conditioned on every 8 E for every input sequence (D1,..., the answers (a),-...00)
-E x4 00 ( (ogg(T log (z))
satisfy (a

---

3 Challenge Differential Privacy
We now introduce the privacy definition consider in this work is. Intuitively, the requirement is that even an adaptive adversary controlling all of the users except Alice, cannot learn much information about the interaction Alice had with the algorithm.
Definition 3.1 (Extension of Naor et al. (202)). Consider an algorithm M that, in each round i [T) obtains an input point Ti oulputs "predicted" label Do and obtains "true" label ys- We say that algorithm M is (e, chhalleee differentially private if for any adversary B we have that On MallineGmee,a M. defined below, is (e, d)-fifferentiillyy private (w.r.t its imput bit b).
Algorithm 4 Onl OnlineGame M,B,TT
Setting: T E N denotes the number of rounds and E is a "group privacy" parameter. not explicitly stated determines the inputs adaptively.
assume that g M is online algorithm and B is adversary that
Input of the game: A bit b {0, 13. (The bit b is unknown M and B.)
1. For i = 1,2....,
(a) The adversary B outputs bit c {0, 1}, under the restriction that Σj=1 Cj S g.
% We interpret rounds in which cs = as challenge rounds. Note that there could be at most challenge rounds throughout the game.
The adversary B chooses two labeled inputs (zi,0: Ms,0) and (ar,1, yt.1), under the restric- tion that if C = 0 then (æi,0; Vi,o) = (Jr,1: (1,1). (c) Algorithm M obtains Fi,b- then outputs Ds. and then obtains yt,b.
(d) If 0 then set y: = Út- Otherwise set y: L.
(c) The adversary obtains 9i:
% Note that the adversary B does not get see the outputs of M in challenge rounds.
2. Output B's view of the game, that is ....... Vr and the internal randomness of B.
% Note that from this we can reconstruct all the inputs specified by B throughout the game.
Remark 3.2. Naor et al. (2023) studied a special case of this definition, suitable to their stochastic setting. More specifically, they considered a setting where the algorithm initially gets a dataset containing labeled examples. Then, on every time step, a new user arrives and submits its unlabeled example to the algorithum, and the algorithum responds with a predicted label. We extend the definition to capture settings in which every user interacts with the algorithu (rather than just submitting its input). In the concrete application we consider (online learning) this corresponds to the user submitting its inpul, then obtuining the predicted label, and then submitting the "true" label. Our generalized definition (Section) Al captures this as special case and allows for arbitrary interactions with each user.
Composition and post-processing. Composition and post-processing for challenge-DP follows immediately from their analogues for (standard) DP. Formally, composition is defined via the in which "meta adversary" 8* is trying to guess an unknown bit b E {0. 1}. The meta adversary B* is allowed to (adaptively) invoke & executions of the game specified in Algorithm 4 where all of these executions done with the same (unknown) bit b. See Algorithm
following game, called CompositionGame
Algorithm 5 CompositionGameg. ,,,e,
Input of the game: A bit b (0, (The bit b is unknown B*.)
1. For L f= 1,2,...,
(a) The adversary B* outputs an (s, -chhllleeele algorithm Mr, an adversary Br, and an integer Te-
(b) The adversary 1 obtains the outcome of Onl OnlineGame, M., (b).
2. Output ' view of the game (its internal randomness and all of the outcomes of Onl OnlineGame it obtained throughout the execution).
The following theorem follows immediately from standard composition theorems for differential privacy [Dwork et al. 2010b
7

---

Theorem 3.3 (special case of [woork et al. 2010b]). For every B", every m E N and every 8' 2 0 it holds that Compos ti ta .mm,,, is (E', mô diffferentii private (w.rt. the input bit b) for ===w 2m ( + me(ef -)).
Group privacy. We show that challenge-DP closed under group privacy. This more subtle than the composition argument. In fact, we first need to define what do we mean by "group privacy" in the context of challenge-DDD which we do using the parameter g in algorithm OnlineGame. Recall that throughout the execution of OnlineGame the adversary is allowed challenge rounds. We show that an algorithm satisfies challenge-DP when the adversary is allowed only a single challenge round, then it also satisfies challenge-DP (with related privacy parameters) when the adversary is allowed g > 1 challenge rounds. This is captured by the following theorem; see Appendix for the proof.
Theorem 3.4. Let M be an algorithm that in each round i E [T' obtains an input point æs outputs a "predicted" label 9h and obtains a "true" " label ye. If M is (e, -.cc)llleee then for every g N and every adversary B (posing most g challenges) we have that On in B,T. is (gE, g e ..9.0 ( -i-ffffrrnyylllyy private.
Algorithm ChallengeAT
Towards presenting our private online learner, we introduce variant of algorithm AboveThreshold with additional guarantees, which we call ChallengeAT. Recall that AboveThreshold "hides" single input point. Intuitively, the new variant we present aims to hide
arbitrary modifications both an arbitrary modification to a single input point and an arbitrary modification to a single query throughout the execution. Consider algorithm ChallengeAT.
Algorithm 6 ChallengeAT
Input: Dataset S E X*, privacy parameters E, 6, threshold t, number of positive reports and an adaptively chosen stream of queries X E each with sensitivity A Tool used: An (c, DP algorithm, PrivateCounter, for counting bits under continual observation, guaranteeing error at most À with probability least 1
1. Instantiate PrivateCounter
2. Denote 7 0 A X
3. In each round i, when receiving query fú, do the following:
(a) Let fa fi(S) Lap(7)
(b) If f. 2 t, then let a; and otherwise let a; = 0
(c) Output o
(d) Feed o; PrivateCounter and let count, denote its current output
(e) count, 2 r then HALT
Remark 4.1. When we apply Chal ChallengeAt, it sets À = O log(T) log (E)) Technically, for this it has to know T and 3. To simplify the description this is not explicit in our algorithms.
The utility guarantees of Challengekt
straightforward. The following theorem follows by bounding (w.h.p.) all the noises sampled throughout the execution (when instantiating ChallengeAT with the private counter from Theorem 2.10).
Theorem 4.2. Let s denote the random coins of Cha ThallengeAT. Then there exists an event E such that: (1) Pr[s E] 2 1-B. B. and (2) Conditioned on every E, for every input dataset S and every sequence Tf queries (fi...., fT) it holds that
1. Algorithm Challense ChallengeAT does not halt before the rth time in which it outputs o; 1,
2. For every such that o; it holds that f.(S) O (2 log( (1)
3. For every such that a; = 0 it holds that f((S) < t 5t+0 (A log ())
where A = (t (og())) log (T) is the error of the counter of Theorem 2010
8

---

The event E in Theorem 4.2 occurs when all the Laplace noises of the counter and ChallengeAT are within factor of (og(T75) of their expectation. The privacy guarantees of ChallengeAT are more involved. They are defined via game with an adversary B whose goal is to guess a secret bit b. At the beginning of the game, the adversary chooses two neighboring datasets So, S1, and ChallengeAT is instantiated with Sy- Then throughout the game the adversary specifies queries fa and observes the output of Chall TengeAT on these queries. At some special round i", chosen by the adversary, the adversary specifies two queries für f. where only f is fed into ChallengeAT. In round 1" the adversary does not get to see the answer of Challenge4r on f (otherwise it could easily learn the bit b since f f/= may very different). We show that any such adversary B has only small advantage in guessing the bit b. The formal details are given in Appendix
5 Online Classification under Challenge Differential Privacy
We now ready present our private online prediction algorithm. Consider algorithm POP. Theorem 5.1. When executed with a learner that makes most mistakes and with parameters
k Ô ( log'( log (5)) and O [kk In ))) then with probubility at least (1 33 the
logg(5))
number of mistakes made by algorithm POP is bounded by Ô ( log)(5) log' (a)(()))
Algorithm 7 POP (Private Online Procedure)
Setting: T denotes the number of rounds in the game. A is non-private online- aaline-algoritmm. Parameters: & determines the number of copies of A we maintain. determines the number of positive reports we aim receive from ChallengeAT.
1. Instantiate k copies , of algorithm A
2. Instantiate algorithm Chall engeeT on an empty dataset with threshold | = k/4,, privacy parameters s, number of positive reports r, and sensitivity parameter A 1.
3. For i 1,2....,
(a) Obtain input x
(b) Let Al ttmp ..... A Atmm be duplicated copies of A ,k
(c) Let E [k] be chosen uniformly random
(d) Let Da,e. Ad, (I;). For j E [k] \ {e,) let Di.5 f- A 1lemp(x))
(e) Feed ChallengeAT the query f. = - 2/2 EjE(N) Whs
and obtain outcome dee (If
ChallengeAT halts then POP also halts.)
% Recall that 0, indicates that disagrcement among ... . Ūs,k-
ESE( Dnds 2 meaning that there is "a lot" of
(f) o; then sample ú: E {0, 1) random. Else let iA majority (nij.ritt 0i,x
(g) Output the bit J as prediction, and obtain a "true" label y/4
(h) Feed to Ar,
% Note that A is the only copy of A that changes its state during this iteration
Informally, the privacy guarantees of POP follow from those of ChallengeAT. We give the formal details in Appendix obtaining the following theorem.
Theorem 5.2. Algorithum POP is (O(e), (hall-Challenge-DP That For every adversary B it holds that TmllnnGammepee is (O(e), ((8)) w.r.t the bit b (the input of the game).
We proceed with the utility guarantees of POP. See Appendix F for an extension to the agnostic setting.
Theorem 5.3. When executed with a learner A that makes at most d mistakes and with parameters
k Ô ( log (+) log" (2)) and r O dkk + ) then with probability at least (1 - (3) the
number of mistakes made by algorithm POP is bounded by Ô ( log log²(t) lo)g (og²(z))

---

Proof. By Theorem 4.2 with probability (1 3) over the internal coins of ChallengeAT, for every input sequence, its answers are accurate up to error of
T log (3) 3)
eTTorCAT = O V
where in our case, the sensitivity A is 1, and the error of the counter À most O log (T) log ( by Theorem 2.10 We continue with the proof assuming that this event occurs. Furthermore, we set k = Ω (errorcAT) large enough, such that if less than h the experts disagree with the other experts, then algorithm POP returns the majority vote with probability 1.
Consider the execution of algorithm POP and define 1/5-Err be random variable that counts the number time steps in which least 1/5th of the experts make an error. That is
1/5-Err
[T]
Σ SEIM
1is + v.) h/5
We also define the random variable
expertAdvance Hi [7]
+ 01,1.)1
That is expertAdvance counts the number of times steps in which the random expert we choose (the e,th expert) errs. Note that the 4,th expert is the expert that gets the "true" label yı as feedback. As we run & experts, and as each of them is guaranteed to make at most d mistakes, we get that
expertAdvance < kd.
We now show that with high probability 1/5-Err is not much larger than Advance. Let v be time step in which at least 1/5 fraction of the experts err. As the choice & (the expert we update) is random, then with probability at least _ the chosen expert also errs. It is therefore unlikely that 1/5-Err much larger than expertAdvance. which is bounded by kd. Specifically, by standard concentration arguments (see Appendix for the precise version we use) it holds that
( 3.
Pr
1/5-Err > 18dk + 18
Note that when at least 1/5 the experts disagree with other experts then at least 1/5 the experts err. It follows that 1/5-Err upper bounds the number of times in which algorithm ChallengeAT returns an "above threshold" answer. Hence, by setting r 18dk 18 + In ($) we ensure that w.h.p. algorithm ChallangeAT does not halt prematurely (and hence POP does not either).
Furthermore our algorithm errs either when there is large disagreement between the experts or when all experts err. It follows that 1/5-Err also upper bounds the number of times which our algorithm errs.
Overall, by setting O 0(dk In (1)) we ensure that POP does not halt prematurely, and by setting = o (r + Aln( log we ensure that POP does not err too many times throughout the execution. Combining the requirement and on k it suffices take
A: = δ
log
log
+ e
log(T) log
I -
)
( log" (t) log²
in which case algorithm POP makes at most
with high probability,
Conclusion
Our work presents a new privacy model for online classification, together with an efficiency preserving transformation from non-private online classification, that exhibits doubly exponential improvement in the error compared to prior works on this topic. We leave open the possibility that such an improvement could also be achieved the setting of Golowich and Livni [20TT) i.e., under the more restrictive notion of privacy where the sequence of predictors does not compromise privacy.
10

---

Acknowledgments and Disclosure of Funding
Haim Kaplan was artially supported by Israel Science Foundation (grant 1595/19), and the Blavatnik Family Foundation.
Yishay Mansour was partially funded from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University.
Shay Moran is Robert J. Shillman Fellow; he acknowledges support by ISF grant 1225/20, by BSF grant 2018385. by an Azrieli Faculty Fellowship, by Israel PBC- -ATAT, by the Technion Center for Machine Learning and Intelligent Systems (MLIS), and by the European Union (ERC, GENERALIZATION, 101039692). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Kobbi Nissim was partially funded by NSF grant No. CNS 2001041 and by a gift to Georgetown University.
Uri Stemmer was partially supported by the Israel Science Foundation (grant 1871/19) and by Len Blavatnik and the Blavatnik Family foundation.
References
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In ICML, volume 70 of Proceedings of Machine Learning Research, pages 32-40, PMLR, 06-11 Aug 2017.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. CoRR, abs/2210.13537, 2022.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, 2009.
Mark Bun, Thomas Steinke, and Jonathan Ullman, Make up your mind: The price of online queries in differential privacy. In Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms,, pages 1306-1325. SIAM, 2017.
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In ICALP (2), volume 6199 of Lecture Notes in Computer Science, pages 405-417 Springer, 2010.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-400 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381-390, 2009.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differrnnial privacy under continual observation. In Symposium on Theory of Computing (STOC), pages 715-724. ACM, 2010a.
Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In FOCS, pages 51-60, 2010b.
Noah Golowich and Roi Livni. Littlestone classes are privately online learnable. In NeurlPS, pages 11462-11473, 2021. 2021.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In SODA, pages 1106-1125, 2010.

---

Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for preaeevvig data analysis. FOCS, pages 61-70, 2010.
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. CoRR, abs/21 12.0012,, 2021.
Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differ- entially private learning. In ICML, volume 32 of JMLR Workshop and Conference Proceedings, pages 476-484, .ML.. 2014.
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In COLT, volume 23 of JMLR Proceedings, pages 24.1-24.34. JMLR.org, 2012.
Haim Kaplan, Yishay Mansour, and Uri Stemmer. The sparse vector technique, revisited. In COLT, volume 134 of Proceedings of Machine Learning Research, pages 2747-2776. PMLR, 2021.
Michael J. Kearns, Mallesh M. Pai, Ryan M. Rogers, Aaron Roth, and Jonathan R. Ullman. Robust mediators in large games. CoRR, abs/1552..02698, 2015.
Nick Littlestone. Learning quickly when irrelevant attributes abound: new linear-threshold algorithm. In Machine Learning, pages 285-318, 1988.
Yifat Nahmias, Oren Perez, Yotam Shlomo, and Uri Stemmer. Privacy preserving social norm nudges. Mich. Tech. Rev., 26:43, 2019.
Moni Naor, Kobbi Nissim, Uri Stemmer, and Chao Yan. Private everlasting prediction. CoRR, abs/2305.09579, 2023.
Roshan Shariff and Or Sheffet. Differentially private contextual linear bandits. In NeurlPS, pages 4301-4311, 2018.
Abhradeep Guha Thakurta and Adam D. Smith. (nearly) optimal algorithms for private online learning in call-information and bandit settings. In NIPS, pages 2733-2741. 2013.
A General Variant of challenge-DP
Definition A.1. Consider an algorithm M that, in each phase i [T], conducts arbitrary interaction with the ith user. We say that algorithm M is (c, challlnee differentially private if for any adversary B we have that Genera M.mee, defined below, is (e, 8) -iffferrentil private (w.rt. its input bit b).
Algorithm 8 GeneralGame.M,.u
Setting: E N denotes the number of phases. M is an interactive algorithm and B an adaptive and interactive adversary.
Input of the game: A bit b E 10, (The bit b is unknown to M and B.)
1. For 1,2,...,
(a) The adversary B outputs bit e; E (0, 1}. under the restriction that Σj=1 Gj S 1.
(b) The adversary B chooses two interactive algorithms I,,0 and Ir,1, under the restric- tion that if c; = 0 then T,0 = T,
(c) Algorithm M interacts with I, Let ÿ: denote the view of I,b at the end of this interaction.
(d) If c; 0 then set Ji = 9.. Otherwise set Ji =
(e) The adversary B obtains Ti.
2. Output B's view of the game
12

---

B Group privacy
In this section we prove Theorem 3.4
Proof of Theorem 3.4 Fix ! E N and fix an adversary (that poses at most g challenge rounds). We consider a sequence of games Wo, W1.... Wg. where W3 is defined as follows.
1. Initialize algorithm M and the adversary B.
For round 1.2....,
(a) Obtain a challenge indicator and two labeled inputs (Ii,a, V6.0) and (2r1,1 V6,1) from B.
(b) If E=
j=1 Cj > then set (w;, x)) = (zi,0, Vc,)) Otherwise set (w,, 2i) = (11,1, (c) Feed wy algorithm M,, obtain an outcome ÿt. and feed it 24.
(d) If c; then set Ys = 9:- Otherwise set U
(c) Give 34 to B.
Output , , Är and the internal randomness of B.
That is, Wj simulates the online game between M and B, where during the first & challenge rounds algorithm M is given (I,,1, Vi,1), and in the rest of the challenge rounds algorithm M is given (3i,0, (i,0). Note that
OnlineGame M.B.T.g (0) Wo and
MalineGame.MBsT.ggl Wg.
We claim that for every 0 < é S it holds that W (e,,) W.. To this end, fix 0 < <8S5 and consider an adversary B, that poses at most one challenge, defined as follows. Algorithm B runs B internally. In every round i, algorithm ß obtains from B challenge bit o; and two labeled inputs (z4.0- V6,0) and (24,1, 11, As long as B did not pose its 9th challenge, algorithm B outputs (I4,1; V6,1), (Ir,1 11.1). During the round in which B poses its éth challenge, algorithm outputs (z4.0, 36,0), (24.1, 36.1). This is the challenge round posed by algorithm B. In every round t afterwards, algorithm B outputs (Ir,o, Vr,0), (Ii,o, vr,)). When algorithm B obtains answer ÿt
Dis q = and gives is to algorithm B.
sets 34 = 1, c; =
As B is adversary that poses (at most) challenge, by the privacy properties of M know that Onl InlineGame M.8.T is (e, DDD.. Recall that the output of OnlineGame, M, includes all of the randomness of B, as well as the answers ÿe generated throughout the game. This includes the randomness of B (which & runs internally). and hence, determines also all of the y. 's defined by B throughout the interaction. Let P be post-processing procedure that takes the output of OnlineGame M.B,T and returns the randomness of well as (ý1,..., ./r). By closure of DP to post-processing, we have that P(On1 ineGame (O)) ((,,)) P(Onl ('0nlineGame, (1)). Now note that P(OnlineGame M. (0)) W and P(InlineGame, (1). We, and hence W (c.6) We. Overall we have that
MmlineGame...BTT.a (0) Wo (c.8) W1 (e,6)) W2 (c,)) ... (c,6) W A.B.i.GaameA.B.T...ll
This shows that Onl malineGame,....rg is (gE. g e - didifferrnttially private, thereby completing the proof.
C Privacy Analysis of ChallengeAT
The privacy guarantees of ChallengeAT captured using the game specified in algorithm ChallengeAT-Game::
Theorem C.1. For every adversary B it holds that ChallengeAT-Game, (0(e), w.r.t the bit b (the input of the game).
13

---

Algorithm 9 ChallengeAT-Gamee
Setting: B is an adversary that adaptively determines the inputs ChallengeAT. Input of the game: A bit b E {0, JJ. (The bit b is unknown to ChallengeAT and B.)
1. The adversary B specifies two neighboring datasets Su. $1 E X
2. Instantiate ChallengeAT with the dataset Sy and parameters e, 6, threshold i, and number of positive reports
3. For i = 1,
(a) Get bit E {0,1) from B subject to the restriction that Σj= Cj S. When 6 = 1 this the Challange round.
(b) Get two queries fo : X - R and f: + RR from B, each with sensitivity A, subject to the restriction that if c2 Ó then f!
(c) Give the query f to ChallengeAT and get back the bit o,.
(d) If = 0 then set üs = J.. Otherwise set ýt =.
(e) Give to the adversary B.
4. Publish B's view of the game, that is "r...., fr and the internal randomness of B.
Proof. Fix an adversary B. Let CATG denote the algorithm Chall MaalllengAT--aame with this fixed B. Consider variant of algorithm CATG, which call CATG-noCount defined as follows. During the challenge round i, inside the call to ChallengeAT, instead of feeding a; to the PrivateCounter we simply feed it 0 (in Step 3d of ChallengeAl
By the privacy properties of PrivateCounter (Theorem 2.10). for every E {0,1) we have that
CATG(b) (e.0) CATG-noCount((),
so it suffices to show that CouG-noCount is DP (w.r.t. b). Now observe that the execution of PrivateCounter during the execution of CATG-noCount can be simulated from the view of the adversary B (the only bit that ChallengeAT feeds the counter which is not in the view of the adversary is the one of the challange round which we replaced by zero in CATG-noCount). Hence, we can generate the view of B in algorithm CATG by interacting with Above Thovehhrehhold instead of with ChallengeAT. This captured by algorithm TTr--GAAovveTheeeee
Algorithm 10 Trre-Aboveehhreee
Setting: B is an adversary that adaptively determines the inputs to ChallengeAT. Input of the game: A bit b E {0, 1}. (The bit b unknown ChallengeAT and B.)
1. The adversary B specifies two neighboring datasets So, S1 E X
2. Instantiate PrivateCounter
3. Instantiate AboveThreshold on the dataset S₁ with parameters e, 8, (r+
4. For i 3...
(a) Get bit e; (0, 1) from the adversary B subject to the restriction that Σj Gj S
(b) Get two queries ff X - R and f X* each with sensitivity A from B, subject to the restriction that if c, 0 then f =
(c) Give the query 1 Algorithm AboveThreshold and get back a bit o,.
(d) If c; = 0 then set J = o,. Otherwise set Ú
(c) Give ÿ to the adversary B.
(f) If = 0 then feed to PrivateCounter, and otherwise feed it O.
(g) Let count, denote the current output of PrivateCounter, and HALT if count;
5. Publish B's view of the game, that is Φ1 ....... fr and the internal randomness of B.
This algorithm is almost identical to CATG-noCount, except for the fact that AboveThreeholdd might halt the execution itself (even without the halting condition on the outcome of PrivateCounter). However, by the utility guarantees of PrivateCounter, with probability at least 1 ô it never errs
14

---

by more than X, in which case algorithm AboveThreshold never halts prematurely. Hence, for every bit b E {0, 1} we have that
CATG-AboveThrrehoddd (0.ā) CATG-noCount())
So it suffices show that CATG-AboveTTrreool is DP (w.Lt. its input bit b). This almost follows directly from the privacy guarantees of AboveThreshold since CATG-Above's boveeThrchold interacts only with this algorithm, except for the fact that during the challenge round i the adversary B specifies two queries (and only one of them fed into AboveThreshold), To bridge this gap, we consider one more (and final) modification to the algorithm. called CATG-Abowe Threholl. This algorithm is identical CATG-Above Trrr-A T'rehold,, except that Step we do feed ff to AboveThr Thresholdele = 1. That is, during the challenge round we do not interact with AboveThresholo.
Now, by the privacy properties of AboveThreshold we have that Cove-Above its input bit b). Furthermore, when algorithm AboveThreshold does halt prematurely, we have that CATG-AboveeThrebhee is identical to CATe--bboveIhrreoold. Therefore, for every bit b {0, 13 we have
is DP (w.r.t
CATC-AbooveThrchol((() (0.55) CATT-AbooeTThrchol(())
Overall get that
CATG(O) (ee,0) CATG-noCount(())
(0,55) CATo-Above(Trrcool((()
(0.8) CATo-AbooeeTrrcool000
(e,65) CATG-AboveThreehol(((
(0066) (ATr-AboveeTrreood(())
(0,5) CATG-noCount(()
(c,0) CATG
D Privacy Analysis of POP
In this section we prove Theorem
5.2
Proof of Theorem 5.2 Let B be an adversary that playes in OnlineGame against POP, posing at most 1 challenge. That is, one time step i, the adversary specifies two inputs (x)) v2), (ar y/ algorithm POP processes (xr, vf). and the adversary does not the prediction ÿi this time step. We need to show that the view of the adversary is DP w.r.t. the bit b. To show this, we observe that the view of B can be generated (up to small statistical distance of 8) by interacting with ChallengeAT in the game ChallengeAT-Gan
Formally, consider the following adversary & that simulates while interacting with ChallengeAT instead of POP.
As 1 only interacts with ChallengeAT, its view at the end of the execution (which includes the view of the simulated B) is DP w.r.t. the bit b. Furthermore, the view of the simulated B generated in this process is almost identical to the view of B had it interacted directly with POP. Specifically, the only possible difference is that the computation of ÿ. in Step 3( of B might not be well-defined. But this does not happen when ChallengeAT maintains correctness, which holds with probability least
1 - 8.
Overall, letting ChallengeAT-Gamei denote the view of the simulated B at the end of the interac-
tion of 8 with ChallengeAT, have that
0nl OnlineGamepop (0)) =(0.8) ChallengeAT-Game, (0)
(s.6)
ChallengeAT-Game, (1)
(0.8) Onl OnlineCamepop.
15

---

Algorithm 11 B
Setting: This is an adversary that plays against Challenge in the game ChallengeAT-Game
1. Specify two datasets So = {0) and S₁ {1}.
2. Instantiate algorithm B
3. For i -..2....,T
(a) Obtain challenge indicator and inputs 2/. . from B (where x! 2 if 0).
(b) Let & E [k] be chosen uniformly random
(c) Define the query 9: {00, 1] where q, (b(b) fs and where S; defined in Step of POP.
Note that, given 6, this can computed from (af. .r).................. (xQ, m!) and E,...., & and y1.... 11-1- Furthermore, whenever e; = 0 then this is query of sensitivity at most When & the sensitivity might he large, which we view as two separate queries, corresponding to challenge round when playing against ChallengeAT.
(d) Output the challenge bit and the query ds which is given to ChallengeAT.
(c) c; 0 then
Obtain an outcome 0, from ChallengeAT
ii. Defie ú; as Step 3f POP, as function of a and (xf, #t). ...., (x), x!)) and
(1,...,f Ea and y1 ........ 1h-1-
iil. Feed the bit Os to the adversary B
(f) Obtain "true" label y; from the adversary B.
E A Coin Flipping Game
Consider algorithm 12 which specifies an m-round "coin flipping game" against an adversary B. In this game, the adapuvely chooses the biases of the coins we flip. In every flip, the adversary might gain reward incur "budget loss". The adversary aims to maximize the rewards it collects before its budget runs out.
Algorithm 12 CoinGameg,
Setting: an adversary that determins the coin biases adaptively. It denotes the "budget" of the adversary. m denotes the number of iterations.
Set budget = & and reward = O.
2. In each round 1,2...., m.
(a) The adversary chooses 0 S p: S and P1 < qi S Ps. possibly based on the first
1) rounds.
(b) random variable X; (0, is sampled, where Pr 1] p: and Pr[X;
2] = 4 and Pr[X; = = - P: Gt-
(c) The adversary obtains X;
(d) If X, 1 and budget > 0 then reward reward 1.
(e) Else if X; then budget budget 1.
3. Output reward.
The next theorem states that adversary obtain reward much larger than & in this game. Intuitively, this holds because in every time step i, the probability of X; = 2 is not much smaller than the probability that X;, then (w.h.p.) it is very unlikely that the number of rewards would be much larger than k.
16

---

Theorem E.1 (Gupta et al. 2010 Kaplan et al. 2021 ) For every adversary' 's strategy, every k 2 0. every E N. and every À E we have
Pr| Pr(CoinGamers.k.m A1 S exp (-0 + 3(k 33(kk+1) +1)
F Extension to the Agnostic Case
In this section we extend the analysis of POP to the agnostic setting. We use the tilde-notation to hide logarithmic factors in T, 8 5
Theorem F.1 ([Ben-Davit et al. 2009)). For any hypothesis class H and scalar M > O there exists an online learning algorithm such that for any sequence ((x1, Vi)...., (rT: yr)) satisfying min E [h(x;) - yel S M* the predictions "1.-.., given by the algorithm satisfy NEH
T Σ 1 val S SM + Ldiim(H) (.dim())n((T)).
Definition F22 For parameters u <, w, let (.,( denote variant of POP in which we halt the execution after the uth time in which we ern, for some arbitrary value u S v S w. (Note that the execution might halt even before that, by the halting condition of POP itself.) This could be done while preserving privacy (for appropriate values of u < w) by using the counter of Theorem for privately counting the number of mistakes.
Lemma F.3. Let H be hypothesis class with d = Lddim()), and let A denote the non-private algorithm from Theorem F.1 with M = dn(()). Denote k = 6 ( ( (kd (T)),, and w. 2u. Consider execuling POP(u,u) with A and with parameters k. on an adaptively chosen sequence of inputs (x1, .......,,
...,, (Iaz Yi-), where i S T denotes the time at which POP [u..]] halts.
Then, with probability at least (1 3) holds that
OPT, A min hEH
[h(x))) Vol > d. dn)n
we set A 52 ( and assume that less than 1/ the experts disagree with the other experts, then algorithm POP [u.w] returns the majority vote with probability 1.
Proof sketch. Similarly to the proof of Theorem 5.3
Let 1/5-Err denote the random variable that counts the number time steps in which at least 1/5th of the experts make eгтor. As in the proof of Theorem 5.3 1/5-Err upper bounds both the number of mistakes made by POP ju.wi which we denote by OurEr as well as the number of times in which algorithm Challengek returns "above threshold" answer, which denote by NumTop. By Theorem 4.2, we know that (w.h.p.) NumTop 2 r. Also let WorstExpert denote the largest number of mistakes made by single expert.
Consider the time at which POP [a.w]] halts. It halts because u S v S w mistakes have been made, then
k WorstExpert 2 1/5-Em 2 OurError 2 u = Ω (Id))(T))
Alternatvely,, if POP [umo] halts after r "above threshold" answer, then
k- WorstExpert 2 1/5-Err Numlopp 2 = Ω (kdln(T))
At any case, when POP w. halts it holds that at least one expert made at least Ω (d]n(T)) mistakes. Therefore, by Theorem we have that ОPT, 2 (nT)
Theorem F.4. Let H be a hypothesis class with Tdiim = d. There exists an (c, -hhhlleeee DP online learning algorithm providing the following guarantee. When executed adaptively
17

---

chosen sequence of inputs (I1, 81)...., ..., (xT, yr) ) then the algorithm makes at most Ô mistakes (w.h.p.), where
d.OPT + d2
OPT - min [h(x;)
Vsl-
REH
Proof sketch. This is obtained by repeatedly re-running POP [u.ul] with the parameter setting specified in Lemma F3 We refer to the time span of every single execution of [0P[,, as phase.
By construction, in every phase, [u,w] makes most ((kd) mistakes. By Lemma R.3 every hypothesis in H makes at least d In(T) mistakes in this phase. Therefore, there could be at most Ô (max {1, OPT }) phases, during which we incur total of at most Ô ( (d-OPT mistakes.
+ 82
18


Reviews:
[{"review_id": "Bnm5c0oCUZ", "reviewer": "Reviewer_LQAr", "summary": "The authors propose a new differential privacy definition with desirable online learning properties. In this new variant named Challenge Differential Privacy, the adversary can observe the output of a sequence of online queries, except a \"challenge query\". In this query, two possible pairs of inputs are picked by an adversary. Based on the transcript of the queries without this challenge step, the adversary needs to decide which data point has been used for the hidden query. The authors introduce an algorithm that satisfies Challenge-DP, in which an ensemble of expert models is used to decide on a majority answer, but only one of the experts is allowed to use the ground truth label of the given sample.\n", "questions": "* The authors provided concise and clear proof for composition in the interactive setting, but I assume that this setting satisfies even the generalization of composition, namely concurrent composition[0], which is even more suitable for the described problem proposed by the authors. Did the authors consider proving/looking into concurrent composition, as it seems that is a definition well suited for this setting\n* In this setting, as far as I understand, the release of the learning algorithms results in a total loss of privacy, is that true, or could it be bounded/there might be a possibility of making a model release in this setting (considering that the initial learning algorithms, before the stream of queries, is not private).\n* Do the authors believe that this definition of privacy could replace $(\\epsilon, \\delta)$-DP for machine learning tasks, or should it be an alternative?\n* Is there an equivalence/relationship that the authors observed between $(\\epsilon, \\delta)$-DP and ChallengeDP?\n\n[0]: https://arxiv.org/abs/2207.08335\n", "limitations": "* Their proposed technique involves maintaining multiple copies of the same model, which is a possibly prohibitive approach when solving the proposed problem in the introduction, given the significant size of expert models.\n* The paper ends with a theorem statement. There is no conclusion, further work or discussion. I am willing to increase the score of the paper if the presentation at the end is improved.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The setting proposed by the authors is interesting. Indeed, the standard definition of Differential Privacy is not well-tailored for online learning.\n* The authors discuss and prove the fundamental properties of Differential Privacy for their proposed variant: post-processing, composition, and group privacy.\n* The authors propose a technique to achieve ChallengeDP, POP, for which they introduce privacy and utility guarantees.\n* The work is compositional; it does not introduce new learning algorithms, but it introduces a technique to convert an existing learning algorithm to a private one that satisfies ChallengeDP.\n", "weaknesses": "* The current work is heavily reliant on the appendix. Consider making the main statements self-contained (ChallengeDP, POP). \n* The paper ends with a theorem statement. There is no conclusion/future work/discussion, giving the feel of possibly unfinished work.\n* $\\overset{\\sim}{O}$ notation inside $O$ notation (theorem 4.4) makes it very hard for the reader to compare it to other work/really understand at a granular level the privacy guarantees. As other results have previously shown, constants/linear terms matter a lot in differential privacy; please consider adding explicit guarantees (maybe in the appendix); otherwise, it is hard to understand the benefits of using this approach.\n* I would strongly suggest the authors state more clearly that in this online setting, the training algorithm that sees a sample uses it as a training point afterwards (possibly a more explicit protocol like the one in Naor et al. [0], figure 1 could be used).\n* A clearer discussion about the difference between private everlasting predictions from Naor et al. [0] and challenge differential privacy could be useful, and why it is a generalization of their work (as stated in the abstract). I acknowledge that the authors provided remark 3.2, but this could be more in-detail justified and discussed, as it is one of the paper's key contributions.\n\n[0]: https://arxiv.org/abs/2305.09579\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**> heavily reliant on the appendix**\n\nWhile our algorithms are relatively simple, the proofs are non-trivial and could not fit the main body at its current form. We are open to reorganizing the paper, and will do our best (within the page limit) towards providing more proof details and insights. \n\n\n**> no conclusion/future work/discussion**\n\nWe will add a conclusion section. The short summary is that our work presents a meaningful and new privacy model for online classification, together with a new algorithm that exhibits a doubly exponential improvement in the error compared to prior works on this topic. \n\n\n**> constants/linear terms matter a lot; consider adding explicit guarantees**\n\nWe agree that concrete bounds matter, but asymptotic bounds obtained in theoretical work are not less important. The asymptotic improvements we obtain are huge (polynomial vs double exponential overhead). We believe that our work would lead to future studies on this topic, both theoretically and practically oriented.\n\n\n**> clearer discussion about the difference from Naor et al**\n\nNaor et al. considers a setting where the algorithm initially gets a dataset S containing labeled examples from n users. Then, on every time step, a new user arrives and submits its unlabeled example to the algorithm (and the algorithm responds with a predicted label). \n\nWe generalize their definition to our setting. Specifically, we extend the definition to capture settings in which every user *interacts* with the algorithm (rather than just submitting its input). In the concrete application we consider (online learning) this corresponds to the user submitting its input, then obtaining the predicted label, and then submitting the \"true\" label. Our generalized definition (Section A in the supplementary) captures this as a special case and allows for arbitrary interactions with each user. We will make this clearer in Remark 3.2.\n\n\n**> Did the authors consider proving/looking into concurrent composition**\n\nWe did not. We believe that the notion does indeed satisfy concurrent composition. Though this seems to require slightly generalizing the existing concurrent composition theorems, because (as they are stated) they assume that the dataset(s) are fixed in the beginning of the execution. In our case the dataset is \"evolving\".\n\n\n**> the release of the learning algorithms results in a total loss of privacy, is that true?**\n\nCorrect. This \"relaxation\" is what allowed us to improve the bounds given in prior work (by a doubly exponential factor).\n\n\n**> Do the authors believe that this definition could replace DP or should it be an alternative?**\n\nWe view it as an alternative that, as we show, would allow you to get better utility in some cases.\n\n\n**> Is there an equivalence/relationship that the authors observed between DP and ChallengeDP?**\n\nThe models are not equivalent. The work of Naor et al. showed that PAC learning is possible with ChallengeDP for any concept class with finite VC dimension, which is known not to be the case with the standard notion of DP. \n"}, {"review_id": "LYEscvG4kS", "reviewer": "Reviewer_FnVa", "summary": "This paper studies privacy in the setting of interactive machine learning processes.  Challenge DP is presented as a new relaxation of DP that is satisfies many of the desirable properties of DP and any non-private online prediction algorithm can be constructed into a Challenge DP online prediction algorithm.  \n", "questions": "is there an actual gap between what is achievable under joint (challenge) DP and (traditional) DP? \n\nIs there just a typo in Algorithm 1 and 6 where noise is not added to the threshold? ", "limitations": "The problem setting is for private online classification, yet the relation to a chatbot example is not quite clear.  ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper tackles an important problem and provides a nice motivating example in the setting of a continually improving chatbot.  It is clear from the example that the interaction is adaptive.  Rather than requiring that the interaction with the chatbot be differentially private, they study a relaxation called joint differential privacy, allowing the transcript of responses to depend arbitrarily on each individual’s prompts, but the chatbot should not leak too much information about others’ conversations in each response.  There has been work for this problem in the setting of (traditional) DP, but this is the first work to study mistake bounds in the setting of Joint DP, or more specifically Challenge DP (interactive variant of JDP), which they define and prove basic properties of. ", "weaknesses": "The motivating example is with a chatbot, but the problem setting is for private online classification, which might not be a relevant problem for a chatbot, as it is not clear what the labels or mistakes of a chatbot would be.  Is there a motivating example that is more related to private online classification?\n\nThe only proof in the paper is proving group privacy of challenge DP.  Although group privacy is an important property of any privacy definition, I do not think it adds to the overall narrative of the paper and not surprising as challenge DP is still related to DP.  The main results of this paper are in Theorems 4.1 and 4.2, so the paper should highlight the analysis there, or at the least provide a proof sketch. From the introduction, it is not clear why the reader should care about a group privacy property.   Furthermore, designing challenge DP algorithms is not clear and its relation with creating an online game that is DP is not clear (as in Theorem 4.1).  \n\nAlthough the problem is well motivated, the full story still seems incomplete. In particular, is there an actual gap between what is achievable under joint DP and (traditional) DP?  Currently, there is an existing DP approach that achieves very large mistake bound and this paper achieves a much better mistake bound, but is there a lower bound result?  \n\nIs there just a typo in Algorithm 1 and 6 where noise is not added to the threshold?  The privacy analysis of AboveThreshold depends on noise being added to the threshold that is reused at each round that is not above the noisy threshold.  I am willing to increase my score if this is merely a typo but would like the authors to verify.\n\n\nMinor: \n- \\mathcal{M} denoted mistake bounds and then in Definition 2.5 \\mathcal{M} is a mechanism.\n\n- Line 116 “if the algorithm errs than at least”\n\n- What is the optimal JDP approach for example 2.6?  Seems like you need to know the median to know which ones are above or below.\n\n- Footnote 1 on page 2, “as =composition”.\n\n- Line 309 “That is, For every”\n\n[Update] I have increased my score based on the rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**> The motivating example is with a chatbot... is there an example that is more related to private online classification?**\n\n1. A hospital conducting a study on a new disease might use private online classification to predict the risk of an individual having this disease (based on available tests and medical history). \n\n2. A bank might use private online classification to decide whether or not to grant an individual a loan.\n\n3. An online seller might use private online classification to decide whether to suggest a promotion or not to a user.\n\n\n**> The only proof in the paper is proving group privacy of challenge DP**\n\nWhile our algorithms are relatively simple, the proofs are non-trivial and could not fit the main body at its current form. We are open to reorganizing the paper, and will do our best (within the page limit) towards providing more proof details and insights. \n\n\n**> the full story still seems incomplete... is there an actual gap?**\n\nWe are not aware of a lower bound / separation result. In our work, we present a meaningful and new privacy model for online classification, together with a new algorithm that exhibits a doubly exponential improvement in the error compared to prior works on this topic. We believe that this tells a significant story, even without a separation result.\n\n\n**> typo in Algorithm 1 and 6 where noise is not added to the threshold? I am willing to increase my score if this is merely a typo**\n\nThis is not a typo. It is true that the standard presentation of AboveThreshold utilizes a noisy threshold, which allows it to satisfy pure (eps,0)-DP. But the algorithm remains private even without the noise on the threshold, in which case it satisfies approx (eps,delta)-DP. This appears, for example, in [Hardt and Rothblum, 2010] and [Kaplan et al., 2021] (which we cited).\n\nIn the standard formulation of AboveThreshold, we add noise to the threshold, and resample this noise after every \"above\" answer. This is OK in the standard setting where the queries are considered to be non-private (and only the data points are private). However, as we mentioned in the beginning of Section 4, in our variant (ChallengeAT), the queries are also considered to be private information. Therefore, resampling the noise is problematic as it depends on the current query in a non-private way. (Replacing a constant 0 query with a constant 1 query would typically trigger a new noise sampling.) In contrast, we needed to ensure that the rest of execution behaves similarly no matter what the current query is, and we don't want one query to generate a new noise sampling while the other do not. \n\nWe would be grateful if you could increase your score, as you suggested.\n\n(We remark that there are variants of AboveThreshold in which we add noise to the threshold in the beginning of the execution, and never re-sample it, even after an \"above\" answer. This would be applicable in our setting, but the \"noiseless\" version helps to slightly simplify our analysis.)\n"}, {"review_id": "yuPTL8BFNi", "reviewer": "Reviewer_4WCj", "summary": "The paper addresses the problem of privacy preserving interactive learning. In this problem, a recommendation algorithm improves its model by answering private queries performed by a set of parties in sequential rounds. The responses to users queries should adapt to the query made by each party. Therefore, in order to provide an accurate service, the algorithm's responses must be strongly sensitive to the users. \nThis imposes an important restriction on the privacy guarantees that can be provided using the classical notion of differential privacy (DP): classical DP requires that all responses to queries are equally privacy preserving. Therefore, if the algorithm satisfies this notion of privacy, its accuracy is limited. \n\nTo tackle this problem, the contribution proposes challenge DP: a relaxed notion of DP in which the mechanism is allowed to provide a sensitive output to the party that generated the query, while still providing a less sensitive view to other parties. Using challenge DP, the contribution proposes a construction that, only by having black-box access to a interactive learning algorithm, can construct\na privacy preserving algorithm. The construction improves the accuracy of previous work, reducing the number of errors from exponential to quadratic in d, where d is the number of mistakes made by the black-box algorithm. Furthermore, these improvements are achieved while assuming an adversary that participates in the learning process controlling multiple parties and that can adapt its input in one round of the protocol. ", "questions": "1- In the definitions of DP under adaptive queries (Def 2.7) and adaptive inputs (Def 2.9), it seems that the neighboring databases are\nalways defined with respect to the bit b. As I understand, this means that the database only changes on the query in which the adversary\nplans to be adaptive. I have the impression that this might not reflect some realistic scenarios in interactive ML. For example, consider the case in which the adversary controls all the parties except of one party: Alice. It would be nice that the output (i.e. the view of the adversary) is differentially private with respect to the participation of Alice or not (which, in my understanding, is independent of bit b). Do the aforementioned definitions contemplate this case? \n\n2- In Theorems 4.1 and 4.2, you show how the POP construction (Algorithm 7) performs when it assumes an adversary that can adapt in a single round. However, you define challenge DP to be compatible with many adaptive/challenge rounds (group privacy). How an increase in the number of challenge rounds allowed to the adversary (i.e. an increase of g) would impact in the privacy/accuracy trade-offs? ", "limitations": "While theoretical improvements are significant, more experimentation is required to understand if the practical deployment of the construction is feasible.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is very well written and key aspects of the contribution are presented clearly. The contribution is novel: the relaxation of classical DP and the POP construction are clever. The results are significant, as improvements with respect previous work are important while \nassumptions on the adversary remain realistic. The overall quality is good.", "weaknesses": "I only have fairly minor remarks with respect to the presentation of the contribution. While the introduction to the problem is very nicely achieved, the space dedicated to the main contributions is a bit short. I would have appreciated if it had been bigger and had provided more details. Also, there are multiple DP definitions (such as Definitions 2.1, 2.7 and 2.9) that overload the statement \"X satisfies (epsilon, delta)-DP\" and then understanding which algorithm satisfies which definition of DP becomes a bit confusing. Different terminology for each case could help in clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**> The space dedicated to the main contributions is a bit short**\n \nWhile our algorithms are relatively simple, the proofs are non-trivial and could not fit the main body at its current form. We are open to reorganizing the paper, and will do our best (within the page limit) towards providing more proof details and insights.\n\n\n**> In definitions 2.7 and 2.9 ... it seems that the neighboring databases are always defined with respect to the bit b. As I understand, this means that the database only changes on the query in which the adversary plans to be adaptive** \n\nThe adversary is adaptive throughout the execution: The bit b indexes two thought experiments which the adversary is trying to distinguish between. At every step of the execution, the adversary adaptively determines an input to be included in the execution, except for Alice’s input where the adversary specifies *two* possible inputs and only one of them is included in the execution (based on the value of the bit b which is unknown to the adversary). The adversary's goal is to distinguish between the executions with b=0 and b=1. In other words, the adversary tries to figure out which of Alice's inputs was included in the execution.\n\nAdaptivity on every step makes a strong adversary. In particular, it might adaptively choose future inputs in order to try and guess the bit b (i.e., try to guess Alice's input).\n\n\n**> Consider an adversary controlling all the parties except for Alice. It would be nice if the view of the adversary is DP with respect to the participation of Alice or not**\n\nAs is standard in the literature, these privacy notions could be stated in two flavors: Either we protect against an arbitrary *change* to one individual's data (say Alice), or we protect against the *addition/removal* of one individual. These variants also exist w.r.t. the standard definition of DP, and are very similar. Definitions 2.7 and 2.9 are stated w.r.t. the first option, but they could easily be modified for the second option (without any real effect on the rest of the paper).\n\n\n**> In Theorems 4.1 and 4.2... how an increase in the number of challenge rounds allowed to the adversary (i.e. an increase of g) would impact the privacy/accuracy trade-offs?**\n\nThis could be obtained from our group-privacy theorem (Theorem 3.4). Specifically, Theorem 3.4 shows that POP (as is, with the same utility guarantees) satisfies $(g\\cdot\\varepsilon , g\\cdot e^{\\varepsilon g}\\cdot \\delta)$-Challenge-DP. Alternatively, by rescaling $\\varepsilon$ and $\\delta$, you could get an $(\\varepsilon,\\delta)$-Challenge-DP algorithm whose utility guarantees are degraded by a roughly $g^2$ factor (compared to Theorem 4.2).\n"}, {"review_id": "wAIDD7nlNY", "reviewer": "Reviewer_4d8Q", "summary": "This work proposes a novel method to apply DP to the context of interactive ML.", "questions": "Are there any practical results to showcase the advantages of the proposed method?", "limitations": "Overall, I do not see many reasons to accept this work in its current state: While the method looks promising and may have broad implications for the use of DP in interactive setting, the manuscript does not do the method any justice and really struggles to make this accessible to a wide range of ML researchers.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The method itself is an interesting proposal, well-supported with proofs and theory. This work also extensively describes prior advances in the field in great detail.", "weaknesses": "The paper has numerous issues with the way it is written. Firstly, there should not be any citations in the abstract, so, please reword it. Secondly, and much more importantly, this paper lacks a proper conclusion. There is no way for the reader to get a clear overview of the implications of this work as well as its relevance to the broader ML community. Instead, the work ends with a large algorithm definition, which really either belongs to the methods section or to the appendix. While I understand the overall idea of what the work proposes, there are no clear contributions either. I strongly encourage authors to rework these, as otherwise it is incredibly difficult to identify the merits of their method.\n\nCertain sections really don’t belong where they are right now: 1.1 in my eyes has nothing to do with the introduction; example 2.6, while helps contextualise the method is really taking the space away from the rest of the work; many algorithms can be placed in the appendix etc. Point being that the work is very difficult to process because some crucial sections are missing, yet some sections which were included really do not add the value to the submission.\n\nFinally, it looks to me as this is a purely theoretical paper, there are no experiments to support what the authors proposed. Given that the submission is presented as application-driven and useful for ML practitioners, this is rather odd.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**> there should not be any citations in the abstract**\n\nThis is a minor issue, and we are willing to remove the citations\n\n\n**> this paper lacks a proper conclusion; there are no clear contributions; it is incredibly difficult to identify the merits; the manuscript does not do the method any justice**\n\nWe have two main contributions:\n1. We present a meaningful and new privacy model for online classification.\n2. We present a new algorithm satisfying our privacy notion, that exhibits a doubly exponential improvement in the error compared to prior works on private online classification.\n\nWe believe that these two contributions constitute a significant story, and will make this clearer in the paper.\n\n\n**> Certain sections really don't belong where they are right now**\n\nWhile our algorithms are relatively simple, the proofs are non-trivial and could not fit the main body at its current form. We are open to reorganizing the paper, and will do our best (within the page limit) towards providing more proof details and insights. \n\n\n**> this is a purely theoretical paper, there are no experiments... Are there any practical results?**\n\nThis is a theory paper. We agree that concrete bounds matter, but asymptotic bounds are not less important, and the asymptotic improvements we obtain are huge (polynomial overhead vs double exponential). We believe that our work would lead to future studies on this topic, both theoretically and practically oriented.\n"}]

Author rebuttal:

Meta-review: The reviewers pointed out many strengths of this paper, including the novelty of the problem, the clear need for the definition in machine learning applications, and that the paper provides methods for satisfying the new definition plus analyzes properties of it. 

Several reviewers noted that parts of the paper seem incomplete, and provided action items to address this. The authors should address these shortcomings in the final version. 

Another major-but-easily-fixable weakness of the paper that the authors should address in the camera ready is the organization of the paper. While the paper does have many strong results, they are mostly in the appendix. The paper contributions start on page 7, with 3.5 pages of intro and 2.5 pages of preliminaries, which only leaves 3 pages for results. This is unusual and seems to diminish the scope of their contribution. The full version of the paper (submitted as supplementary material) contains substantially more technical material and contributions. For the published conference version, the content in the first 6 pages should be substantially reduced to allow for more technical content in the body to better emphasize the contributions.
Decision: Accept (poster)