Model personalization allows a set of individuals, each facing a different learning task, to train models that are more accurate for each person than those they could develop individually. For example, consider a set of people, each of whom holds a relatively small dataset of photographs labeled with the names of their loved ones in the picture. Each person would like to build a classifier that labels future pictures with the names of people in the picture, but training such an image classifier would take more data than any individual person has. Even though the tasks they want to carry out are different-their photos have different subjects-those tasks share a lot of common structure. By pooling their data, a large group of people could learn the shared components of a good set of classifiers. Each individual could then train the subject-specific components on their own, requiring only a few examples for each subject. Other applications of personalization include next-word prediction on a mobile keyboard, speech recognition, and recommendation systems.
The goals of personalization are captured in a variety of formal frameworks, such as multitask learning and metalearning. Roughly, in multitask learning we are given data for t tasks and wish to find t different, but related, models g 1 ,...,g t that each perform well on one task. In metalearning, we aim to find a common representation, which is a summary (e.g. an embedding of the data into a lower-dimensional space) that can be adapted to new test tasks that are similar to the training tasks, and where similarity is formalized through some task distribution.
Although it offers many benefits, model personalization poses new risks for privacy because each individual's model depends on the data of other individuals. Thus, we undertake a systematic study of differentially private (DP) personalized learning. Informally, DP personalized learning requires that the components of the models made visible to people other than you do not reveal too much information about your data. As in the motivating example above, we think of your data as being synonymous with the training data for a single learning task.
Frameworks for private personalization. Our first contribution is a taxonomy of different formal frameworks for private personalized learning, which vary according to the learning objective, the privacy requirements, and the structure of the output.
Our main interest in investigating these models is sample complexity: How many individuals/tasks t need to contribute data to achieve a given learning objective, and how many samples n do we need from each individual/task? We focus on small n, so no one individual data can learn well on their own. Because we focus on sample complexity (as opposed to computation or communication), we consider a centralized curator that can collect and process the data of all parties. Such a curator can typically be simulated by a secure multiparty computation without the need for an actual trusted party. Specifically, we consider the following output structures (omitting citations-see the more detailed discussion and related work sections below):
Billboard: The outputs of the curator are visible to all individuals ("written on a billboard"), but may be adapted locally by each individual for their use. This is the model used in the overwhelming majority of papers on private personalized learning.
Separate Outputs: The curator sends a separate output to each individual, that is only visible to them.
Each output structure leads to one or more corresponding privacy requirements. In the billboard structure, it is clear that the DP condition has to apply to everything the curator outputs. When individuals receive separate outputs, we consider two types of attackers. One type sees the outputs of all but one individual and we want this attacker to be unable to make inferences about the data of the remaining individual (joint DP). In the other (1-out-of-t DP), we require privacy only for an individual that sees one output.
Relating the frameworks. Our second contribution is a set of relationships among and separations between the different combinations of learning objectives and privacy requirements.
We introduce two basic problems, one involving estimation and one involving classification, and show a hierarchy of frameworks for both problems:
Our results have a number of technical and conceptual implications for private personalized learning:
1. Multitask learning with billboard DP implies DP metalearning and vice-versa. 2. For some tasks, multitask learning with a general JDP algorithm can require much less data than for DP billboard algorithms. Thus, while most JDP learning algorithms to date use a billboard, there is potential to significantly reduce the sample complexity by exploring different algorithmic paradigms. As a consequence, there is a separation between DP multitask and DP metalearning, even though the two objectives are essentially equivalent in the absence of privacy constraints. 3. There is a separation between private multitask learning with JDP and with 1-out-of-t DP. Thus, private personalized learning requires much less data if we are in a setting where a realistic adversary can only see the outputs or behavior of a small number of individuals.
In this section we describe the key concepts in our taxonomy and then describe our technical results.
Learning Objectives. We consider two learning objectives-multitask learning and metalearning. In both, data from t people is pooled together for learning. In multitask learning we simply want to learn a separate model for each of these tasks, but in metalearning, we want to extract some kind of representation that can later be specialized to another unseen task. Note that metalearning is intuitively the harder objective because the representation can also be specialized to the original tasks.
In multitask learning, we have t tasks, each of which is modeled by a distribution P i , with training data for the task sampled i.i.d. from this distribution. The algorithm takes in training datasets S i for each task and returns hypotheses g i for each task. Our goal is for the g i to have low error on their respective tasks, as measured by some loss function ω(P i ,g i ), averaged over the t tasks.
Definition 1.1 (Multitask Learning). Let P be a set of t-tuples of distributions and ω be a loss function.
An algorithm M multitask learns P with error ε with t tasks and n samples per task if, when given datasets S 1 → P n 1 ,..., S t → P n t for any (P 1 ,..., P t ) ↑ P , it returns hypotheses g 1 ,..., g t such that E[foot_1 t i↑ [t] ω(P i ,g i )] ↓ ε, where the expectation is taken over the datasets and the randomness of M.
Note that the definition doesn't make assumptions about the individual tasks or relationships between them, but some assumptions will be necessary for any non-trivial multitask learning.
The other learning objective we consider is metalearning, which models learning a representation that can be used for some unseen task. Here, we have a collection of t training tasks and a separate test task drawn from a task distribution. The first algorithm takes training datasets S i for each of the training tasks and outputs a representation 1 h. The second algorithm then takes h and training data for the unseen test task and returns a hypothesis g. Our goal is for the final hypothesis g to have low error on the test task.
Definition 1.2 (Metalearning). Let Q be a distribution over (t +1)-tuples of distributions and ω be a loss function. A pair of algorithms (M meta , M pers ) metalearns Q with error ε using t training tasks, n samples per training task, and a test task with n pers personalization samples if the following holds: Let (P 1 ,..., P t+1 ) be a tuple of tasks drawn from Q. Let S i → P n i for i ↑ [t] and give S 1 ,..., S t to M meta to obtain a representation h. Now give h and S t+1 → P n pers t+1 to M pers to obtain a hypothesis g t+1 . Then E[ω(P t+1 ,g t+1 )] ↓ ε, where the expectation is taking over the choice of tasks, the training datasets, the test dataset, and the randomness of the algorithms.
We consider a range of privacy requirements based on differential privacy, which we summarize here informally (see §2 for precise definitions). Roughly, an algorithm M is differentially private if the distribution of its output is insensitive to changing one individual's data. In our context, this means that if we have S = (S 1 ,..., S t ), where each S i is all the training data of a specific individual/task, and S ↔ which differs on the data for one individual, then M(S) and M(S ↔ ) have nearly the same distribution.
Our privacy requirements vary according to what we assume to be visible to an attacker. Some of these requirements are specific to one of the two learning objectives above, or assume particular structural constraints on the algorithms.
The privacy requirement for metalearning is easiest to describe, because we assume that the representation h is published, and thus require that h does not reveal too much about any of the individuals' data. Formally, this means simply that algorithm M meta is differentially private.
Multitask learning offers a richer space of possible privacy requirements, because the learning framework allows for each person i to receive a different output g i . In this context, the natural privacy requirement is joint differential privacy (JDP). Here, we imagine that each individual i is given only their own model g i . For any non-trivial learning, g i must depend on individual i's dataset S i . However, we do not want an attacker who can observe other players' outputs to learn about individual I 's data set. So, we require that for every individual i, the collection of t ↗ 1 models g ↗i is differentially private as a function of the dataset S i belonging to individual i.
The above definition requires that S i is protected even if every other individual colludes and combines their models. We can also consider a relaxation of this definition called 1-out-of-t differential privacy where we do not allow individual's to collude. Here, we require that for every individual i, and for every other individual i ↔ i, the model g i ↔ given to individual i ↔ is differentially private as a function of the dataset S i belonging to individual i.
The majority of algorithms that satisfy joint differential privacy have a particular form, called a billboard algorithm. This concept is general, but we will describe it in the context of multitask learning. In a billboard algorithm, we decompose M into two phases M BB and M pers . M BB takes the training data S 1 ,..., S t and outputs a representation h, and then for each individual i, we give them (or they compute for themselves) the model g i = M pers (S i ,h). So far we have described billboard algorithms as a constraint on the structure of the algorithm. However, conceptually, we think of the representation h as being published, and thus publicly available, while the individual models g i are computed secretly by each individual and not published. Thus, when defining privacy for a billboard algorithm, we require that the algorithm M BB be differentially private. Any private billboard algorithm also satisfies joint DP.
Intuitively, there is a hierarchy of frameworks for private personalized learning: the easiest is multitask learning with 1-out-of-t-DP, then multitask learning with joint DP, then multitask learning with a private billboard algorithm, and finally the hardest is metalearning.
Technical Contributions. We prove a set of relationships among these frameworks for private personalized learning, which we now summarize.
DP metalearning and DP billboard multitask learning are equivalent. While metalearning can be much harder than multitask learning in general, we show that private multitask learning with billboard algorithms actually implies metalearning. In other words, we recover (a version of) the nonprivate equivalence of Aliakbarpour et al. (2024) when the multitask learner is constrained to produce a publicly visible representation. However, the proof of the implication is quite different. To gain some intuition for the argument, first observe that the syntax of algorithms for the two settings is similar: in both cases, we look at all the training datasets to produce a private representation h and then use an individual's data to specialize h to a model in an arbitrary non-private way. The difference lies in which learning objective we expect this representation to satisfy. We prove the implication using the connection between differential privacy and generalization (Dwork et al., 2014;Bassily et al., 2016;Ligett et al., 2017;Jung et al., 2020). Intuitively, in multitask learning, the billboard depends on the training tasks S 1 ,..., S t and produces a representation that can be specialized to one of those tasks. However, by privacy, the representation would have almost the same distribution if we had inserted data S t+1 from a fresh training task. Hence, the representation can also be specialized to this unseen test task as well. The formal result is stated and proved in §3.
Separating DP billboard multitask and DP met-alearning from JDP multitask learning. Our first main contribution is to show a separation between JDP multitask learning and billboard multitask learning for an estimation problem that we introduce. Since our models satisfy a hierarchy from easier to hardest, this result implies a separation between JDP multitask learning and metalearning as well. Such a result has no nonprivate analogue since, absent a privacy constraint, multitask learning implies metalearning (Aliakbarpour et al., 2024). Perhaps not surprisingly, the nonprivate equivalence is inherently privacy-violating-it uses the concatenation of the training data sets as the "representation".
We prove the separation using what we call the indexed mean estimation problem. Here, each training datum has the form (x, j) where x ↑ {±1} d is a vector and j ↑ [d] is an index of a coordinate in the vector. For a task P, which is a distribution over pairs (x, j), the goal is to output an estimate of the mean of the jth coordinate E (x,j)→P [x j ] low mean squared error. In the multitask learning problem, we will consider ttuples of tasks with the following constraints: (1) For every individual task P i , the marginal distribution of the vector x is identical. (2) For every individual task P i , the marginal distribution of j is deterministic. Under these assumptions, the x part of the distribution has some common mean vector p and and each individual has their own j i , and they want an estimate of p j i .
Our separations show that DP billboard algorithms for this problem have much higher loss than general JDP algorithms, when the dimension d is larger than the number t of individuals. Intuitively, a JDP algorithm can simply give a private estimate of p j i to each individual, which is obtained by averaging x j i over all individuals and adding noise. Since we only compute t values in total, the noise variance can be proportional to t. In contrast, a billboard DP algorithm cannot depend on the specific values j i held by each individual, and thus the billboard must contain enough information to estimate p j for most coordinates j. Since the billboard must estimate every coordinate, it must add noise proportional to d. This last statement follows by adapting the lower bounds of Bun et al. (2014); Dwork et al. (2015) for marginal estimation.
Separating 1-out-of-t DP from JDP. We also use the indexed mean estimation problem to separate 1-outof-t and JDP. In JDP, an attacker sees estimates of t ↗ 1 distinct coordinates of p, while in 1-out-of-t DP, each individual gets just a single coordinate of p so privacy intuitively requires much less noise.
Our results for indexed mean estimation are summarized in Table 1, and stated formally in Section 4.
Separating DP billboard and JDP for classification. The separation above applies for an estimation (unsupervised learning) problem. We also extend our results to prove a separation for a binary classification (supervised learning) problem that we call indexed classification. In this problem, each task is a distribution over labeled examples ((x, j),y) where
and y ↑ {±1}. Our goal is to produce a classifier that predicts y while minimizing the excess classification error. We consider distributions in which y is strongly correlated with x j but uncorrelated with other coordinates of x. We set these distributions up in such a way that finding a good classifier essentially requires estimating the mean of x j . From here, we proceed similarly to indexed mean estimation. We give a careful argument that a DP billboard must estimate the mean vector of x, denoted p, but a JDP algorithm can get away with estimating the mean of a only small number of coordinates of p, and thereby introduce less noise. This argument is more complex than for indexed mean estimation, since a good billboard algorithm only implies good estimates of the sign of each coordinate of p. We overcome this by showing that even this simpler problem is hard under differential privacy, via a novel extension of the fingerprinting technique (Bun et al., 2018;Dwork et al., 2015).
Our results for indexed classification are summarized in Table 1. See §5 for formal statements.
Without privacy constraints, there is a large body of literature on both multitask learning and metalearning, including related concepts or alternative names such as transfer learning, learning to learn, and few-shot learning, which is too vast to survey here. Another related learning framework is collaborative learning (Blum et al., 2017), which considers multitask classification in a setting where each task has a different marginal distribution on features but there exists a single good labeling function for every task.
There is also related work looking at privacy for model personalization. The most directly related work is that of Jain et al. (2021), together with predecessors on private recommender systems (e.g. Mc-Sherry and Mironov (2009)), which fits into our framework of JDP multitask learning. Krichene et al. (2023) consider a private multitask learning setting where each individual can contribute data to one task, as opposed to our framework in which tasks perfectly correspond to individuals. Li et al. (2020) also present a taxonomy of frameworks for multitask and metalearning, but their focus is on more specialized learning procedures than those we consider in our work. Räisä et al. (2024) address a different metalerning scenario, aiming to obtain models that are private with respect to all the individuals' data by doing metalearning where the model is first trained on simulated data and then specialized to the real data that requires protection.
Private model personalization has some similarities to federated learning (see the survey in Kairouz et al. (2019)), in which the data for each task is stored on a different device, with devices coordinated by a central server, and we want the server to obtain a single good model while minimizing what they can learn about the training data. Federated learning refers to a distributed system architecture and not a particular learning objective or privacy model. The objective may still be to solve a single learning problem, and there are not necessarily any privacy constraints at all. The concept of joint differential privacy was introduced in Kearns et al. (2014). Our notion of 1-out-oft DP is also called marginal differential privacy (Kannan et al., 2018). The majority of JDP algorithms use the billboard model, which was first formally defined in Hsu et al. (2014), but was used implicitly in McSherry and Mironov (2009); Gupta et al. (2010).
Our lower bound arguments are based on the fingerprinting methodology that was introduced in Ullman (2013); Bun et al. (2014) and further refined in Dwork et al. (2015). In particular we use (and prove extensions of) the so-called fingerprinting lemmas from Bun et al. (2017);Peter et al. (2024). See Kamath and Ullman (2020) for a partial survey.
We now present the formal definitions of privacy that we utilize throughout the paper. First we present the definition of standard (central) differential privacy, which is the natural privacy notion for billboard algorithms and for metalearning, as both of these produce a single public output.
Table 1: Asymptotic bounds on the squared-error for Indexed Mean Estimation and excess error for Indexed Classification (assuming t ↘ d and n constant). Here (ϑ, ϖ) are the privacy parameters, and we assume ϑ ↓ 1 and ϖ = 1/poly(t) for simplicity.
Learning Objective Indexed Mean Estimation Indexed Classification Upper Bound Lower Bound Upper Bound Lower Bound Nonprivate baseline
Definition 2.1 (Differential Privacy (Dwork et al., 2006;Bun and Steinke, 2016)). A randomized algorithm M : Z t ⇐ O satisfies the following differential privacy notions at the person level if, for any pair of
Intuitively, differential privacy protects against an adversary from inferring any person i's input even if the adversary knows all the other peoples' inputs as well as the algorithm output. We will say that a billboard algorithm is differentially private if the output of the curator is differentially private.
Next we consider different models of privacy for algorithms that may produce different outputs for different people. The definitions protect against an adversary who is trying to infer the input of some person i and who gets all other t ↗1 inputs as well as some outputs of the mechanism. We consider other privacy requirements that vary according to what we assume to be visible to an attacker (corresponding to weaker or stronger privacy guarantees).
Joint DP First, we define Joint DP, where the adversary gets all outputs except the secret person's output. Definition 2.2 (Joint Differential Privacy (Kearns et al., 2014)). A randomized algorithm M : Z t ⇐ O t satisfies (ϑ, ϖ)-JDP if for all people i ↑ [t], all pairs of neighboring datasets for person i S i ,S ↔ i ↑ Z, all datasets for everyone else S ↗i ↑ Z t↗1 , and all E ⇑ O t↗1 , P [M(S i ; S ↗i ) ↗i ↑ E] ↓ e ϑ P M(S ↔ i ; S ↗i ) ↗i ↑ E + ϖ If the analogous definition holds with D ε
1-out-of-t DP We also consider a weaker privacy requirement in which the adversary only sees one person's output (not the secret person's). We call this 1-out-of-t differential privacy (instead of marginal DP (Kannan et al., 2018)).
all pairs of neighboring datasets for person i S i ,S ↔ i ↑ Z, all datasets for everyone else S ↗i ↑ Z t↗1 , and all E ⇑ O,
For further details about our notation and preliminaries see Appendix A.
In this section, we present a general reduction from multitask learning to metalearning. Suppose P (t) denotes the set of all t-tuples that an algorithm M multitask learns. Without loss of generality, we assume that P (t) is closed under permutation. For any tuple in P (t) , an unseen task could be a similar one that can be swapped with any of the t tasks, and the new tuple would still remain in the domain. We can apply metalearning to this set of tasks. In other words, consider a distribution Q over exchangeable tuples of length t + 1. Let Q (t) be the marginal distribution over t-tuples of distributions obtained by taking the first t distributions from a (t + 1)-tuple drawn from Q. If P (t) contains all the t-tuples of distributions that are in the support of Q (t) , then M can metalearn as well. We formalize this argument in the following theorem (proven in Appendix B). The proof relies on Lemma A.5, which requires that the post-processing function (the loss) to be bounded.
Theorem 3.1. Fix parameters ε > 0, ϑ > 0, ϖ ↑ (0, 1), t ↑ N, n ↑ N, a loss function ω taking values in [0, 1], and a distribution Q over (t + 1)-tuples of exchangeable distributions. Assume P (t) is a set of t-tuples of distributions that contains all the t-tuples of distributions in the support of Q (t) (as defined above). Let M = (M BB , M pers ) be an (ϑ, ϖ)-DP billboard algorithm. If M multitask learns P (t) with t tasks and n samples per task with expected error ε, then M also metalearns Q with t training tasks, n samples per training task, and n personalization samples, with expected error at most e ϑ ε + ϖ.
In this section we showcase how different frameworks for private personalization impact the error achieved by a learning algorithm in an estimation problem. The proofs are provided in Appendix C.
For simplicity, we first describe the multitask learning version of the estimation problem we focus on. Every person i in [t] gets n samples drawn from distribution P X over domain {±1} d and an index
Person i aims to find an estimate, pj i , for the true mean of the j i -th coordinate in distribution P X , denoted by p j i . Their loss function is defined as the squared difference between the mean estimate for coordinate j i and its true mean:
(where the 1 4 factor keeps the loss in [0, 1]). To cast this problem in the language of multitask learning, as in Definition 1.1, we can think of the equivalent setting where the input of each person comes from a distribution P i . Instead of assuming that each person has n i.i.d. samples from a shared P X and an index j i , we define P i to be the Cartesian product of P X and a singleton distribution on {j i }. In this new setting, the input of person i is n samples drawn from P i .
We define the domain of t-tuples of distributions for t people that use the same feature distribution P X , but potentially different indices as the following
where P X (p) is the distribution P X with mean p and Det(j i ) deterministically returns j i .
We establish upper bounds for indexed mean estimation in the multitask learning frameworks. All three bounds result from applying the Gaussian mechanism to the empirical means with variance adjusted according to the privacy requirements.
Proposition 4.1 (Nonprivate upper bound). For any d ↑ N and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error 1/4t with t tasks and one sample per task . Theorem 4.2 (1-out-of-t upper bound). For any ϱ ↙ 0, d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error 1 2ϱt 2 + 1 4t with t tasks and one sample per task and satisfies ϱ-1out-of-t-zCDP. Furthermore, for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, and t ↑ N, there exists an algorithm that multitask learns P est,d,t with error ω(min(ϑ, ϑ 2
with t tasks and one sample per task, and satisfies (ϑ, ϖ)-1-out-of-t-DP.
Theorem 4.3 (JDP upper bound). For any ϱ ↙ 0, d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error O( 1 ϱt ) + 1 4t with t tasks and one sample per task and satisfies ϱ-JCDP. Moreover, for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error ω(min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 ) • 1 t + 1 4t with t tasks and one sample per task, and satisfies (ϑ, ϖ)-JDP.
Theorem 4.4 (Billboard upper bound). For any ϱ ↙ 0,d ↑ N,t ↑ N and for loss function ω mean , there exists a billboard algorithm that multitask learns P est,d,t with error d 2ϱt 2 + 1 4t with t tasks and 1 sample per task and satisfies ϱ-zCDP. Moreover, for any ϑ > 0,ϖ ↑ (0, 1),d ↑ N,t ↑ N and for loss function ω mean , there exists an algorithm in the billboard model that multitask learns P est,d,t to error ω(min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 ) • d t 2 + 1 4t with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-DP.
This problem can easily be extended to metalearning for a metadistribution over P est,d,t+1 with t training tasks and a test task with loss function ω mean . Theorem 4.4, combined with our general reduction from metalearning to multitask learning in Theorem 3.1, also implies the existence of a metalearning algorithm within the billboard model.
For any ϑ > 0,ϖ ↑ (0, 1),d ↑ N,t ↑ N and for loss function ω mean , there exists a pair of algorithms (M meta , M pers ) that metalearn a distribution Q over P est,d,t+1 with error ω(e ϑ
•min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 )• d t 2 + e ϑ 4t +ϖ using t training tasks, one sample per training task and a test task with one personalization sample and M meta satisfies (ϑ, ϖ)-DP.
Next, we formally separate the privacy frameworks in the multitask setting by proving a number of lower bounds. The proofs for the JDP multitask lower bound and the metalearning lower bound use the fingerprinting lower bound for private mean estimation. Specifically, we adapt the tracing attack used in the proof of the standard lower bound to each of our threat models.
for a sufficiently large constant, ϑ > 0 and ϖ ↑ (0, 1 96t ). Let ω mean be the loss function. Let M be an algorithm that multitask learns P d,t with error ε with t tasks and one sample per task and satisfies (ϑ, ϖ)-JDP.
Let ω mean be the loss function. Let M = (M meta , M pers ) be a pair of algorithms that metalearn a distribution Q over P est,d,t+1 with error ε with t training tasks, one sample per training task and a test task with one personalization sample and M meta satisfies (ϑ, ϖ)-JDP. Then, ε ↙ ε(min{ d ϑ 2 t 2 , 1}). For the multitask learning lower bound in the billboard model, we use Theorem 3.1 to reduce to the metalearning lower bound in Theorem 4.7.
) and d ↙ ct for a sufficiently large constant c. Let ω mean be the loss function. Let M be a billboard algorithm that multitask learns P d,t with error ε with t tasks and one sample per task, and satisfies
In this section, we characterize the error achievable on a classification problem in different private personalization frameworks. For the proofs of the results presented here see Appendix D.
Every individual i has an index j i ↑ [d] and n labeled samples
where p is a parameter of the data distribution that is the same among individuals. For a fixed vector p = (p 1 ,..., p d ) in [↗1, +1] d and an index j ↑ [d], we define R p,j as the distribution on the outcome of the following sampling process. First, draw an auxiliary random variable w ↑ {±1} d from a product of d independent distributions with mean p. Then, draw y ↑ {±1} uniformly. Finally, construct x as follows
Individual i's goal is to use these samples, and in cooperation with other individuals learn a classifier of the form fi (x j i ) : {±1} ⇐ {±1} that predicts labels y as correctly as possible using only the j i -th feature.
Depending on the output structure of the algorithm, fi might be sent as a private message from the curator or it might be calculated locally by individual i using the representation broadcasted by the curator. The loss function of individual i is the difference between the misclassification error of fi and the optimal classifier for distribution R j i :
where the probability is taken over (x, y) → R p,j i .
We cast this problem in the "multitask learning" language of Definition 1.1 and specify the connection between the data distributions by considering that every individual has n copies of index j i and that the n samples come from the following family of t-tuples of distributions
In this definition, for all P i that are in the same tuple, the distributions over the features, R p,j i are parameterized by the same p. However, the P i s can potentially have different j i s for different people. For convenience we write (x, j, y) → P i , instead of (x, y, j).
We first prove upper bounds on the indexed classification problem by reducing to and from a related learning problem called indexed sign estimation (see Appendix D for details), encoding the sign estimation problem into a mean estimation problem, and finally applying the upper bounds from Section 4 for indexed mean estimation.
Lemma 5.1 (Non-private upper bound). For any d ↑ N and t ↑ N, and loss function ω class , there exists an algorithm that multitask learns P class,d,t with error 1 ≃ t with t tasks and 1 sample per task. Theorem 5.2 (1-out-of-t upper bound). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error
with t tasks and 1 sample per task and satisfies ϱ-1-out-of-t-zCDP. Moreover, it is implied that for any parameters ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error ω(min(ϑ,
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-1-out-of-t-DP.
Theorem 5.3 (JDP upper bound). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N, and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error O( 1
with t tasks and 1 sample per task, and satisfies ϱ-JCDP. Moreover, it is implied that for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N, and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error ω(min(ϑ,
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-JDP.
Theorem 5.4 (Billboard upper bound). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N, and for loss function ω class , there exists a billboard algorithm that multitask learns P class,d,t with error
with t tasks and 1 sample per task, and satisfies ϱ-zCDP. Moreover, it is implied that for any parameters ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N, and for loss function ω class , there exists a billboard algorithm that multitask learns P class,d,t with error ω(min(ϑ,
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-DP.
Finally, Theorem 5.4 and the reduction of metalearning to multitask learning in Theorem 3.1 imply that there exists a mealearning algorithm whose metalearning process is differentially private.
and for loss function ω class , there exists a pair of algorithms (M meta , M pers ) that metalearn a metadistribution Q over P class,d,t+1 with error ω(e ϑ • min(ϑ, ϑ 2 /log(1/ϖ)) ↗1/2 ) • ≃ d t + e ϑ ≃ t + ϖ with t training tasks, 1 sample per training task and a test task with 1 personalization sample and M meta satisfies (ϑ, ϖ)-DP.
We also prove lower bounds for the error of indexed classification that separate the interaction and privacy models in the multitask learning setting. We initially prove lower bounds for indexed sign estimation (defined in Appendix D) using our finger-printing lemma. Finally, we prove the lower bounds for indexed classification by using a reduction of indexed sign estimation to indexed classification.
Theorem 5.6 (classification JDP lower bound). Fix ε ↑ (0, 1 16 ), t ↑ N, d ↙ ct 2 for a sufficiently large constant c, ϑ > 0 and ϖ ↑ (0, 1 2t ). Let M be an algorithm that multitask learns P class,d,t with error ε, for loss function ω class , with t tasks and 1 sample per task, and satisfies
Theorem 5.7 (Metalearning lower bound). Fix ε ↑ (0, 1 8 ), t ↑ N, d ↑ N, ϑ ↑ (0, 1] and ϖ ↑ (0, 1 2t ). Let M = (M meta , M pers ) be a pair of algorithms that metalearn a distribution Q over P class,d,t+1 with error ε, for loss function ω class , using t training tasks, 1 sample per training task and a test task with 1 personalization sample, and M meta satisfies (ϑ, ϖ)-DP. Then,
Let M be a billboard algorithm that multitask learns P class,d,t with error ε, for loss function ω class , with t tasks and 1 sample per task and satisfies (ϑ, ϖ)-DP. Then, ε ↙ ε(min{
Our work gave a taxonomy of formal frameworks for private personalized learning and proved separations and equivalences between these frameworks.
Our work leaves open several future directions. First, can we more thoroughly understand what types of relationships between tasks yield separations? In our separations for classification, we assume that the x part of the data points of all participating individuals is drawn from the same distribution. A natural follow-up question is what upper bounds can be achieved with privacy when the distributions of the individuals are related in more realistic ways. Second, can we relate private multitask learning to learning from a combination of public and private data. From an individual's perspective, private multitask learning can be viewed as a form of public-private learning, where their own samples are treated as public and the samples of others as private. These samples must be used in a specific order, first the private samples and then the public ones. Investigating how this perspective can lead to new algorithms for private multitask learning would be an interesting direction for future research. Conference on Innovations in Theoretical Computer Science, ITCS '14, pages 403-410, Princeton, NJ. ACM. Krichene, W., Jain, P., Song, S., Sundararajan, M., Thakurta, A. G., and Zhang, L. (2023). Multi-task differential privacy under distribution skew. In International Conference on Machine Learning, pages 17784-17807. PMLR. Li, J., Khodak, M., Caldas, S., and Talwalkar, A. (2020). Differentially private meta-learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, S. Z. (2017). Accuracy first: Selecting a differential privacy level for accuracy constrained erm. In Advances in Neural Information Processing Systems 30, NIPS '17, pages 2566-2576. McSherry, F. and Mironov, I. (2009). Differentially private recommender systems: Building privacy into the netflix prize contenders. In ACM SIGKDD international conference on Knowledge discovery and data mining, pages 627-636. Peter, N., Tsfadia, E., and Ullman, J. (2024). Smooth lower bounds for differentially private algorithms via padding-and-permuting fingerprinting codes. In Conference on Learning Theory, COLT '24, pages 4207-4239. PMLR. Räisä, O., Markou, S., Ashman, M., Bruinsma, W. P., Tobaben, M., Honkela, A., and Turner, R. E. (2024). Noise-aware differentially private regression via meta-learning. In Globersons, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J. M., and Zhang, C., editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 -15, 2024. Steinke, T. A. (2016). Upper and Lower Bounds for Privacy and Adaptivity in Algorithmic Data Analysis. PhD thesis. Ullman, J. (2013). Answering n 2+o(1) counting queries with differential privacy is hard. In ACM Symposium on the Theory of Computing, STOC '13. Checklist 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Yes] (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Not Applicable] 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results.
[Yes] (c) Clear explanations of any assumptions.
[Yes]
3. For all figures and tables that present empirical results, check if you include:
(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Not Applicable] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen).
[Not Applicable] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times
). [Not Applicable] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Not Applicable] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if applicable. [Not Applicable] (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]
A PRELIMINARIES Definition A.1 (Rényi Divergence). For two probability distributions P and Q defined over the same domain, the Rényi divergence of order ε > 1 is
, the tuple (P ς(1) ,..., P ς(t) ) is equally likely to occur in Q as the unpermuted one. When the metadistribution is clear from the context, we simply refer to the tuple as exchangeable.
Definition A.3 (Sensitivity). A function q : X n ⇐ R d has sensitivity ϑ if for all x, x ↔ ↑ X n differing in a single entry, we have ⇔q(x) ↗ q(x ↔ )⇔ 2 ↓ ϑ.
Fact A.4 (Gaussian Mechanism for zCDP (Bun and Steinke, 2016)). Let q : X n ⇐ R d be a sensitivity-ϑ query. Consider the mechanism M : X n ⇐ R d that on input x, releases a sample from N (q(x), I d ϕ 2 ). Then, M satisfies (ϑ 2 /2ϕ 2 )-zCDP.
-zCDP, then M satisfies (ϑ, ϖ)-DP.
Lemma A.7 (Birthday Paradox). Suppose we toss t balls uniformly at random into d bins. If d ↙ ct 2 for a sufficiently large constant c, the probability of any two balls falling into the same bin is at most 1 2 .
Theorem 3.1 (Restated). Fix parameters ε > 0, ϑ > 0, ϖ ↑ (0, 1), t ↑ N, n ↑ N, a loss function ω taking values in [0, 1], and a distribution Q over (t + 1)-tuples of exchangeable distributions. Assume P (t) is a set of t-tuples of distributions that contains all the t-tuples of distributions in the support of Q (t) (as defined above). Let M = (M BB , M pers ) be an (ϑ, ϖ)-DP billboard algorithm. If M multitask learns P (t) with t tasks and n samples per task with expected error ε, then M also metalearns Q with t training tasks, n samples per training task, and n personalization samples, with expected error at most e ϑ ε + ϖ.
Proof. We focus on the error of M in the metalearning framework. As we have described the error in Definition 1.2, the error of this algorithm corresponds to its performance on the t + 1-st distribution. More
precisely, we have: E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P t+1 , M pers (S t+1 , M BB (S 1 ,..., S t )) .
We know that the distributions in the tuple that we draw from Q are exchangeable, so the distribution of (t+1)tuples of distributions remains identical when we swap P t+1 with any P i . Therefore, in the metalearning error of M we can swap P t+1 ,S t+1 with any P i ,S i for i ↑ [t]. Let D be the datasets of the first t people, D = (S 1 ,...,S t ), and D ↗i be the t datasets from D after we swap the dataset of person i, S i , with the dataset of person t + 1, S t+1 . Thus, we have that E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P t+1 , M pers (S t+1 , M BB (D)) = 1 t i↑[t] E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P i , M pers (S i , M BB (D ↗i )) .
The error term in the equation above is analogous to the error term in the multitask learning algorithm, with one key distinction. In multitask learning, the i-th error term is computed when S i is included in the dataset provided to M BB . We demonstrate that these two terms are closely related due to the privacy properties of the server's algorithm.
For every individual i ↑ [t], D and D ↗i are neighboring datasets that differ only by the replacement of one person's data. Consequently, the privacy of M BB ensures that M BB (D) and M BB (D ↗i ) are nearly indistinguishable in distribution. It is well established that post-processing does not alleviate this indistinguishability. That is, for any function applied to M BB (D) and M BB (D ↗i ), the resulting outputs remain indistinguishable. Specifically, for each individual i ↑ [t], given a fixed distribution P i and dataset S i , let g i (b) be a post-processing function. g i (b) = E M pers ω(P i , M pers (S i ,b)) . (2) We apply Lemma A.5 for function g i and obtain that E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P i , M pers (S i , M BB (D ↗i )) ↓ e ϑ • E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P i , M pers (S i , M BB (D)) + ϖ Therefore, the error of M in the metalearning setting is bounded by 1 t i↑[t] E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P i , M pers (S i , M BB (D ↗i )) ↓ e ϑ 1 t i↑[t] E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ω(P i , M pers (S i , M BB (S 1 ,..., S t ))) + ϖ.
In the second line, the billboard message is computed using data drawn from tasks 1 to t. This equation captures the multitask learning error for the first t tasks drawn from Q. Alternatively, this tuple is drawn from
, making it a member of P (t) . Given the assumptions of the theorem-that M is a billboard algorithm that multitask learns P (t) with an error bound of ε-it follows that for all (P 1 ,..., P t ) ↑ P (t) , we have the following:
S t →P n t ω(P i , M pers (S i , M BB (S 1 ,..., S t ))) ↓ ε. (3) Combining the inequalities above we obtain that E M pers ,M BB , (P 1 ,...,P t+1 )→Q, S 1 →P n 1 ,...,S t →P n t ,S t+1 →P n t+1 ω(P t+1 , M pers (S t+1 , M BB (S 1 ,..., S t )) ↓ e ϑ ε + ϖ. Thus, the proof is complete. C PROOFS FROM SECTION 4 C.1 Upper bound proofs Proposition 4.1 (Restated). For any d ↑ N and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error 1/4t with t tasks and one sample per task .
Proof. The algorithm takes as input one sample (x (i) ,j (i) ) drawn from P i for every person i ↑ [t] and then computes the empirical mean p ′ 1 t i↑ [t] x (i) . Note that for all ω ↑ [t] and j ↑ [d], x (ω) j is independent of the other coordinates and (x (ω) j ) 2 = 1. Therefore, the error is
x (ω)
Var x
(ω)
Theorem 4.2 (Restated). For any ϱ ↙ 0, d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error 1 2ϱt 2 + 1 4t with t tasks and one sample per task and satisfies ϱ-1-outof-t-zCDP. Furthermore, for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, and t ↑ N, there exists an algorithm that multitask learns P est,d,t with error ω(min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 ) • 1 t 2 + 1 4t with t tasks and one sample per task, and satisfies (ϑ, ϖ)-1-out-of-t-DP.
Proof. We propose the following algorithm, which begins with the empirical mean and produces a private version of the mean for the coordinate of each person i ↑ [t] using the Gaussian mechanism. More precisely, the personalized output for person i with index j i is
ϱt 2 . To show that this algorithm satisfies ϱ-1-out-of-t-zCDP, fix a pair of distinct people i j and focus on the personalized outputs received by person k while replacing the input dataset of person i with a neighboring one. Since each person has a dataset of only one sample (i.e., n = 1), two neighboring datasets correspond to having two different samples. Now, if we change the sample of person i, the sensitivity of the mean at index j k , corresponding to the output of person k, is bounded by
Thus, using Gaussian mechanism as outlined in Fact A.4, pj k satisfy ϱ-zCDP for all distinct i and k. Therefore, our algorithm satisfies ϱ-1-out-of-t-zCDP.
Next, we analyze the error of our estimates. Since the Gaussian noise and the sampled data are independent, we have 1 4t
The last inequality follows from the error analysis in the proof of Theorem 4.1. Using the standard conversion between zCDP and approximate DP, from Fact A.6, we show that this algorithm also satisfies (ϑ, ϖ)-DP by setting ϱ = ω max 1 ϑ ,
.
Theorem 4.3 (Restated). For any ϱ ↙ 0, d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error O( 1 ϱt ) + 1 4t with t tasks and one sample per task and satisfies ϱ-JCDP. Moreover, for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, and t ↑ N, and loss function ω mean , there exists an algorithm that multitask learns P est,d,t with error ω(min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 ) • 1 t + 1 4t with t tasks and one sample per task, and satisfies (ϑ, ϖ)-JDP.
Proof. Here, for each person i with index j i , the algorithm returns an estimate
where
ϱt 2 . This satisfies ϱ-JCDP because the global ω 2 sensitivity of the outputs given to the t ↗ 1 colluding people ( pj 1 ,..., pj t↗1 ) is 2 ≃ t↗1 t . Hence, on average over the t people participating
Theorem 4.4 (Restated). For any ϱ ↙ 0,d ↑ N,t ↑ N and for loss function ω mean , there exists a billboard algorithm that multitask learns P est,d,t with error d 2ϱt 2 + 1 4t with t tasks and 1 sample per task and satisfies ϱ-zCDP. Moreover, for any ϑ > 0,ϖ ↑ (0, 1),d ↑ N,t ↑ N and for loss function ω mean , there exists an algorithm in the billboard model that multitask learns P est,d,t to error ω(min(ϑ, ϑ 2 /log(1/ϖ)) ↗1 ) • d t 2 + 1 4t with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-DP.
Proof. The billboard algorithm runs the Gaussian mechanism once and broadcasts the output to all the people. Then every person can use their index j i to get the estimate they are interested in. More specifically, the algorithm takes as input one sample (x (i) ,j (i) ) drawn from P i from every person i and then computes an empirical mean p 1 t i↑ [t] x (i) and outputs on the billboard p ′ p + Z, where Z → N 0, 2d
(4)
The global ω 2 sensitivity of p is 2 ≃ d t , so this satisfies ϱ-zCDP and, consequently, ϱ-JCDP. To analyze the error, by symmetry it suffices to analyze person i. Since sampling the data and the Gaussian noise are independent, we have
We have Var Z j i = d 2ϱt 2 and Var pj i ↗ p j i ↓ 1 t . Summing these variances gives you that the total error is 1 4t
.
Using the standard conversion between zCDP and approximate DP, from Fact A.6, we show that this algorithm also satisfies (ϑ, ϖ)-DP by setting ϱ = ω max 1 ϑ ,
Theorem 4.6 (Restated). Fix ε > 0, t ↑ N, d ↙ ct 2 for a sufficiently large constant, ϑ > 0 and ϖ ↑ (0, 1 96t ). Let ω mean be the loss function. Let M be an algorithm that multitask learns P d,t with error ε with t tasks and one sample per task and satisfies (ϑ, ϖ)-JDP. Then, ε ↙ ε(min{ 1 ϑ 2 t , 1}).
Proof. For the proof of Theorem 4.6 we follow a series of steps similar to that presented in Kamath and Ullman (2020), which itself closely follows the presentation in Steinke (2016).
We have a JDP algorithm on t tasks/people and d dimensions. Each person i ↑ [t], has a sample (x (i) ,j (i) ) ↑ {±1} ∝ [d] and gives it as input to the algorithm. Let S = {(x (i) ,j (i) )} i↑ [t] denote this dataset. We will construct a hard distribution over the family of distributions P d,t that the samples are drawn from. We draw a vector p ↑ [↗1, +1] d and a vector j ↑ [d] t , both uniformly at random. The datapoint x (i) of person i is drawn from the product distribution with mean p and the index j (i) is deterministically j i . Let the expected error of M be
Our goal now is to prove a lower bound on ε.
We will analyze the case where j has no duplicated indices. So for now we assume that we have a fixed j with no repeats. For person i we define two test statistics
where p↔ j ω denotes the output of algorithm M to person ω for input S →i where x (i) ,j (i) has been replaced with a fresh draw x (i) ↔ ,j (i) ↔ from P i . Since the distribution over the indices is deterministic, j (i) = j (i) ↔ = j i . Now, we will use the privacy guarantee of JDP to provide an upper bound for E p,S,M i↑[t] T i . Since M is (ϑ, ϖ)-JDP for any ϑ, ϖ in (0, 1), we have that { pj ω } ω↑[t]\i is (ϑ, ϖ)-DP with respect to i's dataset. As a result, the following inequality holds
For fixed p, j, and ω, p↔ j ω is independent of x (i)
This means that E T ↔ i = 0. We apply the same observation, that E x (i)
and that every coordinate is independent to show that the cross terms in the variance of T ↔ i cancel out, leaving us with
j ω ↗ p j ω ) 2 is at most 4, we have the upper bound
Plugging these into inequality 6 and summing up over all the t people, we obtain that
The next step is to show that accuracy implies a lower bound for E p,S,M i↑[t] T i . We notice that in the sum of T i we can rearrange the terms.
We can now apply Lemma D.6 to each coordinate j ω .
For a vector of indices j let ε j be the error
Combining the two inequalities for E i↑[t] T i we have shown that when J has no duplicates
If ε j ↓ t 6 , then 8ϖt 2 < t 12 because we have assumed that ϖ < 1 96t . By rearranging the terms in the inequality we see that
Thus, ε j ↙ min t 6 , 1 2304ϑ 2 . We now incorporate the randomness over the choice of j. Let E be the event that the vector of target indices has no duplicates. Since d ↙ ct 2 for a sufficiently large constant c, by Lemma A.7 event E occurs with probability at least 1 2 . Therefore,
For each j without duplicates we have a lower bound on ε j , so
) and d ↙ ct for a sufficiently large constant c. Let ω mean be the loss function. Let M be a billboard algorithm that multitask learns P d,t with error ε with t tasks and one sample per task, and satisfies (ϑ, ϖ)-JDP. Then, ε ↙ ε(min{ d ϑ 2 t 2 , 1}).
Proof. By Theorem 3.1 if we have a billboard algorithm for multitask learning with error ε, then we have metalearning algorithm with error e ϑ ε + ϖ. Then, by Theorem 4.7
We have made the assumption that d ↙ 16•144 11 t.
Let ω mean be the loss function. Let M = (M meta , M pers ) be a pair of algorithms that metalearn a distribution Q over P est,d,t+1 with error ε with t training tasks, one sample per training task and a test task with one personalization sample and M meta satisfies (ϑ, ϖ)-JDP. Then, ε ↙ ε(min{ d ϑ 2 t 2 , 1}).
Proof. We consider that the metalearning algorithm M meta takes as input 1 sample (x (i) ,j (i) ) per person i ↑ [t]. Then the personalization algorithm M pers gets as input the output of M meta and the sample of the (t + 1)-th person (x (t+1) ,j (t+1) ) and outputs an estimate pj (t+1) of the mean of coordinate j (t+1) . By the definition of P d,t+1 , the index of person t + 1 is deterministically j t+1 . Hence, we will write pj t+1 instead of pj (t+1) for simplicity.
To prove this theorem we construct a hard metadistribution Q where we draw a vector of means p ↑ [↗1, +1] d and a vector of indices j ↑ [d] t+1 both uniformly at random. Let the error of M be 4ε ↙ E M, (P 1 ,...,P t+1 )→Q,
x (1) ,...,x (t+1) ( pj t+1 ↗ p j t+1 ) 2 = E M, p,j 1 ,...,j t ,
x (1) ,...,x (t+1)
x (1) ,...,x (t+1)
We consider a tracing attack that uses the following test statistics for i ↑ [t]
and
where p↔ j denotes the output of algorithm M for j t+1 = j when the input of person i to M meta has been replaced with a fresh draw from P i . For i = t + 1 we construct only test statistic
Since M meta is (ϑ, ϖ)-DP with respect to i's dataset for every i ↑ [t], pj is (ϑ, ϖ)-DP with respect to the same dataset for every j ↑ [d]. Therefore,
We will now analyze each term of the right hand side of the inequality. We see that
because T ↔ i is the sum of d entries of value at most 4. Next, since p↔ j is independent of x (i) j conditioned on p, we get that
E M,j 1 ,...,j t x (1) ,...,x (t+1) ,x (i) ↔ ( p↔ j ↗ p j ) E
Finally, by the same observation the crosse terms in the variance of T ↔ i cancel out and we obtain that
Combining the inequalities above we conclude that
For the i = t + 1, we have that
Therefore, by summing up the test statistict
The next step is to show that accuracy implies a lower bound for the test statistics in terms of error ε. We apply Lemma D.6 to every coordinate j ↑ [d] of the estimate
Combining the bounds on E i↑[t+1] T i , we have the following inequality
If we rearrange the terms we get that
For the results of this section, we first prove a reduction to and from an estimation problem we call indexed sign estimation. We then obtain upper and lower bounds for the error of indexed sign estimation that imply bounds for indexed classification.
In the multitask learning version of indexed sign estimation there are t people and every person i ↑ [t] has n samples drawn from the same distribution P X over domain {±1} d and an index j i ↑ [d]. As in Section 4, P X is a product of d independent distributions over {±1} d with mean p ↑ [↗1, +1] d . Person i's goal is to estimate the sign ŝj i of the mean of coordinate j i . The error for person i is |p j i | if they make a wrong prediction of the sign of p j i and 0 otherwise. This means that they get penalized more for the sign of coordinates that have mean further from zero and are, thus, easier to predict. The loss function for person i is ω sign (P X , ŝj i ) I{sign(p j i ) ŝj i }|p j i |, where p j i is the true mean of coordinate j i and ŝj i is the sign estimate of person i. The overall error for multitask learning is
where the expectation is taken over the samples of the t people and the randomness of the algorithm. Following the same process as in Section 4 to cast this problem in the "multitask learning" language, we consider that every person draws n samples from a distribution P i that is in a t-tuple of distributions from family P est,d,t , as defined in Section 4.
We start by showing that we can reduce indexed classification to indexed sign estimation in the multitask learning framework, and vice versa.
Lemma D.1 (Reduction of indexed classification to indexed sign estimation). Fix a ↑ [0, 1]. Let M be an algorithm that multitask learns P est,d,t with error ε, for loss function ω + sign, with t tasks and 1 sample per task. Then, there exists an algorithm that multitask learns P class,d,t with error ε, for loss function ω class , with t tasks and 1 sample per task.
Proof. Let {(x (i) ,j (i) ,y (i) )} i↑ [t] be the input to the multitask classification algorithm that is drawn from a tuple of distributions (P (1) class ,...,P (t) class ) in P class,d,t . We can transform this dataset to an input dataset for algorithm M. For person i we can use j (i) = j i to recover the value of the auxiliary random variable w (i) as follows
ω y (i) , if ω = j (i) .
We see that the tuple of the t distributions (P
est ,..., P
est ) over (w (i) ,j (i) ) for all i ↑ [t] is in P est,d,t . For this reason, we give {(w (i) ,j (i) )} i↑ [t] as input to algorithm M. Let ŝj i be the output of M for person i. Then, for person i ↑ [t] the classification algorithm ouputs the labeling function fi (
The misclassification error of fi for distribution
The misclassification error of a fixed classifier f i for distribution
Given p j i , the function that minimizes this error is
Taking the difference between the misclassification error of fi and f ∞ i , we obtain that
Therefore, if we take the expectation of the error over the samples {(x (i) ,j (i) ,y (i) )} i↑ [t] and the randomness of algorithm M we have that the error of multitask learning for indexed classification is
This concludes our proof.
Lemma D.2 (Reduction of indexed sign estimation to indexed classification). Fix ε ↑ [0, 1]. Let M be an algorithm that multitask learns P class,d,t with error ε, for loss function ω class , with t tasks and 1 sample per task. Then, there exists an algorithm that multitask learns P est,d,t with error ε, for loss function ω est , with t tasks and 2 samples per task.
Proof. Let {(x (i,1) ,j (i,1) ), (x (i,2 ,j (i,2) )} be the dataset of task i ↑ [t] gives to the indexed estimation algorithm. Every sample (x (i,k) ,j (i,k) ), for k ↑ {1, 2}, is drawn from the corresponding distribution
est from a tuple of t distributions (P (1) est ,..., P
We first use one sample from every task/person to construct an input for algorithm M. For every person i we set w (i,1) ′ x (i,1) , draw a y (i,1) ↑ {±1} uniformly and set
We then give {( x(i,1) ,j (i,1) ,y (i,1) )} i↑ [t] as input to the classification algorithm M. Let P
class be the distribution of ( x(i,1)
,j (i,1) ,y (i,1) ). We notice that (P
class ,..., P
class ) is in the family of tuples P class,d,t . Let f1 ,... ft be the functions that M outputs for this input. Then, we use the second sample of person i, (x (i,2 ,j (i,2) ), and function fi to get the sign estimate ŝj i . In particular, we draw y (i,2) ↑ {±1} uniformly, we set w (i,2) ′ x (i,2) and x(i,2)
We see that
class is also the distribution of ( x(i,2) ,j (i,2) ,y (i,2) ). For person i this indexed estimation algorithm outputs ŝj i = fi ( x(i,2)
The next step is to compute the error of ŝj i . In the proof of Lemma D.1 we showed that for person i min
The misclassification error of fi is
We can see that x(i,2)
and we have that
Combining the these steps, we get that the difference of the misclassification error between fi and the optimal classifier is
The average error of the sign estimation algorithm, in expectation over the samples, the randomness of the input/output transformations and the randomness of algorithm M is
Privacy in Metalearning and Multitask Learning
Here we present the proofs of the upper bounds of the error of indexed classification for the different private personalization frameworks.
Proposition 5.1 (Restated). For any d ↑ N and t ↑ N, and loss function ω class , there exists an algorithm that multitask learns P class,d,t with error 1 ≃ t with t tasks and 1 sample per task.
Proof. Fix any d ↑ N, t ↑ N. By Proposition 4.1 there is an algorithm M that multitask learns P est,d,t with error
where pj i is the output of algorithm M to person i, with t tasks and 1 sample per task. We can use M to estimate the signs of the p j i s by setting ŝj i = sign( pj i ). In this case the error for indexed sign estimation is
By applying the reduction of Lemma D.1 we obtain that for all (P 1 ,..., P t ) ↑ P class,d,t
Theorem 5.2 (Restated). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error
with t tasks and 1 sample per task and satisfies ϱ-1-out-of-t-zCDP. Moreover, it is implied that for any parameters ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error ω(min(ϑ,
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-1-out-of-t-DP.
Proof. Fix any d ↑ N, t ↑ N, and ϱ ↙ 0. By Theorem 4.2 there exists a ϱ-1-out-of-t-zCDP algorithm M that multitask learns P est,d,t with error
with t tasks and 1 sample per task. In this algorithm the computes a mean estimate pj i that they send to person i. For the classification learning algorithm the curator can use pj i to construct an estimate of the sign of p j i by setting ŝj i = sign( pj i ) before sending anything to the people. Then, using the reduction of Lemma D.2 we get a function that the server can send to person i, by setting fi (x, j) = ŝj i x j i .
As fi is a post-processing of pj i that only uses j i , which is already in the dataset of person i, the output of this algorithm remains ϱ-1-out-of-t-zCDP. By Lemma D.1 we obtain that the error of of f1 ,..., ft is
Theorem 5.3 (Restated). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N, and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error O( 1
with t tasks and 1 sample per task, and satisfies ϱ-JCDP. Moreover, it is implied that for any ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N, and for loss function ω class , there exists an algorithm that multitask learns P class,d,t with error ω(min(ϑ,
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-JDP.
Proof. Fix any d ↑ N, t ↑ N and ϱ ↙ 0. Similarly to the proof above we can base our algorithm on the algorithm of Theorem 4.3. Our classification algorithm takes the mean estimate pj i for person i and produces fi (x j i ) = ŝj i x j i , with error
The new algorithm also satisfies ϱ-JCDP because the curator just post-processes the output of the ϱ-JCDP mean estimation multitask learning algorithm using only j i for person i, which is their personal information.
Theorem 5.4 (Restated). For any parameters ϱ ↙ 0, d ↑ N, t ↑ N, and for loss function ω class , there exists a billboard algorithm that multitask learns P class,d,t with error
with t tasks and 1 sample per task, and satisfies ϱ-zCDP. Moreover, it is implied that for any parameters ϑ > 0, ϖ ↑ (0, 1), d ↑ N, t ↑ N, and for loss function ω class , there exists a billboard algorithm that multitask learns P class,d,t with error
with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-DP.
Proof. By Theorem 4.4 there exists a billboard algorithm (M BB , M pers ) that multitask learns P est,d,t with t tasks and 1 sample per task, and M BB is ϱ-zCDP. Our classification algorithm keeps the billboard algorithm as it is and modifies the personalization part. In particular, person i takes their mean estimate pj i and produces fi (
where ŝj i = sign( pj i ). By applying the reduction of D.2 we get error
As we mentioned, the billboard part of the new algorithm remains the same. Thus, it still satisfies ϱ-zCDP.
Our error lower bounds for indexed classification are based on a generalization of the fingerprinting lemma by Bun et al. (2014). Our lemma differs in two ways; the mean p is drawn uniformly at random from an interval [↗ε, ε] for ε ↑ (0, 1] (instead of [↗1, 1]) and the error function is 2(|p| ↗ f (x))p = 4|p|I{f (x) sign(p)} (instead of the mean-squared-error). The key idea is that for a fixed ε a function f cannot be bad at predicting the sign of the p and highly correlated with the sum of samples drawn from a distribution with mean p at the same time. [↗ε, +ε] is sampled uniformly at random and x 1 ,..., x t ↑ {±1} t are sampled independently with mean p, then
We break the proof of our fingerprinting lemma into smaller lemmas following the proof in Bun et al. (2017).
Then,
Proof. We can write
where x 1 ,..., x t ↑ {±1} t are sampled independently with mean p. We can now compute its derivative [↗ε, +ε] is drawn uniformly at random, then
where
Similarly, we can show that when ε 2 = 1
Proof of Lemma D.3. Applying Lemmas D.4 and D.5 we have
We can show that the fingerprinting lemma in Bun et al. (2014) follows from our fingerprinting lemma for ε = 1.
Lemma D.6 (Fingerprinting Lemma Bun et al. (2014)). Let f :
] is sampled uniformly at random and x 1 ,..., x t ↑ {±1} t are sampled independently with mean p, then
Proof. We have that
The last inequality follows from Lemma D.3.
In this section we provide the proofs for the lower bounds of the error of indexed classification in the private personalization frameworks we consider. We first prove lower bounds for indexed sign estimation and then prove the corresponding lower bounds for indexed classification by using the reduction of Lemma D.2.
Lemma D.7 (Indexed sign estimation JDP lower bound). Fix parameters ε ↑ (0, 1/16), t ↑ N, ϑ > 0, ϖ ↑ (0, 1 2t ), and let ω sign be the loss function. Let M be an algorithm that multitask learns P est,d,t with error ε, for loss function ω sign , with t tasks and 2 samples per task and satisfies (ϑ, ϖ)-JDP. If d ↙ ct 2 for a sufficiently large constant c, then
Proof. Fix parameters ε ↑ (0, 1/16), t ↑ N, ϑ > 0, ϖ ↑ (0, 1 2t ). Let M be a JDP algorithm that gets as input the d-dimensional samples of t tasks/people. Each person i ↑ [t], gives samples (x (i,1) ,j (i,1) ), (x (i,2) ,j (i,2) ) to the algorithm. We start by constructing a hard distribution over the family of distributions P est,d,t that the samples are drawn from. We draw a vector p ↑ [↗↼, ↼] d for ↼ = 16ε and a vector j ↑ [d] t , both uniformly. The k-th datapoint x (i,k) of person i is drawn from the product distribution with mean p and the index j (i,k) is deterministically j i .
M returns an estimate ŝj i of the sign of p j i to each person i ↑
our goal is to prove a lower bound on ε.
We will first analyze the case where j has no duplicated indices. So for now we assume that we have a fixed j with no repeats. For person i ↑ [t] and sample k ↑ {1, 2} we define two test statistics
where ŝ(i,k) j ω denotes the output of algorithm M to person ω when the input x (i,k) ,j (i,k) if person i has been replaced with a fresh draw from P i . Since the distribution over the indices is deterministic, j (i,k) is always j i . Now, we will use the privacy guarantee of JDP to provide an upper bound for E i↑[t] (T i,1 + T i,2 ) . Since M is (ϑ, ϖ)-JDP, we have that { ŝj ω } ω↑[t]\i is (ϑ, ϖ)-DP with respect to i's dataset. As a result, the following inequality holds
This means that E T ↔ i,k = 0. We apply the same observation, that E x (i,k) j ω = p j ω , and that every coordinate is independent to show that the cross terms in the variance of T ↔ i,j cancel out, leaving us with
Since (x (i) j ω ↗ p j ω ) 2 is at most 4 and ( ŝ(i,k) j ω ) 2 = 1, we have the upper bound
Plugging these into inequality above and summing up over all the t people and k ↑ {1, 2}, we obtain that
The next step is to show that accuracy implies a lower bound for E i↑[t] (T i,1 + T i,2 ) . We notice that in the sum of T i we can rearrange the terms.
We can now apply Lemma D.3 to each coordinate j ω .
For vector of indices j let ε j be the error
Combining the two inequalities for E i↑[t] (T i,1 + T i,2 ) we have shown that when j has no duplicates
By rearranging the terms we get that
We now incorporate the randomness over the choice of j. Let E be the event that the set of target indices has no duplicates. Since d ↙ ct 2 for a sufficiently large constant c, by Lemma A.7 event E occurs with probability at least 1 2 . Therefore,
For each j without duplicates we have a lower bound on ε j , so substituting this bound for
Lemma D.8 (Indexed sign estimation metalearning lower bound). Fix parameters ε ↑ (0, 1 8 ), t ↑ N, ϑ ↑ (0, 1], ϖ ↑ (0, 1 2t ), and error function ω est . Let M = (M meta , M pers ) be a pair of algorithms that metalearn a metadistribution Q over P est,d,t+1 with error ε using t training tasks, 2 samples per training task and a test task with 2 personalization samples and M meta satisfies (ϑ, ϖ)-DP. Then, ε ↙ ε(min{1,
Proof. Fix parameters ε ↑ (0, 1 8 ), t ↑ N, ϑ ↑ (0, 1], ϖ ↑ (0, 1 2t ), and error function ω est . The metalearning algorithm M meta takes as input 2 samples (x (i,1) ,j (i,1) ), (x (i,2) ,j (i,2) ) per person i ↑ [t]. The personalization algorithm M pers gets as input the output of M meta and the two samples of the (t + 1)-th person (x (t+1,1) ,j (t+1,1) ), (x (t+1,2) ,j (t+1,2) ). It then outputs an estimate ŝj (t+1,1) of the sign of the mean of coordinate j (t+1,1) . By the definition of P est,d,t+1 , the index of person t + 1 in both samples is deterministically j t+1 . Hence, we will write ŝj t+1 instead of ŝj (t+1,1) for simplicity.
To prove this theorem we construct a hard metadistribution Q where we draw a vector of means p ↑ [↗↼, +↼] d , for ↼ = 8ε ↑ (0, 1) and a vector of indices j ↑ [d] t+1 both uniformly at random. Let the error of M be ε ↙ E M, (P 1 ,...,P t+1 )→Q,
x (1,1) ,x (1,2) ,...,x (t+1,1) ,x (t+1,2)
x (1,1) ,x (1,2) ,...,x (t+1,1) ,x (t+1,2)
x (1,1) ,x (1,2) ,...,x (t+1,1) ,x (t+1,2)
I{sign(p j ) ŝj }|p j | .
We construct a tracing attack that uses the following test statistics for i ↑
[t], k ↑ {1, 2} T i,k def = j↑[d] ↼ 2 ↗ p 2 j 1 ↗ p 2 j ŝj (x (i,k) j ↗ p j ) and T ↔ i,k def = j↑[d] ↼ 2 ↗ p 2 j 1 ↗ p 2 j ŝ(i,k) j (x (i,k) j ↗ p j ),
where ŝ(i,k) j denotes the output of algorithm M pers for j t+1 = j when the input (x (i,k) ,j (i,k) ) of person i to M meta has been replaced with a fresh draw from P i . For i = t + 1 we construct only test statistics
for k ↑ {1, 2}. Since M meta is (ϑ, ϖ)-DP with respect to i's dataset for every i ↑ [t], ŝj is (ϑ, ϖ)-DP with respect to the same dataset for every j ↑ [d]. Therefore, for k ↑ {1, 2}
We will now analyze each term of the right hand side of the inequality. We see that
j conditioned on p, we get that
↼ 2 ↗ p 2 j 1 ↗ p 2 j E j 1 ,...,j t x (1,1) ,...,x (t+1,2) ,x (i,k) ↔ ŝ(i,k)
Finally, by the same observation the cross terms in the variance of T ↔ i,k cancel out and we obtain that
Combining the inequalities above we conclude that
For the i = t + 1, we have that
Therefore, by summing up the test statistics T i,k
The next step is to show that accuracy implies a lower bound for the test statistics in terms of error ↼. We apply Lemma D.3 to every coordinate j ↑ [d] of the estimate
↼ ↗ E 4I{sign(p j ) ŝj }|p j | = d↼ ↗ 4dε.
Combining the bounds on E i↑[t+1] k↑{1,2} T i,k , we have the following inequality d↼ ↗ 4dε ↓ 8ϑ↼ 2 t ≃ d + 8ϖdt↼ 2 + 4↼ 2 d. By rearranging the terms and replacing ↼ with 8ε we have that ε ↙ 1 16 1 8ϑt ≃ d + 8ϖt + 4 . Since ϖ < 1 2t , ε ↙ 1 16 1 8ϑt ≃ d + 8 . Finally, if 8ϑt ≃ d ↓ 8, then ε ↙ ≃ d 16 2 ϑt . Otherwise, ε ↙ 1 16 2 . Therefore, we have shown that ε ↙ min ≃ d 16 2 ϑt , 1 16 2 Lemma D.9 (Indexed sign estimation billboard lower bound). Fix parameters t ↑ N, ϑ ↑ (0, 1], ϖ ↑ (0, 1 32 2 t ), d ↙ ϑ 2 t 4 . Let ω sign be the loss function . Let M be a billboard algorithm that multitask learns P est,d,t with error ε with t tasks and 2 samples per task and satisfies (ϑ, ϖ)-DP. Then, ε ↙ ε(min{ ≃ d ϑt , 1}). Proof. By Theorem 3.1 if we have a billboard algorithm for multitask learning with error ε, then we have a metalearning algorithm with error e ϑ ε + ϖ for metadistributions over P est,d,t+1 . Then, by Lemma D.8 e ϑ ε + ϖ ↙ min ≃ d 16 2 ϑt , 1 16 2 . If ≃ d 16 2 ϑt < 1 16 2 , then since ϖ < 1 32 2 t , d ↙ ϑ 2 t 4 , t ↙ 1, and ϑ ↓ 1, we have that ε ↙ 1 e ϑ ≃ d 16 2 ϑt ↗ ϖ (7) ↙ ≃ d e ϑ 2 • 16 2 ϑt ↙ ≃ d 6 • 16 2 ϑt . (8) If ≃ d 16 2 ϑt ↙ 1 16 2 , since ϖ < 1 32 2 t we get that ε ↙ 3 e ϑ 4 • 16 2 > 1 4 • 16 2 . Therefore, ε ↙ ε min 1, ≃ d ϑt Theorem 5.6 (Restated). Fix ε ↑ (0, 1 16 ), t ↑ N, d ↙ ct 2 for a sufficiently large constant c, ϑ > 0 and ϖ ↑ (0, 1 2t
). Let M be an algorithm that multitask learns P class,d,t with error ε, for loss function ω class , with t tasks and 1 sample per task, and satisfies (ϑ, ϖ)-JDP. Then, ε ↙ ε(min{ 1 ϑ ≃ t , 1}).
Proof. If there exists an (ϑ, ϖ)-JDP algorithm M that multitask learns P class,d,t with t tasks and 1 sample per task to error ε < min ≃ t 4•32ϑ , 1 64 , then by the reduction in Lemma D.1 we get that there exists a sign estimation algorithm that multitask learns P est,d,t with t tasks and 2 samples per task and has error ε < min ≃ t 4•32ϑ , 1 64 , for loss function ω sign . The algorithm we get from the reduction is also (ϑ, ϖ)-JDP due to post-processing. This contradicts the statement of Lemma D.7. Therefore, we get that ε must be at least min ≃ t 4•32ϑ , 1 64 .
Theorem 5.7 (Restated). Fix ε ↑ (0, 1 8 ), t ↑ N, d ↑ N, ϑ ↑ (0, 1] and ϖ ↑ (0, 1 2t ). Let M = (M meta , M pers ) be a pair of algorithms that metalearn a distribution Q over P class,d,t+1 with error ε, for loss function ω class , using t training tasks, 1 sample per training task and a test task with 1 personalization sample, and M meta satisfies (ϑ, ϖ)-DP. Then, ε ↙ ε(min{1,
Proof. We notice that a metadistribution Q class over P class,d,t+1 where we draw a vector of means p ↑ [↗↼, ↼] d , for ↼ ↑ (0, 1) and a vector of indices j ↑ [d] t+1 uniformly at random corresponds to metadistribution Q est over P est,d,t+1 where we draw p and j in the same way.
We will show that we can reduce metalearning for metadistribution Q est for indexed sign estimation with t training tasks, 1 sample per training task and a test task with 2 personalization samples to metalearning for the corresponding distribution Q class for indexed classification using t training tasks with 1 sample per task and a test task with 1 personalization samples by following the steps of the proof of Lemma D.2 with some small changes.
In indexed sign estimation, let (x (i) ,j (i) ) be the sample of individual i that is drawn from P We can transform every sample (x (i) ,j (i) ), for i ↑ [t] to a sample for indexed classification by setting w (i) ′ x (i) , drawing a y (i) ↑ {±1} uniformly and setting
The distribution of ( x(i) ,j (i) ,y (i) ) is P ,j (i) ,y (i) ), to the metalearning algorithm for indexed classification. Person t + 1 transform their two datapoints from {(x (t+1,1) ,j (t+1,1) )), (x (t+1,2) ,j (t+1,2) ))} to {( x(t+1,1)
,j (t+1,1) ,y (t+1,1) ), ( x(t+1,2) ,j (t+1,2) ,y (t+1,2) )} using the same procedure as the people with the training tasks. They then run the personalization part of that algorithm with sample ( x(t+1,1)
,j (t+1,1) ,y (t+1,1) ) and get a f (x j t+1 ) with error
E P (x,j,y)→P (t+1) class f (x j t+1 ) y ↗ min f P (x,j,y)→P (t+1) class f (x j t+1 ) y
where the expectation is taken over the t-tuple of classification distributions, the samples of the t training tasks, the randomness of the algorithm and the first sample of individual t + 1. Then, person t + 1 can get an estimate of the sign by postprocessing f using their second transformed sample ( x(t+1,2) ,j (t+1,2) ,y (t+1,2) ):
)
x(t+1,2)
.
Following the same calculations as in the proof of Lemma D.2 we get that E I{sign(p j t+1 ) ŝj t+1 }|p j t+1 | = E
where the expectation of the LHS of the equation is taken over the t-tuple of indexed sign estimation distributions, the initial samples of the t training tasks, the randomness of the algorithm we described and the two samples of individual t + 1. By Lemma D.8 we have that ε ↙ ε(min{1,
Privacy in Metalearning and Multitask Learning
We do not constrain the form of h in any way, and use "representation" to mean any summary of the training data that can be specialized to future tasks. In fact, if privacy were not a concern, the representation could consist of raw training data.