{'fraction_non_alphanumeric': 0.05515075108442488, 'fraction_numerical': 0.020812410521592342, 'mean_word_length': 3.82225656877898, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Transfer Learning In Differential Privacy's Hybrid-Model

The hybrid-model (Avent et al 2017) in Differential Privacy is a an augmentation of the local-model where in addition to N local-agents we are assisted by one special agent who is in fact a curator holding the sensitive details of n additional individuals. Here we study the problem of machine learning in the hybrid-model where the n individuals in the curators dataset are drawn from a different distribution than the one of the general population (the local-agents). We give a general scheme -- Subsample-Test-Reweigh -- for this transfer learning problem, which reduces any curator-model DP-learner to a hybrid-model learner in this setting using iterative subsampling and reweighing of the n examples held by the curator based on a smooth variation of the Multiplicative-Weights algorithm (introduced by Bun et al, 2020). Our scheme has a sample complexity which relies on the chi-squared divergence between the two distributions. We give worst-case analysis bounds on the sample complexity required for our private reduction. Aiming to reduce said sample complexity, we give two specific instances our sample complexity can be drastically reduced (one instance is analyzed mathematically, while the other - empirically) and pose several directions for follow-up work.


Introduction
Differential privacy (DP) has become modern era's de-facto gold standard for privacy-preserving data analysis. In particular, the local model of DP -in which each user interacts in a computation by sending randomized messages whose view yields at most -privacy loss -has gained much popularity due to its (relative) design simplicity. In particular, much work has dealt with the problem of machine learning in the local-model of DP: assuming the N users' details are drawn i.i.d. from some distribution T, how can we design local-DP protocols for finding an hypothesis h of small loss w.r.t. T. However, as opposed to the curator-model of DPin which all data is held by a trusted curator in charge of executing the computation -machine learning in the local model of DP suffers from two drawbacks: (1) its has a much larger sample complexity and (2) it is of limited learning capabilities -where only problems that are SQ-learnable are learnable in the local model, in contrast to the curator model that allows us to learn (almost) any PAC-learnable problem (Kasiviswanathan et al., 2008). In order to address these problems, there has been an extensive study in recent years regarding augmentations of DP's local-model. Most notably, the shuffle model has gained much focus (Bittau et al., 2017;Cheu et al., 2019;Balle et al., 2019;Ghazi et al., 2021a; as it reduces the privacy-loss of localmodel protocols drastically. Yet the focus of this work is on a different, far less studied, augmentation of local-DP. We study the hybrid-model of differential privacy (Avent et al., 2017) -in which a local-model computation protocol with N users is augmented by the aid of one special agent who is in fact a curator holding the sensitive details of additional n individuals. (We refer to the former N users as the "local-agents" and the latter n individuals as the "curatoragents.") The hybrid-model models a situation in which some users (the n curator agents) trust a proposed curator and allow her unrestricted access to their sensitive details; while the remaining N n users trust solely themselves and opt for the local-model. Indeed, hybrid-model improves the learning capabilities of the local-model: the theoretical work of Beimel et al. (2020) have proven that in the hybridmodel certain problems, which are inefficiently solvable in the standard local-DP model, are efficiently and privately computable. Alas, in the analysis of Beimel et al. (2020), the n curator-agents come from the exact same distribution T as the remaining N local-agents. 1 In contrast, this work is motivated by a setting in which the n individuals voluntarily opt-in to the curator-model. Coping with such a "selection bias" was posed by Beimel et al. (2020) as an acute open problem since (quoting Beimel et al. (2020) verbatim:) "from a practical point of view, this ... is aligned with current industry practices, and the ... individuals willing to contribute via a curator can be employees, technology enthusiasts, or individuals recruited as alpha-or beta-testers of products... (Merriman, Oct 7, 2014;Microsoft, Sep 15, 2017;Mozilla, June 4, 2019)" In this work we model this selection bias as a particular type of a transfer learning problem. We no longer assume that the n curator-agents were drawn from the same distribution T as the local-agents, but rather that they were drawn from some different distribution S (the source distribution). Our goal, however, remains the same: to learn a good hypothesis w.r.t. T (the target distribution) while incurring at most privacy-loss for any of the agents involved in the computation. Naturally, should S and T be so different that they reside on disjoint support then the n curator agents provide no assistance our transfer learning problem. Thus, in our model S and T are of bounded χ 2 -divergence (see details in Section 2). In other words, we study a particular variation of a transfer learning problem: in the process of finding h of small loss w.r.t. T we are allowed to conduct a DP computation over a set of examples drawn from S and also to conduct a local-DP computation over N additional examples drawn from T. And so we ask: Are there learning tasks that are infeasible in the local-model, yet can be computed privately and efficiently when we have a DP curator-model access to samples drawn from a different distribution?
Our Contribution. Our transfer-learning problem has two naïve baselines.
(1) Relying solely on the N local-agents and learning a small loss hypothesis w.r.t. T via some off-the-shelf local-model protocol; this is infeasible for certain problems (e.g. PARITY (Kasiviswanathan et al., 2008)) and costly for others (e.g. sparse problem in a d-dimensional setting, where known sample complexity bounds are ≥ d, (Duchi et al., 2013;Smith et al., 2017)).
(2) Relying solely on the n curator-agents and learning an hypothesis via the some off-the-shelf DP learning algorithm guaranteed to return an hypothesis of small loss, such as a loss upper bounded by err S (h) ≤ α /D ∞ (T S) or err S (h) ≤ α 2 /χ 2 (T S)+1 (assuming these divergences are finite, see definition in Section 2). 2 This venue is feasible only when indeed an hypothesis h exists whose error over S is as small as we require; but fails to give a meaningful guarantee in an agnostic setting, even if the best hypothesis in H has error Θ(α).
Our work proposes a third technique, whose sample complexity of the N local-agents is independent of d and whose sample complexity of the n curator-agents depends on pdim(H) (so if |H| = poly(d), e.g. the Example in Section 4, then n = polylog(d)) and which may be feasible in the agnostic setting as well. Our proposed framework resembles 'Subsample & Aggregate ' (Nissim et al., 2007) in broad brushstrokes, except that instead of subsampling in parallel in order to convert a non-private mechanism to a private one, we subsample sequentially in order to convert a curator-model learning mechanism over S to hybrid-model learner. The crux of our technique is that upon each time we subsample and produce an hypothesis of small-loss w.r.t. S yet high loss w.r.t. T, we make a Multiplicative-Weights (MW)-based update step to our subsampling distribution. With each MW-update we transition closer to a "target" distribution which is based on the importance sampling (IS) weights of the points drawn from S. We thus title our technique Subsample-Test-Reweigh.
For clarity, we partition our analysis into two parts. The first, detailed in Section 3, presents the main ideas of our techniques while tabling the notion of privacy for a later section. Specifically, seeing as we know that learning in the local-model is equivalent to SQ-learning and that the vast majority of PAC-learnable problems are learnt in the curatormodel, we pose the following model. Fix an hypothesis which is PAC-learnable via hypothesis class H of pdim d through some learning algorithm M. We are given n labeled examples drawn from S and only a SQ-oracle access to T (see formal definitions in Section 2). So we iteratively (1) set a distribution µ over the n examples, (2) use M to learn an hypothesis h of small loss w.r.t. µ, (3) query the SQoracle to see if h's loss is sufficiently small (halt if yes), (4) if h has large loss we reweigh the distribution using the MW-algorithm and proceed to the next iteration. In Section 3 we prove that w.h.p. this algorithm outputs in T = O(α −2 ) iterations an hypothesis h of error err T (h) = O(α) provided n =Ω(d(χ 2 (T S) + 1)α −2 ). The crux of the proof lies in showing (w.h.p.) the existence of a particular distributionū over the n drawn samples from S s.t. ∀h ∈ H the loss of h w.r.t.ū and its loss w.r.t. T are close. Based on the seminal results of Cortes et al. (2010), it is not surprising that thisū is the truncated IS weights w(x) = P T (x) P S (x) for each x drawn from S.
Next, in Section 4 we give the privacy-preserving version of our MW-based technique from Section 3. Replacing the SQ-oracle calls with simple applications of the Randomized-Response mechanism is trivial, but maintaining the privacy of the n curator-model agents is far trickier. First, it is evident that our off-the-shelf learner M must now be a privacypreserving PAC-learner. More importantly, our MW-update step must also maintain bounded privacy-loss. Luckily this latter point was already addressed by Bun et al. (2020) who use the notion of κ-dense distributions to give a MW-based algorithm where any intermediate distribution µ is such that no one single point has probability mass exceeding 1 /κn (see details in Section 4). Using known several results regarding subsampling and privacy (Karwa & Vadhan, 2018;Bun et al., 2018), we end up with the following reduction. Denote m 1 as the sample complexity of some off-the-shelf curator-model learner that outputs an hypothesis of loss ≤ α under privacy loss parameter of = 1. In order to successfully apply the learner T times under our κ-dense MW-update subsampling scheme and have a total privacyloss of , we require a sample of n curator-agents drawn ) and N =Ω( −2 α −4 ) local-agents. While, admittedly, these bounds are less than ideal, this is the first result to prove the feasibility of private transfer learning using poly-size sample even for problems whose sample complexity in the local-model is exponential.
In Section 5 we pose suggestions as to how to reduce this bound as open problems, leveraging on the fact that the worst-case bounds for either the number of iterations T or the density parameter κ may be drastically reduced for specific hypothesis classes / instances. We give two particular examples of such instances: one proven rigorously (for the case of PARITY under the uniform distribution) and one based on empirical evaluations of our (non private version of the) transfer-learning technique in a two high-dimensional Gaussian settings, in which our algorithm makes far fewer iterations than our O(α −2 ) worst-case upper-bound.

