Private Everlasting Prediction
Authors: Moni Naor
Kobbi Nissim
Uri Stemmer
Chao Yan
Venue: NeurIPS 2023 oral (2023)
Keywords: Differential privacy
private learning
private prediction

Abstract: A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al., FOCS 2008]. Past research uncovered that private learners may need to exhibit significantly higher sample complexity than non-private learners as is the case of learning of one-dimensional threshold functions [Bun et al., FOCS 2015, Alon et al., STOC 2019].

We explore prediction as an alternative to learning. A predictor answers a stream of classification queries instead of outputting a hypothesis. 
Earlier work has considered a private prediction model with a single classification query [Dwork and Feldman, COLT 2018]. We observe that when answering a stream of queries, a predictor must modify the hypothesis it uses over time, and in a manner that  cannot rely solely on the training set.

We introduce {\em private everlasting prediction} taking into account the privacy of both the training set {\em and} the (adaptively chosen) queries made to the predictor. 
We then present a generic construction of private everlasting predictors in the PAC model.
The sample complexity of the initial training sample in our construction is quadratic (up to polylog factors) in the VC dimension of the concept class. Our construction allows prediction for all concept classes with finite VC dimension, and in particular threshold functions 
over infinite domains, for which (traditional) private learning is known to be impossible.

Private Everlasting Prediction
Moni Naor*
Kobbi Nissim
Uri Stemmert
Chao Yan
Abstract
A private learner is trained sample of labeled points and generates a hypothesis that can be used for predicting the labels newly sampled points while protecting the privacy of the training set Kaaivviwannathann et al., FOCS 2008]. Past research uncovered that private learners may need to exhibit significantly higher sample complexity than non non-private learners as is the case of learning of ame-dimensione threshold functions [Bun et al., FOCS 2015, Alon et al., STOC 2019]. 9.]
We explore prediction an alternative learning. A predictor answers a stream of classification queries instead of outputting hypothesis. Earlier work has considered private prediction model with a single classification query [Dwork and Feldman, COLT 2018]. 8J. We observe that when answering a stream of queries, predictor must modify the hypothesis it uses over time, and in manner that cannot rely solely on the training set.
We introduce private everlasting prediction taking into account the privacy both the training set and the (adaptively chosen) queries made to the predictor. We then present generic construction of private everlasting predictors in the PAC model. The sample complexity of the initial training sample in construction is quadratic (up to polylog factors) in the VC dimension of the concept class. Our construction allows prediction for all concept classes with finite VC dimension, and in particular threshold functions over infinite domains, for which (traditional) private learning is known to be impossible.
Introduction
A PAC learner for concept class Cs given labeled examples S ((x,, (()l,i))) drawn i.i.d. from an unknown underlying probability distribution D over a data domain X and outputs a hypothesis that can be used for predicting the label of fresh points I sampled from the same underlying probability distribution D [Valiant, 1984]. It is well known that when points are labeled by a concept selected from concept class C= (c: - (0, 1]] then learning is possible with sample complexity proportional to VC(C).
"Department of Computer Science and Applied Math, Weizmann Institute of Science. moni naor@veizmann. ac. il. Incumbent of the Judith Kleeman Professorial Chair. Research sup- ported in part by grants from the Israel Science Foundation (no.2686/20) 20), by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center.
'Department of Computer Science, Georgetown University. kobbi.nissinngeeeee..... missin@georgetomm.m edu. Re- search supported in part by by NSF grant No. CNS-2001041 and gift to Georgetown University. tBlavatnik School of Computer Science, Tel Aviv University, and Google Research, u@uri. co. il. Partially supported by the Israel Science Foundation (grant 1871/19) and by Len Blavatnik and the Blavatnik Family foundation.
$Department of Computer Science, Georgetown University. cy3994georgetomm. edu. Research supported in part by by gift to Georgetown University.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

Learning often happens in settings where the underlying training data is related to individ- uals and privacy-sensitiee For legal, ethical, or other reasons, the learner then required, to protect personal information from being leaked in the learned hypothesis h. Private learning was introduced by Kasiviswanathan et al. [2011] ]] as a theoretical model for studying such tasks. A private learner is a PAC learner that preserves differential privacy with respect to its training set S. That is, the learner's distribution on outcome hypotheses must not depend too strongly on any single example in S. Kasiviswanathan et al. showed that any finite concept class can be learned privately and with sample complexity n = Ollo (CI), value that is sometimes significantly higher than the VC dimension of the concept class C.
now understood that the gap between the sample complexity of private and non- -oiitriv learners is essential an important example is private learning of threshold functions (defined over an ordered domain X as Cyhresh- = [Cy]rex where c₃(x) = 11xa)), which requires sample complexity that is asymptotically higher than the (constant) VC dimension of Cihresh- In more detail, with pure differential privacy, the sample complexity of private learning is characterized by the representation dimension of the concept class [Beimel et al., 201 The representation dimension of Cthresh (hence, the sample complexity of private learning thresholds) is @llog |X)) [Feldman and Xiao, 20.5]. With approximate differential privacy, the sample complexity of learning threshold functions is @ [X]) [Beimel et al., 2013b, Bun et al., 2015, Alon et al., 2019, Kaplan et al., 2020, Cohen et al., 2022]. Hence, whether with pure or with approximate differential privacy, the sample complexity of privately learning thresholds grows with the cardinality of the domain [X] and no private learner exists for this task over infinite domains. In contrast, non non-private learning is possible with constant sample complexity (independent of [X])
Privacy preserving (black- box) prediction. Dwork and Feldman [2018] proposed privacy- preserving prediction as an alternative for private learning. Noting that "[i]t is now known that for some basic learning problems [.. producing an accurate private model requires much more data than learning without privacy," they considered a setting where "users may be allowed to query the prediction model on their inputs only through an appropriate interface". That is, setting where the learned hypothesis is not made public and may be accessed only in a black-box manner via privacy-preserving preserving query-answering prediction interface. The prediction interface is required to preserve the privacy of its training set S:
Definition 1.1 (private prediction interface [Dwork and Feldman, 2018] (rephrased)). A prediction interface A is (E, ())-)fffreenntallly private if for every interactive query generating algorithm Q, the output of the interaction between Q and A(S) is (c, -)ddiiffreettillly private with respect to S.
Dwork and Feldman focused on the setting where the entire interaction between Q and A(S) consists of issuing single prediction query and answering it:
Definition 1.2 (Single query prediction [Dwork and Feldman, 2018]). Let A be an algorithm that given set of labeled examples S and unlabeled point x produces label y. A is an (e, difffefrrrettllllyy private prediction algorithm if for every x, the output A(S,x) is (e.f)-differentially private with respect to S.
W.r.t. answering single prediction query, Dwork and Feldman showed that the sample complexity of such predictors is proportional to the VC dimension of the concept class.
1.1 Our contributions
We extend private prediction to answering sequence unlimited in length of prediction queries. We refer to this as private everlasting prediction (PEP). Our goal is to present a generic private everlasting predictor with low training sample complexity (S].
1.1.1 Private prediction interfaces when applied to a large number of queries
We begin by examining private everlasting prediction under the framework of Definition 1.1.
We prove:

---

Theorem 1.3 (informal version of Theorem 3.3). Let A be a private everlasting prediction interface for concept class C and assume A bases its predictions solely on the initial training set S, then there exists private learner for concept class C with sample complexity [S}.
This means that everlasting predictors that base their prediction solely the initial training set S are subject to the same complexity lowerbounds as private learners. Hence, to avoid private learning lowerbounds, private everlasting predictors need rely on more than the initial training sample S as a source of information about the underlying probability distribution and the labeling concept.
In this work, we choose to allow the everlasting predictor to rely on the queries made which are unlabeled points from the domain X assuming the queries are drawn from the same distribution the initial training S is sampled from. This requires modifying the privacy definition, as Definition 1.1 does not protect the queries issued to the predictor.
1.1.2 A definition of private everlasting predictors
Our definition of private everlasting predictors is motivated by the observations above. Consider an algorithm A that is first fed with a training set S of labeled points and then executes for an unlimited number of rounds, where in round algorithm A receives as input query point x; and produces label D:- We say that A is an everlasting predictor if, when the (labeled) training set and the (unlabeled) query points are coming from the same underlying distribution, A answers each query points x; by invoking a good hypothesis h; (i.e., h; has low generalization error), and hence the label i; produced by A is correct with high probability. We say that A is private everlasting predictor if its sequence of predictions 91, 22, P3.... protects both the privacy of the training set and the query points X2, in face of any adversary that chooses the query points adaptively.
We emphasize that while private everlasting predictors need to exhibit average-case utility as good prediction is required only for the case where the initial training set S and the queries x1, X2, are selected i.i.d. from the same underlying distribution - our privacy requirement is worst-case, and holds in face of an adaptive adversary that chooses each query point x; after receiving the prediction provided for (xI....,XiI)) ) and not necessarily in accordance with any probability distribution.
1.1.3 A generic construction of private everlasting predictors
We show a reduction from private everlasting prediction of concept class to non con-private PAC learning of C. Our Algorithm GenericBBL, presented in Section 6, executes in rounds.
Initialization.
The input to the first round is labeled training set where [S] ((VC(C)))² assumed to be labeled consistently with some unknown target concept c E C. Denote S S and c.
Rounds. Each round begins with collection S: of labeled examples and ends with newly generated collection of labeled examples S,+1 that feeds as input for the next round. The size of these collections grows by a constant factor at each round, to allow for the accumulated error of the predictor to converge. The construction ensures that each labeled set S; is consistent with some concept in c E C, which is not necessarily the original target concept c, but has a bounded generalization error with respect to c. In more detail, the construction ensures that Prx-DIGH+1 (x)x decreases by factor of two in every round, and hence, by the triangle inequality, Pr Pr.--lc((x)) x c(x)) is bounded.
We briefly describe the main computations performed in each round of GenericBBL.5
Round initialization: At the outset of a round, the labeled set S is partitioned into sub-sets, each with number of samples which is proportional to the VC dimension (so we have x VCIC)
sub-sets). Each of the sub-sets is used for training a classifier
'Important details, such as privacy amplification via sampling and management of the learning accuracy and error parameters omitted from the description provided in this section.
3

