Differentially Private Model Personalization
Year: 2022

Abstract:
We study personalization of supervised learning with user-level differential privacy. Consider a setting with many users, each of whom has a training data set drawn from their own distribution Pi. Assuming some shared structure among the problems Pi, can users collectively learn the shared structure—and solve their tasks better than they could individually—while preserving the privacy of their data? We formulate this question using joint, user-level differential privacy—that is, we control what is leaked about each user’s entire data set. We provide algorithms that exploit popular non-private approaches in this domain like the Almost-No-Inner-Loop (ANIL) method, and give strong user-level privacy guarantees for our general approach. When the problems Pi are linear regression problems with each user’s regression vector lying in a common, unknown lowdimensional subspace, we show that our efficient algorithms satisfy nearly optimal estimation error guarantees. We also establish a general, information-theoretic upper bound via an exponential mechanism-based algorithm.

text: We provide algorithms that exploit popular non-private approaches in this domain like the Almost-No-Inner-Loop (ANIL) method, and give strong user-level privacy guarantees for our general approach. When the problems Pi are linear regression problems with each user’s regression vector lying in a common, unknown lowdimensional subspace, we show that our efficient algorithms satisfy nearly optimal estimation error guarantees. We also establish a general, information-theoretic upper bound via an exponential mechanism-based algorithm.

heading: 1 Introduction
text: Modern machine learning techniques are amazingly successful but come with a range of risks to the privacy of the personal data on which they are trained. Complex models often encode exact personal information in surprising ways—allowing, in extreme cases, the exact recovery of training data from black box use of the model [7, 8]. The emerging architecture of modern learning systems, in which models are trained collaboratively by networks of mobile devices using extremely rich, personal information exacerbates these risks.
The paradigm of model personalization, a special case of multitask learning, has emerged as one way to address both privacy and scalability issues. The idea is to let users train models on their own data—for example, to recognize friends’ and family members’ faces in photos, or to suggest text completions that match the user’s style—based on information that is common to the many other similar learning problems being solved by other users in the system. Even a fairly limited amount of shared information—a useful feature representation or starting set of parameters for optimization, for example—can dramatically reduce the amount of data each user requires. But that shared information can nevertheless be highly disclosive.
In this paper, we formulate a model for reasoning rigorously about the loss to privacy incurred by sharing information for model personalization. In our model, there are n users, each holding a dataset of m labeled examples. We assume user j’s data set Dj is drawn i.i.d. from a distribution Pj ; the user’s goal is to learn a prediction rule that generalizes well to unseen examples from Pj . Ideally, the user should succeed much better than they could have on their own. We give new algorithms for this setting, analyze their accuracy on specific data distributions, and test our results empirically.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We ask that our algorithms satisfy user-level, joint differential privacy (DP) [28] (called task-level privacy, in the context of multi-task learning [32]). In this setting, each user provides their data set Dj as input to the algorithm and receives output Aj = Aj(D1, ..., Dn). We require that for every choice of the other data sets D−j = (D1, ..., Dj−1, Dj+1, ..., Dn) and for every two data sets Dj and D′j , the collective view of the other users A−j be distributed essentially identically regardless of whether user j inputs Dj or D′j . The standard model of differential privacy doesn’t directly fit our setting, since the model ultimately trained by user j will definitely reveal information about user j’s data set. That said, the algorithms we design can ultimately be viewed as an appropriate composition of modules that satisfy the usual notion of DP (an approach known as the billboard model). For simplicity, we describe our algorithms in a centralized model in which the data are stored in a single location, and the algorithm A is run as a single operation. In most cases, we expect A to be run as a distributed protocol, using either general tools such as multiparty computation or lightweight, specialized ones such as differentially private aggregation to simulate the shared platform.
Intuitively, strong privacy requirement at user level, while still demanding that users share some common information is significantly challenging. For one, as each user individually has a small amount of data, it has to share information about it’s model/data to learn a meaningful representation. Furthermore, in practical personalization settings, there is feedback loop between the common or pooled knowledge of all users and the personalized models for each user. That is, starting with reasonable personalized models for each user, leads to a better pooled information, while good pooled information then helps each user learn better personal model. Now, requirement of strong privacy guarantees forces the pooled information quality to degrade up to some extent, which can then lead to poorer personalized model and form a negative feedback loop.