Related Work
The bounds and limitations of private learning were first established by Kasiviswanathan et al. (2008) who proved that (roughly speaking) the learning capabilities of the localmodel are equivalent to SQ-learning. This, together with the seminal result of Blum et al. (1994), gives an exponential lower bound on the number of local-agents required for learning PARITY in the local-model (fully formally proven in Beimel et al. (2020)). Other results regarding the power and limitations of the local-model were given in Beimel et al. (2008); Duchi et al. (2013); Bassily & Smith (2015); Smith et al. (2017); Duchi & Rogers (2019) culminating in Joseph et al. (2019). And yet, the classical SGD-algorithm is still applicable in the local-model (Smith et al., 2017).
The two main works about the hybrid model (Avent et al., 2017;Beimel et al., 2020) have been discussed already, as well as the elegant private boosting paradigm of Bun et al. (2020). Other works have also studied the applicability of the MW-algorithm for various tasks in DP (Hardt & Rothblum, 2010;Gupta et al., 2011). In the context of transfer learning, few works tied differential privacy with multi-task learning (Gupta et al., 2016;Xie et al., 2017;Li et al., 2020), hypthesis testing (Wang et al., 2018) and in a semi-supervised setting (Kumar, 2022); all focusing on empirical measuring of the utility and none giving any general framework with proven guarantees as this work. Also, it could be interesting to implement a version of our algorithm which isn't private w.r.t. the samples from S in a "PATE"-like setting (Papernot et al., 2018) where public (or partially public) datasets are also available.
The classic problem of transfer learning has been studied extensively since the 20th century, and has too long and too rich of a history to be surveyed properly here. We thus mention a few recent works that achieved sample complexity bounds based on importance sampling (IS) weights and show concentration bounds related to divergences between the source and that target distributions. Some works (Agapiou et al., 2017;Chatterjee & Diaconis, 2017) showed sample complexity bounds based, in part, on exp(KL(T S)) ≤ χ 2 (T S) + 1 as well as other properties of the distribution 3 which lack our desired sub-Gaussian behavior. The seminal result of Cortes et al. (2010) achieved a bound that is, in spirit, more similar to the desired sub-Gaussian behavior. They also proved that with sample size bounds depending on χ 2 (T S) we can achieve accurate estimation of the loss of any hypothesis (simultaneously) in a finite pdim hypothesis class H. Recently, Metelli et al. (2021) suggested a method of correction of the weights that allow obtaining sub-Gaussian behavior, assuming prior knowledge of the second moment of the weights. Maia Polo & Vicente (2022) studied the case where access to distribution T is restricted to unlabeled examples, and propose methods for evaluating the IS weights. Yao & Doretto (2010) use a boosting algorithm (based on the MW algorithm) for transfer learning, yet in their work, the distributions S and T are identical but the features of the classes are different.