---

non non-privately, hence creating a collection of classifiers F; = If: [0, that are used throughout the round.
Queries are issued to the predictor in an online manner. A query is first labeled by each of the classifiers in F,- Then the predicted label is computed by applying a
Query answering:
majority vote these intermediate labels. By standard )
composition theorems for differential privacy, we could answer roughly |F ~ VC[C)
|s,1
queries without exhausting the privacy budget.
Generating a labeled set for the following round: A round ends with the preparation of collection S,+1 of labeled samples that is to be used in the initialization of next round. We explore alternatives for creating Si+1:
As at the end of a round the predictor has already labeled all the queries presented during the round's execution, one alternative is to let S consist of these queries and the labels provided for them. Note, however, that it is not guaranteed that the majority vote would result in set of labels that are consistent with some concept in C, even if S; is consistent with some concept in C. Hence, following this alternative would require the use of non non-private agnostic learners instead. Furthermore, the error introduced by the majority vote can be larger than the generalization error of the classifiers in Fj by a constant factor greater than one. This may prevent the generalization error of the classifiers used in future rounds from converging.
To overcome this problem, we use Algorithm LabelBoost - a tool developed by Beimel et al. [2021] in the context of private supersupe learning. LabelBoost takes as input the sample S; (labeled by concept 9 E C) and the (unlabeled) queries made during the round. It labels them with a concept ci+1 E C where the error of C++1 with respect to G, i.e., Pra-p(çi+1(X (x) = (x)x) is bounded.
Controlling the generalization error: Let S/+1 denote the (re)labeled query points
obtained in the ith round. This is a collection of size [S (v Hence, provided
that |S,| 2 (VC(C))² we get that |S |Syl- This allows to lower the accuracy parame- ters of the non- con-piivate learners in each round, and hence ensure that the total error converges.
Theorem 1.4 (informal version of Theorem 6.1). For every concept class C, Algorithm GenericBBL is a private everlasting predictor requiring an initial set of labeled examples which is (upto polylogarithmic factors) quadratic in the VC dimension of C.
1.2 Related work
Beyond the work of Dwork and Feldman [2018] 8] on private prediction mentioned above, our work is related to private semi-supervised learning and joint differential privacy.
Semi-supervised private learning. As in the model of private semi-supervised learning of Beimel et al. [2021], our predictors depend on both labeled and unlabeled samples. Beyond the difference between outputting hypothesis and providing black-box prediction, major difference between the settings is that in the work of Beimel et al. [2021] all samples labeled and unlabeled are given once at the outset of the learning process whereas in the setting of everlasting predictors the unlabeled samples are supplied in an online manner. Our construction of private everlasting predictors uses tools developed for the semi-supervised setting, and in particular Algorithm LabelBoost of of Beimel et al.
Joint differential privacy. Kearns al. [2015] introduced joint differential privacy (JDP) as a relaxation of differential privacy applicable for mechanism design and games. For
6o see that the majority vote can increase the generalization error by constant factor consider three classifiers fú f2. each with generalization error a, and let A, C be three disjoint subsets of the support of the underlying distribution, each of probability weight a/2. If the classifier fi errs on inputs in A U B, the classifier f2 errs on A U C, and fa errs on BUC C then the majority of fi. f2. errs on inputs in A J B U C and hence the generalization error grows from to 1.5a.

---

every user u, JDP requires that the outputs jointly seen by all other users would preserve differential privacy w.r.t. the input of u. Crucially, in JDP users select their inputs ahead of the computation. In our settings, the inputs to private everlasting predictor are prediction queries which are chosen in an online manner, and hence query can depend on previous queries and their answers. Yet, similarly to JDP, the outputs provided to queries not performed by a user u should jointly preserve differential privacy w.r.t. the query made by u. Our privacy requirement hence extends JDP to adaptive online setting.
Additional works on private prediction. Bassily et al. [2018] studied variant of the private prediction problem where the algorithm takes a labeled sample S and is then required to answer prediction queries (i.e., label sequence of m unlabeled points sampled from the same underlying distribution). They presented algorithms for this task with sample complexity [S] ž vm. This should be contrasted with our model and results, where the sample complexity is independent of m. The bounds presented by Dwork and Feldman [2018] and Bassily et al. [2018] were improved by Dagan and Feldman [2020] and by Nandi and Bassily [2020] who presented algorithms with improved dependency on the accuracy parameter in the agnostic setting.
1.3 Discussion and open problems
We show how transform any (non- coon-prittee learner for the class C (with sample complexity proportional to the VC dimension of C) to a private everlasting predictor for C. Our construction is not polynomial time due the use of Algorithm LabelBoost, and requires an initial set S of labeled examples which is quadratic in the VC dimension. We leave open the question whether [S] can be reduced to be linear in the VC dimension and whether the construction can be made polynomial time. A few remarks are in order:
1. While our generic construction is not computationally efficient, it does result in efficient learners for several interesting special cases. Specifically, algorithm LabelBoost can be implemented efficiently whenever given an input sample S it is possible to efficiently enumerate all possible dichotomies from the target class C over the points in S. In particular, this is the case for the class of 1 1-dim threshold functions Cihresh, as well as additional classes with constant VC dimension. Another notable example is the class thresh which intuitively is an "encrypted" version of Ciiresh. Bun and Zhandry [2016] 6] showed that (under plausible cryptographic assumptions) the class Chreeh cannot be learned privately and efficiently, while it can be learned efficiently non-privately. Our construction can be implemented efficiently for this class. This provides an example where private everlasting prediction be done efficiently, while (standard) private learning is possible but necessarily inefficient.
2. It is now known that some learning tasks require the produced model to memorize parts of the training set in order achieve good learning rates, which in particular disallows the learning algorithm from satisfying (standard) differential privacy [Brown et al., 2021]. Our notion of private everlasting prediction circumvents this issue, since the model is never publicly released and hence the fact that it must memorize parts of the sample is not of direct privacy threat. In other words, our work puts forward a private learning model which, in principle, allows memorization. This could have additional applications in broader settings.
3. As mentioned above, in general, private everlasting predictors cannot base their predic- tions solely on the initial training set, and in this work we choose to rely on the queries presented to the algorithm (in addition to the training set). Our construction can be easily adapted to setting where the content of the blackbox is updated based on fresh unlabeled samples (whose privacy would be preserved), instead of relying on the query points themselves. This might be beneficial to avoid poisoning attacks via the queries.
5

---

Preliminaries
2.1 Preliminaries from differential privacy
Definition 2.1 ((e, d--iddistinguuhhabblity. Let R be two random variables over the same support. We say that R are (e, di.iiiidiistinnuuhhabllle if for every event E defined over the support of R,,
Pr[Ro E E] s ef Pr(R E and Pr[R] E E of Pr[Ro E E]
Definition 2.2. Let X be data domain. Two datasets x, e X" are called neighboring if x = x/]l= Definition 2.3 (differential privacy [Dwork et al., 2006)). A mechanism M X - Y is (c, diffeererreetllllly private if M(x) and M(x') are (c, diiitiiiiiitnnnuhhaalle for all neighboring x,x' X
In our analysis, we use the proc-progs and composition properties of differential privacy, that we cite in their simplest forms.
Proposition 2.4 (post-processing). Let M1 Y be an (e, d)-differentially private algorithm and M2 Y Z be any algorithm. Then the algorithm that on input x E X" outputs Mz(M,(x) is (eff0-diiferenttaall private.
Proposition 2.5 (composition). Let M, be a (e,, ( diffferrret private algorithm and let M2 be (22,62) 5-)-dffferenttillyy private algorithm. Then the algorithm that on input X outputs M2x() is (é1 + 62, + ( biffeeifferntlilllyy private.
Theorem 2.6 (Advanced composition Dwork et al. (2010b)) Let MI...,,yy M, X Y be (e.f)-differentially private algorithtms. Then the algorithm that on input x E outputs (x(xx)....M((x)) is (E',kō+ -'fff-'riifrrentiilll private, where E' 22kIn(1/8)) for every 8' 0. Definition 2.7 (Laplace mechanism [Dwork et al., 2006]). For f X
Let A max ((x'), where the maximum is taken over all neighboring x, e X". The Laplace mechanis is M(x) = fx) + Y, where Y is sampled from the laplace distribution Lap(Ay/E). The Laplace mechanism is (e, -)fiieerrent private.
Definition 2.8 (Exponential mechanism [McSherry and Talwar, 2007]). Let q: x be a score function defined over data domain X and output domain Y. Define A max (lq(x, y) y)l) where the maximum is taken over all y E and all neighbouring databases x E X" The exponential mechanism is the (c, ().))difffrenntalll private mecha-
eginel
nism which selects output y E Y with probability proportional Ex
Claim 2.9 (Privacy amplification by sub-sampling [Kasiviswanathan et al., 2011]). Let A
database of size Let S 1 and let (3 exp(E')). Construct an algorithm B operating the database D = (zi) Algorithm B randomly selects a subset J C (1,2)...,,f of size and executes A on Dj = (Z,)iej- Then B is
be an (E', (=',8') "-dffferenniillly private algorithm operating
(e, ) differentialy private.
2.2 Preliminaries from PAC learning
A concept class C over data domain X is a set of predicates c: X- [0, (called concepts) which label points of the domain by either or 1. A learner A for concept class C is given examples sampled i.i.d. from an unknown probability distribution D over the data domain and labeled according to an unknown target concept c E C. The learner should output hypothesis h: - [0, that approximates for the distribution D. More formally, Definition 2.10 (generalization error). The generalization error of a hypothesis h X - [0, 1] with respect to concept and distribution D is defined as error h) = Exp==-/ll((x)--eee -
Definition 2.11 (PAC learning [Valiant, 1984].. Let C be a concept class over a domain X. Algorithm A is an (a, B. n)-AC learner for C if for all C C and all distributions D on X,
Pr[(x],..., ~ DD" h ((x (x,,,((,)) error h) s 1
where the probability is over the sampling of (xi...., from D and the coin tosses of A. The parameter n is the sample complexity of A.

---

See Appendix A for additional preliminaries on PAC learning.
2.3 Preliminaties from private learning
Definition 2.12 (private PAC learning [Kasiviswanathan et al., 2011]). Algorithm A is a (a, 6, it) -t)pprivte PAC learner (i) A is an (a,p,n)-PAC, learner and (ii) A is (c,õ) differentially private.
Kasiviswanathan et al. [2011] provided a generic private learner with O(log((Xi)) labeled samples.' 7 Beimel et al. [2013a] introduced the representation dimension and showed that any concept class C can be privately learned with ((RepDim(C)) samples. For the sample complexity of (c, difffrrreett private learning of threshold functions over domain X, Bun et al. [2015, 5] gave a lower bound of Qllog" [X]). Recently, Cohen et al. [2022] gave (nearly) matching upper bound of Ó(log" [X])
3 Towards private everlasting prediction
In this work, we extend private prediction to answering any sequence prediction queries -unlimited in length. Our main goal is to present generic private everlasting predictor with low training sample complexity (S].
Definition 3.1 (everlasting prediction). Let A be an algorithm with the following properties:
1. Algorithm A receives as input n labeled examples S = [(x;,)))) E (X (0, 1))" and selects a hypothesis ho : X 1).
2. For round r e IN, algorithm A gets query, which is an unlabeled element Xntr X, outputs ( and selects hypothesis h, X - 1].
We say that A is (a, B, evverlastn predictor for a concept class C over domain X if the following holds for every concept e C and for every distribution D over X. If X2... are sampled i.i.d. from D, and the labels of the initial samples S are correct, i.e., y1 c(x;) for i E [n], then Pr Ar 2 0 s.t. errorp(c, h,) a] s B, where the probability is over the sampling of X2... from and the randomness of A.
Applying the Feldmmmn notion of a private prediction interface to everlasting predic- tors we get:
Definition 3.2. An algorithm A is an (a,8, e,, everlasssgg differentially private predic- tion interface if (i) A (e, (effe-diifrrentiillly private prediction interface M (as in Defini- tion 1.1), and (ii) A is an -.).Blst-verlllttin predictor.
As warmup, consider an (a,8,e, ô, n) everlastngg differentially private prediction interface A for concept class C over (finite) domain X (as in Definition 3.2 above). Assume that A does not vary its hypotheses, i.e. (in the language of Definition 3.1) h, = ho for all r 0. Note that computationally unlimited adversarial querying algorithm can recover the hypothesis ho by issuing all queries x E X. Hence, in using A indefinitely we lose any potential benefits to sample complexity of restricting access to hg to being black-box and getting to the point where the lower- bounds on n from private learning apply. A consequence of this simple observation that a generic private everlasting predictor should answer all prediction queries with single hypothesis it should modify its hypothesis over time as it processes new queries.
We now take this observation step further, showing that private everlasting predictor that answers prediction queries solely based on its training sample (and randomness, but not on the queries) is subject to the same sample complexity lowerbounds as private learners.
We omit the dependency e, e, 8 in this brief review.
8 Formally, A can be thought of as two mechanisms A = (Ma,M, where Mo is (c, diffferiifl private. (i) On input a labeled training sample S mechanism Mo computes a hypothesis ho. (ii) On query X mechanism Mj replies ho(x).
7

---

Consider an (a, < m evverlassn differentially private prediction interface A for concept class over (finite) domain X that upon receiving the training set S e (0, 1 selects an infinite sequence of hypotheses [K,]r20 where h, X - [0, 1j. Formally, we can think of A as composed of three mechanisms A (M, where Mo is (e,ô)- differentially private:
On input a labeled training sample S E (X x (0, 11)" mechanism Mo computes an initial state and an initial hypothesis ho) Mo(S).
On a query Nu+r mechanism M1 produces an answer (x(x)+r)= (x and mech- anism M2 updates the hypothesis-stann pair (M,=1-0r+1) M2(a,).
Note that as Mo and M2 do not receive the sequence (Aæ4rlr20 as input, the sequence (12) depends solely on S. Furthermore sequence of queries and predictions (x,,,, respect to the training set S. In Appendix B we prove:
M₁ and M2 post-process the outcome of Mo. i.e., the preserves (e, dedfffiffrrittiialll privacy with
Theorem 3.3. A can be transformed into e for C.
PAC learner
4 Private everlasting prediction definition
Theorem 3.3 requires us to seek private predictors whose prediction relies on more infor- mation than what is provided by the initial labeled sample. Possibilities include requiring the input of additional labeled or unlabeled examples during the lifetime of the predictor, while protecting the privacy of these examples.
We choose to rely on the queries for updating the predictor's internal state. This introduces potential privacy risk for these queries as sensitive information about query may be leaked in the predictions following it. Furthermore, we need take into account that privacy attacker may choose their queries adversarially and adaptively.
Definition 4.1 (private everlasting black-box prediction). An algorithm is an (a, (a,B,,,d,n) private everlasting black box predictor for a concept class C if
1. Prediction: A is an
- everllstiigg predictor for (as in Definition 3.1).
2. Privacy: For every adversary B and every / 1, the random variables View B, and View (defined in Figure 1) are (e, di..-iiidistinnuuhhblee.
Tools from prior works
We briefly describe tools from prior works that we use our construction. See Appendix for more detailed account.
Algorithm LabelBoost [Beimel et al., 2021]: Algorithm LabelBoost takes as input partially labeled database S T E (X x (0, 1, 1])" (where the first portion of the database, s, contains examples by some concept C C) and outputs similar database where both S and are (re)labeled by a concept /t E such that errorp h) is bounded. We use the following lemmata from Beimel et al. [2021]:
Lemma 5.1 (privacy of Algorithm LabelBoost). Let A be an (c.))-dfffreentialll private al- gorithm operating on labeled databases. Construct an algorithm B that on input a partially labeled database SoT E (X x (,,,, applies A on the outcome of Labe LabelBoost(SoT) Then, B (c+ 3, 4ed) (ee))differenttilly private.
Lemma 5.2 (Utility of Algorithm LabelBoost). Fix and B, and let SoT be s.f. S is labeled by some target concept c C, and s.t. [T] VVCCC) exp( a|S] - IS). Consider the execution 2VC(c) of LabelBoost on SoT, and let h denote the hypothesis chosen by Labe LBoost to relabel SoT. With probability at least (1 (1-B) B) we have that errors (h) S a.
8

---

Parameters: b (0,1), tE N.
Training Phase:
1. The adversary B chooses two sets of n labeled elements (x b..... (x y/ and
(xt.9))..... (x vit,, subject to the restriction
| [m] (x. = (x 9 E (0, 1|.
2. If s.t. px) (x) then set Flag = 1. Otherwise set Flag
3. Algorithm A gets (x "i..,,,...,, (x,, w and selects hypothesis ho X (0.1).
| the adversary B does not get to see the hypothesis ho *
Prediction phase:
4. For round r 1, I;
(a) If Flag 1 then the adversary B chooses two elements xntr x X.
Otherwise, the adversary B chooses two elements x x X.
(b) If x = x then Flag is set to 1.
(c) x = then the adversary B gets hy-1 h
\" the adversary does not get to see the label x # x/-r "I
(d) Algorithm gets x and selects hypothesis h, X - (0, 1).
\" the adversary B does not get to see the hypothesis h, "\
Let View be B's view of the execution, i.e., its own randomness and the sequence of predictions in Step 4c.
Figure 1: Definition of View B, and View
B,t"
A Generic Construction
Our generic construction Algorithm GenericBEL transforms (non-private) learner for concept class C into a private everlasting predictor for C. The theorem below follows from Theorem 6.2 and Claim 6.3 which are proved in Appendix E.
Theorem 6.1. Given a, < 1/16, < 1, Algorithm GenericBBL is a (4a, e,, n) n,)d),n)ppateee everlasting predictor, where n is set as in Algorithm GenericBBL.
Theorem 6.2 (accuracy of algorithm GenericBBL). Given a, R.B,d 1/16, E 1, for any con- cept and any round algorithm GenericBBL can predict the label of as h,(x,), such that Pr(errorp(c(x,) h,(x)) 4a] 4 Claim 6.3 (privacy of algorithm GenericBBL). GenericBBL is (E, d..f--differentialll private.
Remark 6.4. For simplicity, analyzed GenericBBL in the realizable setting, i.e., under the assumption that the training set consistent with the target class C. Our construction carries over to the agnostic setting via standard arguments (ignoring computational efficiency). We refer the reader to [Beimel et al., 2021] and [Alon et al., 2020] for generic mmmottictt--raalzall reductions in the context of private learning.
6.1 Improving the sample complexity dependency on accuracy
We briefly sketch how to improve the sample complexity of Algorithm GenericBBL from (C²(C)
é
to n = é VC*(C) ae by modifying steps 3(d)i and 3(d)ii Algorithm GenericBBL.
To simplify the description, we consider constant c, we ignore the privacy amplification by subsampling occurring in steps 2 and 3f and illustrate how the modified algorithm would execute by considering round i 1 of Algorithm GenericBBL.
Note that S where и |S, = - and A; @(VC(C)/;) is the sample complexity needed such that each of the hypotheses computed in Step 3b has error except for

---

Algorithm GenericBBL
Initial input: A labeled database
s E
(X x (0, 1])"
where 8r
atc?
64vciC1log( + 3+32
26 (og)())) (8V
log()))log)
(3 + exple 4)).
ea
8VC[C] 18 444go
1. Let T> 50. Set a1 21 Define A,
/ by Theorem A.2 A; samples suffice for PAC learning C with parameters aj a */
ro1f- Hog' 20
2. Let S₁ SSS be a random subset of size n 3+exple14)
3. Repeat for 1,,,
(a) Divide S into T; Hog sam
disjoint databases Si,1...., St,, of size A₁- (b) For t E [7;] let fi C be a hypothesis minimizing errors,, Define F;
(c) Set R
12800|5.| Set the privacy parameters e/=
and 8 2R
Instantiate
3 In(
noises f/1...., MR, ~ Lap(T/T,e))
(d) For 2= to Rj:
Receive as input a prediction query Xi, X. ii Compute yx, (F,) +, f(x,e) and let yi 9x,, (F;) + Ne
iii. Respond with the label yi 1/2 and yı 1/2.
(e) Denote D: = (x,,1...,xxR;,)
eSI (f) Let S, S.S. S; and D. S. D; be random subsets of size 3+exple+4] and dDI
3+expic14] respec-
tively, and let S/DD;= + LabelBoost($,oD.) Let S S Dÿ be a random subset of size d++1 Ti+1-
(g) Set a++1 0;/2 and Bi+1 B1/2.
probability B: Applying advanced composition, we get that é(T,²) noisy majority queries implemented in steps steps 3(d) and 3(d)iii can be performed, i.e, R1 ÔTT?). Finally, to feed the next phase with [S2] ([S] labeled samples, we need that R = θ(T A1)= é(T, VC(C)a) and hence T = Ó (C))) resulting in (C)aa))
However, when queries are made from the same underlying distribution S was selected, we expect that most of them would exhibit a clear majority in steps 3(d)ii and (d)iii, except for fraction of O(a). Hence natural way to improve on the number of majority queries that can be performed to replace steps 3(d)i and 3(d)iii with decision based the sparse vector technique of Dwork et al. [2009]. In particular, BetweenThresholde mechanism of Bun et al. [2016] to get improved R₁ = and and n @/vc²/a)
use the
hence get Ti
final important wrinkle that the above calculation is based on the queries coming from the same underlying distribution S was selected, while our worst-case privacy require- ment allows for an adversarial choice of queries that may in turn cause the execution of BetweenThresholds to halt too often and hence exhaust the privacy budget for the phase. is hence important to estimate the number of times BetweenThresholdd halts within phase and to stop the execution of Algorithm GenericBBL when the estimate crosses threshold. This estimate needs to be done in an online manner and should preserve differ- ential privacy with respect to the queries." 9 This can be done, e.g., using the private counter algorithm of Dwork et al. [2010a], which preserves differential privacy under continual observation.
For example, stopping GenericBBL after the count of halts crosses precise threshold would reveal that the last query caused Between[hreeholdss halt, and hence breach differential privacy.
10

---

References
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860. ACM, 2019. doi: 10.1 10.1155/315276.331666 URL attps://dol
11145/3311276.3316533
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 119-152. PMLR, 2020.
Raef Bassily, Abhradeep Guha Thakurta, and Om Dipakbhai Thakkar. Model-agnostic private learning. In NeurIPS, pages 7102-7112, 2018.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In ITCS, pages 97-110. ACM, 201 3a.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In APPROX-RANDOM, pages 363-378, 2013b.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples. Algorithmica, 83(1):177-2155 2022.
2021.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, and Kunal Talwar, When is memorization of irrelevant training data necessary for high-accuracy learning? In STOC, pages 123-132. ACM, 2021.
Mark Bun and Mark Zhandry. Order-revealing encryption and the hardness of private learning. In TCC (A7), volume 9562 of Lecture Notes in Computer Science, pages 176-206. Springer, 2016.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learming of threshold functions. In FOCS, pages 634-649, 2015.
Mark Bun, Thomas Steinke, and Jonathan Ullman. Make up your mind: The price of online queries in differential privacy. CoRR, 0tes/1604.0455 8, 2016. URL http: // /rrxiv org/ abs/1604. 04618.
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. CoRR, abs/2211.000 2211.06387, 2022. doi: (044550//rXxi.2211..066 06387.
221222211111 URL https://doi. org/10. aat.////...5///........ 2211.
Yuval Dagan and Vitaly Feldman. PAC learning with stable and private predictions. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 1389-1410. PMLR, 2020.
Cynthia Dwork and Vitaly Feldman. Privacy- preaeeciip prediction. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018 volume 75 of Proceedings of Machine Learning Research, pages 1693-1702. PMLR, 2018. URL http: attp://proceedings. mlr hir..press/v5// dwork18a. html.
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. Differential privacy under continual observation. In Symposium on Theory of Computing (STOC), pages 715- 724. ACM, 2010a.
11

---

Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51 51-60, 2010b.
Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM Comput., 44(6):140-1164, 2015. doi: 10.1137/140991844 URL http://dx.doi.orr//on
doi. 1ttp..org/....11..1/ 1117/110..197/14999914444
Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In COLT, volume 125 of Proceedings of Machine Learning Research, pages 2263-2285. PMLR, 2020.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM J. Comput., 40(3):793-826, 2011.
Michael J. Kearns, Mallesh M. Pai, Ryan M. Rogers, Aaron Roth, and Jonathan R. Ullman. Robust mediators in large games. CoRR, abs/ (bbs/5122 102021691,,,, 2015.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94-103. IEEE, Oct 20-23 2007.
Anupama Nandi and Raef Bassily. Privately answering classification queries in the agnostic PAC model. In ALT, volume 117 of Proceedings of Machine Learning Research, pages 687-703. PMLR, 2020.
L. G. Valiant. A theory of the learnable. Commun. ACM, 27(111:1133-1114, November 1984. ISSN 0001-0782. doi: 10.1145/1968.199 URL http://doi. org/10. 1145/1968. 1972.
Vladimir N. Vapnik and Alexey Y. Chervonenkis. On the uniform convergence of relative frequencies events to their probabilities. Theory of Probability and Applications, 16 (2):264-280, 1971.
12

---

A Additional Preliminaries from PAC Learning
It is well know that that sample of size @(VC(C)) is necessary and sufficient for the PAC learning of concept class C, where the Vapnik-Chervonenkke (VC) dimension of a class C defined follows:
Definition A.1 (VC-Dimension |Vapnik and Chervonenkis, 1971]). Let C be concept class over a domain X. For set = [b]...., by] S of points, let let ( ((c(b)). (...,,.(bb))) c C) be the set of all dichotomies that are realized by C on B. We say that the set B X is shattered by C if C realizes all possible dichotomies over B, in which case have [I[[(B]] 2|
The VC dimension of the class C, denoted VC(C), the cardinality of the largest B shattered by C.
Theorem A.2 (VC bound). Let be a concept class over a domain X. For a, < </2, there exists an (a, B, n) PAC learner for C, where n= SVC(C]log( 13 J+ 1+4
B Proof of Theorem 3.3
The proof of Theorem 3.3 follows from algorithms Hypothesisseaarner, AccuracyBoost and claims B.1, B.2, all described below.
In Algorithm fyyothesisLearme prediction interface A was fed with и wi.. samples taken from some (unknown) distribution D and labeled by an unknown concept e C. Assumning the sequence of hypotheses (2,) produced by A satisfies
we assume that the everlasting differentially private
Vr hr,
(1)
use it to construct with constant probability hypothesis h with error bounded by O(a).
Algorithm HypothesisLearner
Parameters: 0<B B 1/8, R log(()) log((X)))og(((/)))) log(1/8) Input: hypothesis sequence [hy]r20
1. for all x X let L, 0
2. for r 0, 0,
0,,,2,..,, (a) select x uniformly at random from X and let L, U (h,
3. if Lg 0 for some x E then fail, output an arbitrary hypothesis, and halt
/* Pr[Ax such that L, = 0) s [X[(1
IX R [Xle R/|xi BB
4. for all x let r be sampled uniformly at random from Lx
5. construct the hypothesis h, where h((x) =x
Claim B.1. If executed hypothesis sequence satisfying Equation then with probability at least 3/4 Algorithm HypothesisLearner outputs a hypothesis satisfying errorp(c,h) S 8a.
Proof. Having D,c C fixed, and given hypothesis h, we define en(x) to be if h(x) c(x)
and otherwise. Thus, we can write errorp(c,h) = =x
Observe that when Algorithm HypothesissLearner does not fail, rx (and hence h(x)) is cho- sen with equal probability among (h, (x)) and hence [x]e = Eien[R| (x)]
where & denotes the randomness of HypothesisLLarner. We get:
Fglerrorp(c,h)) = Fg (
Ex-DEiex(R[ (x)) Ei [x-Dlen
Em-R/a==a =a
By Markov inequality, we have Prelerrorple ht) > 8a] < 1/8. The claim follows noting that Algorithm HypothesisLearner fails with probability at most 1/8.
D
13

---

The second part of the transformation is Algorithm AccuracyBoost that applies Algorithm Hypotheeisseearer O(log(1/B) times obtain with high probability hypothesis with ((a) error.
Algorithm AccuracyBoost
Parameters: B, 1041n
Input: R labeled samples with examples each (Sp....,,g) where S; E (X x (0,
1. for i = 1,2...R
(a) execute A(S,) to obtain hypothesis sequence (1/)
(b) execute Algorithm keadHHypochhesisleeareer on (22) to obtain hypothesis
H'
2. construct the hypothesis h, where h(x) = maj(h (x).,,,))))
Claim B.2. With probability 1 1 B, Algorithm AccuracyBoost output 24a-good hypothesis over distribution D.
Proof. Define B; to be the event where the sequence of hypotheses (h/)r20 produced in Step la of AccuracyBoost does not satisfy Equation 1. We have,
Pr(errorp(c.h)) > 8a] Pr[B] + (1 Pr(B)) Pr(errorp(c,h)) 8a] S β 1/4 3/8.
Hence, by the Chernoff bound, when R 104In J we have at least 7R/8 hypotheses are 8a-good over distribution D. Consider the worst case, in which R/8 hypotheses always output wrong labels. To output a wrong label of x, we require at least 3R/8 hypotheses to output wrong labels. Thus h is 24a-good over distribution D.
C Tools from Prior Works
C.1 Algorithm LabelBooat [Beimel al., 2021|
Algorithm LabelBoost [Beimel et al., 2021]
Parameters:
A concept class C.
Input:
A partially labeled database SoT e (X 10)
% We assume that the first portion of the database (denoted S) contains labeled examples. The algorithm outputs a similar database where both and T are (re)labeled.
1. Initialize H = 0.
2. Let P= -p........ pel be the set of all points E X appearing at least once SoT. Let [T((P) ((cpp))).......c(()))) c C) be the set of all dichotomies generated by C on P.
3. For every 2g) E CP()), add to H an arbitrary concept e C.t. c(p;) = for every S iiit 5.
4. Choose h H using the exponential mechanism with privacy parameter c=1, solution set H, and the database S.
5. (Re)label SoT using h, and denote the resulting database (SoTy", that is, if SoT = (x), then (SoT)* (x,, 1/) where y/ h(x,).
6. Output hh
Lemma C.1 (privacy of Algorithm LabelBoost [Beimel et al., 2021]). |). Let A be an 0)- differentially private algorithm operating partially labeled databases. Construct an algorithm that on input partially labeled database SoT (X x [0, 1,1) applies A on the outcome of LabelBook (obe Then, B is (e 3, 4ed) diffeereinelllilllll private.
14

---

Consider an execution of LabelBoost on database SoT, and assume that the examples in are labeled by some target concept c C. Recall that for every possible labeling of the elements in S and in T, algorithm LabelBoost adds to H hypothesis from C that agrees with Z. In particular, H contains hypothesis that agrees with the target concept e on (and on T). That is, 3f e H s.t. e 0. Hence, the exponential mechanism (on Step 4) chooses (w.h.p.) ) a hypothesis E H s.t. errors(h) is small, provided that [S] roughly log HH), which is roughly VC(C) log([S] + +[Tl) by Sauer's lemma. So, algorithm LabelBoose takes input database where only a small portion of is labeled, and returns a similar database in which the labeled portion grows exponentially.
Lemma C.2 (utility of Algorithm LabelBoost [Beimel et al., 2021]). Fix and B, and let SoT be s.t. S is labeled by some target concept c E C, and s.t.
ITI L eC(C)exp( a 2VC(C) )-I).
Consider the execution of LabelBoost SoT, and let h denote the hypothesis chosen Step 4. With probability at least (1 -B) we have that errors(h) s a.
D Some Technical Facts
We refer to the execution of steps 3a-3g of algorithm GenericBEL. phase of the algorithm, indexed by i = 1,2,3,....
In GenericBBL, require that the set of all predictions in the phase i is (1, (lifeediife private.
Claim D.1. For ò the composited Laplace mechanism used in step in the i-th iteration, is (1, (1.0)-differenntiall private.
Proof. Let 0f be in Step 3c. Since - 22 for 0 < < we have
v2 2 11.
e Ree/(efi 1) 1)5 2R, ) 2R 3
|2R In( R
9ln(3)
The proof is concluded by using advanced composition (Theorem 2.6).
In step 3f, GenericBBL takes random subset of size Ait1 Trt1 from DjD We show that the size of D is at least A T++1-
Claim D.2. When $ for any i 1, we always have | 2 Ait1 Ti+1-
Proof. Let 3+exp(e+4) < 200. By the step 3c, step 3e and step 3f, |D,1 <ID,1 1280015,1 64|s;| = =41,T Then sufficient to verify 1281,77 Tj Aj+1
n
We can verify that
8VC(C)log( 13) llog(
8VC(C)log( 13
1) 4(log(
2 3 1)
ai-1
Pi+)
41 42,=4 4.
4.
2 Aj+1
aj
24
and
16r A log( } log²( caspo
4t Ait1 log( ( log2( (Tea
Au1
16T,
>
2 Tj+1-
The last inequalitu holds because Aj 4 and a Bj < 1/2.
To apply the privacy and accuracy of Labet the sizes of the databases need to satisfy the inequalities in lemma C.2. We verify that each phase, the sizes the databases always satisfy the requirement.
15

---

Claim D.3. When s 1, for any 2 1, we have [D - \C(C)
a;15,l 2VCIC]
) 15
Proof. By claim D.2, step 3c and step 3f,
|D <DD:l m
(1, o VC(C)log"(VCIC)) -poly
_
1 1 log (
poly _ log(
Bi
and
|S = e|Sil
MI
= =
(2)
= =o (Ccc)llog3VVCCCC) poly - log(
1
log 2
a; B;
Note that
B: VC(CCeep 2VC(C) - = (C=((c)- for T, z.dp
agSa
exp exp (plyy - a;
log( Bi logl 1
(1))
bog" Tagppo
the inequality holds when t 50.
E Accuracy of Algorithm GenericBBL. proof of Theorem 6.2
We refer to the execution of steps 3a-3g of a algorithm GenericBBL. as a phase of the algorithm, indexed by = 1,,.3.....
We give some technical facts in Appendix D. In Claim E.1, we show that in each phase, samples are labeled with high accuracy. In Claim E.3, we prove that algorithm Generi cBBL fails with low probability. Claim E.4, we prove that algorithm GenericBBL predict the labels with high accuracy.
Claim E.1. For each phase we have
Pr 3g E C s.t. errors, (g) = and errorp(gi, c) S
aj 1
Bj. 1=0
1=1
The base case for i is trivial, with gi c. As- sume the claim holds for all S i. By the properties of LabelBoost (Lemma C.2) and Claim D.3, with probability at least 1 1- ß, have that is labeled by hypothesis & E C s.t. errors, (g--.g)) S a; Observe that the points in S; (without their labels) are chosen i.i.d. from D, and hence, By Theorem A.2 (VC bounds) and |S,-1l 2 128A;-1 2 A,, with probability at least B; have that errorp(g:-gi-))) a;- Hence, with probability 1 28, have crrorp(g:-::1)) S a, Finally, by the triangle inequality, errorp(g, E az except with probability 2
Proof. The proof is by induction
Combining claims E.1 union bound, we get:
Claim E.2. Let D be an underlying distribution and let e C be target concept. Then
Pr[Vi Ag s.t. errors, (g:) and errorplg,. s a 1-2..
For each phase i, if there exists noise ') 1/16 in step 3c, say the phase fails. Define the following good event.
Event Ey: Phase doesn't fail for all i 1.
16

---

Claim E.3. When 12 1, x 1 & 1/2, 6 & 1/2, event E occurs with probability at least 1-B.
Proof. In each phase i, For each Tij, by the property of Laplace distribution, we have
Pr[ly] 2 1/16]= T7//16 48 1n, s B,/R; This inequality holds when T 2 1. By union bound, we have Pr[phase fails] Bj.
Using to union bound,
Pr[Event Ej occurs) 1 --B.
Notations. Consider the ith phase of Algorithm GenericBBL, and focus on the j-th it- eration of Step Fix all of the randomness noises. Now observe that the output on step 3(djii is deterministic function of the input xt,). This defines hypothesis which we denote hi.j-
%
St1
f
Iu, (F)
Adding Laplace noise
Label
S.n
fr.
b (fix the randomneas)
Figure 2: Hypothesis hij
Claim E.4. For B < 1/16, with probability at least 1 - 4β, all of the hypotheses defined above are 4a ta-good w.r.t. and
Proof. In the phase i, by Claim F.2, with probability at least 1 2B we have that S; is labeled by hypothesis gi E C satisfying errorp(g;, S a. We continue with the analysis assuming that this is the case.
On step 3a of the ith phase we divide S; into T; subsamples of size A each, identify consistent hypothesis f, E C for every subsample Si,, and denote F; = (fi..., fr). By Theorem A.2 (VC bounds), every hypothesis in F, satisfies errorplf.. gi) $ a with probability 1- B;, in which case, by the triangle inequality we have that errorp(fi.c) 2a.
512(1-48,1n(+
(1-640,² using Chernoff bound, it holds that for at least 15T;/16 of the hypotheses F; have error errorp(fi.c) s 2a with probability at least Bi-
Set T 2
By Claim E.3, with probability 1 1- all Laplace noises added in step 3d is less than To. Let X (0, defined as m(x) maj (f(xx)). For to
point (w.r.t. the target
concept c), it must be that at least 3/8-fraction of the 2a 2a-good hypotheses in F err Consider the worst case Figure 3, based on Claim E.3, we have errorp(m,c) s 4a with probability 1 1-B.
17

---

High hypotheses: 1/16
Laplace nolses: 1/16
Error of PAC
learned hypotheses: 3/8
Error PAC
learned hypotheses: 3/8
Error PAC learned hypotheses: 2/8
20
20;
Figure 3: The horizontal represents the input point. The vertical represents the hypothesis. The red parts represent the incorrect prediction. We let to hypothesis predict all labels Ti To output an incorrect label, there must exist z hypothesis output the incorrect label. In the worst case, most 4a of points are incorrectly classified.
incorrectly and let Laplace noises to be as large as T6' 37,
Conclude all above, with probability 1-4 all the hypotheses are 4a 4a-good.
E.1 Privacy analysis proof of Claim 6.3
Fix f E and the adversary B. We need to show that View B.t and View (defined in Figure 1) are (c, - indistinguishuble. We will consider separately the case where the executions differ in the training phase (Claim E.5) and the case where the difference occurs during the prediction phase (Claim E.6).
Privacy of the initial training set S. Let S e (Xx 10) be neighboring datasets of labeled examples and let View E, and View be in Figure where ((x (...,l)...., (x), (22r 5 and ((x) (x)..., =
Claim E.5. For all adversaries for all 1> 0, and for any two neighbouring database S and S selected by B, View B, and Viewl,, are (..0)iindistinguishbblel
Proof. Let Rj (1) Note that View labels Algorithm GenericBEl produces in Step 3(d)iii for the R₁ first unlabeled points selected by B. Let s be the result of the first application of algorithm LabelBoost Step 3f of GenericBBL (if < R₁ we set S as 1). The creation of these random variables is depicted in Figure 4, where Df denotes the labels Algorithm GenericBBL produces for the unlabeled points D..
8.R; is prefix of View B.r which includes the
Observe that View B, results from post-processing (jointly by the adversary and Algo-
rithm GenericBBL) of the random variable (View B. $ and hence it suffices show that B.R 56) and (View s.R st are (e, d) iniistiugiitt.....bblle..
(View
We follow the processes creating View B, and 2 in Figure 4: (i) The mechanism Mj cor- responds to the loop in Step 3d of GenericBBL where labels are produced for the adver-
18

---

M
S
S
S
S2
D
M
M
D
Figure 4: Privacy of the labeled sample S
sarially chosen points DJ. By application of claim D.1, M1 is diffeerrite private. (ii) The mechanism M2, corresponds to the subsampling of Š from S and the applica- tion of procedure LabelBoost the subsample in Step 3f of GenericBBL resulting in sh. By application of Claim 2.9 and Lemma C.1, M2 is (e, O)ddiffeerret private. Thus (M,, is (e diffeerrfrry private. (iii) The mechanism M3 with input of s and output (D .h)) (View B.R; B.R; applies (2) on the sub-sample sy obtained from
5h in Step of GenericBBL, By application of Claim 2.9 M3 is (e, 3-exple+T) ( differentially private. Since 3+exp(c+1] indistinguishable
4ed
4:8
S ò for any hence (View B.Rg S9 and (View' s2 are (c,
Privacy of the unlabeled points D. Let D", e x neighboring datasets of unla- beled examples and let View B,t and Viewl, be in Figure 1 where (x!......?) D and
x+......!!==D!!!
Claim E.6. For all adversaries B, for all > O, and for any two neighbouring databases D and D. selected by B, View and View', are (E, (e.0)-indistinguisaabb.
M
S,
3,
S
SELE
SH22
D
M
D
D
D
D
D
M,
Figure 5: Privacy leakage of D;
Proof. Let DI..D...., and DJ, D!...,,, D/ be the set of unlabeled databases in step 3e of GenericBBL. Without loss of generality, assume DQ and DJ differ one entry. When
19

---

i = k, View
8, View because all selected hypothesis are the same. When i < k, let
R' = min 1+1 [
B, results from a post post-processing of the ran- Similar to the analysis if Claim E.5, View
dom variable (View S/22) (if 1 Rj we set S as 1). Note that View B.R, (DPL D.. D and (D follow the same distribution for e (0, 1}, where D is the labels of points in DJ expect the different point. So that it suffices to show that (D%4.s9) and (D [+111 5 are (c, didisiiuiiss.n.ushbbbll....
We follow the processes creating D and s in Figure 5: (i) The mechanism M1 corre- sponds the loop in Step 3d of GenericBBL where labels are produced for the adversarially chosen points 1 By application of claim D.I, M1 is (1, differiitty private. (ii) The mechanism M2, corresponds to the subsampling of 5 from S%., and the applica- tion of procedure LabelBoost on the subsample Step
GenericBBL resulting in $/ By application of Claim 2.9 and Lemma C.1, M2 (e, (e.00-diiferentialll private. Thus (2) is (E + 1, output (DAL
( differentialll private. (iii) The mechanism M3 with input of DJ and (1i sb applies (M), on Si-1, which is generated from Df and in Step 3f of GenericEBL. By application of Claim C.1, M3 (e + 4, diffeeerrryy private. (iv) The mechanism M4, corresponds to the subsampling D from DØ' and the application of M4 on D.. By application of Claim 2.9, M4 is (E, 3+exp(e+4) 3 diffeerttiil private. Since 1666
16eeà
S 1 for any E, (D $9) and (D!,). are (e, (:.0)iindisiinguushabbl
3+expie44
Remark E.7. The above proofs work on the adversarially selected D because: (i) Lemma works on the adaptively selected queries. (We treat the hypothesis class F; as the database, the unlabelled points xig as the query parameters.) (ii) LabelBoost generates labels by applying one private hypothesis on points. The labels are differentially private by post-pri pott-prccessing.
20


Reviews:
[{"review_id": "zIZuZicuGv", "reviewer": "Reviewer_9JKU", "summary": "This work studies differentially private prediction. It has two major contributions: \n\na) Prediction corresponds to being given an initial labeled training set, and then subsequently making predictions on other data points based on it. This paper shows that differentially private prediction can be performed on an unbounded number of queries, with strong accuracy guarantees, with the initial training set sample complexity scaling only as a polynomial in the VC dimension of the hypothesis class. Prior work either studied prediction for a small number of queries or studied the more stringent task of private PAC learning where significantly stronger lower bounds are known (PAC learning asks for the release of an entire model as opposed to predictions alone).  \n\nb) Since queries correspond to data points, they are usually sensitive user information. The authors formalize a model of privacy (similar to joint differential privacy) that gives a meaningful notion of privacy for these data points, even when adversaries can choose the queries adaptively. Their algorithms satisfy this notion of privacy.\n", "questions": "1) The reasoning for the use of LabelBoost didnt entirely make sense to me- the stated reason was that the predictions provided during a round are not consistent with any concept in the hypothesis class. However, it’s not immediately clear to me that this is a problem- for example, using agnostic (non-private) learning algorithms may get around this issue (at the expense of worse sample complexity dependence on the accuracy parameter). More explanation of this would be useful.\n\n2) The comment about their model of prediction, in principle, allowing memorization was interesting. It’s not clear that this is true- it seems like memorizing something in the training set would affect future predictions which would affect the adversary’s views. Would love more clarification on this.\n\n3) Is there a simple (eps, 0)- version of this algorithm? It’s not clear to me that approx DP is necessary (sparse vector by itself is pure DP, though a variant is used in this paper).\n\n4) The diagrams in the privacy proofs are a little too convoluted to be useful to the reader. I don’t have great suggestions on how to simplify them, but the privacy proofs by themselves are relatively simple, and I’m not sure the diagrams make them simpler to understand.\n\n5) Some minor comments:\n\na) In Algorithm LabelBoost step 4, ‘choose’ based on exponential mechanism is not well defined since the score function is not specified (it can be inferred from context that it’s the negative of empirical risk) but specifying would be good.\n\nb) In Claim E.4 don’t you need to account for the fact that the function labeling the sample is not the real function, but rather the one chosen by LabelBoost? Specifically, Claim E.3 is about a function with 0 sample error, whereas LabelBoost will incur some error, and hence I think you want a version of claim E.3 where sample error is bounded by alpha.\n\nc) On page 8, where it says ‘using standard privacy amplification arguments, BetweenThresholds can be modified to allow for c times of outputting bot before halting)’, I think you mean privacy composition.", "limitations": "Limitations adequately addressed.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This paper makes a valuable and somewhat surprising discovery by proving that differentially private prediction can be performed on an unbounded number of queries, with no training set sample complexity dependence on the number of queries! They leverage standard techniques such as sparse vector in clever ways to do so. They operate in rounds, and use queries themselves as data points for future rounds, calling upon techniques from the semi-supervised differentially private learning literature . Their results suggest new ways to get around lower bounds for differential privacy.\n\nTheir algorithms involve reducing private prediction to non-private PAC learning, and while their techniques are not yet practical in many cases (because of time complexity), their reduction can be readily extended to any non-private learning algorithm, and hence there is lots of potential for future work to come up with ways to make their techniques more practical.\n", "weaknesses": "One (minor) drawback is that the notion of privacy defined for the adaptively chosen queries is (necessarily) not as strong as would be nice since the label for a data point needs to depend on the data point to achieve any reasonable notion of accuracy (since otherwise you can only do something like randomized response). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. Below we address the points you make:\n\n**> the notion of privacy defined... is not as strong as would be nice since the label for a data point needs to depend on the data point**\n\nWe don’t see the fact that the adversary does not get to see the label of one point (where the inputs differ) as a serious weakness - this is a necessity due to the characteristics of the problem, and it makes sense in may applications of private prediction (e.g., when prediction is used to support a decision whether to give a patient a certain treatment, it is OK for the patient to learn the result of applying the prediction to their own medical information; what is important is that privacy of other patients needs to be preserved). Note that the adversary we consider is nevertheless very powerful. In particular, after the single point where it does not see the label it can still adaptively choose an unbounded number of points and learn their labels.\n\n**> The reasoning for the use of LabelBoost didnt entirely make sense to me**\n\nIn our construction we need to ensure that the sum of $\\alpha_i$ converges, so that the overall error is under control. LabelBoost helps here because its utility guarantees are better than what we can guarantee during \"runtime\", i.e., when responding to the queries online. We do not know if LabelBoost is necessary for this, but so far we could not get the error to converge without it.\n\n**> The comment about their model of prediction, in principle, allowing memorization was interesting. It's not clear that this is true- it seems like memorizing something in the training set would affect future predictions which would affect the adversary's views** \n\nMemorization need not be of just the initial training set but also of the query points posed to the predictor. What we meant to say is that our construction yields private predictions regardless of how the internal non-private learners operate, and even in case they memorize points of the training set or points presented as queries.\n\nA possible example for this would be the class $C^{enc}_{thresh}$ (described in Item 1 in the same section). Bun and Zhandry [2016] showed that privately learning this class is computationally hard, whereas non-private learning is easy. This difference actually follows from the private learner's inability to memorize data points from the training set. As we mentioned in Item 1, our construction yields an efficient learner for this class (in our privacy model). The resulting learner would not leak to the adversary information about data points, but it would still memorize some of them internally. We will include this observation in the final version.\n\n**> Is there a simple (eps, 0)- version of this algorithm?**\nWe don't know whether pure-DP everlasting predictors exist. Our analysis strongly relies on the advanced composition theorem, and hence yields approximate-DP.\n\n**> The diagrams in the privacy proofs are a little too convoluted to be useful to the reader** \nThank you for the comment. We will consider whether to keep the diagrams (or simplify them).\n\n**> In Algorithm LabelBoost step 4, 'choose' based on exponential mechanism is not well defined (it can be inferred from context)**\n\nRight. We will state this explicitly.\n\n**> In Claim E.4 don't you need to account for the fact that the function labeling the sample is not the real function, but rather the one chosen by LabelBoost?**\n\nYes, the samples are labeled by the concept chosen by LabelBoost. We argue that this concept has low error compared with the original concept in claim E.3\n\n**> On page 8... I think you mean privacy composition**\n\nYes, we use advanced composition because BetweenThreshold will halt within c times with high probability.\n"}, {"review_id": "f1J4FF5lI3", "reviewer": "Reviewer_xv4Q", "summary": "This paper provides an intriguing path to evading known lower bounds for differentially private PAC learning. Whereas nonprivately the sample complexity of learning is proportional to the VC dimension, the private sample complexity for (pure) DP is characterized by the representation dimension, which can be much larger. In particular, some natural classes such as threshold functions over an infinite domain (e.g. Z or R) have finite VC dimension but infinite representation dimension, so they can be learned nonprivately but not privately (even with approximate DP, by a separate result).\n\nThis paper shows that this impossibility only holds for privately releasing a hypothesis and not for privately classifying samples. In particular, it shows that in the online prediction setting, for any hypothesis class there is a generic stateful algorithm with sample complexity based on the VC dimension (to be precise, quadratic in the VC dimension) that can privately answer an unbounded sequence of iid queries with the same accuracy guarantee as PAC learning, but where the state of the algorithm remains hidden and only the query labels are revealed. The algorithm is allowed to remember previous queries but must be differentially private with respect to them as well as the points of the original (labeled) training set. It also shows that statefulness is necessary to achieve this result.\n\nFor general hypothesis classes the algorithm is inefficient, but it can be made efficient on important special cases, including threshold functions. ", "questions": "1) Is it strictly necessary for accuracy that the query points are iid? Or could we hope for the following stronger statement: \n\nGiven query points x_1, x_2, ... and a subset of indices I (not known to the algorithm) such that x_i is sampled from the distribution for i\\in I but is chosen by the adversary for i\\notin I, we require accuracy only for the points in I. \n\nThat is, as long as the challenge queries are sampled from the distribution, we want to be robust to data poisoning using the other queries. Does this seem like it could be possible, or is it too strong?\n\n2) Minor clarification: In the technical overview on page 3-4 it sounds like the parameters discussed are based on the standard composition bound, without using BetweenThresholds. It might be helpful to clarify whether this is the case and if we get a similar or only slightly weaker result without using BetweenThreshold, or if we truly need the tighter privacy analysis of BetweenThreshold. ", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very interesting result that enhances our understanding of differentially private learning by bypassing known lower bounds. It essentially gives a separation between interactive and non-interactive private prediction, showing that interactivity reduces the private sample complexity to nearly that of nonprivate learning (as long as we only have to output predictions and not a hypothesis). The paper is quite well-written.", "weaknesses": "There are two obvious limitations of the main result, that yield very interesting open problems posed in the paper: whether it's possible to come up with a similar algorithm that is computationally efficient for all hypothesis classes, and whether it's possible to improve the sample complexity from VC^2 to VC.\n\nMinor corrections:\n104: points --> point\n147: \"upto\" should be \"up to\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. Below we address the points you make:\n\n**> There are two obvious limitations of the main result that yield very interesting open problems… computational efficiency and sample complexity**\n\nWe believe that - even with these questions unresolved - the concept of everlasting prediction is of interest to the private learning community, in particular because it gets around impossibility results. We hope that follow up work will resolve the open questions we present in the paper.\n\n**> Is it strictly necessary for accuracy that the query points are iid? ... Does this seem like it could be possible, or is it too strong?**\n\nWe believe that a construction similar to ours should work in a setting where not too many of the challenge queries are chosen adversarially, provided that the given non-private learners can withstand a poisoning attack with related parameters. We view this research direction (and in particular the stronger formulation you suggested) as an interesting direction for future work.\n\n**> Minor clarification ... can we get a similar or only slightly weaker result without using BetweenThreshold**\n\nWe can get a similar (but weaker) result even without BetweenThresholds. Specifically, this will yield an algorithm in which the initial labeled sample S has a worse dependency on the accuracy parameter alpha.\n"}, {"review_id": "5CJbfKTJGo", "reviewer": "Reviewer_nCbQ", "summary": "The paper discusses private everlasting prediction, which extends private prediction to answer an unlimited sequence of prediction queries. The goal is to present a generic private everlasting predictor with low training sample complexity. The paper introduces definitions for everlasting prediction and everlasting differentially private prediction interfaces. It then presents a generic construction called GenericBBL for private everlasting prediction.", "questions": "What is the application scenario of the everlasting prediction?", "limitations": "It lacks experimental analysis of the proposed algorithm, which makes it hard to justify the utility of the proposed algorithm.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper introduces a formal framework for everlasting prediction.\n2. This paper provided a comprehensive privacy analysis to the proposed privacy-preserving everlasting prediction task.", "weaknesses": "1. Limited applicability: The paper focuses on the theoretical aspects of private everlasting prediction and does not provide concrete practical applications or empirical evaluations. It remains to be seen how well the proposed approach translates into real-world scenarios.\n2. Lack of comparative experimental analysis: The excerpt does not mention any comparison or benchmarking against existing methods or alternative approaches. Without such comparisons, it is difficult to assess the novelty or superiority of the proposed method.\n3. Lack of empirical validation: The excerpt does not mention any empirical experiments, simulations, or case studies to validate the effectiveness or robustness of the proposed private everlasting predictor. It is unclear how the proposed construction performs in terms of privacy preservation, utility, and sample complexity compared to other techniques.\n4. The contents shown in the supplementary materials contain a lot of redundant information compared with the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. Below we address the points you make:\n\n**> Limited applicability: The paper focuses on the theoretical aspects of private everlasting prediction and does not provide concrete practical applications or empirical evaluations**\n\nWe agree that the construction of efficient practical algorithms that can be used in concrete practical applications is important. Establishing a sound theory of private learning and improving the asymptotic behavior of private learning algorithms is no less important. In fact many if not most of the practical applications of differential privacy would not have existed hadn't they began as concepts which were introduced in theoretical results, even if initial constructions were impractical.\n\n**> Lack of comparative experimental analysis**\n\nWe present a novel concept (everlasting prediction) as an alternative to private learning. We also present a construction demonstrating that everlasting prediction is possible in tasks where private learning was proved to be impossible. For example, the sample complexity for private learning of threshold functions grows with the domain size. In contrast, as we mention in the paper, threshold functions can be predicted efficiently, regardless of the domain size.\n\n**> Lack of empirical validation... makes it hard to justify the utility of the proposed algorithm**\n\nAt this phase of this research, an experimental analysis and an empirical validation would not yield meaningful conclusions beyond deeming the current algorithms \"impractical\". Rather, a mathematical asymptotic analysis is the right tool for analyzing our results. We believe that our work would lead to future studies on this topic, both theoretically and practically oriented.\n\n**> The contents shown in the supplementary materials contain a lot of redundant information compared with the paper**\n\nThe supplementary materials contain all the formal details which were omitted from the main paper. We are open to reorganizing the paper (within the page limit).\n\n**> What is the application scenario of the everlasting prediction?**\n\nEssentially, private everlasting predictors can be used in many scenarios where we would like to use the outcome of private learning algorithms for prediction, e.g.,\n\n1. A hospital might use a private everlasting predictor in supporting decisions whether patients need to be treated for COVID19, based on their tests and medical history. The process would bootstrap with an initial sample of patients that would be labeled by experts and continue with private prediction. Due to the very sensitive nature of the data (as well as legal and ethical considerations) it is important to protect the information of both the initial sample and of patients to whom prediction is applied.\n\n2. Similarly, a bank might use a private everlasting prediction as part of its decision process whether to offer loans to customers.\n"}, {"review_id": "SBxncvPPHY", "reviewer": "Reviewer_NTTD", "summary": "This work proposes the notion of private everlasting prediction. Given a training dataset, the predictor responds to a sequence of queries and privacy has to be preserved for both the training data and all queries. The authors explore the PAC learnability problem under this model and show that the sample complexity scales quadratically with the VC dimension through a generic construction from non-private learners. ", "questions": "In practice, some large models are pretrained on public data which can be considered non-private. Theoretically, is it relevant to consider the case when the training set $S$ is non-private and the stream of queries is private? How would the sample complexity change?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The authors formulate a new notion of private everlasting prediction. This is an original theoretical concept which extends the single query prediction model and has practical relevance.\n2. The authors prove several interesting theoretical properties for private everlasting prediction. First it requires that the hypothesis needs to change over time. Second, the authors show that the sample complexity scales quadratically with the VC dimension of the concept class. This is a significant improvement compared to private learning which is impossible over infinite domains.\n3. The writing is clear and easy to follow.\n\nUpdate: increased my score to seven after seeing the authors' response and other reviewer comments.", "weaknesses": "1. In the algorithm GenericBBL, $\\tau>1.1\\times 10^10$ seems too large. Can the constant be made any smaller?\n2. The algorithm is not computationally efficient.\n3. In terms of writing, the authors could provide a brief overview of the proof ideas for Theorem 5.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. Below we address the points you make:\n\n**> In the algorithm GenericBBL,  $\\tau>1.1\\times 10^{10}$, seems too large. Can the constant be made any smaller?**\n\nWe have not optimized constants as our contribution focuses on asymptotic complexity. The  paper introduces a new concept - private everlasting prediction - and demonstrates an unbounded asymptotic improvement over private learning. While the construction may be impractical at this stage, we believe that it provides a significant theoretical improvement that would be followed by more theoretical and practical research towards making everlasting predictors usable in a variety of practical applications. \n\n**> The algorithm is not computationally efficient**\n\n Although our algorithm is not computationally efficient it does yield in some cases polynomial time constructions. We clearly state the question of making the construction efficient as an open problem. We expect that future work would resolve the question whether an efficient generic construction exists.\n\n**> In terms of writing, the authors could provide a brief overview of the proof ideas for Theorem 5.1.**\n\nWe will include an overview of the proof. Very briefly - the high-level idea is to use LabelBoost to label the unlabeled dataset and use BetweenThreshold to predict labels. The privacy and accuracy guarantees come from these two algorithms.\n\n**> In practice, some large models are pretrained on public data which can be considered non-private. Theoretically, is it relevant to consider the case when the training set S is non-private and the stream of queries is private? How would the sample complexity change?**\n\nVariations of this question were studied in the standard private learning model (where the learner releases a model), e.g., by [1,2]. We believe that this could also be relevant in our context, but this would require adjustment to the learning scenario to be meaningful. More specifically, in our context, if pre-training can be performed on O(VC) non-private labeled examples, then that would nullify the need for private learning/prediction, as we could simply release the resulting non-private model. \n\nWe believe that this would make sense in other learning scenarios where you would like to use the private queries in order to improve the error of the non-private model you obtained from the initial (non-private) training set. Our privacy definition could potentially fit such scenarios.\n\n[1] Beimel, Nissim, Stemmer. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy. RANDOM 2013.\\\n[2] Bassily, Moran, Alon. Limits of Private Learning with Access to Public Data. NeurIPS 2019\n"}]

Author rebuttal:

Meta-review: The paper got a very strong set of reviews. The reviewers, and I will recommend the authors to update the presentation in light of the discussions.
Decision: Accept (oral)