heading: 1.1 Contributions
text: We consider two types of algorithms for DP model personalization: inefficient algorithms (based on the exponential mechanism [35]) that establish information-theoretic upper bounds on achievable error, and efficient ones based on popular iterative approaches to non-private personalization [40, 26, 51, 52]. These latter approaches are popular for their convergence speed and low communication overhead. As is often the case, those same features make them attractive starting points for DP algorithms.
Problem Setting: Consider a set of n users, and suppose each user j ∈ [n] holds a data set of m records Dj = {(xij , yij)}i∈[m] where xij ∈ R
d, yij ∈ R. The goal is to learn a personalized model fj(·) = f(·; θj) : Rd → R for each user j, where θj is a vector of parameters describing the model. We aim to learn a shared, low-dimensional representation for the features that allows users to train good predictors individually. For concreteness, we consider a linear embedding specified by a d× k matrix U , where k d. We may think of U either as providing a k-dimensional representation of the feature xij (as U>xij) or, alternatively, as a compact way to specify a d-dimensional regression vector θj = Uvj where vj is vector of length k. In both cases, user j’s final predictor has the form
fj(xij) = f ′(〈xij ,Uvj〉) = f ′(〈U>xij ,vj〉)
One may view this as a model as a two-layer neural network, where the first layer is shared across all users and the second layer is trained individually. A useful setting to have in mind is one where k m d—so users do not have enough data to find a good solution on their own, but they do have enough data to find the best vector vj once an embedding U has been specified. Without loss of generality, we assume U ∈ Rd×k to be an orthonormal basis and refer to it as embedding matrix. For brevity, we will define the matrix V = [v1| · · · |vn] ∈ C ⊆ Rk×n with vjs as columns.
Measure of Accuracy: Let LPop(U ;V ) = E(i,j)∼u[m]×[n],(xij ,yij)∼Pj [ ` ( 〈U>xij ,vj〉; yij )] , where the loss function takes the form ` : R × R → R. We will focus on excess population risk defined in (1). The privately learned models are denoted by ( Upriv,V priv ) . The error measures are defined with respect to any fixed choice of parameters (U∗,V ∗).
RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) = LPop(Upriv,V priv)− LPop(U∗,V ∗). (1)
Alternating Minimization Framework: We develop an efficient framework based on alternating minimization [46, 29, 23]: starting from an initial embedding map U0, the algorithm proceeds in
rounds that alternate between users individually selecting the model v(t)j that minimizes the error of the predictor f ′(〈·,U (t)v(t)j 〉), and then running a DP algorithm, for which user j provides inputs Dj ,v (t) j , to privately select a new embedding U (t+1) that minimizes the error of the predictor f ′(〈·,U (t+1)v(t)j 〉). In both steps, the optimization to be performed is convex when the loss being optimized is convex. This helps us handle the inherent non-convexity in the problem formulation.
Instantiation and Analysis for Linear Regression with Gaussian Data: For the specific case of linear regression with the squared error loss, we show that our framework can be fully instantiated with an efficient algorithm which converges quickly to an optimal solution. For simplicity, we consider the case where the feature vectors and field noise are normally distributed and independent of each user’s “true” model θ∗j , and furthermore that the θ ∗ j vectors admit a common low-dimensional representation

heading: U∗ ∈ Rd×k, so that θ∗j = U
text: ∗v∗j . We show that careful initialization of U0 followed by alternating
minimization converges to a near-optimal embedding as long as m = ω(k2) and n = ω ( k2.5d1.5
ε
) .
Notice that non-privately, one would require n = ω(dk) users to get any reasonable test error. For standard private linear regression in dk dimensions, current state-of-the-art results (Theorem 3.2, [3]) have a sample complexity similar to what we achieve.
Theorem 1.1 (Special case of Theorem 4.2). Suppose the output for point xij ∼ N (0, 1)d of user j is given by yij ∼ 〈(U∗)>xij ,v∗j 〉 +N (0, σ2F) where U
∗ ∈ Rd×k is an orthonormal matrix that describes the shared representation, and suppose v∗j ∼ N (0, 1)k. Let σF ≤ √ k and ε ≤ 1. Then, assuming the number of users n is at least (kd)1.5/ε, and the number of points per user m is at least k2, with high probability Algorithm 1 learns an embedding matrix Upriv such that the average test error of a linear regressor learned over points embedded by Upriv is at most Õ ( d3k5
ε2n2 + σ 2 F · km
) .
Our instantiation of the framework in this case has two major components: The initial embedding U0 is derived from users’ data by a single noisy averaging step which roughly approximates the d× d projector onto the k-dimensional column space of U∗. The idea is that given two data points (xij , yij) and (x(i+1)j , y(i+1)j), the expected value of the rank-one matrix yijy(i+1)jxijx>(i+1)j is (when rescaled) a projector onto the space spanned by the regression vector θj . Adding these rank-one matrices across many data points and users produces a matrix with high overlap with the desired projector U∗(U∗)>. This is similar to the approach taken by [13] to design a non-private algorithm for a related, less general setting.
The DP minimization step, which fixes the vj’s and seeks a near-minimal U , can be performed using any DP algorithm for convex minimization [9, 4]. In this particular case, one can view this step as solving a linear regression problem in which U represents a list of dk real parameters: once x and v are fixed, 〈U>x,v〉 = x>Uv is a linear function of U .
For the analysis to be tractable, we restrict our attention to linear regression with independent, normally-distributed features. However, the framework we provide is more general, and can be applied to a wider class of models. Developing mathematical tools to analyse the behavior of noisy alternating minimization algorithms in more general settings remains an important open question.
Additionally, we run simulations on synthetic data to demonstrate the effectiveness of our proposed algorithm. Our algorithm reaches a significantly better privacy-utility tradeoff compared to two baselines: i) each user uses their own data, and ii) all users jointly learn a single model under differential privacy.
Information-theoretic Upper Bounds: In addition to developing efficient algorithms for particular settings, we give upper bounds on the achievable error of user-level DP model personalization via inefficient algorithms. Specifically, we consider the natural approach of using the exponential mechanism [35] to select a common structure that provides low prediction error on average across users. For the specific case of a shared linear embedding (a generalization of the linear regression setting above), when the feature vectors are drawn i.i.d. from N (0, 1)d, and when the v∗j ’s are drawn i.i.d. from N (0, 1)k, we provide an upper bound showing that n = ω ( k1.5d1.5
ε
) users suffice to learn
a good model, assuming m is sufficiently large for users to train the remaining parameters locally
(Theorem 5.2). In comparison to alternating minimization, the sample complexity is better by a factor of k.
In summary, we initiate a systematic study of differentially private model personalization in the practically important few-shot (or per-user sparse data) learning regime. We propose using users’ data to learn a strong common representation/embedding using differential privacy, that can in turn be used to learn sample efficient models for each user. Using a simple but foundational problem setting, we demonstrate rigorously that this technique can indeed learn accurate common representation as well as personalized models, despite users housing only a small number of data points.