Preliminaries
PACand SQ-Learning. The seminal work of Valiant (1984) defined PAC-learnability, where the learner has access to poly-many examples drawn from a given distribution T over a domain X labeled by some and its goal is to approximate as well as the best hypothesis in some given hypothesis class H. We measure our prediction success using some loss-function L where for every x ∈ X , h ∈ H and any labelling function it holds that L(h(x), (x)) ∈ [0, 1]; and so for any distribution T we de- The learner's ability to draw n i.i.d. examples is simulated via an example-oracle which upon a query returns such a labeled example. Thus, in the PAC-mode, a learner has full access to all of the details of any drawn example. In contrast, the Statistical Query (SQ) model (Kearns, 1998) restricts the operation of the algorithm to view solely statistical proper-ties of the distribution T and the labeling function . This is simulated via access to a SQ τ -oracle which upon a statistical query φ : X × R → [0, 1] returns an estimation of Ex∼T[φ(x, (x))] up to a tolerance parameter τ (polynomially bounded away from 0). Differential Privacy. Given a domain X , two multi-sets I, I ∈ X n are called neighbors if they differ on a single entry. An algorithm (alternatively, mechanism) is said to be ( , δ)-differentially private (DP) (Dwork et al., 2006b;a) if for any two neighboring I, I and any set S of possible outputs we have: The Randomized-Response mechanism (Warner, 1965;Kasiviswanathan et al., 2008) is one of the classic ( , δ)-DP mechanisms in the local-model. Given privacy parameters , δ, on an input b ∈ [0, 1] it outputs RR ,δ (b) ∼ N (b, 2 ln(2/δ) 2 ). When applied to N i.i.d. draws from a Bernoulli r.v. of mean µ, then we estimate µ by θ = 1 N i RR ,δ (b i ). Standard application of the Hoeffding bound and Gaussian concentration bounds proves that applying the mechanism to N (α, β, , δ) = 4 ln(2/δ) ln(4/β) Differentially Private Machine Learning is by now too large of a field to be surveyed properly. It was formally initiated by (Kasiviswanathan et al., 2008) who, as discussed above proved that the set of hypothesis-classes which is SQlearnable is conceptually equivalent to the set hypothesisclasses learnable in the local-model of DP. It is also worth mentioning the DP techniques for Empirical Risk Minimization and especially private SGD (Chaudhuri et al., 2011;Bassily et al., 2014) which we use as our private learner in Appendix A.
Divergence Between Distributions. Given two distributions S and T over the same domain X that have a Radon-Nikodym derivative, we denote said derivative as the importance sampling (IS) weight at a point x ∈ X as (Csiszár & Shields, 2004) states the for any twicedifferentiable f it holds that D f (T S) ≈ f (1) 2 χ 2 (T S) (as follows from f 's Taylor series). In the context of transfer learning, Cortes et al. (2010) proved that weighing all examples in a sufficiently large sample drawn from S ac-cording to their IS weights gives an accurate estimation of the loss of any hypothesis in a finite pdim hypothesis class H over T; where their sample size bounds depend on χ 2 (T S). Another well-used notion of divergence is the α-Reyni divergence between T and S, definted as for any α > 1, which was also used to define similar notions of privacy (Bun & Steinke, 2016;Mironov, 2017;Bun et al., 2018). Note that D 2 (T S) = ln(χ 2 (T S)+1). We also denote D ∞ (T S) = sup x∈X w(x).
Bernstein Inequality: In our work we use several standard concentration bounds (Markov-/ Chernoff-/ Hoeffdinginequalities), and also the slightly less familiar inequality of Bernstein (1954): be independent zero-mean random variables. Suppose that |X i | ≤ M almost surely, for all i. Then for any positive t, (1)

A Non-Private Model
For the sake of clarity, we introduce our algorithm in stages -where first we disregard the privacy aspect of the problem. In this section we deal with a specific transfer learning model, whose details are as follows. We are given a known domain X and some unknown labelling function : X → R. We also have the following access oracles to two unknown distributions S and T over X -we are given an example oracle Ex access to S, that upon a query returns an example x drawn from S and labeled by ; and we are given a statistical query oracle SQ τ to T, that upon a query φ : X × R → [0, 1] returns an answer in the range Ex∼T[φ(x, (x)] ± τ . Our goal is learn through some hypothesis class H; i.e. to find an hypothesis h whose loss w.r.t. over T is comparable to the loss of the best hypothesis in H, whose pdim(H) = d. Formally, we introduce our algorithm in the realizable setting, so given a parameter α > 0 and a loss function L : R 2 → [0, 1] our goal is to find h such that err T (h) = α. (We later discuss extension to the agnostic case.) In addition, we are given an algorithm M which is a (α, β)-PAC learner for our hypothesis class H. Namely, given α, β > 0, our learner M takes a sample of m(α, β) i.i.d. examples drawn from some distribution µ and labeled by some and w.p. ≥ 1 − β returns a function h ∈ H whose loss is upper bounded by err µ (h) ≤ α. So, had we been able to draw i.i.d. examples from T, we would have just fed them to the algorithm and produce a good hypothesis h. Alas, in our model, we only have statistical query oracle access to T, SQ τ , with error of ±τ .
In this section, we propose a general reduction of a PAClearner over S to finding a good hypothesis w.r.t. T, which depends solely on χ 2 (T S) def = χ 2 . We argue that Algo- Apply M to the drawn points and obtain a function h t . Set a t as the reply of the SQ τ -oracle for the query Note that Algorithm 1 is presented for the realizable case. If we deal with an agnostic case, namely -where α H > 0, then our algorithm iterates as long as err µ t (h t ) < α H + α.
(A condition which ought to hold when we begin with h 1 , the a good hypothesis w.r.t. S and err S (h 1 ) err T (h 1 ).) It ought to be clear that by returning h t with the smallest error estimation given by the SQ-oracle in all T iterations, an hypothesis h ∈ H of small loss w.r.t. T is obtained.
The proof of Theorem 3.1 relies on proving the following lemma, and builds on -and extends -a theorem of Cortes et al. (2010).
Lemma 3.2. Given 0 < α, β ≤ 1 /8 and two distributions S and T whose holds that there exists a distributionū over the n drawn points such that (i) its divergence to the uniform distribution over the n drawn point, Proof of Theorem 3.1. Based on Lemma 3.2, we now simply apply the characterization of the MW-algorithm from the seminal work of Arora et al. (2012). Setting the 'cost' of example i w.r.t. hypothesis h t as m t i = 1−L(h t (x i ), (x i )) we have that applying the MW-algorithm with costsm 1 , ...,m T and with an update rate of η = α /8, we get that for any fixed Note that w.p. ≥ 1 − β our algorithm M returns an hypothesis of err µ t ≤ α in all T iterations. In contrast, we know that each MW-update happens since err T (h t ) ≥ 2α + τ − τ = 2α; and so, w.p. ≥ 1−β, we have a distribution ν =ū given by Lemma 3.2, which we plug-in to the above equation and have Rearranging we get the bound 3αT Hence, w.p.≥ 1−2β Algorithm 1 halts within some iteration where P T and P S denotes the PDFs of T and S resp. We call w(x) the weight of x.
denoting the indicator of whether x ∈ A or not. And so: To that end, we apply the Bernestein inequality. First, we have that and similarly we can prove Now, settingū as the distribution where point i is sampled w.p. u(xi) U we can use the above bound on U to infer that proving the first part of the claim.
). Note that ( * ) is taken verbatim from Cortes et al. (2010) Theorem 8. Thus, w.p. ≥ 1 − β both the above bounds on U hold and we have that for any h ∈ H it holds that

The Private Boosting Paradigm
We now turn our attention to the full hybrid-model, and to our need to privatize Algorithm 1. In order to design a private version of Algorithm 1 one required multiple changes. First, and perhaps the easiest, is the fact that instead of a SQ τ oracle access to T we estimate the error of h t using RR (in the local-model). Assuming our algorithm makes at most T iterations, standard argument shows that each such query requires Ω( 1 2 α 2 log(T /β)) users so that w.p. ≥ 1 − β /T we get a α-esimation of err T (h t ); so, the number of local-users required for our paradigm is Second, which is also a rather straight-forward change, is that we need to replace the learning mechanism M with a privacy-preserving learning mechanism whose sample complexity depends also on the privacy-loss parameter(s). This implies that the sample complexity of M is a function of the 4 parameter m = m(α, β, , δ). 5 The question of setting the privacy parameters of M, thereby inferring the sample complexity of M, will be discussed momentarily.
Lastly, the more challenging aspect of the problem is maintaining the privacy of the samples among the n examples that are drawn from S. To that end, we rely on the MWvariant of (Bun et al., 2020), which in turn requires we introduce one more parameter, namely κ, into the problem.
Definition 4.1. Fix some 0 < κ < 1. Given n points and a set of weights w 1 , w 2 , ..., w n ≥ 0, we denote w avg = 1 n i w i and w max = max i {w i }. We say that the distribution induced by these weights, namely the distribution From a privacy stand-point, it is clear why a dense distribution is a desired trait: it makes it so that in a random sample of m draws from µ we expect each point i to be drawn no more than 1/κ times. (Bun et al., 2020) showed that for any set of weightsw = (w 1 , w 2 , ..., w n ) where ∀i, w i ∈ (0, κ], by setting Π κ (w) = min{c · w 1 , 1}, min{c · w 2 , 1}, . . . , min{c · w n , 1} (2) for the smallest c s.t. Π κ (w) 1 = κn, we obtain a set of weights whose induced distribution µ = Πκ(w) Πκ(w) 1 is κ-dense. Using this projection we get the following claim.
Claim 4.1. Let S and S be any two neighboring datasets of size n each. Letw andw be two weight vectors in (0, κ] n which may differ on the only entry that differs between S and S , and let µ and µ be the two distributions derived fromw andw resp. using the projection of (2). Let H be an hypothesis class and let M be a ( , δ)-DP mechanism that takes as input a dataset of size m = m(α, β, , δ) and outputs some h ∈ H. Then, for any T ⊂ H, if we denoteX (resp.X ) as the result of m i.i.d. draws from S (resp. S ) using µ (resp. µ ), then, setting * = 6 m κn and δ * = 4me * δ κn
Pick arbitrarily a new batch B of N 0 local-users, and Proof. This follows immediately from applying Lemma 6.1 in (Karwa & Vadhan, 2018) to this setting, using the bound TV(µ, µ ) ≤ 1 /κn proven by Bun et al. (2020).
A reader familiar with sample complexity bounds in DPliterature, knows that usually the dependency of m in is inverse. Thus, the dependency of * in m suggests that * ends up independent of the privacy-loss of parameter set to the private learning mechanism M. That is why chose to apply M with = 1, a parameter under which most private and non-private sample complexity bounds are asymptotically equivalent. 6 The flip side of it is that we now set n to be proportional to −1 . We are now ready to give our DP algorithm for transfer learning in the hybrid model.
Proof. First, it is clear that each local-user is asked a single query and replies using a mechanism that is ( , δ)-DP. As for the privacy of the curator-agents, by setting m 1 = m(α, β /T , 1, κδ 8eT ), Claim 4.1 asserts that in each iteration we are ( * , δ * )-DP for * = 6·1·m1 Applying the Advanced Composition theorem of (Dwork et al., 2010) we get that in all T iterations together we are ( , δ)-DP w.r.t. to each of the n curator-agents.
Proof. Again, the proof relies on the characterization of the utility of the MW-mechanism w.r.t. k-dense set of weights. Again, letw 1 be the initial weights vector where w 1 i = κ for all i. Letw * ∈ [0, 1] n be any fixed set of weights which is κ-dense, and denoteŵ =w * w * 1 as its induced distribution. Then, we have that for any sequence of costsm 1 ,m 2 , ...,m t , Bun et al. (2020) proved that this MW-mechanism with learning rate of η = α 8 guarantees that where φ(w * ,w 1 ) is the Bregman divergence induced by the entropy function, namely Asw * we aim to use the weights which Lemma 3.2 guarantees whose nice properties hold w.p.≥ 1 − β. Thus, we set for each x i drawn from S the weight w * i = u(xi) 4(χ 2 +1) /α ≤ 1. As Lemma 3.2 asserts, it holds that U = u(x i ) lies in the range [(1 − 3α /8)n, (1 + α /8)n], thus w avg = 1 n αu(xi) we have that w avg ≥ κ · 1 ≥ κw max , implying w * is indeed κ-dense. Also, the same bounds on U imply that The remainder of the proof is as in Theorem 3.1. In each iteration it must hold that err µ t (h t ) ≤ α; whereas a t ≥ 3α, which w.p.≥ 1 − β -using classic utility bounds for the Randomized Response mechanism -implies that err T (h t ) ≥ 2α. Plugging this bound to Equation (3) stating the regret of the κ-dense MW-algorithm we get Rearranging yields the bound 3αT Thus in a realizable setting, given a finite H, we can set M as the exponential mechanism over H returns w.p. ≥ 1 − β an hypothesis of error Θ(α) when the sample size it at least Ω( ln(|H|) /α ). We thus obtain the following corollary. Example: Sparse Hypothses. It is worth noting that our sample complexity bounds are independent of the dimension d (assuming the domain X ⊂ R d ). So consider a specific case that deals with a s-sparse problem over a high d-dimensional set where s d, say, where H is a linear seprartor that uses no more than s = O(1) features out of the d features of each example. This suggests that |H| = d O(s) = poly(d). We thus obtain s · polylog(d) sample complexity bounds (setting all other parameters to be come reasonable constants.) whereas learning solely over T requires a sample complexity ≥ d (see Duchi et al. (2013)).
Private SGD. The specific case where the private learning mechanism M is SGD discussed in Appendix A. This case is discussed separately for two main reasons. First, its algorithmic presentation is slightly different than in Algorithm 2, since in each iteration it makes successive draws from µ t rather than a single draw of a subsample. Secondly, this is the one canonical case where L is continuous (rather than binary), and so the subject of scaling comes into play. Whereas thus far we assumed L is bounded by 1, it is straightforward to see that a L-Lipfshitz convex loss function over a convex set of diameter D has loss ∈ [0, LD], thus our goal is now to obtain a loss ≤ α (rather than α·LD). Lastly, aiming to give a tight analysis, we use the notion of (ρ, ω)-tCDP (Bun et al., 2018) which is then converted to ( , δ)-DP scheme. Nonetheless, the sample complexity bounds we get are similar to those of Algorithm 2.

On Reducing Sample-Complexity Bounds
While our work is the first to show the feasibility of transfer learning using poly-size sample, its sample complexity bound for the curator-agents is a large multiplicative factorÕ( −1 α −2 ) over the sample complexity of a (nontransfer) curator-model learner. We believe that it is possible to significantly improve said bound, at least for particular instances. Here we provide two specific instances where indeed the number of required iterations until convergence of our algorithm is o(α −2 ), leading to a much smaller sample complexity.
Transfer Learning for PARITY under the Uniform Distribution. Consider the domain X = {0, 1} d and the class of PARITY functions, where for any S ⊂ [d] we have c S (x) = i∈S x i . It is a well-known result that under the uniform distribution the PARITY class cannot be learnt in the local-model unless the number of local-agents is N = exp(d), yet a sample of size n = Θ( d / α) suffices to learn PARITY under any distribution in the curatormodel (Kasiviswanathan et al., 2008). In Appendix B we show that in the hybrid-model one can learn PARITY in a single iteration, provided S and the uniform distribution T have polynomial χ 2 -divergence. The crux of the proof lies in proving that w.h.p. a sufficiently large sample drawn from S is linearly independent over F d 2 . This suggests that the private curator-model learner for PARITY (Kasiviswanathan et al., 2008) -which leverages on (multiple) Gaussian elimination over F d 2 -returns w.h.p. the true labeling function in the PARITY hypothesis class.
Empirical Experiments: When Both S and T are Gaussians. Next, we show empirically that in other settings, both the number of required iterations until convergence and our sample complexity bounds are far greater than required. First, we consider a setting where S is a simple spherical Gaussian in d = 500-dimensions, S = N (0, I d ) whereas for T we picked an arbitrary set of k = 10 coordinates and set the standard deviation on these k as σ = 0.02 whereas the remaining d−k coordinates have standard deviation of 1, i.e. T = N (0, I d−k ⊗σ 2 I k ). It is a matter of simple calculation to show that χ 2 (T S) + 1 = ( far below the ≈ α −2 upper bound. The results appear in Figures 1a and 1b in Appendix C. Second, we consider a setting where the true hypothesis actually corresponds to a k-dimensional ball over the k coordinates that are more concentrated in T than in S and ran both the private and non-private version of our algorithm. While the non-private version converged very fast, the private version required a very large sample of curator-agents, and so we were able to conduct only preliminary experiments with it. The experiment is detailed in Appendix D where the results appear in Figures 2 and 3. Open Problems. Our work is the first to present a general framework for transfer learning in the hybrid-model, thus providing an initial answer to the open problem of "selection bias" posed by Beimel et al. (2020). While our framework does surpasses certain naïve baselines in some specific cases, there is still much work to be done in order to reduce its sample complexity. Considering different divergences can be a promising direction, especially if we know that the 4th moment of the IS weights is bounded (as it may increase the value of κ). A different venue can be the study of repeated uses of Subsample-Test-Reweigh -when person A applied the paradigm until she finds a good hypothesis, then hands over her last set of weights to Person B who uses it for learning a different hypothesis. Lastly, we believe that there's more to be studied in general in the intersection between DP and transfer learning, as the problem can be tackled from the alternative approach of discrepancy between hypothesis classes (Ben-David et al., 2010;Mansour et al., 2009).

A. Private Stochastic Gradient Descent
The Private SGD Algorithm. In this section, we discuss our private Subsample-Test-Reweigh paradigm where the private learning mechanism applied in each iteration is the standard private SGD (see Hazan (2016); Bassily et al. (2014)). For simplicity, we give the algorithm here.

Algorithm 3 Online SGD
Input: Parameters α, β, σ Lipfshitz constant L and a convex set H ⊂ R d of diameter D. A distribution µ over a sample S.
Standard arguments from Hazan (2016) give the following utility theorem.
Proof. The proof follows from the usual analysis of SGD, under the observation that in each iterations and that Plugging those into the bounds of the generalization properties of the SGD for convex functions we obtain: , 8D 2 L 2 ln( 2 /β) α 2 yields that err µ (h) ≤ α H + α 2 + α 2 as required. Similarly, for a
While we can apply a privacy analysis of Algorithm 3, we table it to the privacy analysis of our full algorithm.
The Subsample-Test-Reweigh Using SGD. We now transition to the full analysis of STR when we apply SGD as an intermediate procedure.
The utility analysis of Algorithm 4 is just as the one of Algorithm 2 modulo the fact that the non-negative loss is now bounded by LD rather than 1, which implies we must increase the number of MW-iterations by L 2 D 2 . It requires a sample complexity of n = Ω(L 2 D 2 (χ 2 + 1) log( 1 /α) α 2 (d log( d α ) + log( 1 β ))) curator-agents, and N = N 0 T = Ω( L 2 D 2 log((χ 2 +1)/α) log(log(χ 2 +1)/αβ) 2 α 4 ) local-agents to return, w.p.≥ 1 − 3β an hypothesis of error ≤ α H + α. (The increase in the number of curator-agents is due to the fact that the loss is now in the range [0, LD] rather than [0,1].) The privacy analysis of Algorithm 4 requires we transition of (ρ, ω)-tCDP given in Bun et al. (2018). Its definition as well as some of its basic properties (proven in Bun & Steinke (2016);Mironov (2017); Bun et al. (2018)) are provided below. Definition A.1. A mechanism M is said to be (ρ, ω)-tCDP if for two neighboring inputs I and I the α-Reyni divergence of the two distributions is bounded: D α (M(I)||M(I )) ≤ αρ for any 1 < α ≤ ω. Fact A.2.
• Let f be a d-dimensional function of L 2global sensitivity of max I,I neighbors f (I) − f (I ) ≤ L. Then the mechanism that outputs for any instance I an output drawn from N (f (I), • Let M 1 , M 2 be two (ρ 1 , ω 1 )-tCDP (resp. (ρ 2 , ω 2 )-tCDP) mechanisms. Then the mechanism that applies them to the same instance but using independent coin toss for each is (ρ 1 + ρ 2 , min{ω 1 , ω 2 })-tCDP.
Perhaps, however, the most important property of tCDP is that it is amplified by subsampling. Let s be a constant satisfying log( 1 /s) ≥ 3ρ(2 + ln( 1 /ρ)). Let M be a (ρ, ∞)-tCDP mechanism. Let I and I be two neighboring instance and let µ be a distribution where the probability of sampling the one different entry between the two instances is s. Then the mechanism that samples entries from the input and then applies M on the subsample is (13s 2 ρ, log( 1 /s) 4ρ )-tCDP.
To establish this, we prove the following sequence of claims and corollaries.
Proof. We prove the claim inductively as we iterate over all vectors in S. Due to simple counting argument, it is easy to see that the probability to draw an vector that is linearly dependent of given set of i vectors in a the d-dimension space F d 2 is at most 2 i−d . So fix any 0 ≤ i ≤ d − 1. At each step we have a set of i linearly independent vectors spanning a subspace of dimension i. We argue that the probability that among the next t = log 2 (d/β) vectors in S the probability that all t vectors are linearly dependent of these i basis vectors is at most (2 i−d ) t ≤ 2 −t = β /d. And so, after d iterations we have found a set of d linearly independent vectors in S w.p. ≥ 1 − β.
Claim B.2. Fix 0 < β < 1 /2. Let T be the uniform distribution over {0, 1} d and let S be a distribution over the same domain s.t. χ 2 (T S) = χ 2 is finite. Let S be a sample of n ≥ 4(χ 2 + 1)d ln( d /β) points drawn i.i.d. from S. Then the probability that S isn't linearly independent is ≤ β.
Proof. The claim is proven in a similar inductive fashion to Proposition B.1. Fix any 0 ≤ i ≤ d − 1. At each step we have a set of i linearly independent vectors spanning a subspace of dimension i. We argue that the probability that among the next t = log 2 (d/β) vectors in S the probability that all t vectors are linearly dependent of these i basis vectors is at most ≤ β /d, from which the claim follows immediately.
Corollary B.3. Fix β > 0. Set k = log 4 /3 ( 2 /β). Under the same notation as in Claim B.2 let S 1 , S 2 , ..., S k be k independently drawn batches from S s.t. each S i contains at least n ≥ 32(χ 2 +1)d ln( 2dk /β) . Then w.p. ≥ 1 − β it holds that when we drawn from each S i a subsample S i where each x ∈ S i is put in the subsample w.p. /4 independently of all other examples, then all S i are linearly independent.
Proof. Straight-forward application of the Chernoff bound gives that w.p.≥ 1 − β /2 each of the k S i -s contains at least /8|S i | many points. This suffices for us to apply Claim B.2 and have that w.p. ≥ 1 − β /2 all S i are linearly independent.
Based on Corollary B.3 we can now apply the same PARITY learning algorithm from Kasiviswanathan et al. (2008) on the kn curator-agents just once and then test its correctness over the N . This algorithm outputs for each S i either a ⊥ or a solution in the affine subspace that solves a system of equations over F 2 . But due to the linear independence of each S i , this solution must be the indicating vector of the relevant features of the true classifying function c * S ∈ PARITY. It follows that for each S i outputs the true classifying function w.p.≥ 1/4; and so, w.p. ≥ 1 − β all S i return either ⊥ or c * S where at least one of the S i -s outputs the true classifier. Note that the true classifier's loss -under any distribution S or T -must be 0. Using additional O( −2 α −2 ) we can test and see that indeed we have an hypothesis c ∈ PARTIY which is of small loss.

C. Experimental Evaluation of Non-Private
Subsample-Test-Reweigh.
In this section, we show empirically that in another setting, both the number of required iterations until convergence and our sample complexity bounds are far greater than required. We consider a setting where S is a simple spherical Gaussian in d = 500-dimensions, S = N (0, I d ) whereas for T we picked an arbitrary set of k = 10 coordinates and set the standard deviation on these k as σ = 0.02 whereas the remaining d − k coordinates have standard deviation of 1, i.e. T = N (0, I d−k ⊗ (0.01) 2 I k ). It is a matter of simple calculation to show that χ 2 (T S) + 1 = ( 1 σ 2 (2−σ 2 ) ) k/2 > 3 · 10 15 . Now, true hypothesis is a hyperplane separator set on the k coordinates on which S and T have a different variance, so that is classifies precisely α = 0.01 of the mass of T as −1.
We applied the non-private version of our algorithm (Algorithm 1). In the non-private version, in order to learn in each iteration a hyperplane separator over a subsample of examples from S we used SVM, where our optimization goal is 1 2 w 2 + C · x max{0, 1 − w, x } with a very large C = 10 30 (aiming to find an exact hyperplane as possible) over a subsample whose size is set to be d+ln(0.05/T ) α . First, aiming to find the sample complexity of the curator-agents that already yields an hypothesis of error ≤ 2α, we ran our experiments with varying values  of n = {10 4 , 2 · 10 4 , ..., 8 · 10 4 , 9 · 10 4 }, repeating each experiment t = 50 times. We observed that for n = 80, 000 we consistently return an hypothesis of small-loss. Results appear in Figure 1a. Then, for even larger values of n = {9 · 10 4 , 1 · 10 5 , .., 1.4 · 10 5 } we ran our experiment to see at which iteration do we halt. For n = 80, 000 we halt after ≈ 1300 iterations whereas for n = 140, 000 we halt after T ≈ 1200; yielding the rather surprising result that T isn't greatly affected by the increasing sample complexity. But regardless, this is very far below than the O(α −2 )-upper bound. Results appear in Figure 1b. In fact, looking at the error of the resulting hypothesis along the run itself returns roughly the same values, as seen in Figure 1c.

D. Experimental Evaluation of Private Subsample-Test-Reweigh
In order to implement the private algorithm, we used another example with bounded examples and hypotheses.
Similarly, to the previous experiment, we consider a setting where S is a simple spherical Gaussian in d = 200dimensions, S = N (0, I d ) whereas for T we picked an arbitrary set of k = 6 coordinates and set the standard deviation on these k as σ = 0.4 whereas the remaining d − k coordinates have standard deviation of 1, i.e.
It is a matter of simple calculation to show that χ 2 (T S) + 1 = ( 1 σ 2 (2−σ 2 ) ) k/2 > 39.1. However, we now set the true labeling function as one that correlated to points with large importance sampling weight. It is fairly simple to see that by looking at the k-coordinates with smaller variance in T, any origin-centered ball has more probability mass in T then in S. And so, our hypothesis class is the set of origin-centered ellipses H = {w 1 , ..., w d , b ∈ [0, 1] : d i=1 w i x 2 i ≤ b} where so that x i ∼ S and thus y ∼ χ 2 k . The true hypothesis is the hyperplane separator withw = 0 · I d−k ⊗ 1 · I k and b = σ 2 r 0 , where r 0 is the a numerically set threshold under which a Pr X∼χ 2 k [X < r 0 ] = 0.3. Thus labels precisely 30% of the probability mass of T as −1, whereas it labels a significantly smaller fraction of S as −1.
As the curator-model learning algorithm we used the online SGD as presented in Hazan (2016), after mapping each example x ∈ R d to the vector y ∈ R d + where y i = x 2 i for each coordinate y. This allows us to use the Hinge-loss function -L(y) = max{0, * (y)( w, y −b)}. The learning rate of the algorithm depends on a bounded diameter of the hypothesis and Lipschitzness of the loss that upper-bound the ȳ . So we set a value B = 27.9 -the empirically the max value of ȳ of 90% of the examples drawn from S, and projected each example with norm > B onto this simplex: {y ∈ R d + : y ≤ B}. Therefore, including the additional intercept coordinate, we get: ∇L(ȳ) 2 ≤ B 2 + 1, so we can use the Lipschitz parameter of L = √ B 2 + 1. We also verify that the diameter is lower than √ d + 1 by verifying that σ ≤ 1 / √ r.
Non-privately, we run the online SGD with a maximum of 10 4 iterations or until finding an exact hyperplane with a loss of at most α = 0.01 with β = 10 −6 /T . Aiming to find the sample complexity of the curator-agents for which we get an hypothesis of error ≤ 2α over T, we ran our experiments with varying values of n = {75K, 100K, 125K, 150K, 175K, 200K}, repeating each experiment t = 50 times. Note that all these values of n are below the worst-case bound (in our settings is 15 · 10 12 ), we consistently return a hypothesis of small-loss on T. Results appear in Figure 2a. Again, we see that the number of MWiterations, T , isn't greatly affected by the increasing sample complexity, as seen in Figure 2c. Also in all values of n we halt after ≈ 1000 iterations (Results appear in Figure 2b) which is far below than the O(α −2 )-upper bound.
In the private version of the algorithm we applied Algorithm 4 with the private online SGD (Algorithm 3). The settings of the non-private version required a vast amount of memory because of the sample complexity bounds that are pretty big even for moderate values of α and , so we had to change some parameters and use fairly close distributions S and T. The changes from the non-private settings are as follows. We set the dimension to d = 8 and the number of "closer" coordinates to k = 2, so S = N (0, (0.1) 2 I d ) whereas T = N (0, (0.1) 2 I d−k ⊗ (0.07) 2 I k ). (It is a matter of simple calculation to show that χ 2 (T S) + 1 = ( σ 4 S σ 2 T (2σ 2 S −σ 2 T ) ) k/2 > 1.35, where σ S , σ T are the std in the k coordinates of S and T respectively.) We also set r 0 is a threshold for 0.4 of the examples, i.e. Pr X∼χ 2 k [X < r 0 ] = 0.4. We set α = 0.08, and κ = α 4(χ 2 +1) , and used the privacy parameters of = 0.5 and δ = 0.0001. Following similar calculations to before we set the bound on our hypothesis set's diameter as B = 0.006 and the Lipschitz value of L = 0.1.
We succeeded to get from the SGD a hypothesis whose loss is lower than α = 0.08 with β = 10 −6 /T after 50M iterations. So we run SGD with R = 50M , R = 75M , and R = 100M iterations, repeating each experiment t = 50 time, to see their influence of them on the required number of MW-iterations. Our calculations lead to a sample complexity of n = 324, 700, 000 which we used in all runs. We can see (in Figure 3b) that the number of MW-iterations decreases as the iteration of SGD is increasing. In addition, the loss on T starts higher as the SGD iterations decrease (Figure 3c). However, in all these runs MW algorithm converged to 2α (Figure 3a).
Due to the sample size, we were not able to experiment thoroughly with the private version of our algorithm, alas, our   experiments do show that we succeed in implementing the algorithm. Furthermore, we also experimented with a SGD version which minimized the Lasso-regularized version of our algorithm. This version converged in a single iterationnamely, it found the true separating coordinates on S. This is similar in spirit to the work of Avent et al. (2017) which also used the curator-agents to find the coordinates of the regression.