Differentially Private Model Personalization
Authors: Prateek Jain
J Keith Rush
Adam Smith
Shuang Song
Abhradeep Guha Thakurta
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differential Privacy
Model Personalization
Alternating Minimization
Learning Theory

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 $P_i$. Assuming some shared structure among the problems $P_i$, 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 $P_i$ are linear regression problems with each user's regression vector lying in a common, unknown low-dimensional 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.

Differentially Private Model Personalization
Prateek Jain Google Research
Keith Rush Google Research
Adam Smith Boston University ads 220bu. edu
prajain@google.com
krush@google. com
Shuang Song
Abhradeep Thakurta Google Research athakurta@google... com
Google Research
shuangsongggoogle.com
Abstract
We study personalization of supervised learning with user-level differential privacy. Consider setting with many users, each of whom has training data set drawn from their own distribution P, Assuming some shared structure among the problems P., can collectively learn the shared structure-and solve their tasks better than they could individually-whinn preserving the privacy of their data? We formulate this question using joint, user-level differential privacy- that is, 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 Mrmmost-N-Inner-Loog (ANIL) method, and give strong user-level privacy guarantees for our general approach. When the problems P: are linear regression problems with each user's ' regression vector lying in common, unknown low- dimensional subspace, we show that our efficient algorithms satisfy nearly optimal estimation error guarantees. We also establish general, information-theoree upper bound via an exponential mechanism- based algorithm.
Introduction
Modern machine learning techniques amazingly successful but come with range of risks the privacy of the personal data on which they are trained. Complex models often encode exact personal information surprising ways-allos allowing, 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 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 fairly limited amount of shared information- useful feature representation or starting set of parameters for optimization, for example- dramatically reduce the amount of data each user requires. But that shared information can nevertheless be highly disclosive.
In this paper, we formulate model for reasoning rigorously about the loss to privacy incurred by sharing information for model personalization. In our model, there are users, each holding dataset of m labeled examples. We assume user j's data set D, is drawn i.id. from distribution Pf; the user's goal is to learn prediction rule that generalizes well to unseen examples from P,. Ideally, the user should succeed much better than they could have on their own. We give new algorithms for this setting, analyze their accuracy specific data distributions, and test results empirically.
35th Conference on Neural Information Processing Systems (NcurIPS 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 D2 as input to the algorithm and receives output A = A, Da). We require that for every choice of the other data sets D-j = (Di, Dj-1; Dj+1:..., D,) and for every two data sets D) and Dj the collective view of the other users A_, be distributed essentially identically regardless of whether user j inputs Dj or D'. The standard model of differential privacy doesn't '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 an appropriate composition of modules that satisfy the usual notion of DP (an approach known as the billboard model). For simplicity, describe our algorithms in centralized model in which the data are stored in single location, and the algorithm A is run as a single operation. In most cases, we expect A to be run as distributed protocol, using either general tools such 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 significantly challenging. For one, as each user individually has small amount of data, it has to share information about it's model/data to learn meaningful representation. Furthermore, in practical personalization settings, there 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 negative feedback loop.
1.1 Contributions
We consider two types of algorithms for DP model personalization: inefficient algorithms (based on the exponential mechanism [35]) that establish information -hhoorett upper bounds on achievable error, and efficient ones based on popular iterative approaches to non-pri 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 set of users, and suppose each user j E [na] holds data set of m
records D3 = {(xij, (xxi) Vey)) where Xij E IRd, Mij E IR. The goal is to learn a personalized model f(()) - f.; : Rd + RR for each user j. where O is a vector of parameters describing the model.
We aim to learn shared, low-dimensional representation for the features that allows users to train good predictors individually. For concreteness, we consider a linear embedding specified by d x matrix U, where k < d. We may think of U either as providing k-dimensional representation of the feature Xij (as U xij) or, alternatively, as compact way to specify d-dimensional regression vector 0j = Un, where By is vector of length In both cases, user j's final predictor has the form
xxxx) = f((c) Ue,)) = f'U Xiy, Uz))
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 find the best vector vj once embedding U has been specified. Without loss of generality, we assume U E Ra brevity, we will define the matrix V = [vil--. [v,] E C kxn with U,s as columns.
k to be an orthonormal basis and refer as embedding matrix. For
[e ((UT x,y, oy)s wb where the loss function takes the form L IR x TR + IR. We will focus on excess population risk defined in (I). The privately learned models are denoted by (Urriy vpriv). The error measures are defined with respect to any fixed choice of parameters
Measure of Accuracy: Let Czop (U;
Risk ( (Uerit yerie); :U'", V*)) = Loop (Ueriv Veriv) - Loop (U",
(U" V*).
(I)
We develop an efficient framework based on alternating minimization [46, 29, 23]: starting from initial embedding map Uo. the algorithm proceeds in
Alternating Minimization Framework:

---

rounds that alternate between users individually selecting the model o/ that minimizes the error of the predictor f(((, ( f(((,,7())) ( ))),, and then running a DP algorithm, for which user provides inputs Dy, (1) to privately select a embedding ((+++) that minimizes the error of the predictor f( " ()) optimized is convex. This helps us handle the inherent non-convexity in the problem formulation.
)). In both steps, the optimization to be performed is convex when the loss being
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 Jj and furthermore that the 0j vectors admit common low-dimensional representation U E [gd so that 03 Uh Uz. We show that careful initialization of Uo followed by alternating
Instantiation and Analysis for Linear Regression with Gaussian Data:
minimization converges to a optrmalpiimll embedding as long as m = (k²)) and n. = w (12.6 2.66
Notice that non-privately, one would require n ((lk) users to get any reasonable test error. For standard private linear regression in dk dimensions, current ofte-of-the-an 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 x.j ~ (O, 1)d of user 05) + NN00, of) where U E BRd is an orthonormal matrix that
j is given by Vig ~ describes the shared representation, and suppose Di ~ ~O,, Let oF S Vk and S 1. Then, assuming the number of users n is at least (kd)1s /e, and the number of points per user m is least k.2 with high probability Algorithm I learns an embedding matrix Upziy such that the average test error of a linear regressor learned over points embedded by Uprsy is at most Ö
p + + )
Our instantiation of the framework in this case has two major components: The initial embedding Uo is derived from users' data by a single noisy averaging step which roughly approximates the d x d projector onto the k-dimensional column space of U The idea is that given two data points (Xij. and (X(++));, 1(i+)) the expected value of the rank-one matrix Wi)M(+11y ((+ is (when rescaled) a projector onto the space spanned by the regression vector 0j. Adding these rank-one matrices across many data points and users produces matrix with high overlap with the desired projector U (T"") This is similar to the approach taken by [13] to design a non-private algorithm for related, less general setting.
The DP minimization step, which fixes the vy 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 linear regression problem in which U represents list of dk real parameters: once and fixed, (U x, v) Up is a linear function of U.
For the analysis be tractable, restrict our attention to linear regression with independent, features. However, the framework we provide is more general, and can be applied to 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 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-theereti Upper Bounds: 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 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 drawn i...d. from (/00 1)a, and when the o are drawn
i.idd. from (0, 1)², we provide an upper bound showing that n = w 1 users suffice to learn good model, assuming is sufficiently large for users to train the remaining parameters locally
3

---

(Theorem 5.2). In comparison to alternating minimization, the sample complexity is better by factor of k.
In summary, we initiate 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 learn 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, demonstrate rigorously that this technique can indeed learn accurate common representation as well as personalized models, despite users housing only small number of data points.
1.2 Related Work
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, 25J.
"Common representation". This approach, which we adopt in this paper, assumes low- di-ddmmnnsionll 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 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, 40J) 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, 47J. In particular, the most similar 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 low- dimensional 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.
(ANIL) method by [38]
In setting, the data set is made up of users' individual data sets Di...., Dn, where each D, 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 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.
Privacy:
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 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 known discrete set).
A few studies attempt to provide only record-level privacy 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 [2]. The work of [32] discusses both task- and 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 our case.
1.3 Notation
We denote all matrices with bold upper case letters (e.g., A), and all vectors with bold lower letters (a). Unless specified explicitly, all vectors are column vectors. We denote the clipping
operation on a vector as clip (a; () = a min 1, ||al|a }
2 Background on Privacy
Billboard model: In this paper, we operate in the billboard model [20] of differential privacy [15, 14, 36). Consider users, and computing server. The server runs 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 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.c., from the output of the algorithm available an adversary, they will not be able to detect the presence/absence of all the data samples belonging to single user. Correspondingly. in the definition of differential privacy below (Definition 2.1), '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 user with another, instead of the presence/absence of user.
Definition 2.1 (Differential Privacy [15, 14, 36]). A randomized algorithm A is (e, 6) diffferrentill private if for any pair of data sets D and D' that differ in one record (i.e., DAD' 1), and for all S in the output range of A, we have
Pr(A(D) E S) Pr(A(D") E S]
where probubility is over the randomness of A. Similarly, an algorithm A is (ar, p)- Rényi differ- entially private (RDP) if Da (A(D))IA(D') S p, where Da is the Rényi divergence of order a.
3 Model Personlization via Private Alternating Minimization
In this section, first provide generic/meta al- gorithm for private model personalization (Algo-
of
Compute embedting U
rithm 1 (Algorithm APrivAltMMnn), )). The main idea is
to alternate between two states for I iterations, i.c.,
Prasoo ddeck
for t [T], (i) Estimate the best embedding trix (ttt) based on the current personalized models
011) g..., Un
(t) (()) while preserving user-level (a,
RDP, and (ii) update the personalized modes based on the updated embedding matrix (t)), Finally, out- put Uroriv x- ((++)) which will be used by each user j E [n]] to train her final personalized model weziv. While Algorithm APri-AlMin ural method for model personalization, to the best of our knowledge, this is the first work that formally studies the privacy/utility trade-offss under user-level privacy. Prior works [40, 37] have used similar ideas in the non-private meta-learing setting. The estima- tion of the embedding matrix can be implemented by any differentially private convex optimization algorithm (e.g., DP-SGD [42, 4, 1J). 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 it. A similar idea was used in [41, 39].
V2
V:
VE
Usert 1
User2
User
Usern
Figure 1: User-compute interaction in the billboard model. Shaded boxes represent privileged computation. U refer to the com- mon embedding function, and v refers to the model for user j E [n].
fairly nat-
We provide a formal description Algorithm 1. In Section 4, we instantiate it in the context of personalized linear regression. There, also provide formal excess population risk guarantees under
5

---

Algorithm Apriv.AltMin Differentially Private Alternating Minimization Meta-algorithm
Require: Data sets from each user j [n]] D, {(xy E I& Mij R)
[mm] for m
mod 4 = O, rank of the projector: k, privacy parameters: (a, p), number of iterations: T', initial
rank-k subspace matrix: Uinit, loss function:
1: Initialize U t- Uiint
2: Randomly permute the users j E [n] via permutation Munif [n]. Set t- x(j), Vj [n].
3: for E (7) do
4: St - + (1-1)n
in
5: Each user j E [St] independently solves o t arg min 4 SRt :E(m/4]
E e (((U())) x.j, w); vis)
6: Estimate U(++1) t arg min 4 UEK
Σ
(IUT Xij. (/));; ): ): under (a, p)-
m-[S.
RDP, where IC is the set of all rank-k k matrices with orthonormal columns in Ra
7: end for
8: Uprlv f (T+1),
some data generating assumption. Since Line 6 guarantees (o,, P)-DP, and disjoint sets of users are used each iteration, we can conclude that the whole algorithm guarantees (a, P)-RDP
Instantiating Algorithm APriv-lttMin with Linear Regression
In this section, we instantiate Algorithm AprivAltMin (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 follows. There is fixed model oj e R for each user j E [n). and a fixed rank-k matrix with orthonormal columns U E dx across all users. Let V : [uull ... I,,]]. For each feature vector Xij E Rd, the response Yıy is given by:
Yij ((U*))xx Xij, vj) Ziji Zij ~ (0,
In Theorem 4.2, we provide the privacy and utility guarantee for an instantiation of Algorithm I (Algorithm AprivAlsMinn where the loss function is e ((UT Xijs "UT" e): Uv: (U Xis. 0) We will adhere to Assumptions 4.1 for the utility analysis.
Assumption 4.1 (Assumptions for Utility Analysis). Let di O be the i-th eigenvalue of 1. V (V*))))). and let μ max
[ujll /KAR be the incoherence parameter. Let
jE(m)
ratio be NSR N)0 and corresponding Yij be generated using (2), (ii) ã ((1 NSR) k k?), (iii) ② 12dk +
d=
We assume: (i) vi e [m], E [n], rid
VAx
(NSR² + 12k)²² + d A(e,s) (NSR² + p²2k) d012)
Here, (2(-)
Au
Au A
hides polylog (n, m,k)-
Theorem 4.2 (Main Result. Bound on Excess Risk). Lei Vpriv = -upriv verin with
2
Σ (vi- - ((URrin) Xij, (x,r,, x))²
arg min DERA
M
Let Assumption 4.1 hold. Then, Algorithu Apriv AltMin with parameters in Lemma 4.4 and D /16log(1/6) outputs Ueziv such that i) it is (s, -)diffferentially private, and ii) it has the following excess population risk w.p. least 1 1/n2 (over the randomness of data generation and the

---

Algorithm 2 Instantiating Line 6 of Algorithm (Algorithm Apriv.AttMin)
Require: Set of users at time step & E [T]: S... Current models: {of] : E S.). data samples:
(xxy May) j E S E [m]]] privacy parameter: (ec,)), clipping threshold for model: 7,, clip- ping threshold for response: Ç-
1: Wij clip (zbkyin] and Dij clip (yis () for all i [m/44 / 1, m/2.j E S..
2: W priv f
Σ JES /E mm/3
W, x W.J. + Noym (0, m² mn A (44))/4) dlxak and
boriv
Σ
Dig + N (0, m² 2 A ()4))/4))
3: Z arg min uERdE m-
(u" W PeLv
2u boriv)
4: return ((t-l) t
Q part of the QR-decomposiiion of (t+1)
algorithm):
Riskeop (Ueziv vocie) :('", V)) AGGoslof + d)) =0
o k2
k
-polylog (d, + m
o².
n²
nm
See supplementary material for the proof.
Remark 1. Let us understand the bound above for simple setting where the personal model for each user 25 1)² Assuming large enough n, this implies that d = and μ Ō(1). Now even when V is known priori, obtain reasonable estimate of U* we need to solve the following linear regression problem while ensuring DP: Upziv min
U (ur (x,)(t)),, U.
Note that x1) is isotropic. Now, without differential privacy, the information theoretical optimal estimation error is θ (o? dk
nya where dk is the size of the linear regression problem and mn is the number of samples. Now, if we were solve the above regression problem with DP, the best known algorithm [41] will have an additional error of Ô (N dit ))) where = OF + maxi |xxy( |r | = Ö(a + v dk.2.. Note that the first two terms in Theorem 4.2 indeed match O (KS da me) + o
dk up to an additional factor of k and up to polylog (d, factors. Finally, the last error term in the above theorem is due excess risk in estimating o" for given user with m samples, and is information theoretically optimal.
Remark 2. Under the assumption in Remark 1 and for a. 0, the sample complexity for Theo- rem 4.2 is n = (kk..b 2.5 d....l-// /E + d) and m = (lk2). Note that, for - oc, the complexity is O(k) worse than the information theoretic optimal. Furthermore, the sample complexity suffers from an additional Vd for constant compared to non-private case. Even for standard linear regression, similar additional vd factor present in the sample complexity bound [41]; we leave further investigation into the optimal sample complexity for future work.
In Section 4.1, show an instantiation of Algorithm Apriv-AltMin (Algorithm 1) s.t. if the embedding matrix (U (iint) is initialized well, then Ueriv (Ureiv) converges in || ||r to T In Section 4.2, we provide algorithm to obtain good initialization of the embedding matrix (Trinit). Combining these two results imply Theorem 4.2.
4.1 Local Subspace Convergence
xds In Algorithm 2, we instantiate Line 6 of Algorithm APrivAAttMin- For any matrix A Rddxxd let A Rdid2 be the vectorized representation with columns of A placed consecutively. Let N Nymm (0, ) denote a Wigner matrix with entries drawn i.i.d. from (0, a²). The privacy guarantee of Algorithm 2 presented in Lemma 4.3 and the local subspace guarantee Lemma 4.4.
Lemma 4.3 (Privacy guarantee). we set A(c.s) /8log(1/ (1/ then instantiation of Algorithm AprivAAtMMin with Algorithm 2 is (5, diffeerrrell private in the billboard model.
7

---

Lemma 4.4 (Local Subspace Convergence). Recall Assumptions 4.1. In Algorithm 2, let model clipping threshold 1l = (uvAkkk)) and response clipping threshold Ö (or + py Let the number of iterations of Algorithm (Algorithm Apriv-AltMin) be T Ω (oog
(A1/Da)
NBR+ Acr, Finally,
assume U init be s.t. II(I U" (U") JU Ule S
32 We have the following for Algorithm I
(Algorithm AtMin) instanfiated with Algorithm 2, w.p. at least 1/n (over the randomness of data generation and the algorithm):
(U-))()))) |
( =
(Aa (AAr00(NSR uV uV JUV J
NSR pv pykd kd
Vnm
/llo((1/6) In Ō().
Here, the noise-to-signal-ratio NSR we hide polylog (d, n).
o_ and privacy parameter (e,6) AAe
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 fo-no..
4.2 Initialization Algorithm
In Algorithm 3, we describe private estimator for the estimation U* This estimator eventually gets used in initializing the linear regression instantiation of Algorithm 1. We provide the privacy and subspace closeness guarantees Lemma 4.5 and 4.6, with proofs in supplementary material.
Algorithm 3 Apriviintti Private Initialization Algorithm for Algorithm Apriv-ltMMin
Require:
Data sets from each user E [n]: Dj {(xx, E Rd Yky E R) i [m]]. clipping bound for response: Ç. noise standard dev. for privacy: (c.8); and rank the orthonormal basis:
Wij i sym
x(2a)>l Meas-nslla clip (Mransi s) clip (M1a++)3i() for all i [m/2] and j
x (act)))
[n]. Here, sY)
makes matrix ERaxd symmetric by replicating the upper triangle.
axd
2: M Noisy + 2
Σ
W ij + Nsym (0.
Jelm/21.jEmm
3: UpEiv f- Top-k eigenvectors of M Noisy columns.
Lemma 4.5 (Privacy guarantee). If we set ((e,5) = /8log(1/8)/s, Algorithm 3 (Algorithmm Apriv-nitt is (s, didfffffrelttillly private.
Lemma 4.6 (Subspace closeness). Recall Assumptions 4.1. Let the clipping bound for response be < Ö(Ø og + HvkA)). We have the following for Algorithm 3 (Algorithm Aprivinitt) w.p. at least
1 1/n 10;
( =ō /Aress (NSK² + 12)) 83/2
(NSR² + 4 222)VVd
/nm
Here, privacy parameter ((E,8) /8log(1/8) In Ö(.). 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 weaker than Lemma 4.4. especially in its dependence & and NSR.
Lemma 4.6 implies that under Assumption 4.1, |(T ((-U(())) U = - (2) which
is sufficient to satisfy the initialization condition in Lemma 4.4. Hence, if we initialize U using Algorithm 3 (Algorithm Aprivinit) with disjoint set of samples for each user, it immediately follows that the the local convergence guarantee in Lemma 4.4 is indeed global convergence guarantee.

---

Algorithm 4 A Joint Differentially Private ERM via Exponential Mechanism
Require: Data sets from each user j [n]: D3 ((x, TRd Mi E IR) E [m]] where m
mod 2 = O; model fg-norm constraint C; clipping bound the projected features L5; privacy parameter e; rank of the projection matrix k; net width Φ, loss function & IR x IR + R; Lipschitz constant & of w.r.t. its first parameter.
1: Define a score function for any rank-k matrix with orthonormal columns E IR as
score (U) = =
min
Σ e ((clip (Uxx;;; Lf) us)::ks))
xiyi
sE[m] |1lsll,.c
1E/m/4
2: Define a net No of |le-rrdi & over matrices with orthonormal columns in Raxk,
3: Sample Upriv E No with Pr[UErt U] exp (- (~BL, BL,CC score score(U)). (U)).
4: Each user j [n] independently estimates oith arg min Σ e (((Urrii)) T
Xij: 0):0))
|| 1=m/2+1
5 Exponential Mechanism based Model Personalization
In this section, we take more general approach towards outputting a projector Upriv that approxi- mately 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 subspace closeness, we can guar- antec better convergence under milder assumptions. Recall the loss function Leop (U, V) from (1).
We want to optimize min UEK <VE**".,lu>ll
min
Ceop (U, (U. while ensuring e-DP in the billboard
model. (Here I. E RRd 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 Ey-net of radius @ over K. The algorithm is presented in Algorithm 4 (Algorithm AExp).
The privacy analysis of Algorithm AEsp follows from the standard analysis of exponential mechanism, and the utility analysis goes via first proving 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 e-differentially private in the billboard model.
Theorem 5.2 (Utility guarantee). Suppose the loss function E is E-Lipschitz in its first parameter, and C is the bound on the constraint set. Set the net size & = 1/(en) and the clipping norm b = 40vd log(mm) in Algorithm 4. Assuming & E (0, and that the feature vectors are drawn i..d. from ((0 1)d, we have (w.p. 2 1 1/mindd,1, Id))
d..
Vi
Risk (ackeop(Urriz Voriv) ;U' V+) 0 EC
-polyoo (d, n).
EN
mm
Here, U and V are any fixed values of the common embedding matrix (orthonormal, in Rdak)) and matrix of individual regression vectors (in TR 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 AExo (Theorem 5.2) is much more general than that in Theorem 4.2. Unlike Theorem 4.2, it allows arbitrary Lipschitz loss function f, 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= C=VI, one can make Theorems 4.2 and 5.2 comparable. Theorem 4.2 shows an excess population risk δ
d en2
+ m)
whereas Theorem 5.2 gives δ VI-
A-2
Theorem 4.2 is tighter in the
regime where 22k33.5 (...)) This difference is comparable to the so-called fast rates [43]. However, the sample complexity of Theorem 5.2 is better terms of m by a factor 1.1.5
Numerical Simulation
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

---

Non-private
Single model
2.5
Population MSE
2.0
2.5
1.0
0.5
8
10
epsilinn
Figure 2: MSE vs. per-user & for linear regression.
users (called own data), and ii) 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 (Algorithm AprivAltMiin 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 50 and rank k noise o₂ of target y is set to be 0.01. We normalize U to unit norm. We run Algorithm with full batch, i.e.,
We sample x. and v from Gaussian distributions, and the field
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 and pick optimal the number of epochs {1, 2,
In Figure 2, we fix 8 = 10-6 and plot the population mean squared error (MSE) computed based on the groundtruth model for multiple E. As reference, the MSE for a purely random model is around 4. In addition to (e, ddifferrena privacy, we also report the value of Kero-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 e = {1, 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 high values of E.
Conclusion
In this paper we studied the problem 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 per-user user and while preserving each user's '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 linear embedding function, (ii) Can we make variant of the exponential mechanism algorithm computationally feasible?, and (fii) Empirically validate the privacy/utility trade-offs on real world data sets.
As more and more ML models personalized for tastes, ensuring privacy of individuals' data is paramount to fair, responsible system. We provide 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 Google Faculty Research Award.
10

---

References
[1] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS' 16), pages 308-3 318-318,,1 2016.
[2] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 2003.
[3] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In NeurlPS, pages 1 11279-11221 2019.
[4] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. Foundations of Computer Science (FOCS), 2014.
[5] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
[6] Emmanuel J. Candès and Yaniv Plan. Tight oracle bounds for low-rank matrix recovery from minimal number of random measurements. CoRR, abs/1 00039, 2010.
[7] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pages 267-284, 2019.
[8] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, al. Extracting training data from large language models. arXiv preprint arXiv:2012.07885, 2020.
HerberttVVsss, Voss, Kather-
[9] Kamalika Chaudhuri. Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12MMar): 2011.
[10] Yinbo Chen, Xiaolong Wang, Zhuang Liu, Huijuan Xu, and Trevor Darrell. A new meta-baseline for few-shot learning. arXiv preprint N0X.::2003.0449900 2020.
[11] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. arXiv preprint urXiv:2102.07078, 2021.
[12] Chandler Davis. The rotation of eigenvectors by a perturbation. Journal of Mathematical Analysis and Applications, 6(2):159-173, 1963.
[13] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint N.Kiv:2002.09444 2020.
[14] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT, pages 486-503, 2006.
[15] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265-284, 2006.
[16] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, 2010.
[17] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pages 11-20, 2014.
[18] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. arXiv preprint arXiv: / 77070034000 2017.
[19] Robin C. Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: client level perspective. CoRR, abs/1712.07557, 2017.

---

[20] Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In STOC, 2014.
[21] Rui Hu, Yuanxiong Guo, Hongning Li, Qingqi Pei, and Yanmin Gong. Personalized federated learning with differential privacy. IEEE Internet Things J., 7(10):9530 95000,95399 2020.
[22] Shaoli Huang and Dacheng Tao. All you need is a good representation: A multi-level and classifier-centric representation for shw-shot learning. arXiv preprint arXiv: 1911. 12476, 2019.
[23] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674, 2013.
[24] Prateek Jain, Om Dipakbhai Thakkar, and Abhradeep Thakurta. Differentially private matrix completion revisited. In International Conference on Machine Learning, pages 2215-2223
PMLR, 2018
[25] Muhammad Abdullah Jamal and Guo-Jun Qi. Task agnostic meta-learning for few-shot learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11719-11727, 2019.
[26] Yihan Jiang, Jakub Konevený, Keith Rush, and Sreeram Kannan, Improving federated learning personalization via model agnostic meta learning. CoRR, abs/1909. 12488, 2019.
[27] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 531-540, 2008.
[28] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
[29] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[30] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10649-10657. IEEE Computer Society, 2019.
[31] Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and Ananda Theertha Suresh. Learning with user-level privacy. CoRR, abs/2102.11 11844 2021.
[32] Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar. Differentially private meta-learning, In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[33] Percy Liang. Cs229t/stat231: Statistical learning theory (winter 2016), 2016.
[34] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
[35] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103, 2007.
[36] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEBE, 2017.
[37] Seewong Oh, Prateek Jain, and Kiran Thekumparampil. Sample efficient linear meta-learning by alternating minimization. Personal communication, 2021.
[38] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of MAML.. arXiv preprint arXiv:1909.099 1909.09157, 2019.
12

---

[39] Or Sheffet. Old techniques in differentially private linear regression. In ALT, 2019.
[40] Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, Keith Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. CoRR, abs/2102.03448, 2021.
[41] Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pages 58-77. IEEE, 2017.
[42] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE, 2013.
[43] Karthik Sridharan, Shai Shalev-shwartz, and Nathan Srebro. Fast rates for regularized objectives. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2009.
[44] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. In Proceedings of the IEEE international conference on computer vision, pages
2017.
[45] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[46] Kiran Koshy Thekumparampil. Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Sample efficient linear meta-learning by alternating minimization, 2021.
[47] Yonglong Tian, Yue Wang, Dilip Krishnan, Joshua B Tenenbaum, and Phillip Isola. Re- thinking few-shot image classification: a good embedding is all you need? arXiv preprint arXiv:2003. //539 2020.
[48] Nilesh Tripuraneni, Chi Jin, and Michael I Jordan. Provable meta-learning of linear representa- tions. arXiv preprint arXiv:2002.11684 2020.
[49] Joel A Tropp.
User-friendly tail bounds for sums of random matrices. Foundations of compula- lional mathematics, 2012.
[50] Joel A Tropp. An introduction to matrix concentration inequalities. arXiv:1501.00 2015.
arXiv preprint
[51] Kangkang Wang. Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. CoRR, abs/1910.10252. 2019.
[52] Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. CoRR, abs/2000.004758, 2020.
13


Reviews:
[{"review_id": "wLIkTaAjfh7", "reviewer": "Reviewer_XcxK", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written and technically sound. My current decision is acceptance. However, the paper has several unclarities the authors should address.\n\nThe model personalization task and its privacy risk are well-motivated. The authors reveal a reasonable excess risk bound for their proposed method based on the exponential mechanism, which can be a significant technical contribution. \n\nAn unclarity comes from the upper bound shown in Theorem 4.2. The last term in this bound is a constant $\\sigma_F^2$ and is dominated when $n$ and $m$ are large. Also, this result indicates that $\\mathcal{A}_{\\mathrm{Priv-AltMin}}$ can be inconsistent. Hence, I'm wondering why this bound is reasonable. Additionally, since the constant term dominates the bound as mentioned above, the error bound shown in Theorem 1.1 is misleading; the constant term should not be ignored.\n\nSome notations are unclear. What is $f'$ in Lines 71-72? $\\mathcal{C}$ in Line 77 is not defined. \n\nIt is better to compare the resultant upper bounds with the best bound for the method without the privacy guarantee. By such a comparison, we can see the tightness of the present bounds roughly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " The limitations and potential societal impacts are adequately discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "ptpJmiaqbLl", "reviewer": "Reviewer_2osN", "summary": "\nThe 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. \n\nThe paper contribution is a theoretical analysis of the proposed algorithm with DP guarantees and utility bounds. \n\nAs 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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written, although the notations are heavy, the contribution very technical and a bit hard to follow. The paper includes a description of the setting and a less formal presentation of the contributions that are very welcome. However, two points could be improved. A first regret concerns the presentation of the algorithms. There is no informal explanation after Section 3 and even if lines are mostly easy to understand, some choices and notation are difficult to understand. A second point is that a discussion of Assumptions 4.1 is missing. \n\nThe generic approach is presented in Section 3 and  instantiated with linear regression in Section 4. The point that is unclear to me is how the data sets are split to estimate U and v. It is clear that the choice was to take different subsets for both estimations but this should be explicitly explained in the main text. Also, why the summation is over the first quarter of samples (i \\in [m/4]) for v on line 5 and the second quarter for U on line 6, and not taking half of the data for each estimation is not explained (The same comment can also be made for Algorithm 2). \n \nThm 4.2 presents the main (utility) result, a bound on the excess risk of Algo 1. Algo 1 has \\alpha,\\rho  RDP parameters and the result depends on \\epsilon and \\delta. It should be clearer to have coherent parametrization for the two. \n\nThe bound depends on structural  parameters of the regression v. In an oversimplified case, when these parameters are close to  constants, Remark 1 and 2 give comparisons of Thm 4.2 with the non DP case. It is not clear in the general case how these parameters impact the bound.\n\nEssentially, the proposed algorithm proceeds by alternating the optimization of the embedding and the optimization of the regression parameters in the embedded space and the privacy budget is split for the 2 subtasks. It is not discussed if the proposed split is optimal or not. Only the parallel composition is proposed and may not be suitable when the number of samples m is low, which is generally assumed in collaborative learning. \n\nAdditionally, a good starting point for the embedding is necessary to obtain Thm 4.2. This initialization step is proposed in Sect 4.2. Again a description of this algorithm is welcome. For instance why consecutive samples are used to estimate M^noisy and why U^init consists in its top eigenvectors.  \n\nStrengths \n- Interesting problem\n- Theoretically grounded\n- Clear presentation\n\nWeaknesses \n- Very technical and proofs are difficult to follow\n- Analysis conducted in the case of linear regression with independent features, which seems limited (and maybe limits the benefits of finding a common embedding)\n- No experimentation\n\n\ntypos and comments\n- l210 models\n- I don't understand the notation ||v||_2 \\leq R^k line 5 of Algorithm 1. \n- l255: citation is missing\n- Algorithm 3 should output U^init and not U^priv. Same in Lemma 4.6\n- I've try to read the proof in the supplementary, but they are too technical for the time I had to make a review. For instance l503-514 are not sufficiently explained for me. \n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sect. 6. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "jAZuDL26D_h", "reviewer": "Reviewer_AbPh", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper focuses on an important problem which is protecting the user-privacy in a multi-task setting. The setting considers multiple users each holds a dataset and the authors introduces an algorithm for private model personalization. The contribution of the work and the problem definition are clear and the theoretical analysis of privacy and utility seems correct to me. \n\nHowever, the main problem of this paper is lack of motivation. I couldn't understand how this method is different/better than any related published work in the literature. There are similar works proposed before, and the authors didn't discuss the similarities and the differences clearly. There are no experiments, so it is not possible to see how well this method performs on even toy dataset, so it is really difficult to foresee the success of the proposed approach. I will write in detail in the following section, but another concern is the limitations of the proposed approach. \n\nI can suggest to the authors to explain the goals of the proposed method better, compare with the previous works and run some experiments on at least some toy datasets to show the practicality of the proposed method better. As a minor comment, I encounter some typos/grammatical mistakes that makes to follow the paper difficult, so it could be also improved in the future.\n\n===================================================\n\nIn the rebuttal authors clarified my concern about comparison of this method with Gaussian mechanism. I read the paper again and read the other reviewers comments. In addition to that, they run some experiments and that further clarified my concerns. I'll update my score depending on these inputs. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As the authors already mentioned, the method has some limitations. The first question from my side is the reason of choosing exponential mechanism. There are some recent approaches such as \"Privacy Amplification by Sampling and Renyi Differential Privacy\" (Wang et al.) , \"Privacy Amplification via Random Check-Ins\" (Balle et al.), \"Accuracy Gains from Privacy Amplification Through Sampling for Differential Privacy\" (Hu et al.). These papers uses Gaussian mechanism and it has been proved that Gaussian mechanism is more efficient than exponential mechanism in iterative approaches. Could the authors please explain the reason of this choice?\n\nThe second one is the generalizability of the approach to deep networks. The proposed approach uses a two-layer neural network, where the first layer is shared across all users and the second layer is trained individually. I'm wondering how that method can be applied to different models. In the current version, it is a restrictive approach and it might not work/perform well on large or complex datasets as we encounter in real-world.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "KFHYXOSqq5w", "reviewer": "Reviewer_KGBe", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a strong paper. It's a well-written paper. It studies an important yet remarkably understudied problem that has many applications. It gives two types of algorithms: exponential mechanism based model personalization and model personalization via private alternating minimization. The algorithm and the theoretical results are sound. Although the algorithm is fairly natural, the idea of formulating the problem as learning a 2-layer neural network is very novel, and the result is quite exciting--it shows we can accurately share a linear representation of the data while preserving user-level privacy, and the error bounds and sample complexity are nearly-optimal. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provide several open problems that this work leads. This work has a positive social impact as it motivates practitioners and researchers to make their personalization ML systems differentially private.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes a setting in which multiple users, each with their own dataset, wish to collaborate so as to learn better personalized model, while maintaining the privacy of their data. In the framework analyzed, all users share a common, low-dimensional embedding model, the output of which is used as the input for each personalized model. The paper presents two algorithms, based on two DP mechanisms, and proves that they are $(\epsilon, \delta)$-DP while also providing bounds on the excess population risk w.r.t. non-private learning -- i.e., the price paid for private learning.

This is a very interesting and timely topic at the intersection of federated learning, on-device personalization and differential privacy. The theoretical results are compelling and clearly presented. The writing is OK, although I noticed a few typos in the intro -- mostly missing articles. The reviews ended up being unanimously positive. One reviewer was originally against acceptance, but was later convinced to change their score by the authors' response.

I am recommending this paper for a spotlight because I believe that DP personalization is an important emerging topic that has not yet received much attention in the community. However, I recognize that the paper did not receive very high scores, so I am comfortable with the SAC/PCs downgrading it to a poster if need be.

Note that the submitted manuscript does not contain experimental results, but the authors provided some during discussion at the request of a reviewer. I encourage the authors to include these in the paper. (Experiments may strengthen the case for a spotlight -- or even a full oral.)

I also encourage the authors to give the paper a close read for grammar, syntax and clarity, as there were multiple complaints about the paper's clarity, and I myself think the writing could be polished.
Decision: Accept (Spotlight)