heading: 1.2 Related Work
text: Personalization Frameworks: Model personalization is a special case of multitask or few-shot learning [10, 25] where the goal is to leverage shared structure amongst multiple tasks to better learn the individual tasks. There are many different frameworks for multi-task learning, each capturing a different kind of shared structure. In the context of model personalization, where tasks correspond to users, two broad approaches stand out.
“Neighboring models”. This approach assumes that while each user learns their own model, all or a fraction of the models are close to each other thus can be learned together [18, 25].
“Common representation”. This approach, which we adopt in this paper, assumes a low-dimensional shared subspace where all points can be represented and now each user/task can learn a sample efficient model to solve the individual task [47, 38]. A common instantiation is a DNN architecture in which the weights in the last layer are user-specific but other weights are shared. Algorithmically, this second approach is more complex since it entails simultaneously finding an accurate representation of data and models building upon those representations. But several studies [38, 47] have shown it to be significantly more effective than other approaches like neighboring models.
Recent works on this approach (e.g. [44, 47, 22, 40]) follow a similar training strategy to ours— that is, they alternatively update the shared representation using gradient descent and then finetune individual classifiers [38, 30, 47]. In particular, the Almost-No-Inner-Loop (ANIL) method by [38] is most similar to the alternating optimization method that we adopt (see Algorithm 1). Theoretical understanding of these methods generally lag significantly behind their empirical success. However, several interesting recent results explain the effectiveness of these methods on simple tasks [13, 46]. Most of the papers in this domain focus on the linear regression problem with a shared lowdimensional representation that we study [46, 11, 48]. They show that one can provide much better estimates for the shared representation, and overall prediction error, by pooling information than would be possible for individual users acting alone. These existing analyses do not allow for noise in the iterations. In fact, for the general problem, the noise can lead to suboptimal solutions. Thus, a key contribution of our work is to show that in a widely studied setting, alternating minimization converges even when the minimization of U is noisy.
Privacy: In our setting, the data set is made up of users’ individual data sets D1, ..., Dn, where each Dj potentially contains many records (labeled training examples). Users interact via a central algorithm, which we assume for simplicity to be implemented correctly and securely (either by a trusted party or using cryptographic techniques like multiparty computation). This algorithm provides output to each of the users. We aim to control what those outputs leak about the users’ input data.
That is, presence/absence of user and its entire data should not affect the outputs significantly. This notion is known as user-level or task-level privacy and has been widely studied in the literature [34, 31], albeit mostly without personalization component. The only works we are aware of that look at personalization (or multitask learning more generally) with user-level guarantees are [19] and [24]. Geyer et al. [19] consider the “neighboring models” approach, which cannot work in the setting we study. Jain et al. [24] consider matrix completion, which can be viewed as a version of our setting in which training examples are limited to indicator vectors (items from a known discrete set).
A few studies attempt to provide only record-level privacy – a significantly weaker notion of privacy where presence/absence of only single record should be undetected by the output of the model. While the notion has been studied extensively for the standard non-personalized models [27, 9], for personalized models the literature is somewhat limited [21, 32]. The work of [32] discusses both taskand record-level privacy, but ultimately provides only algorithms that satisfy the weaker guarantee.
As mentioned above, our goal is to provide strong user-level privacy guarantees so such methods do not apply in our case.

heading: 1.3 Notation
text: We denote all matrices with bold upper case letters (e.g., A), and all vectors with bold lower case letters (a). Unless specified explicitly, all vectors are column vectors. We denote the clipping operation on a vector a as clip (a; ζ) = a ·min { 1, ζ‖a‖2 } .

heading: 2 Background on Privacy
text: Billboard model: In this paper, we operate in the billboard model [20] of differential privacy [15, 14, 36]. Consider n users, and a computing server. The server runs a differentially private algorithm on sensitive information from the users, and broadcasts the output to all the users. Each user j ∈ [n] can then use the broadcasted output in a computation that solely relies on her data. The output of this computation is not made available to other users. A block schematic is shown in Figure 1. One important attribute of the billboard model is that it trivially satisfies joint differential privacy [28].
User-level privacy protection: In this work, we provide user-level privacy protection [16]. I.e., from the output of the algorithm available to an adversary, they will not be able to detect the presence/absence of all the data samples belonging to a single user. Correspondingly, in the definition of differential privacy below (Definition 2.1), a “record” consists of all the data samples belonging to a single user. Furthermore, we adhere to the replacement model of privacy, where the protection is with respect to the replacement of a user with another, instead of the presence/absence of a user.
Definition 2.1 (Differential Privacy [15, 14, 36]). A randomized algorithm A is (ε, δ)-differentially private if for any pair of data sets D and D′ that differ in one record (i.e., |D4D′| = 1), and for all S in the output range of A, we have
Pr[A(D) ∈ S] ≤ eε ·Pr[A(D′) ∈ S] + δ,
where probability is over the randomness of A. Similarly, an algorithm A is (α, ρ)- Rényi differentially private (RDP) if Dα (A(D)||A(D′)) ≤ ρ, where Dα is the Rényi divergence of order α.

heading: 3 Model Personlization via Private Alternating Minimization
text: In this section, we first provide a generic/meta algorithm for private model personalization (Algorithm 1 (Algorithm APriv-AltMin)). The main idea is to alternate between two states for T iterations, i.e., for t ∈ [T ], (i) Estimate the best embedding matrix U (t) based on the current personalized models[ v
(t) 1 , . . . ,v (t) n
] while preserving user-level (α, ρ)-
RDP, and (ii) update the personalized modes based on the updated embedding matrix U (t). Finally, output Upriv ← U (T+1), which will be used by each user j ∈ [n] to train her final personalized model vprivj . While Algorithm APriv-AltMin is a fairly natural method for model personalization, to the best of our knowledge, this is the first work that formally studies the privacy/utility trade-offs under user-level privacy. Prior works [40, 37] have used similar ideas in the non-private meta-learning setting. The estimation of the embedding matrix can be implemented by
any differentially private convex optimization algorithm (e.g., DP-SGD [42, 4, 1]). As discussed in Section 4, for specific case of linear regression, we can perturb the sufficient statistics to obtain differential privacy guarantee, and then optimize over it. A similar idea was used in [41, 39].
We provide a formal description in Algorithm 1. In Section 4, we instantiate it in the context of personalized linear regression. There, we also provide formal excess population risk guarantees under
Algorithm 1 APriv-AltMin: Differentially Private Alternating Minimization Meta-algorithm Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]} for m
mod 4 = 0, rank of the projector: k, privacy parameters: (α, ρ), number of iterations: T , initial rank-k subspace matrix: Uinit, loss function: `.
1: Initialize U (1) ← Uinit. 2: Randomly permute the users j ∈ [n] via permutation π ∼unif [n]. Set j ← π(j),∀j ∈ [n]. 3: for t ∈ [T ] do 4: St ← [ 1 + d (t−1)nT e, d tn T e ] .
5: Each user j ∈ [St] independently solves v(t)j ← arg min ‖v‖2≤Rk 4 m ∑ i∈[m/4] ` ( 〈(U (t))>xij ,v〉; yij ) .
6: Estimate U (t+1) ← arg min U∈K 4 m·|St| ∑ i∈[m/4+1,m/2],j∈St ` ( 〈U>xij ,v(t)j 〉; yij ) under (α, ρ)RDP, where K is the set of all rank-k matrices with orthonormal columns in Rd×k. 7: end for 8: Upriv ← U (T+1).
some data generating assumption. Since Line 6 guarantees (α, ρ)-RDP, and disjoint sets of users are used in each iteration, we can conclude that the whole algorithm guarantees (α, ρ)-RDP.
4 Instantiating Algorithm APriv-AltMin with Linear Regression In this section, we instantiate Algorithm APriv-AltMin (Algorithm 1) in the context of linear regression. While our privacy guarantees hold for any instantiation of the training data, the utility guarantees hold under the following data generating assumption.
Data generation: We instantiate the problem description in Section 1.1 as follows. There is a fixed model v∗j ∈ Rk for each user j ∈ [n], and a fixed rank-k matrix with orthonormal columns U∗ ∈ Rd×k across all users. Let V ∗ := [v∗1| · · · |v∗n]. For each feature vector xij ∈ Rd, the response yij is given by:
yij = 〈(U∗)>xij ,v∗j 〉+ zij , zij ∼ N (0, σ2F). (2)
In Theorem 4.2, we provide the privacy and utility guarantee for an instantiation of Algorithm 1 (Algorithm APriv-AltMin) where the loss function is ` ( 〈U>xij ,v〉; yij ) = ( yij − 〈U>xij ,v〉 )2 .
We will adhere to Assumptions 4.1 for the utility analysis.
Assumption 4.1 (Assumptions for Utility Analysis). Let λi > 0 be the i-th eigenvalue of 1n ( V ∗ (V ∗) > )
, and let µ := max j∈[n] ∥∥v∗j∥∥2 /√kλk be the incoherence parameter. Let Noise-to-signal ratio be NSR = σF√
λk . We assume: (i) ∀i ∈ [m], j ∈ [n],xij ∼iid N (0, 1)d, and corresponding yij be generated using (2), (ii) m = Ω̃ ( (1 + NSR) · k + k2 ) , (iii)
n = Ω̃ ( λ1 λk · µ2dk + ( λ1 λk )2 d k2 · ( NSR2 + µ2k )2 + λ1λk ·∆(ε,δ) · ( NSR2 + µ2k ) d3/2 ) . Here, Ω̃(·)
hides polylog (n,m, k).
Theorem 4.2 (Main Result. Bound on Excess Risk). Let V priv = [vpriv1 , . . . ,vprivn ] with
vprivj ← arg min v∈Rk
2
m ∑ m 2 <i≤m ( yij − 〈(Upriv)>xij ,v〉 )2 .
Let Assumption 4.1 hold. Then, Algorithm APriv-AltMin with parameters in Lemma 4.4 and ∆(ε,δ) :=√ 16 log(1/δ)
ε outputs U priv such that i) it is (ε, δ)-differentially private, and ii) it has the following
excess population risk w.p. at least 1 − 1/n9 (over the randomness of data generation and the
Algorithm 2 Instantiating Line 6 of Algorithm 1 ( Algorithm APriv-AltMin) Require: Set of users at time step t ∈ [T ]: St. Current models: { v (t) j : j ∈ St } , data samples:
{(xij , yij) : j ∈ St, i ∈ [m]}, privacy parameter: ∆(ε,δ), clipping threshold for model: η, clipping threshold for response: ζ. 1: W ij = clip ( # » xijv > j ; η ) and ỹij = clip (yij ; ζ) for all i ∈ [m/4 + 1,m/2], j ∈ St.
2: W priv ← ∑
j∈St,i∈[m/4+1,m/2] W ijW
> ij +Nsym ( 0,m2η4∆2(ε,δ)/4 )dk×dk, and bpriv ←
∑ j∈St,i∈[m/4+1,m/2] ỹijW ij +N ( 0,m2ζ2η2∆2(ε,δ)/4 )dk 3: #» Z(t+1) ← arg min
u∈Rdk
4 m·|St|
( u>W privu− 2u>bpriv ) 4: return U (t+1) ← Q part of the QR-decomposition of Z(t+1)
algorithm): RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) ≤
= O
( ∆(ε,δ)(σ 2 F + µ 2k2dλk)(µ 4k3d2)
n2 + σ2Fµ 4k2d nm
) · polylog (d, n) + k
m · σ2F.
See supplementary material for the proof.
Remark 1. Let us understand the bound above for a simple setting where the personal model for each user v∗j ∼ N (0, 1)k. Assuming large enough n, this implies that λk ≈ 1 and µ ≈ Õ(1). Now even when V ∗ is known a priori, to obtain a reasonable estimate of U∗, we need to solve the following linear regression problem while ensuring DP: Upriv = min
U
∑ ij(yij − 〈xij(v∗j )>,U〉)2.
Note that xij(v∗j ) > is isotropic. Now, without differential privacy, the information theoretical optimal estimation error is Θ ( σ2F · dknm ) , where dk is the size of the linear regression problem and mn is the number of samples. Now, if we were to solve the above regression problem with DP, the best known algorithm [41] will have an additional error of Õ (( κ · dknε )2) , where κ = σF + maxij ‖xij(v∗j )>‖F · ‖U ∗‖F = Õ(σF + √ dk2). Note that the first two terms in Theorem 4.2
indeed match O (( κ · dknε )2 + σ2F · dknm ) up to an additional factor of k and up to polylog (d, n) factors. Finally, the last error term in the above theorem is due to excess risk in estimating v∗ for a given user with m samples, and is information theoretically optimal.
Remark 2. Under the assumption in Remark 1 and for σF = 0, the sample complexity for Theorem 4.2 is n = ω̃(k2.5d1.5/ε + d) and m = ω̃(k2). Note that, for ε → ∞, the complexity is O(k) worse than the information theoretic optimal. Furthermore, the sample complexity suffers from an additional √ d for constant ε compared to non-private case. Even for standard linear regression, a similar additional √ d factor is present in the sample complexity bound [41]; we leave further investigation into the optimal sample complexity for future work.
In Section 4.1, we show an instantiation of AlgorithmAPriv-AltMin (Algorithm 1) s.t. if the embedding matrix (Uinit) is initialized well, then Upriv ( Upriv )> converges in ‖ · ‖F to U∗(U∗)>. In Section 4.2, we provide an algorithm to obtain a good initialization of the embedding matrix (Uinit). Combining these two results imply Theorem 4.2.

heading: 4.1 Local Subspace Convergence
text: In Algorithm 2, we instantiate Line 6 of Algorithm APriv-AltMin. For any matrix A ∈ Rd1×d2 , let #»
A ∈ Rd1d2 be the vectorized representation with columns of A placed consecutively. Let Nsym(0, σ2)d×d denote a Wigner matrix with entries drawn i.i.d. from N (0, σ2). The privacy guarantee of Algorithm 2 is presented in Lemma 4.3 and the local subspace guarantee in Lemma 4.4.
Lemma 4.3 (Privacy guarantee). If we set ∆(ε,δ) = √
8 log(1/δ)/ε, then instantiation of Algorithm APriv-AltMin with Algorithm 2 is (ε, δ)-differentially private in the billboard model.
Lemma 4.4 (Local Subspace Convergence). Recall Assumptions 4.1. In Algorithm 2, let model clipping threshold η = Õ(µ √ λkdk), and response clipping threshold ζ = Õ ( σF + µ √ kλk ) . Let the
number of iterations of Algorithm 1 (Algorithm APriv-AltMin) be T = Ω ( log (
(λ1/λk) NSR+∆(ε,δ)
)) . Finally,
assume Uinit be s.t. ‖(I − U∗ (U∗)>)Uinit‖F ≤ λk32λ1 . We have the following for Algorithm 1 (Algorithm APriv-AltMin), instantiated with Algorithm 2, w.p. at least 1− 1/n10 (over the randomness of data generation and the algorithm):
∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥ F = Õ ( ∆(ε,δ)(NSR + µ √ dk2)µ √ k2d2 n + NSR · µ √ kd√ nm ) .
Here, the noise-to-signal-ratio NSR = σF√ λk
and privacy parameter ∆(ε,δ) = √ 8 log(1/δ)
ε . In Õ(·), we hide polylog (d, n).
See supplementary material for the proofs. The analysis of Lemma 4.4 roughly follows the analysis of alternating minimization [46], while accounting for the noise introduced due to privacy. At each iteration, we show that the embedding subspace gets closer in the Frobenius norm, and each of the personalized models gets closer in the `2-norm.

heading: 4.2 Initialization Algorithm
text: In Algorithm 3, we describe a private estimator for the estimation of U∗. This estimator eventually gets used in initializing the linear regression instantiation of Algorithm 1. We provide the privacy and subspace closeness guarantees in Lemma 4.5 and 4.6, with proofs in supplementary material.
Algorithm 3 APriv-init: Private Initialization Algorithm for Algorithm APriv-AltMin Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]}, clipping bound
for response: ζ, noise standard dev. for privacy: ∆(ε,δ), and rank of the orthonormal basis: k. 1: W ij ← sym ( x(2i)jx > (2i+1)j
‖x(2i)j‖2·‖x(2i+1)j‖2 · clip
( y(2i)j ; ζ ) · clip ( y(2i+1)j ; ζ )) for all i ∈ [m/2] and j ∈
[n]. Here, sym(W ) makes a matrix ∈Rd×d symmetric by replicating the upper triangle.
2: MNoisy ← 2nm ( ∑ i∈[m/2],j∈[n] W ij +Nsym ( 0,∆2(ε,δ)ζ 4m2 )d×d) . 3: Upriv ← Top-k eigenvectors of MNoisy as columns.
Lemma 4.5 (Privacy guarantee). If we set ∆(ε,δ) = √
8 log(1/δ)/ε, Algorithm 3 (Algorithm APriv-init) is (ε, δ)-differentially private. Lemma 4.6 (Subspace closeness). Recall Assumptions 4.1. Let the clipping bound for response be ζ = Õ(σF + µ √ kλk). We have the following for Algorithm 3 (Algorithm APriv-init) w.p. at least 1− 1/n10:∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥ 2 = Õ ( ∆(ε,δ) ( NSR2 + µ2k ) d3/2 n + (NSR2 + µ2k) √ d√ nm ) .
Here, privacy parameter ∆(ε,δ) = √ 8 log(1/δ) ε . In Õ(·), we hide polylog (d, n).
The proof goes via direct analysis of the distance between the estimated subspace from the training examples, and the true subspace. While the convergence guarantee in Lemma 4.6 is unconditional, it is weaker than Lemma 4.4, especially in its dependence on k and NSR.
Lemma 4.6 implies that under Assumption 4.1, ∥∥∥(I−U∗ (U∗)>)Upriv∥∥∥
F = O
( λk λ1 ) , which
is sufficient to satisfy the initialization condition in Lemma 4.4. Hence, if we initialize U using Algorithm 3 (Algorithm APriv-init) with a disjoint set of samples for each user, it immediately follows that the the local convergence guarantee in Lemma 4.4 is indeed a global convergence guarantee.
Algorithm 4 AExp: Joint Differentially Private ERM via Exponential Mechanism
Require: Data sets from each user j ∈ [n]: Dj = {(xij ∈ Rd, yij ∈ R) : i ∈ [m]} where m mod 2 = 0; model `2-norm constraint C; clipping bound on the projected features Lf ; privacy parameter ε; rank of the projection matrix k; net width φ, loss function ` : R×R→ R; Lipschitz constant ξ of w.r.t. its first parameter.
1: Define a score function for any rank-k matrix with orthonormal columns U ∈ Rd×k as
score (U) = ∑ j∈[n] ( min ‖vj‖2≤C 2 m ∑ i∈[m/2] ` ( 〈clip ( U>xij ;Lf ) ,vj〉; yij )) .
2: Define a net N φ of ‖ · ‖F -radius φ over matrices with orthonormal columns in Rd×k. 3: Sample Upriv ∈ N φ with Pr[Upriv = U ] ∝ exp ( − εn
8LfCξ · score (U)
) .
4: Each user j ∈ [n] independently estimates vprivj ← arg min ‖v‖2≤C 2 m m∑ i=m/2+1 ` ( 〈 ( Upriv )> xij ,v〉; yij ) .

heading: 5 Exponential Mechanism based Model Personalization
text: In this section, we take a more general approach towards outputting a projector Upriv that approximately minimizes the excess population risk without worrying about actually estimating the projector onto U∗. Here, as we only care about low-excess risk, as opposed to subspace closeness, we can guarantee better convergence under milder assumptions. Recall the loss function LPop(U ,V ) from (1).
We want to optimize min U∈K
( min
V ∈Rd×n,‖vj‖2≤C LPop(U ,V )
) while ensuring ε-DP in the billboard
model. (Here K ∈ Rd×k is the set of matrices with orthonormal columns, and vj corresponds to the j-th column of V .) To that end, we will use the exponential mechanism [35], over an `F -net of radius φ over K. The algorithm is presented in Algorithm 4 (Algorithm AExp). The privacy analysis of AlgorithmAExp follows from the standard analysis of exponential mechanism, and the utility analysis goes via first proving an excess empirical risk bound, and then appealing to uniform convergence to get to excess population risk bound.
Theorem 5.1 (Privacy guarantee). Algorithm 4 is ε-differentially private in the billboard model.
Theorem 5.2 (Utility guarantee). Suppose the loss function ` is ξ-Lipschitz in its first parameter, and C is the bound on the constraint set. Set the net size φ = 1/(εn) and the clipping norm Lf = 40 √ d · log(nm) in Algorithm 4. Assuming ε ∈ (0, 1) and that the feature vectors are drawn i.i.d. from N (0, 1)d, we have (w.p. ≥ 1− 1/min{d, n}10):
RiskPop( ( Upriv,V priv ) ; (U∗,V ∗)) = O ( ξC · ( k · d1.5
εn + √ k√ m
)) · polylog (d, n) .
Here, U∗ and V ∗ are any fixed values of the common embedding matrix (orthonormal, in Rd×k) and matrix of individual regression vectors (in Rn×k, with rows of norm at most C), respectively. See supplementary material for the proofs of Theorems 5.1 and 5.2.
Comparison of the utility guarantee to Theorem 4.2: The utility guarantee for Algorithm AExp (Theorem 5.2) is much more general than that in Theorem 4.2. Unlike Theorem 4.2, it allows arbitrary Lipschitz loss function `, and any distribution over the feature vectors. However, for linear regression with i.i.d. spherical normal feature vectors and setting the diameter of the constraint set C = √ k, one can make Theorems 4.2 and 5.2 comparable. Theorem 4.2 shows an excess population
risk Õ ( k5d3
ε2n2 + k m
) whereas Theorem 5.2 gives Õ (√ k3d3 εn + √ k2 m ) . Theorem 4.2 is tighter in the
regime where n = Ω(k3.5d1.5/ε). This difference is comparable to the so-called fast rates [43]. However, the sample complexity of Theorem 5.2 is better in terms of m by a factor of k1.5.

heading: 6 Numerical Simulation
text: In this section, we provide numerical simulations to validate our theoretical results. There are three baselines: i) each user solves their problem using their own data without consulting with other
users (called own data), and ii) a single differentially private global model trained on all users data together (called single model), and iii) non-private variant of alternating minimization, trained up to convergence. Overall, we observe that Algorithm 1 (Algorithm APriv-AltMin) outperforms the private baselines by a significant margin.
We consider the linear regression problems on synthetic data and the alternating minimization algorithm 1. We set the number of users n = 50, 000, number of samples per user m = 10, data dimension d = 50 and rank k = 2. We sample x, U and v from Gaussian distributions, and the field noise σF of target y is set to be 0.01. We normalize U to unit norm. We run Algorithm 1 with full batch, i.e., T = 1 and for multiple epochs. The privacy risk will accumulate over epochs, and we use the RDP sequential composition to account for that. We fix the clipping norm to be 10−4 and pick the optimal the number of epochs in {1, 2, 5, 10}. In Figure 2, we fix δ = 10−6 and plot the population mean squared error (MSE) computed based on the groundtruth model for multiple ε. As a reference, the MSE for a purely random model is around 4. In addition to (ε, δ)-differential privacy, we also report the value of Zero-Concentrated Differential Privacy (zCDP) [5], as it better captures the privacy properties, especially for Gaussian mechanism based algorithms. The definition can be found at Appendix A. In particular, privacy parameter ε = {1, 2, 5, 10} corresponds to 0.009, 0.04, 0.23, 0.90-zCDP, respectively. We observe that at ε ≈ 5, the population MSE for Algorithm 3 is comparable to the non-private baseline. In contrast, the error for the single model baseline remains very high, even at high values of ε.

heading: 7 Conclusion
text: In this paper we studied the problem of personalized supervised learning with user-level differential privacy. Through our framework and Algorithm 1, we demonstrated that we can indeed learn accurate shared linear representation of the data, despite a limited number of samples-per-user and while preserving each user’s privacy. Our error bounds and sample complexity bounds are nearly optimal in key parameters and are in fact, comparable to the best known bounds available for a much simpler linear regression problem.
This work leads to several interesting questions: (i) In our model, can we provide similar privacy/utility trade-offs for deep networks based embedding functions instead of a linear embedding function, (ii) Can we make a variant of the exponential mechanism algorithm computationally feasible?, and (iii) Empirically validate the privacy/utility trade-offs on real world data sets.
As more and more ML models are personalized for user tastes, ensuring privacy of individuals’ data is paramount to a fair, responsible system. We provide a rigorous framework to design such solutions, which hopefully will motivate practitioners and researchers to make privacy as a first class citizen while designing their personalization based ML system.
Acknowledgements and Funding Disclosure We would like to thank Brendan McMahan, and Daniel Ramage for various helpful discussions during the course of this project. Adam Smith was supported in part by NSF award CCF-1763786 as well as a Sloan Foundation research award and a Google Faculty Research Award.

Review summaries:
 The paper presents an algorithm for differentially private (DP) learning of personalized models. A set of users with their own private data collaborate to privately learn a good embedding of the data followed by a linear regression based on this embedding.   The paper contribution is a theoretical analysis of the proposed algorithm with DP guarantees and utility bounds.   As far as I know there is no such bounds in the literature within the same setting. The author compare their result with the bounds in the non private case and with an upper bound obtained using the exponential mechanism which provides an information theoretic bound but cannot be efficiently implemented. In the later case, the bounds on the excess risk differs by O(1/\epsilon) and O(1/\sqrt(m)), m being the number of samples and \epsilon the privacy budget.  

This paper focuses on a setting, where there are multiple users each holds a training dataset. In this setting, users have to share information about their model or data to learn a meaningful representation and to solve their tasks better than they could without using the shared, low-dimensional representation. The paper proposes an approach for this problem that provides strong user-level differential privacy guarantees at the same time. For the privacy guaranteees, the method uses exponential mechanism and utility analysis of the algorithm is made by using that.

The authors deal with personalized model learning under the user-level joint differential privacy. In this problem, each user aims to build a user-specified model to make a prediction for the user's data. In the training process, the users utilize knowledge from the other users' data to improve their model's performance. In this setup, we want to prevent the leakage of the sensitive information in the user's data to the other user. The authors develop the differentially private algorithms for the model personalization task and reveal the upper bounds on the personalized model's accuracy of these algorithms. 

This paper studies the problem of model personalization with user-level differential privacy in the setting where users don't have enough data to find a good solution on their own but can leverage information in similar learning problems shared by other users. The problem is viewed as learning a 2-layer neural network, where the first embedding is the shared structure and the second layer is trained individually. This paper provides two types of algorithms: inefficient algorithms based on the exponential mechanism that establish information-theoretic upper bounds on an achievable error and efficient algorithms based on alternating minimization, which starts from an initial embedding and then repeatedly uses a DP minimizer to minimize the error. For the specific case of linear regression with squared error loss, the paper shows the alternating minimization framework can converge to a near-optimal embedding.