A Statistical Framework for Personalized Federated Learning and Estimation: Theory, Algorithms, and Privacy
Authors: Kaan Ozkara
Antonious M. Girgis
Deepesh Data
Suhas Diggavi
Venue: ICLR 2023 poster (2023)
Keywords: Personalized Federated Learning
Personalized Statistical Estimation
Differential Privacy
Empirical/Hierarchical Bayes

Abstract: A distinguishing characteristic of federated learning is that the (local) client data could have statistical heterogeneity. This heterogeneity has motivated the design of personalized learning, where individual (personalized) models are trained, through collaboration. There have been various personalization methods proposed in literature, with seemingly very different forms and methods ranging from use of a single global model for local regularization and model interpolation, to use of multiple global models for personalized clustering, etc. In this work, we begin with a statistical framework that  unifies several different algorithms as well as suggest new algorithms.  We apply our framework to personalized estimation, and connect it to the classical empirical Bayes' methodology. We develop novel private personalized estimation under this framework. We then use our statistical framework to propose new personalized learning algorithms, including AdaPeD based on information-geometry regularization, which numerically outperforms several known algorithms. We develop privacy for personalized learning methods with guarantees for user-level privacy and composition. We numerically evaluate the performance as well as the privacy for both the estimation and learning problems, demonstrating the advantages of our proposed methods.

Published as a conference paper at ICLR 2023
A STATISTICAL FRAMEWORK FOR PERSONALIZED FED- ERATED LEARNING AND ESTIMATION: THEORY, ALGO- RITHMS, AND PRIVACY
Kaan Ozkara", Antonious M. Girgis", Deepesh Data & Suhas Diggavi Department of Electrical and Computer Engineering University of California, Los Angeles fkaan, amgirgis s fuucla. edu, deepesh. data@gmail. com, suhassee. ucla .edu
ABSTRACT
A distinguishing characteristic of federated learning is that the (local) client data could have statistical heterogeneity. This heterogeneity has motivated the design personalized learning, where individual (personalized) models are trained, through collaboration. There have been various personalization methods proposed in lit- erature, with seemingly very different forms and methods ranging from use of a single global model for local regularization and model interpolation, to use of multiple global models for personalized clustering, etc. In this work, begin with statistical framework that unifies several different algorithms as well as suggest new algorithms. We apply our framework to personalized estimation, and connect it to the classical empirical Bayes' methodology. We develop novel private personalized estimation under this framework. We then use our statistical frame- work to propose new personalized learning algorithms, including AdaPeD based on
regularization, which numerically outperforms several known algorithms. We develop privacy for personalized learning methods with guarantees for user-level privacy and composition. We numerically evaluate the performance well as the privacy for both the estimation and learning problems, demonstrating the advantages of our proposed methods.
INTRODUCTION
The federated learning (FL) paradigm has had huge recent success both in industry and academia (McMahan et al. 2017 Kairouz et al. [002I). as it enables to leverage data available in dispersed devices for learning while maintaining data privacy. Yet, it was recently realized that for some applications, due to the statistical heterogeneity of local data, a single global learning model may perform poorly for individual clients. This motivated the need for personalized learning achieved through collaboratio,, and there have been a plethora of personalized models proposed in the literature as well (Fallah et al. 2020 Dinh et al. 2020 Deng et al., 2020) Mansour et al.) 2020 Acar et al. 2021 Li et al.) 2021 Ozkara et al. 2021 Zhang al. 2021| Hu et al., (020). However, the proposed approaches appear to use very different forms and methods, and there is a lack of understanding of an underlying fundamental statistical framework. Such statistical framework could help develop theoretical bounds for performance, suggest new algorithms as well as perhaps give grounding to known methods. Our work addresses this gap.
In particular, we consider the fundamental question of how one can use collaboration to help personalized learning and estimation for users who have limited data that they want keep private. Our proposed framework founded on the requirement not only of personalization but also privacy, as maintaining local data privacy what makes the federated learning framework attractive and thus any algorithm that aims to be impactful needs to also give formal privacy guarantees. The goal of this paper is develop statistical framework that leads to new algorithms with provable privacy guarantees, and performance bounds. Our main contributions are (i) Development of statistical framework for federated personalized estimation and learning (ii) Theoretical bounds and
"Equal Contribution.

---

Published as a conference paper at ICLR 2023
novel algorithms for private personalized estimation (iii) Design and privacy analysis of new private personalized learning algorithms; as elaborated below. Omitted proofs/details are in appendices.
Statistical framework: We connect this problem to the classical empirical Bayes' method, pi- oncered by Stein [956); D James& & Stein [961): Robbins (956)), which proposed a hicrarchical statistical model Gelman al. (2013). This is modeled by unknown population distribution P from which local parameters { are generated, which in turn generate the local data through the distribution Q(::). Despite the large literature on this topic, especially in the context of statistical estimation, creating a framework for FL poses new challenges. In contrast to classical empirical Bayes' estimation, we introduce a distributed setting and develop framework that allows information (communication and privacy) constraints" This framework enables us to develop statistical perfor- mance bounds as well as suggests (private) personalized federated estimation algorithms. Moreover, we develop our framework beyond estimation, for (supervised) distributed learning, where clients want to build local predictive models with limited local (labeled) samples; we develop this framework in Section 3 which leads to new (private) personalized learning algorithms.
Private personalized estimation: Our goal is to estimate individual (local) parameters, when each user has very limited (heterogeneous) data. Such a scenario motivates federated estimation of individual parameters, privately. More precisely. the users observe data generated by an unknown distribution parametrized by their individual (unknown) local parameters 0,, and want estimate their local parameters 0; leveraging very limited local data; see Section 2 for more details. For the hierarchical statistical model, classical results have shown that one enhance the estimate of individual parameters based on the observations of a population of samples, despite having independently generated parameters from an unknown population distributions. However, this has not been studied for the distributed case, with privacy and communication constraints, which we do (see Theorem 2 for the Gaussian case and Theorem 4 for the Bernoulli case, and also for mixture population models in Appendix D). We estimate the (parametrized) population distribution under these privacy and communication constraints and use this as an empirical prior for local estimation. The effective amplification of local samples through collaboration, in Section 2 gives us theoretical insight about when collaboration is most useful, under privacy and/or communication constraints. Our results suggest how to optimally balance estimates from local and population models. We also numerically evaluate these methods, including application to polling data (see Section + and Appendices) to show advantages of such collaborative estimation compared to local methods.
Private personalized learning: The goal here is to obtain individual learning models capable of predicting labels with limited local data in supervised learning setting. This is the use case for federated learning with privacy guarantees. It is intimately related to the estimation problem with distinctions including (i) design good label predictors rather than just estimate local parameters (ii) the focus on iterative methods for optimization, requiring strong compositional privacy guarantces. Therefore, the statistical formulation for learning has a similar flavor that in estimation, where there is a population model for local (parametrized) statistics for labeled data; see Section 3 for more details. We develop several algorithms, including AdaPeD (in Section 3.22.. AdaMix (in Section 3.1). and DP-Ada (in Section (33). inspired by the statistical framework. AdaPeD uses information divergence constraints along with adaptive weighting of local models and population models. By operating in probability (rather than Euclidean) space, using information-geomety (divergence), enables AdaPeD to operate with different local model sizes and architectures, giving it greater flexibility than existing methods. We integrate it with user-level privacy to develop DP -A-AdPPe with strong compositional privacy guarantees (Theorem B) AdaMix x is inspired by mixture population distributions, which adaptively weighs multiple global models and combines it with local data for personalization. We numerically evaluate these algorithms for synthetic and real data in Section [
Related Work. Our work can be seen in the intersection of personalized learning, estimation, and privacy. Below we give a brief description of related work; a more detailed comparison which connects our framework to other personalized algorithms is given in Appendix J
Personalized FL: Recent work adopted different approaches for learning personalized models, which can be explained by our statistical framework for suitable choices of population distributions as explained in Appendix []] These include, meta-learning based methods (Fallah et al. 2020 Acar
al. 2021 Khodak et al. 2019]; regularization (Deng et al. 2020 Mansour et al. 2020 Hanzely
'The homogencous case for distrihuted estimation is well-studied; see (hhag 2016 and references.
2

---

Published as a conference paper at ICLR 2023
& Richtárik
)020);
clustered FL Zhang al. 2021 Mansour et al. 2020;
Ghosh et al. 2020
Smith et al.
2017) | MMrroq et al. 2021); ) using knowledge distillation (Lin et al. 2020 Ozkara
ct al. 2222]; multi-tan task Learning (Dinh et al. [020 Hanzely & Richtárik] 2020 Smith et al. 2017
Vanhaesebrouck et al. 2017 Zantedeschi et al. 2020); and using common representations (Du et al.
Raghu al. | [020] Tian al.] 2000] Collins al. (02T) and references therein. Our work
enables not just unified view of these methods, but suggests new algorithms developed in this paper,
along with privacy guarantees.
After the conclusion of our work (Ozkara et al. 2022, July we found two concurrent and independent works (Kotelevskii et al., 2022. Junej Chen et al., 2022) that use a hierarchical Bayes approach to construct personalized learning algorithms,, and are closest to our statistical framework. (Kotelevskil et al. 2022, June) is based on using a MCMC method to estimate a population distribution; such methods could be computationally intensive (see the discussion in (Blei et al. 2003); (Chen et al. 2022) considers the unimodal Gaussian prior, and effectively does what the classical empirical Bayes suggests (see also Theorem D. None of these works consider privacy, which we do both for estimation and learning algorithms (see Theorems
Appendix [ and for DP De-AdaPeD in Theorem 5). Note that MCMC methods could have detrimental privacy implications. Also, they do not include ceeemaatoo-ggommetee techniques (like our AdaPeD) or methods inspired by mixture distributions (e.g., AdaMix)
Privacy for Personalized Learning. There has been a lot of work in privacy for FL. when the goal is to learn a single global model (see (Girgis et al./ (021b) b) and references therein); though there
fewer papers that address user-level privacy (Liu et al 2020 Levy et al. [021] Ghazi et al. [022]] There has been more recent work on applying these ideas to learn personalized models (Girgis et al. 2022: Jain et al.) 2021b; Geyer et al. [017 Hu et al. 2020 Li et al. 2020). These are for specific algorithmsmmodels e.g., Jain et al. (202Ib) focuses on the common representation model for linear regression described earlier or on ievel privacy (Hu et al. 20200 Li et al. (020). We believe that DP-AdaPeD proposed in this paper is among the first user-level private personalized learning algorithms with compositional guarantees, applicable to general deep learning architectures.
2 PERSONALIZER ESTIMATION
We consider a client-server architecture, where there are m clients. Let TP(T) denote global population distribution that is parameterized by an unknown I and let o,..... 6m are sampled i.i.d. from PTT and are unknown to the clients. Client i is given dataset X, == (X;i.... X.,), where Xij.j E [n] are sampled i.i.d. from some distribution Q(:)), parameterized by 0, E Rd. Note that heterogeneity in clients' datasets is induced through the variance in PPTT), and if the variance of IP(T)
is zero, then all clients observe i.i.d. datasets sampled from the same underlying distribution.
The goal at client for all [m]] is to estimate O, through the help of the server. We focus on one-round communication schemes, where client j applies a (potentially randomized) mechanism on its dataset X, and sends 9; == q(X,) ) to the server, who aggregates the received messages, which is denoted by Agg(A1 )m ). and broadcasts that to all clients. Based on (X,, Agg(O).... ....),m)). client i outputs estimate O, of 0,, We measure the performance of θ through the Bayesian risk for mean squared eтrоr (MSE), as defined below (where P is the true prior distribution with associated density x, O: P is the true local parameter, and 0 = 0(X,, Agg(g),.. ... (m)) is the estimator):
Ea.-PEp D.. xm 10. - -0,1 = _ Ni............. x 0. - (0.)00,
(1)
The above statistical framework can model many different scenarios, and we will study in detail three settings: Gaussian and Bernoulli models (Sections]) 2.1iionns1.1111 2.2 below), and Mixture model (Appendix (
2.1 GAUSSIAN MODEL
In the Gaussian setting, PTT) N(H, L.d and Q(0,) Ni ((O,,ooLL)) for all i E implies that ......,.................. Om (H, ozLLa i..d and XII..... Xn, Ai La i..d for i e [m]. Here, do 2 0, > 0 are known, and μ., ........ On are unknown. For the case of single local
[m], which
In our understanding their numerics seem be restricted unimodal Gaussian population model.
3

---

Published as a conference paper at ICLR 2023
sample this is identical to the classical James-Stein estimator (James & Stein 1961): Theorem doess a simple extension for multiple local samples and is actually a stepping stone for the information constrained estimation result of Theorem Omitted proofs/details are provided in Appendix B
Our proposed estimator. Since there is no distribution on μ. and given μ. we know the distribution of 0 s, and subsequently, of Xiy ss. So, consider the maximum likelihood estimator:
i mm. P = arg max P(O..X;)lP (0).... mm XI...... Xm 01....0mm.
(2)
Theorem 1. Solving ② yields the following closed form expressions for ju and 0 .1.....
Om:
o
X
and
0, =ax +1 a) for E [mm] where og + o. o2/n
(3)
The above estimator achieves the MSE: Es, XI........ 00 - -0:0,1 م do + aa)
follows that the mechanism q and the aggregation funetion Agg for the estimators in 33 (as described
in (I) are just the average functions, where client sends qi (X,) = X; = E== 1==1-9 Xi, to the server, and the server sends jı := Agg(A). 4m) m Σ qi back the clients.
Remark 1 (Personalized estimate vs. local estimate). When ae 0, then 0. which implies that 0. + It and MSE - do mn. Otherwise, when oā large in comparison to o / or n + 00, then + 1, which implies that 0, + X; and MSE + do n. These conform to the facts that (i) when there is no heterogeneity, then the global average is the best estimator, and (ii) when heterogeneity not small, and we have lot of local samples, then the local average is the best estimator: Observe that the multiplicative gap between the MSE of the proposed personalized estimator and the MSE of the local estimator (bused on local data only, which gives MSE of do //n) is given by (~=e + a)) < 1 that proves the superiority of the personalized model over the local model, which is equal to 1/m when σe 0 and equal to 0.01 when
10 n 100 and o² 10, oī 10-3 for example.
Remark 2 (Optimality of our personalized estimator). In Appendix B we show the minimax lower bound: inf, supgge Ex-N((o [x(x) 0| 2 do? (~-a + a). which exactly matches the upper bound on the MSE Theorem ] thus establishes the optimality our personalized estimator in (3)
Privacy and communication constraints. Observe that the scheme presented above does not protect privacy of clients' data and messages from the clients to the server can be made communication efficient. These could be achieved by employing specific mechanisms q at clients: For privacy, we can take a differentially-prinn -private 9. and for caaimuunnaationfffciineee Inspired by the scheme presented above, here consider q be a function q : Rd + Y that takes the average of n data points as its input, and the aggregator function Agg to be the average function. Define By : m xi=1 (())) and consider the following personalized estimator for the i-th client:
we can take to be a quantizer.
- =x=aX, +1 a).
for some E [0, 1].
(4)
Theorem 2. Suppose for all x E IRdd, q satisfies B[((=)] x and [(( 1: s dož for some finite 0g. Then the personalized estimator in has MSE:
do? /1-0
og + o0/m-
Eo X 10, 0:112
where
(5)
og + 2 m o2/1
Furthermore, assuming E [-r, for some constant r (but is unknown), we have:
1. Communication efficiency: For any E N. there is a whose output can be represented
using k-bits (i.e., q is quantizer) that achieves the MSE in (5) with probability at least
1 2/mn and with 0g (25-1) where b + oo / /log m2
Vlog(m?n).
V
2. Privacy: For any en E (0, 1), 8 > O, there is a q that is user-level (Eo, 8)-locally differentially
private, that achieves the MSE in (5) with probability at least 1- - 2/ and with Og
b. (8log(2/8), where b + σe o /log(m?n) "x /log(m?n).
4

---

Published as a conference paper at ICLR 2023
2.2 BERNOULLI MODEL
For the Bernoulli model, IP is supported on [0, 1], and pi..... Pm are sampled i.i.d. from IP, and client i is given n i.i.d. samples X:I.-.. Xin Bern(p;). This setting has been studied in (Tian al. (2017): Viiaaak et al. (2019) for estimating P. whereas, our goal is to estimate individual parameter P: at client using the information from other clients. order derive closed form MSE result, we assume that IP is the Beta distribution Here, I = (a, P1........... Pm are unknown, and client i's goal is to estimate p: such that the Bayesian risk X X.. (Pi pt)² minimized, where denotes the density of the Beta distribution. Omitted proofs/details are provided in Appendix [
Analogous to the Gaussian case, we can show that if o., are known, then the posterior mean estimator has a closed form expression: p; aX; (1 -) where 7/o+B+n and c/(a+3) is the mean of the beta distribution. When a, 38 are unknown, inspired by the above discussion, natural approach would be to estimate the global mean μ = e/(a-0) and the weight a = "/(a+8+n), and use that the above estimator. Note that, for x² = (a2((a+t99 (a) is the variance of the beta distribution. Therefore, it is enough to estimate and o² for the personalized estimators {6i}. In order make calculations simpler, instead of making one estimate of jı; 0² for all clients, we let each client make its own estimate of o² (without using their own data) as: P4. m- Eiạ; X1 and o = m- Eizi (X: fax) 2 and then define the local
need to estimate a + 8, which is equal to M "(1=1)/0² 1, where
weight as 0; P,0-- I+n' Now, client i uses the following personalized estimator:
p: = a, + (1 a.)
(6)
Theorem 3. With probability at least 1 mn' the MSE of the personalized estimator in (6) is given by: a8
PAi..Ex,....... (f: -p.)² S ( ((o++)(o++++))) + E[(1 - -,,) (()))((( (0++)))0 + 3log( (mm?")) Remark 3. When n + co, then ā - 1, which implies that MSE tends to the MSE of the local estimator X,, which means if local samples are abundant, collaboration does not help much. When o²= =²==8/(an (4+ 1) - O, Le, there is very small heterogeneity in the system, then 0; -> O, which implies that MSE tends the error due to moment estimation (the last term in the MSE in Theorem 3
a8
Privacy constraints. For any privacy parameter cg > O and input x E [0, 1], define grriv : :10, 1] + R:
T 250 250 +I++I w.P. e0
ppiv (x)
10
w.p. 200 + x cra+1
e50 -1
The mechanism gariv is unbiased and satisfies lser- 60 Thus, the ith client sends qoriv (X+) to the server, which computes pirriv 1 m-1 Eizi (X)) and the variance o, ((prrv))
m- (a (X1)) )² and sends (D.riv _o, o.(pri)) to client i. Upon receiving this, client i 2 -p 2/2 +n and uses piriv -apriv X; - -agin )arriv to estimate pi. 2ip0
defines apriv
Theorem 4. With probability at least 1 1
mn. the MSE of the personalized estimator p, de- ag
fined above is given by: Ep Egpre (oppi,X1,. XI....X.... ppry
(P. (P.riv p.) S
+ B[(1
o8 (C+t))
(c"0-1)² log(Am (4m Am²n))
3( 11=0--I"(m-
See Remark 4 (in Appendix B) and Remarks 6 and (in Appendix C for discussion on privacy, communication efficiency, and client sampling.
PERSONALIZED LEARNING
Consider client-server architecture with m clients. There is an unknown global population distribu- tion P(T Jove Rdd from which m. i.i.d. local parameters ......, Om. E IRd are sampled. Each client
Beta distribution has a density Beta(o, .) Ho.a) ".l.))="''4 "- (1-=)) is defined for os, > 0 and [0. 1),
where B(a,, (3) a normalizing constant. Its mean is ats and the variance (.+.)(o0+34))
*Upon receiving (X,) from all clients, the server can compute (74, a,) ) and sends (7., o() ) to the i-th client. For simplicity we will consider this unknown population distribution P to be parametrized by unknown (arbitrary) parameters r.
5

---

Published as a conference paper at ICLR 2023
i [m] is provided with a dataset consisting of n data points {(X11 Ya). ......... (Xins Ynn); where
Yi 's are generated from (Xiz, 0.) using some distribution pe. (Yy (1))) Let Y; := -Yii..... Ymn)
and X; == (Xi....,, Xin) for i [m]. The underlying statistical model for our setting is given by
m
m a
(X..)) (0....., l mm ,I.... X Xm)
II p
IIII Po. (Y))))))
(8)
i=1j=1
Note that if we minimize the negative log likelihood of (8). we would get the optimal parameters:
m
0 6m = arg min
ΣΣ o..... Om i= ==1
- -log(po, (Yi) (Yill + Σ log(p(0.)).
Here, fi(O:)= =- ブ log(pe, (Yig (x,))) denotes the loss function at the i-th client, which only depends on the local data, and R( == Σ.= log(p(0.)) is the regularizer that depends on the (unknown) global population distribution !' (parametrized by unknown I'). Note that when clients have little data and we have large number of clients, i.e., n < m- the setting of federated learning, clients may not be able to learn good personalized models from their local data alone (if they do, it would lead to large loss). In order to learn better personalized models, clients may utilize other clients' data through collaboration, and the above regularizer (and estimates of the unknown prior distribution P. through estimating its parameters I') dictates how the collaboration might be utilized. The
statistical framework (9) can model many different scenarios, detailed below:
1. When P(T) GM((P)) (p 31 (or,) is Gaussian mixture, for r {(pp))- (1)) (oo,)==1)) pt 2 0, E/= Pt 0o,1 2 0, RR,, then R((0:)) - ) )/(((T00,)) )22)) Here, the client models 0 ...... On are drawn i.i.d. from PP(T), where 0; ~ ~N (N,, La) with prob. pr, for I = ,,...,k.. For - 1, R({0:)) = md log(2Toz) - -x || 2.12 Here, unknown μ can be connected to the global 20r
-E log (Ek pt exp( [|M 20
2
model and 0,'s as local models, and the alternating iterative optimization optimizes over both. This justifies the use of lg regularizer in earlier personalized learning works (Dinh et al. 2020
Ozkara et al. 2021 Hanzely & Richtárik 2020 Hanzely et al. 2020 Li et al. 2021).
2. When P(T) = Laplace( b), for r = {1,, b >> 0}, then R({0.)) = m (2g) >
100 MMI
3. When Pe, (Xiy)) is according to (V,,, (2), then f((O,) is the quadratic loss as in linear (1-
regression. When po. (Y,) Xxj) = a (0, (x)) Ku - X.,))) (1-))) where (2) =
1/1+e-* for any 2 E R. then ((,)) is the cross-entropy (or logistic) loss as in logistic regression.
3.1 ADAMIX: ADAPTIVE PERSONALIZATION WITH GAUSSIAN MIXTURE PRIOR
Now we write the full objective function for the Gaussian mixture prior model for a generic local loss function (0.) at client (the case of linear/logistic regression with (single) Gaussian prior and solving using alternating gradient descent is discussed in Appendices
arg min Mp.
F.Tm (0.)
= Σ 1=1
(Fi(0.) log(
k
pl exp(
|4,
0
/(((
20
1=1
(10)
common example of (0,) is a generic neural network loss function with multi-class softmax output layer and cross entropy loss, i.c., f((0.) == =,=; llg(pe, (Yig x), where pe, (Yi, (xa) where ({2) = 1/1-e- for any z E R. To solve (00), we
o ((0,, Xxy)))x(t can either use alternating gradient descent approach. or we can a clustering based approach where the server runs a (soft) clustering algorithm on received personalized models. We adopt the second approach here (described in Algorithm T) as it provides an interesting point of view and can be combined with DP clustering algorithms. Here clients receive the global parameters from the server and do a local iteration on the personalized model (multiple local iterations can be introduced as in FedAvg (McMahan et al. 2017)), later the clients send the personalized models. Receiving the personalized models, server initiates GMM algorithm that outputs global parameters
o (0,,
A discrete mixture model can he proposed as special case of GM with 0 variance. With this we can recover similar algorithm in Marfoq et al. (202)). Further details are presented in Appendix G

---

Published as a conference paper at ICLR 2023
3.2 ADAPED: ADAPTIVE PERSONALIZATION VIA DISTILLATION
It has been empirically observed that the knowl- edge distillation (KD) regularizer (between local and global models) results in better performance than the & regularizer (Ozkara al. 2021). In fact, using our framework, we can define, for the first time, certain prior distribution that gives the KD regularizer (see Appendix H.. We use the following loss function at the i-th client:
Algorithm 1 Personalized Learning with Gaussian Mixture Prior (AdaMix)
Input: Number of iterations T, local datasets (X,, Y,) for E [m]] learning rate 17.
1: Initialize
(0)
and
P(O), 14
(0)
8,1 0,k-
2: for t = 1 to T do
f.(),) + log(2 + f (K: 1))
3: On Clients:
(11)
2τb
4: for i = 1 to m: do
where l denotes the global model, 0g denotes the personalized model at client i, and ab can be viewed as controlling heterogeneity. The goal for each client is to minimize its local loss fune-
5: Receive 1P(t-)
1 (t-1)
and
08,1 ...... a from the server
(t-1)
6:
Update the personalized parameters:
tion, so individual components cannot be too large. For the second term, this implies that du cannot be unbounded. For the third term, if 1:0 14) is large, then tà will also increase (implying that the local parameters are too de- viated from the global parameter), hence, it is better to emphasize local training loss to make the first term small. If / (0;// (a) is small, then ab will also decrease (implying that the local pa- rameters are close to the global parameter), so is better to collaborate and learn better personal- ized models. Such adaptive weighting quantifies the uncertainty in population distribution during training, balances the learning accordingly, and improves the empirical performance over non- adaptive methods, c.g., (Ozkara et al. 202I).
v
cm (0) (0(--1)
Send 0 to the server
7:
8:
end for
9:
At the Server:
Receive 0( ..... (0 from the clients
10:
11: Update the global parameters:
p(t) (e) Mh 0.11 0,k
(t)
+ GMM(
e
12: Broadcast (()), 1 10
H to all
clients
13: end for
Output: Personalized models ...... T
To optimize [1] propose an alternating min- imization approach, which we call AdaPeD; see Algorithm 2 Besides the personalized model 0 each client keeps local copies of the global model μıţ and of the dissimilarity term of and at synchronization times, server aggregates them to obtain global versions these μı,, ... In this way, the local training of 0 also incorporates knowledge from other clients' data through pt: In the end, clients have learned their personalized models {0, mm
3.3
DP DP-ADAA ADAPED: DIFFERENTIALES PRIVATE ADAPTIVE PERSONALIZATION VIA DISTILL..
Note that client i communicates ut; of (which are updated by accessing the dataset for computing the gradients h kf) to the server. So, to privatize ut vof client i adds appropriate noise to h kt. In order to obtain DP AdaPeD, we replace lines 13 and 15, respectively, by the update rules:
h
++1 = 11 p1
72 max(Ili///CC.. + +11) and wit = of 173 max (k + t2))
where v1 NO, o2 11a) and 12 .N(00, 92 for some og 0 that depend on the desired privacy level and C1, C2, which are some predefined constants.
The theorem below (proved in Appendix M states the Rényi Differential Privacy (RDP) guarantees.
Theorem 5. After T iterations, DP -d-ddaPeD satisfies (a, RRD) for a > 1, where c(a) =
K 2 6
C² + Koo ) where m
c²
K. denotes the sampling ratio of clients at each global iteration.
Ko
We bound the RDP, as it gives better privacy composition than using the strong composition (Mironov et al. 2019). We can also convert our results to user-level (c, 8DP by using the standard conversion from RDP to (c, DDP (Canonne et al. 2020). See Appendix A for background privacy.
7

---

Published as a conference paper at ICLR 2023
Figure 1: Fig. la we plot MSF vs. 60 for personalized estimation. In Fig. [b we plot Test Accuracy vs. on FEMNIST with client sam- pling 0.33, for DP-AdaPeD with unsampled elient iterations. Since local training is private, both plots remain constant against
mator DP Persona Leat Eoilmdorr
ASS
(a) Private Estimation (Sec. 2.1
(b) Private Learning (Sec.
3.3
4 EXPERIMENTS
Personalized Estimation. We run one experi- ment for Bernoulli setting with real political data and the other for Gaussian setting with synthetic data. The latter one is differentially private.
Algorithm 2 Adaptive Personalization via Distilla- tion (AdaPeD)
Parameters: local variances (vi?), personalized models (0?). local copies of the global model (k.), learning rates 72; 18s, synchronization
Political tendencies on county level. One natural application of Bernoulli setting is mod- cling bipartisan elections (Tian et al. 2017). We did a case study by using US presidential elec-
gap r
1: for t = 0 to T - do if T divides / then
2:
tions on county level between 2000-2020, with
3:
On Server do:
m = 3112 counties in our dataset. For each
Choose subset K S [n] of K clients 5: Broadcast jz' and ef
4:
county the goal is to determine the political ten- dency parameter ps. Given 6 election data we did 6-fold cross validation, with 5 elections for training and 1 election for test data. Local es-
6: On Clients E KC' (in parallel) do:
7: Receive μ v/; set μa n of th!
8:
end if
timator takes an average of 5 training samples and personalized estimator is the posterior mean. To simulate Bernoulli setting we set the data equal to if Republican party won the election and 0 otherwise. We observe the personalized estimator provides MSE (averaged over 6 runs) gain of 10.7 = 1.9% against local estimator.
9: On Clients i E KC (in parallel) do:
/o (O)
10: Compute g = Vo fi(0') +
20
11:
Update: 0 O mg
12:
Compute h = Vay s (0 p2)/200
13:
Update: uo μ -2hh
14: Compute k = 1 ( 1 +1+"1+++*22000 1/2(0))²
DP personalized estimation. To measure
20:
the performance tradeoff of the DP mechanism 15:
Update: wi+ = of 7akk
described in Section 2.1 we create a synthetic
16:
if T divides t + then
experiment for Gaussian setting. We let m = 10000, n 15 and σg = 0.1, oz 0.5, and create a dataset at each client as described in Gaussian setting. Applying the DP mechanism we obtain the following result in Figure Ta Here, expected, when privacy is low (eo is high) the private personalized estimator recovers the reg- ular personalized estimator. For higher privacy
17:
Clients send 14! and vif to Server
18:
Server receives [1])er" and (wieer
19:
Server computes 11 1+1 = 1
K Eiek p
and 1++ K EiEK vs
20: end if
21: end for
Output: Personalized models (0,²) )mm
the private estimator's 's performance starts to become worse than the non- non-private estimator.
Personalized Learning. First we describe the experiment setting and then the results.
Experiment setting, We consider image classification on MNIST, FEMNIST (Caldas et al. 2018). CIFAR-10. CIFAR- 100 (experimental details for CIFAR- 100 is given Appendix K); and train CNN, similar to the one considered in (McMahan et al. 2017). that has 2 convolutional and 3 fully connected layers. We set m = for FEMNIST and m 50 for MNIST, CIFAR-10. 10, CIFAR- For FEMNIST, we use subset of 198 writers so that each client has access to data from 3 authors, which results in a natural type of data heterogeneity due to writing styles of authors. On MNIST, CIFAR-10 we introduce pathological heterogeneity by letting each client sample data from 3 and 4 randomly selected classes only, respectively. We set T = 10 and vary the batch size so that each epoch consists of 60 iterations. On MNIST we train for 50 epochs, on CIFAR- 10 for 250 epochs, on FEMNIST for 40 and 80 epochs, for 0.33 and 0.15 client sampling ratio, respectively. We discuss further details in Appendix K
8

---

Published as a conference paper at ICLR 2023
Table 1: Test accuracy (in %) for CNN model. The CIFAR-IO, MNIST, and FEMNIST columns have client sampling ratios of 0.2, 0.1, and 0.15, respectively.
Method
CIFAR-10
CIFAR-100
FEMNIST
FedAvg
60.86 + 0.94
30.48 1 0.33
92.18 1 0.13
FedAvg+fine tuning Jiang et al.
2019
63.12 0.31
39.98 0.26
94.12 1 0.26
AdaPeD (Ours)
72.49 + 0.42
53.11
96.55 + 0.32
pFedMe (Dinh et al. 2020
69.53 + 0.16
43.65 0.18
94.95 + 0.55 0.55
Per-FedAvg FFllah
2020)
59.95 + 0.79
34.78 0.41
93.51 0.31
QuPeD (FP) (Ozkara a
2021
71.61 0.70
51.94 :.21 0.21
95.99 + 0.08
Federated (Shen et al.
2020
71.09 + 0.67
50.42 + 0.26
1.12+
Method
3.35
13.16
27.30
Table 2: (DF-AdaPeD) Test
Accuracy (in %) vs. e on MNIST without client sampling.
DP-FedAvg
11.73 + 0.85
29.91 + 1.28
55.79 + 0.29
DF-AdaPeD (Ours)
93.32 1.18
98.51 + 0.90
99.01 + 0.65
Method
T
Y 20
71
Table 3: Mean squared error of our
AdaMi x algorithm and the local train- ing for linear regression.
Local Training
39.93 = 0.13
30.02 0.08
19.97 + 0.07
AdaMix
10.42 = 0.15
3.12 0.04
2.35 + 0.04
Results. In [able we compare AdaPeD against FedAvg McMahan al. 2017). FedAvg+ (Jiang
ct al.
2019) and various personalized FL algorithms: pFedMe (Dinh et al.) (2020), Per- FedAvg (Fallh
al. 2020). QuPeD (Ozkara al., 2021 without model compression, and Federated MI. (Shen
2020). We report further results in Appendix K We observe AdaPeD consistently outperforms other methods. It can be seen that methods that use knowledge distillation perform better; on top of this, AdaPeD enables us adjust the dependence on collaboration according to the compatibility of global and local decisions/scores. For instance, we set oğ to a certain value initially, and observe it progressively decrease, which implies clients start to rely on the collaboration more and more. Interestingly, this is not always the case: for DP-AdaPeD, we first observe a decrease in of and later it increases. This suggests: while there is not much accumulated noise, clients prefer to collaborate, and as the noise accumulation on the global model increases due to DP noise, clients prefer not to collaborate. This is exactly the type of autonomous behavior we aimed with adaptive regularization.
et al.
DP-AdaPeD. In Figure [igure[bJandd an] Table we observe performance of DP-DD----E AAdaPeD under different values. AP-AdaPeD outperforms De-FedAvg because personalized models do not need to be privatized by DP mechanism, whereas the global model needs to be. Our experiments provide user-level privacy (more stringent, but appropriate in FL), opposed to the item-level privacy.
DP-AdaPeD with unsampled client iterations. When we let unsampled clients to do local iterations (free in terms of privacy cost and realistic scenario in cross-silo settings) deseribed in Appendix H.] we can increase DP -P-AdaPeD's performance under more aggressive privacy constants c. For instance, for FEMNIST with 1/3 client sampling obtain the result reported in Figure lb
AdaMix. We consider linear regression on synthetic data, with m = 1000 clients and each client has n E (10, 20, 30) local samples. Each local model 0, E RRd is drawn from a mixture of two Gaussian distributions M(u,, Σ) and (N-H,, E), where Σ = 0.001 x Ta and d = 50. Each client sample (X,,, Yıj) distributed as X1j ~ (O( and Yg (X 0.) + Way. where Way ~ (O 0.1). Table demonstrates the superior performance of AdaMix x against the local estimator.
5 CONCLUSION
We proposed a statistical framework leading to new personalized federated estimation and learning al- gorithms (e.g., AdaMix, AdaPeD); we also incorporated privacy (and communication) constraints into our algorithms and analyzed them. Open questions include information theoretic lower bounds and its comparison to proposed methods; examination of how far the proposed alternating minimization methods (such as in AdaMix, AdaPeD) are from global optima]
The work in this paper was partially supported by NSF grants 2139304, 2007714 and gift funding by Meta and Amazon.

---

Published as a conference paper at ICLR 2023
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ruizhao Zhu, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Debiasing model updates for improving personalized federated training. In International Conference on Machine Learning, pp. 21-31. PMLR, 2021.
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4): FOCS17-97, 2019.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpre- tations and renyi differential privacy. In Silvia Chiappa and Roberto Calandra (eds.). International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pp. 2496-25006 PMLR, 2020.
Leighton Pate Barnes, Yanjun Han, and Ayfer Ozgur. Lower bounds for learning distributions under communication constraints via fisher information. Journal of Machine Learning Research, 21 (236):1-30, 2020.
Jeremy Bernstein, Yu- Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
David M. Blei, Michael I. Jordan, and A. Ng. Hierarchical bayesian models for applications in information retrieval. 2003.
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In ACM SIGACT Symposium on Theory of Computing (STOC), pp. 74-86, 2018.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:18/2.0/09) 2018.
Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In Neural Information Processing Systems (NeurIPS), 2020.
Huili Chen, Jie Ding, Eric Tramel, Shuang Wu, Anit Kumar Sahu, Salman Avestimehr, and Tao Zhang. Self-aware personalized federated learning. CoRR, 0atp/2204.08009, 2022. doi: 10.48550/ arXiv.2204.0800 URL /tttas:t::///ett http///toooooo/o.o.//o//e/o. 48550/45555300 arxiv 2204. 08069
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared represen- tations for personalized federated learning. In Marina Meila and Tong Zhang (eds.), International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pp. 2089-2099. PMLR, 2021.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 13461, 2020.
Canh T. Dinh, Nguyen H. Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Advances in Neural Information Processing Systems, 2020.
Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee. and Qi Lei. Few-shot learning via learning the representation, provably. International Conference on Learning Representations, 2021. URL
Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 9(344:2111440 2014.
10

---

Published as a conference paper at ICLR 2023
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), pp. 265-284,25 2006.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. In Advances in Neural Information Processing Systems, 2020.
Andrew Gelman, John B. Carlin, Hal S. Stern, David B. Dunson, Aki Vehtari, and Donald B. Rubin. Bayesian Data Analysis. Chapman and Hall/CRC, 2013.
Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv: /71.:0171. 2017.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approxima- tion ratios. Advances in Neural Information Processing Systems, 33:4040-4054, 2020.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In Neural Information Processing Systems (NeurIPS), pp. 20172-20184, 2021.
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In Advances in Neural Information Processing Systems, 2020.
Richard Gill and Boris Levit. Applications of the van trees inequality: A bayesian cramér-rao bound. Bernoulli, 1:59-79, 03 1995. doi: 10.2307/33 1
Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of federated learning: Privacy, accuracy and communication trade-off's. IEEE Journal on Selected Areas in Information Theory, 2(1):464-478 2021a.
Antonious M. Girgis, Deepesh Data, Suhas N. Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled model of differential privacy in federated learning. In International Conference Artificial Intelligence and Statistics (AISTATS), volume 130 Proceedings of Machine Learning Research, pp. 2521-2529. PMLR, 2021b.
Antonious M. Girgis, Deepesh Data, and Suhas Diggavi. Distributed user-level private mean estimation. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2201, 2022. doi: 10. 110//S/T150566.2222299922
Filip Hanzely and Peter Richtárik. Federated learning of mixture of global and local models. arXiv preprint arXiv:2002.05516. 2020.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Advances in Neural Information Processing Systems, 2020.
Rui Hu, Yuanxiong Guo, Hongning Li. Qingqi Pei, and Yanmin Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10):530- 9539, 2020.
Prateek Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. Differentially private model personalization. Advances in Neural Information Processing Systems, 34, 2021a.
Prateek Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. Differentially private model personalization. In Advances in Neural Information Processing Systems, volume 34, 2021b.
William James and Charles Stein. Estimation with quadratic loss. In Proceedings Berkeley Symposium Mathematics and Statisties, Vol 1, pp. 361-379. University of California Press, 1961.
Yihan Jiang, Jakub Konečný. Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv preprint 1.XXv:1999.124800 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-210, 2021.
11

---

Published as a conference paper at ICLR 2023
Shiva Prasad Kasiviswanathan, Homin K Lee. Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-88) 2011.
Mikhail Khodak, Maria- Maria-Florina F Balcan, and Ameet S Talwalkar. Adaptive gradient- based meta- learning methods. In Advances in Neural Information Processing Systems, 2019.
Nikita Kotelevskii, Maxime Vono, Eric Moulines, and Alain Durmus. Fedpop: A bayesian approach for personalised federated learning. CoRR, abs/2206.03611, 2022, June.
Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehryar Mohri, and
Ananda Theertha Suresh. Learning with user-level privacy. In Neural Information Processing Systems (NeurIPS), pp. 1166-1224,,,222
Daliang Li and Junpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint arXiv:1910.0358) 2019.
Jeffrey Li, Mikhail Khodak, Sebastian Caldas, and Ameet Talwalkar. Differentially private meta-
learning. In International Conference on Learning Representations, 2020. URL https://
openreview net w
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6368. PMLR, 2021.
Tao Lin, Lingjing Kong, Sebastian U. Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. In Advances in Neural Information Processing Systems, 2020.
Yuhan Liu, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: user vs item-level privacy. In Neural Information Processing Systems (NeurIPS), 2020.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Frederic M. Lord. Estimating true-score distributions in psychological testing (an empirical bayes estimation problem)*. ETS Research Bulletin Series, (96 doi: https://doi.rr//10 1002// 1967 tb00535.xx URL https::pp.... http:s:://nliiii httl:///baaiaarrrr.......aaa wwtpobrrrrwwlllll............ www.ey.co//da.e... cwm/ 2333- 35033333-00.... 1967 tb00535.x
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications to federated learning. arXiv preprint arXiv:2002.10619, 2020.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Lactitia Kameni, and Richard Vidal. Federated multi-task learning under a mixture of distributions. Advances in Neural Information Processing Systems, 34, 2021.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efficcentt learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Ilya Mironov. Rényi differential privacy. In IEEE Computer Security Foundations Symposium (CSF), pp. 263-275, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. CORR, abs/1908. 10530, 2019. /Rt.:tttt.//arx/..orrr/////
908. 0530
Kaan Ozkara, Navjot Singh, Deepesh Data, and Suhas Diggavi. Quped: Quantized personalization via distillation with applications to federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Kaan Ozkara, Antonious M Girgis, Deepesh Data, and Suhas Diggavi. A generative framework for personalized learning and estimation: Theory, algorithms, and privacy. arXiv preprint arXiv:2207.01771, 2022, July.
12

---

Published as a conference paper at ICLR 2023
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse?
towards understanding the effectiveness of MAML. In 8th International Conference on Learning Representations. ICLR 2020, Addis Ababa. Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URI.https. /ttttps://ppanrevee
net f http:/oommmmmdorooooo d=kgMKCEEPP
Herbert Robbins. An empirical bayes approach to statistics. In The Proceedings of Third Berkeley Symposium on Mathematical Statisties and Probability, pp. 157-163, 1956.
Tao Shen, Jie Zhang, Xinkang Jia, Fengda Zhang, Gang Huang, Pan Zhou, Kun Kuang, Fei Wu, and Chao Wu, Federated mutual learning. arXiv preprint 2rXiv:2006.1677 2020.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S. Talwalkar. Federated multi-task learning. Advances in Neural Information Processing Systems, pp. 4424 4434, 2017.
Charles Stein. Inadmissibility of the usual estimator for the mean of a multivariate normal distribution. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, 1954- 1955, vol. I, pp. 197-206. University of California Press, Berkelcy-Los Angeles, Calif., 1956.
Uri Stemmer. Locally private k-means clustering. In SODA, pp. 548-559, 2020.
Kevin Tian, Weihao Kong, and Gregory Valiant. Learning populations of parameters. Advances in neural information processing systems, 30, 2017.
Yonglong Tian, Yue Wang, Dilip Krishnan, Joshua B Tenenbaum, and Phillip Isola. Rethinking few-shot image classification: a good embedding all you need? In European Conference on Computer Vision, pp. 266-282. Springer, 2020.
Paul Vanhaesebrouck, Aurélien Bellet, and Marc Tommasi. Decentralized collaborative learning of personalized models over networks. In Artificial Intelligence and Statistics, pp. 509-517. PMLR, 2017.
Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, and Sham Kakade. Maximum likelihood estimation for learning populations parameters. In International Conference on Machine Learning, pp. 6448 6457-655. PMLR, 2019.
Martin J Wainwright, High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Valentina Zantedeschi, Aurélien Bellet, and Mare Tommasi. Fully decentralized joint learning of personalized models and collaboration graphs. International Conference on Artificial Intelligence and Statistics, pp. 864-874. PMLR, 2020.
Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M. Alvarez. Personalized federated learning with first order model optimization. In International Conference on Learning Representations, 2021.
Yuchen Zhang. Distributed machine learning with communication constraints. PhD thesis, EECS Department, University of California, Berkeley, May 2016. URL http:// eecs berkel 1 ley. btter//eww..ee//uusss/eeee////// 2wt/22/110/E/EE22/222202 201ECC5-211--7..11
13

---

Published as a conference paper at ICLR 2023
A
PRELIMINARIES
We give standard privacy definitions that we use in Section A. some existing results on RDP to DP conversion and RDP composition in Section A.2 and user-level differential privacy in Section A.3
A.1 PRIVACY DEFINITIONS
In this subsection, we define different privacy notions that we will use in this paper: local differential privacy (LDP), central different privacy (DP), and Renyi differential privacy (RDP), and their user- level counterparts.
Definition 1 (Local Differential Privacy LDP (Kasiviswanathan et al. 2011)). For 2 0, randomized mechanism R. : X -> y is said to en-local differentially private (in short, eo-LDP), if for every pair of inputs d, d' E X, we have
Pr(R(d) E S) S e Pr(R(d') E S), VS VS
(12)
Let D = fx1...., Fnl denote dataset comprising points from X. We say that two datasets nnn } are neighboring (and denoted by D D') if they differ D {.i..... )n and D' {a',...,. ..'..,
in one data point, i.e., there exists an i E [rx] such that + x/ and for every E [m],. + i, we have Ty = =x'z.
Definition 2 (Central Differential Privacy DP (Dwork et al. 2006 Dwork & Roth 2014)), For 8, 2 0, a randomized mechanism M X + said to be (c,ō) diffeferrett private (in short, (c. 6)-P), for all neighboring datasets D ~ D' E X and every subset S S Y, we have
Pr (M E S S c Pr [M((')) E S] 8..
(13)
If 8 = 0, then the privacy is referred to pure DP.
Definition 3 ((), c(A)) (Renyi Differential Privacy) (Mironov 2017)). A randomized mech- anism M : X + y is said to have ReA)iRenyi differential privacy of order X E (1, x (in short, (X))(D)) if for any neighboring dalasets DD ~ D' X", the Renyi divergence between M(D) and M(D) is upper-bounded by e(A), i.e.,
[
D*(M(D)IM(D') x-1 log EEWM(DD
S <((A),
where M(D)(() denotes the probability that M on input D generates the output 6. For convenience, instead of E()) being an upper bound, we define it as e(A) supp>D' D>(M(D))MM(D''.
A.2 RDP DP CONVERSION AND RDP COMPOSITION
As mentioned after Theorem 5 we can convert the RDP guarantees of DP-AdaPeD to its DP guarantees using existing conversion results from literature. To the best of our knowledge, the following gives the best conversion.
Lemma 1 (From RDP to DP (Canonne al. 2020 Balle al. 20200). Suppose for any X 1, mechanism M is (A, (A))-RDP. Then, the mechanism. M is (e, -D-P, where e, 8 are define below:
For given d 10
mine (A) log (1/0) (A 1) log (1 1/A) log (A)
For given 6 0:
min exp (() 1) (e (c - c))
11
X
The main strength of RDP in comparison to other privacy notions comes from composition. The following result states that we adaptively compose two RDP mechanisms with the same order, their privacy parameters add up in the resulting mechanism.
Proposition 1)). For any X X> 1. let Mi X + Y, be (A, e, (x))- RDP mechanism and M₂ Y, x + y be a (A, (2())))) RDD mechanism. Then, the mechanism defined by (M)) satisfies (), (A) (DD)
Lemma 2 (Adaptive composition of RDP (Mironov 2017
14

---

Published as a conference paper at ICLR 2023
A.3 LEVEL DIFFERENTIAL PRIVACY LEVY ET AL.
2021
Consider a set of m users, each having a local dataset of n samples. Let D; = frah.... Iin denote the local dataset the i-th for i E [m/], where Zij E X and X Rd. We define D = (Di,..., Dm) E (Am") as the entire dataset.
We have already defined DP, LDP, and RDP in Section A.1 w.r.t. the item-level privacy. Here, we extend those definition w.r.t the user-level privacy. In order to do that, we need a generic neighborhood relation between datasets: We say that two datasets D, D' are neighboring with respect to distance metric dis if we have dis(D, D') 1.
Item-level DP/RDP vs. User-level DP/RDP. By choosing dis(D, D")
1 #
we recover the standard definition of the DP/RDP from Definitions DP/RDP. In the item-level DP/RDP, two datasets D, D' are neighboring if they differ in single item. On the other hand, by choosing dis D') E [(D; + D we call it user-level DP/RDP, where two datasets D. D' E (A*)) are neighboring when they differ in a local dataset of any single user. Observe that when each user has a single item (n 1), then both item-level and user-level privacy are equivalent.
3 which we call item-level
User-level Local Differential Privacy (LDP). When we have a single user (i.e., m = and D X²),, by choosing dis (D, D') = 1 { & )') for D, D' E X", we call it user-level LDP. In this case each user privatize her own local dataset using a private mechanism.
We can define user-level LDP/DP/RDP analogously to their item-level counterparts using the neigh- borhood relation dis defined above.
B PERSONALIZED ESTIMATION GAUSSIAN MODEL
B. PROOF OF THEBRRM II
We will derive the optimal estimator and prove the MSE for one dimensional case, i.e., for d = 1; the final result can be obtained by applying these to each of the coordinates separately.
The posterior estimators of the local means 01,...,0w, and the global mean μr are obtained by solving the following optimization problem:
0 i....., 0m j
arg max pxj0 (X1, Xm1 ..... 9m) Palu (01, ................................ 0mlpp)
01.... Om....0mm..!!
= arg min - log (pxie (X1,...,
Xm Sm.... )m,) - log (0 (01,...,0mlle 0mll)))
0 Om.pp
X 0.)
(0: 11)
arg min C+
Ps....0mm..p
where the second equality is obtained from the fact that the log function is a monotonic function, and C' is constant independent of the variables 0 (fI...., ...) Observe that the objective function
of F(0, 11) = Em Σド= (x(-)))² + Em (Q==n)² is jointly convex in (0, p). Thus, the optimal is
Di=l ob
obtained by setting the derivative to zero as it an unbounded optimization problem.
0F
ΣØ=
2(0,
X!)
2(0: ()) o
0,
Vi E [m]
00:
02
4=
0F
2( - 8.) 0.
1=1
0p
o
0=
By solving these m equations in m + unknowns, we get:
1 Σ
0, =a
x
+ +(1 - a)
x!
(14)
1=1
15

---

Published as a conference paper at ICLR 2023
where a By letting X; n, EE= X for all i [m]). we can write 0, = ax; + (1
o o + X
Observe that E [0,00] = al; + 1 m
0g where 0 = (01,,..,,0 0m) Thus, the estimator 14 is
an unbiased estimate of {0.}. Substituting the 0. in the MSE, we get that
Ex Ex........ Xm [0. - 0.) )
Egg
E Ex..... Xm
00 0:
2 10
EE
E Ex Xm
(0: IE 00110
EE
0:10
0:) 10)
(0: IE [0:10]
[ 0.:00 - 0 10
Es
E Ex Xm
10
Es
Exi Xm
(15)
Claim 1.
(o_ - E [0,10]
2 10
a² -
o2
of
Eg Exi...m Xm
(1 a)²
+ 2a (1
a)
n
71
mn
BB [0:10] 0.) 2 10
( ( Σ On 0z
27
p 1)
Eg
Ex Xm
(1 a)
(1 a)
m
Proof. For the first equation:
2
[o: - E [0,10] 2 10 Egg
[a(x:- -0,) + (1 a) m
m
Eg Ex,...
Ex
Xx 0k)
2
m
= a E [X, - 0.) 10] + (1 2)
> (X - 0k)
10
m
k=1
m
+ +2a a)
E
[x (x) 0k)
m
2 oi n
a)² 0²
+ (1
+ 2a
a)
mn
mn
For the second equation, first note that IE 0:10
0,
a0:
1-a
> Lkm 02
0,
(1
a) m kー 02 0.):
27
Eg Ex
Xm
0.100 [1E[0.10]
E
0.) 10
(1
a)²B
(
m
0₂
0
m71
k=1
2
(1 - a)²
E
Σ (0x 0:)
m²
(1 - a
Σ E[0 - -0,3 + Σ
E(O, - 0,)(0, 04)
m²
(1 -) m²
E((; 11)2 + E(O: - 11)21
Σ
E(O= - (6: 0:)
(1 a)²
2(m - 1)02 +
Σ
E(Os - 0,)(0, 04)
m²
16

---

A Published as a conference paper at ICLR 2023
(1 a)²
2(m - 1)08 +
Σ
Blu - 0:)2
(Since [[O,] = μ for & E [m])
m²
(1-a) a)²
[2(m 1)02 + (m 1)(m - 2)0
m
= (1 a)² (m
This concludes the proof of Claim
1
Substituting the result of Claim into
15 we get
(o. (0.-0.) 0:)
0z
+ (1 a)² o²
02
+ (1 a) 2 - 1)
Ex Ex....... Xm
<
+ 2a (1 a)
(16)
0
(1 a)² + 2a a)
m -
a
+ a( 0x)
0²
1 - a
a+
m
05 for the last term to write (1 - a)20
a2 a(1 a m-1
where in (a) we used a
+ -
Observe that the estimator in 14 is weighted summation between two estimators: the local m
estimator X, Σド= X², and the global estimator ý 1 Ei X, Thus, the MSE in (a)
consists of four terms: 1) The variance of the local estimator ( 2) The variance of the global estimator mm
3) The correlation between the local estimator and the global estimator ). 4) The
bias term Eg
E E
E 0:10 8.) 10
This completes the proof of Theorem
B.2 PROOF OF THEOREM EQUATION
Similar to the proof of Theorem 1
here also will derive the optimal estimator and prove the MSE
for the one dimensional case, and the final result can be obtained by applying these to each of the d coordinates separately.
Let 0 = (fI...., 6m) denote the personalized models vector. For given constraint function we the personalized model as follows:
n2
( m [
0
x
+
+1 a)
Vi E [m],
(17)
n
m
where X, EE= X From the second condition the function g, get that
1 0 m
0,10 = aB; +
(18)
m
Thus, by following similar steps as the proof of Theorem
we get that:
E (0.
0.)
27
=
E
E
0,
8.
18
E
E
0, E
00100
+ E
0.10
0,
1
E
E
00 E
[0:10] ) 10
+ E
E
E
[0.10]
0.)
e
2 02
+ (1 2E
Σ
9 x(x,) - 01
10
17

---

Published as a conference paper at ICLR 2023
+ 2a(1 - aB (x:-0) - -0.) - m
[ (Xi) -01 10 10]
(
[
1 m
27
+ (1 - a)
02 0:
(1 a)² (0 + t
(6)
2
2a(1 - a)o²
+ (1 a)
1
Σ
On 0z
mn
2 0
(1 - a)²
02 + 02
02
2 o 1)
2a(11
+ (1 a)²
n
m
mn
m
(c)
(1 a)²
2a a)
a
a(1 a)
m
m
n a
(19)
where step (a) follows by substituting the expectation of the personalized model from 18) Step (b) follows from the first and third conditions of the function q. Step (c) follows by choosing
This derives the result stated in (5) in Theorem 2
B.2.1 PROOF OF THEOREM 2 PART
The proof consists of two steps. First, we use the concentration property of the Gaussian distribution to show that the local sample means (X, } are bounded within a small range with high probability. Second, we apply an unbiased stochastic quantizer on the projected sample mean.
The local samples _!......?? X7" are drawn i.i.d. from Gaussian distribution with mean 6, and variance o and hence, we have that X; .N0O,, ). Thus, from the concentration property of the Gaussian distribution, we get that Pr| 0.1 > al S exp (- -o? for all e [m]. Similarly, the models 0I,...,,n, Om are drawn i.i.d. from Gaussian distribution with mean μ E for all i E [m]] Let + c1 + c2. Thus, from the union bound, we get that
[-r,r] and variance og. hence,, we get Pr[16, /4| > 02) S exp
E = [xxx E [-a,a] Vi E [m]]. where
ne?
02 log(m2n) and c2 v Vo log(mEn), we get Pr[E] > 1 m(e of +e ") By setting Ci V
that a = r + au
/lg(mm2n) + oe (mn(m?)), and Pr[E] = 1 2 रα
Let qk: a + V/s be a quantization funetion with b-bits, where Y/8 is a discrete set of cardinality [Y = 2*. For given E [-a, a), the output of the function qu is given by:
2a
U (x) = 2 - [1$ + Bern (+ (+)) a,
(20)
where Bern(p) is a Bernoulli random variable with bias p. and ă = 2 (x aa)+a E [0, 2 1]. Observe that the output of the function qi requires only k-bits for transmission. Furthermore, the function qe satisfies the following conditions:
E [x)] F,
(21)
a²
E (()(()) - x)]]
(22)
(2* 1)2
Let each client applies the function za on the projected local mean X; Proj
[ and sends
the output to the server for all i E [m]] Conditioned on the event E, i.e., X, E I-a,a and using (19, get that
Vi E [m],
MSF = Rex [(0:- -o.)"
S 02 (1-a a
(23)
m
18

---

Published as a conference paper at ICLR 2023
where 0 (2 1)
and a =
r 3x Vloommnn) to /log(//n)
Note that the event
+ 114-17 1)
& happens with probability at least 2
B.2.2 PROOF OF THEOREM 2 PART 2
We define the (random) mechanism Op 1-a, a| + R that takes an input x E [-a, a] and generates
user-level (to, 6)-LDP output y E I, where y = 4p (a) is given by:
4p = x +
(24)
where v ~ (0, o2,)) is a Gaussian noise. By setting o = 8a (2/()
we get that the output of the function gp (x) is (co: 8)-LDP from Dwork & Roth 2214)). Furthermore, the function 9p satisfies the following conditions:
s
E [pp())]] = I,
(25)
Sa² (og(2/6)
og = E [()p(a) xz)
(26)
Similar to the proof of Theorem 2 Part 1, let each client applies the function qo on the projected local mean X; -r.jl [ and sends the output to the server for all i [m]] Conditioned on the
event E, i.c., X, E a, a] Vi E [m]] and using (19). we get that
MSE Ex,x (0. (0.-0.)
0, 0
1 a
(27)
03 de les(2/5)
where a
and a = r vn v log(m=n) + ag log(m2n).. Note that the event
+ Sa log
(m)
happens with probability at least 1
Remark (Privacy with communication efficiency). Note that our private estimation algorithm for the Gaussian case adds Gaussian noise (which real number) but that can also be made caamumication-effcciee by alternatively adding a discrete Gaussian noise (Canonne et al. 2020).
B.3 LOWER BOUND
Here we discuss the lower bound using Fisher information technique similar to Barnes et al. (2020) In particular we use a Bayesian version of Cramer-Rao lower bound and van Trees inequality Gill
& Levit (1955.. Let us denote ((X(0) as the data generating conditional density function and π (0) as the prior distribution that generates 9. Let denote Eg the expectation with respect to the randomness of f and E as the expectation with respect to randomness of X and A. First we define
two types of Fisher information:
(x V. N
1(x) EV, log(
namely Fisher information of estimating 0 from samples X and Fisher information of prior Here logarithm elementwise. For van Trees inequality we need the following regularity conditions:
f f and (-)) are absolutely continuous and π (--) vanishes at the end points of e.
Eg Ve (f (X 0)) 0
We also assume both density functions are continuously differentiable.
These assumptions satisfied for the Gaussian setting for any finite mean μ, they satisfied for Bernoulli setting as long as parameters a and /3 are larger than 1. Assuming local samples X are generated i.i.d with f (x) the Trees inequality for one dimension is follows:
19

---

Published as a conference paper at ICLR 2023
B(0(X)- - -0 nEI, (0) + (TT)
where (0) lgg log(J and [(x) = E logí (0) Assuming 0 E IRd and each dimension independent from each other, by Gill & Levit (1995) we have:
d
B((((X) - 0112 > nETT(II())) + (T))
(28)
Note, the lower bound on the average risk directly translates a lower bound on supace Ex [x
0|. Before our proof we have useful fact:
Fact 1. Given some random variable X of) where Y N(),oo) we have X ~ N22
og))
Proof. We will give the proof in one dimension, however, it can easily be extended to multidimen- sional case where each dimension is independent. For all f E R we have,
0.122 )] Ex(exp(itX)] = By Ex(exp = By (expptitty
0212
exp(
]Ey (exp(((t))
2
222
0/
exp(
exp(itzz
2
(o" + o
cxp(itz
where the last line is the characteristic function of Gaussian with mean 2 and variance 0 + oz
Gaussian case with perfect knowledge of prior. In this setting we know that 0; ~ Nu11, oa
hence, I(T)) La similarly Ix (0) = _ la. Then,
d²
dogo²
sup EX(Ø((X) - 0,11 8:
(29)
+ d nlE 03
no? + o²
Gaussian case with estimated population mean. In this setting instead of a true prior we have a prior whose mean is the average of all data spread across clients, i.e., assume 0; ~ N oāLa) where 7 mon Eni mm X². We additionally know that there a Markov relation such that X/10, ~ N (0,, La) and 0j ~ [(, La).). While the true prior is parameterized with mean μe, 0; in this form is not parameterized by μ but by which itself has randomness due X However, using Fact | twice we can write 0; Nu, (a] + a of
La). Then using the van Trees inequality similar to the lower bound in perfect case we can obtain:
000
sup Ex (x - 0,112 6.E0
mn no + +03
(30)
20

---

Published as a conference paper at ICLR 2023
C PERSONALIZED ESTIMATION BERNOULLI MODEL
C.I WHEN O, 3 ARE KNOWN
Analogous to the Gaussian case, we can show that if a, are known, then the posterior mean estimator has a closed form expression: p: aX; + (1 a) o-B (where +/a++++n) and achieves the MSE: of
Epina Ep.... X.. (P. p:)²² S n(a+B]aa-B1) B411 a+3+h We show this below.
For a client i, let (p:) be distributed Beta(a, 3). In this setting, we model that each client generates local samples according to Bern(p;). Consequently, each client has a Binomial distribution regarding the sum of local data samples. Estimating Bernoulli parameter p; is related to Binomial distribution Bin(n, Pi) (the sum of data samples) Z; since is the sufficient statistic of Bernoulli distribution.
The distribution for Binomial variable Z, given p; is P(Z; = pp)); - (=" (1 - pp,) It is
known fact that for any prior, the Bayesian MSE risk minimizer the posterior mean E [ps Z2 = 2;]
When P. Beta(a, B), we have posterior
f(p:|Z 21) P(sslpt) P(z)) (pp))
()) -P:)" pi- (1 pr)
10-1(1
P(zi)
B(a,3) 3)
(7)
B(a + Zú, 3+,B+ +n 21) Pj
1 100-1111111 p:) 8t)3---2
P(z.)
B(a,8) 3)
B(a + 22, +n 2i)
where B(a, B)
(() and 3(++3)
P(z)) = / Pl P(zslpt)((s)dg
/
n1
20-10 (1 pc)
p² -p:)
dpi
B(a, 3)
BEi +a, -
Di 1 px) 8tn-21-1 dp
2i
B(a,
B(a + 2i, 3 + 21)
integral of Beta distribution
n B(z, +a, n
2
B(a, B)
(1-p)) (1-p)) Stm-
Thus, we get that the posterior distribution flp = 2,) 21 distribution Beta(2; + a, n 2, + 3). As result, the posterior mean is given by:
is a beta
+ 2i
( + (1 a)
(4)
p
(31)
a B+
where a -++8 Observe that Ep,~Beta(o, .)) [p:] a+.3 i.e., the estimator is weighted summa- tion between the local estimator žs and the global estimator μ a+3
a
We have Rg (Px) = B(p p.) The MSE of the posterior mean is given by:
MSE = E(ia - -
(a
24
+ (1 a)(u - p.)) (p:)) p:
= E
Pi
n2
a
2
2
27
+ (1 - 2B (11 - -p=)p p=)2
pi
pr(1 - px)
a8
= a²
+ (1 a)²
n
(a (+
21

---

Published as a conference paper at ICLR 2023
ag
aB (a+ + () +1++
a² n(a + 3) + 1+
+(1-a)²
aB
n(( + () + B + 1)
a+ 1++B+1
The last equality is obtained by setting = a++++
Remark 5. Note that X; = n is the estimator based only on the local data and (/(0))) is the true global mean, and p; = aX,+ a)
o where a = -/a+++n (see (3I) is the estimator based on all the data. Observe that when n + co, then a + 1, which implies that p. + X Otherwise, when a + 3 is large (i.e., the variance of the beta distribution is small), then a + 0, which implies that ps + 2/(a+B). Both these conclusions conform to the conventional wisdom as mentioned the Gaussian case. It can be shown that the local estimate X, achieves the Bayesian risk of B) I,,,XxIX,,,1, - = Bu.--Bettt..0) (p= (p((1-p))/ = as ad//nia-B (1 which implies that the personalized estimation with perfect prior always oulperforms the local estimate with multiplicative gain 7/( S 1.
C.2 WHEN a, 3 ARE UNKNOWN: PROOF OF THEOREM 3
The personalized model of the ith client with unknown parameters a, 3 is given by:
= a; + (1 a.) (Pt):
(32)
where 0j
the empirical mean jú;
m- Eips X1, and the empirical variance
1
11 Hal +n 0, a?- - m- E1et (X j. From
Tian al. 2017 Lemma 1), with probability m we get
that
3 log(4m?n)
1 Pul S
m
3 log( (m?n)
0 0,l S
m
where / a+B o²
0g (a+ (a+ the true mean and variance of the beta distribution, 3og 4m)
respectively. Let /
Conditioned on the event E[pp Aul S c, c,,l02 -,,1 S c:
m-
vi [m]} that happens with probability at least mn get that:
1
2
E (f:: pa))
FF
+ (1 -a (iis: pr)² [2-1]
Pj
a
0/3
+ a)² (B (n - px)²]
+ (m (n- (2))t)
n(a + B) + 1)
n²
a
+ (1)
(a+33) + + +11 + (n (n- -pa)?
ag
n(a + () + 3 11)
< n(a + (a +
a
+ 7)
(a + () + 1+1) e
a3
where the expectation is with respect to 2 Binom(pi,.) n) and p. Beta 3) and Z_, (Zi...., ........, 2m denotes the entire dataset except the ith client data (2,). By taking the expectation with respect to the datasets 7-i, get that the MSE is bounded by:
a8
)
o
3 loo 4m2 m 1
MSE < E [a2]
+E (1 (1=
n1a B) + B + 1)
3) + B+11
with probability at least
1 This completes the proof of Theorem
3
mn
22

---

Published as a conference paper at ICLR 2023
C.3 WITH PRIVACY CONSTRAINTS: PROOF OF THEOREM 4
First, we prove some properties of the private mechanism Op- T, x. [0, 1J. we have that:
Observe that for any two inputs
(r( = yl
50
e00
+50+1
S
c
(33)
Pr Pr(gp(x') y)
650+1
e50+1
for y -- Similarly, we can prove (33 for the output
r0 I
Thus, the mechanism 4p is
user-level eo LD-. Furthermore, for given [0, 1]. we have that
(x)) = x.
(34)
Thus, the output of the mechanism 9p is unbiased estimate of the input æ. From the Hoeffding's inequality for bounded random variables, we get that:
3(e 1)2 1)t²
Pr(la? 11| > t] S 2xx
(e50 + 112
(35)
3 1)2 - 1))t
Pr[lo? 2(m) - o2 > 1 < exxp
(00 + 1)2
Thus, we have that the event & (|ā!! pal S Cpp 10
0²| S cp : Vi [ml] happens with By following the same steps as the non-private estimator, get the fact that the MSE of the private model is bounded by:
probability at least mn. where Cp =
(e"o lom 3 (m-1)
MSE < E [a2] (n(a+ B)(a + 1+1)
aB
ag (a + 1)
(e + 1)² log 4m3")) (36)
+ (11 - =
3(eto 1) 1)
where a(p)
and the expectation is with respect the clients data
( (2)
t
and the randomness of the private mechanism 4p- This completes the proof of Theorem
(Z1,.... 2 7441>
Remark 6 (Privacy with communication efficiency). Note that private estimation algorithum for the Bernoulli case is already communication efffccien as each client sends only one bit to the server.
Remark (Client sampling). For simplicity, in the theoretical analysis Gaussian and Bernoulli models, we assume that all clients participate in the estimation process. However, simple modifi- cation to our analysis also handles the case where only K out of m clients participate: all our theorem statements we would have to modify to have K instead m. Note that we do client sampling for our experiments Table
D PERSONALIZED ESTIMATION - MIXTURE MODEL
Consider a set of m clients, where the i-th client has local dataset X; = (Xa..... Xin) of samples for E [m], where X,z E Rd The local samples X, of the i-th client are drawn i.i.d. from Gaussian distribution AOO,, o a)) with unknown mean 0, and known variance T
In this section, assume that the personalized models 0,,..., Om drawn i.i.d. from discrete distribution IP = [pi..... . Pk] for given & candidates pı...., 24 E R2d In other works, Pr(O; = μı] Pl for E [k] and E [m]. The goal of each client estimate her personalized model {0.} that minimizes the mean square error defined as follows:
MSE E.e....) > 10, 0.1
(37)
where the expectation taken with respect to the personalized models 0, and the local samples (Xiz ~ Ni(0, o.].). Furthermore, 0, denotes the estimate of the personalized model 0, for i [m].
23

---

Published as a conference paper at ICLR 2023
First, we start with simple case when the clients have perfect knowledge of the prior distribution, ie., the i-th client knows the Gaussian distributions N (H1 og) .N (H4 og) and the prior distribution a = [01,...., Qx). This will serve as stepping stone to handle the more general case when the prior distribution is unknown.
D.1 WHEN THE PRIOR DISTRIBUTION IS KNOWN
In this case, the i-th client does not need the data of the other clients as she has a perfect knowledge about the prior distribution.
Theorem 6. For given perfect knowledge a sa ook and N (M1 oz) ,..., N (m4, oā)
the optimal personalized estimator that minimizes the MSE is given by:
0,
Pb
(38)
2g 1X4, 11
where 0i
(8)
pt exp
2n
denotes the weight associated the prior model p
E/
1xg Hull
D Po exp
20
for E [kc].
Proof. Let 0, ~ P, where P = [pi,.... Pk. and pl = Pr(O, = 141 for E [b]]. The goal to design
an estimator 0; that minimizes the MSE given by:
MSE Ee Pe Ex.
|10: 0 01113]
(39)
Let X; (X.1 X By following the standard proof of the minimum MSE, we get that:
Eg, Ex, |10: 0:12
= Ex,
[|0: E
X.
+ E X. 0.112 x
= 1xx,E0,115
||[[,||X]]
1 X + Exx Eo, 1x. [[ - 0u]1? X.
2 Ex, Fo, Ix
|| [X
0:11 x.]
(40)
where the last inequality is achieved with equality when 0: = E X.). The distribution on 0, given the local dataset X, is given by:
Pr(O. = MXxx = 5(x,10; 14) Pr(O. Ms]
f(Xi)
J(X, 14) Pr(O: - 1q]
Σ f(X; m.) Pr(0: = [4.]
(41)
- 1| -1ll
pl exp
20
aj (4)
E [Xy -,, ?
-==1 exp
207
As result, the optimal estimator is given by:
0 E(O,|X
Σ aj
( Pi.
(42)
1=1
This completes the proof of Theorem 6
The optimal personalized estimation in 38 is weighted summation over all possible candidates vectors ...... M4+ where the weight aj increases the prior pl increases and/or the local samples {Xij} } are close to the model μ4, for I E [R.]. Observe that the optimal estimator θ in Theorem 6 that minimizes the MSE is completely different from the local estimator (+ Σ"= X.3) Furthermore,
it is easy to see that the local estimator has the MSE dimension d. On the other hand, the MSE of the optimal estimator in Theorem a function of the prior distribution IP [Pı,...PPa]] the prior vectors p . Mgg and the local variance o².
da
which increases linearly with the data
24

---

Published as a conference paper at ICLR 2023
D.2 WHEN THE PRIOR DISTRIBUTION IS UNKNOWN
Now, consider candidates 11.---- 24g are unknown to the clients. In this case, the clients collaborate with each other by their local data estimate the priors P' and 4 I..... Mg. and then, each client uses the estimated priors to design her personalized model as in (88
practical case when the prior distribution P = [pi.-.... ..... Pk] and the
We present Algorithm based on alternating minimization. The algorithm starts by initializing the local models (0 == n -ド= X Then, the algorithm works in rounds alternating between esti-
mating the priors (p((-1) = [p] ((+1) Pk
.....Pk (1+1)]
j4i (t+1) ..... (t-1) for given local models {0) (2) and
estimating the personalized models (0(+ for given global priors p(++1) and μ4 (*+1) P (++1)
Observe that for given the prior information p(t), {ut), each client updates her personalized model in Step which is the optimal estimator for given priors according to Theorem 6 On the other hand, for given personalized models {0(*), ). we estimate the priors p(t), {pf} using clustering algorithm with sets in Step [1 The algorithm Cluster takes vectors a1, ai..... am and an integer k its input, and its goal to generate a set of &t cluster centers M1..... Mu that minimizes > mitlre |la, - -,,
also return the prior distribution P., by setting pr [ where S C {a...... am } denotes the set vectors that are belongs to the I-th cluster. There are lots of algorithms that do clustering. but perhaps, Lloyd's algorithm gloyd (1982) and Ahmadian Ah- madian et al. (2019) are the most common algorithms for k-means clustering, Our Algorithm 3 can work with any clustering algorithm.
Furthermore, these clustering algorithms
Algorithm 3 Alternating Minimization for Personalized Estimation
Input: Number of iterations T, local datasets .Xi,,..,,Ka, for E [m].
1: Initialize 0 = E Xı for [m]]
2: for 1 to T do
3: On Clients:
4: for 1 to m: do
5: Receive p(t) M (1
0 from the server 6: Update the personalized model:
(4)
>
14,00
Pi exp
20
0
and
aj
(i)
Σ x s=1 Po exp
Σi=
[| - 10
20
7: Send 0 the server
8: end for
9: At the Server:
10: Receive 0(0) ..... (()) from the clients
11: Update the global parameters: IP((), M1
M + Cluster (0 ..... (
12: Broadcast IP(() (4) "..,....... H to all clients
13: end for
Output: Personalized models 0f ..... OT
D.3 PRIMCYYCOOMMUNCATION CONSTRAINTS
In the personalized estimation Algorithm 3 each client shares her personalized estimator ( to the server each iteration which is not communication-effiiee and violates the privacy. In this section we present ideas on how to design communicationnefiicceenn and/or private Algorithms for personalized estimation.
Lemma 3. Let py.... Mgg E Rd be unknown means such that || S r for each i E [k]. Let P. where Po (p.,... .Pk] and pt Pr(0, m1). For i [m], let Xar. Xin
0 0,...., On
25

---

Published as a conference paper at ICLR 2023
N(O, o2), i...d Then, with probability at least 1 1
mn. the following bound holds for all E [m]]
1 Th )
o. + 2 log( m
o2 +
<41 d
(43)
n
n
Proof. Observe that the vector (X; - 0,) Dim Xij - 0₂ is sub-Gaussian random vector with proxy =2 As a result, we have that:
22 log 1/n)
I 0:112 - 41
d
+ 21
(44)
72
n
with probability at least from Wainwright 11,1l2 S for each i [R:]. we have:
2019
Since Ml. Pe Rd are such that
|Xill S 4 + 2/ log(1 (11)) +r,
(45)
and using the with probability - 77 from the triangular inequality. Thus, by choosing nj m union bound, this completes the proof of Lemma
Lemma shows that the average of the local samples {X,} has a bounded & norm with high probability. Thus, we can design communication--fficcnnn estimation Algorithm as follows: Each n
client clips her personal model g within radius 4v d + 2 log(m²n) of + r. Then, each client applics a vector-quantzatioon scheme (c.g.. Bernstennttn et al. (2018); Alistarh et al. (2017); Girgis et al. (2021a)) to the clipped vector before sending it to the server.
To design a private estimation algorithm with discrete priors, each client clips her personalized { within radius 4 dd + l2ggom?) o2 +r. Then, we can use a differentially private algorithm for clustering (see e.g.. St..mmreeer (2220) for clustering under LDP constraints and Ghazi
estimator
cct al. (2020) for clustering under central DP constraints.). Since, we run T iterations in Algorithm 3 we can obtain the final privacy analysis (e, 8) using the strong composition theorem Dwork & Roth
(0014).
E PERSONALIZED LEARNING - LINEAR REGRESSION
In this section, we present the personalized linear regression problem. Consider A set of clients, where the i-th client has a local dataset consisting of n samples (X,1, Y.)...., (Xim, Yi.), where Xij Ind denotes the feature vector and Yú R denotes the corresponding response. Let Y, (Ya,..., Yn) E R and X, (Xi,,.... in E Raxd denote the response vector and the feature matrix at the i-th client, respectively. Following the standard regression, we assume that the response vector Y, is obtained from linear model as follows:
Y = =x,,; + wi.
(46)
where 0, denotes personalized model of the i-th client and w; N oQ,, noise vector. The clients' parameters oI...., Om are drawn i.i.d. from Gaussian distribution oI..... Om ~ N(p, TfTa) i...d.
Our goal is to solve the optimization problem stated in 9 (for the linear regression setup) and learn the optimal personalized parameters (0.). The following theorem characterizes the exact form of the optimal (0.) and computes their minimum mean squared error w.r.t. the true parameters (0.). Theorem 7. The optimal personalized parameters al client with known μa, oi o is given by:
0,
X 0²
X
Y
4
(47)
0
The mean squared error (MSE) of the above 0 is given by:
E .. 0 0.1 -r
X
+
(48)
o%
26

---

Published as a conference paper at ICLR 2023
Proof. The personalized model with perfect prior is obtained by solving the optimization problem stated in (9). which is given below for convenience. Note that for linear regression with Gaussian and po, (iy) according to o))
prior, we have PTT) = [H, ozلlla)
0, = arg min
log( (Vyl - (
0,
(Yg 0.)
10,
1
arg min
20
20
0,
j=l
Y
x,0,11
110 u
arg min
20
20
By taking the derivative with respect to 0,, we get
0 x (X,0; Yi)
μ
(49)
00
0
Equating the above partial derivative to zero, get that the optimal personalized parameters 0, is given by:
0: I
X7
X Y 2
/ 0
(50)
0
Taking the expectation w.r.t. Wi, get:
X
-1
X X, 0 2
1
Ew, [0 =
(51)
2 /
0
Thus, we can bound the MSE following:
E. |0. - 0:
l|2 Ee,, ,
0, En,, [0.] + Ew, 0. - 0,
E.,,0,
10, Ew. 0:11"
+ Ew, Ew: 0 - 0
+ 2E (0. -0.-10 Ew, -w. 1., 10. [0.] - 0.)
0: Ev,, 00:l 0i1l² 1| Ew,,,
2
EE,, 0,
Bus 00: 0:
In the last
equality.
we
used
Ew....
(0,
En,, [0.) [0.] 0. 0.]-0:)
Eg, EE,, [0,] - Ew. 0.), Ew: [0.] - 0.) = O, where the first equality holds because Ex. [0.] [0,]-0111 is
independent of wn;
Letting M = 03 + x.x, x; and Tr denoting the trace operation, we get
0. 0 -0! =Tr M MMEEw.
02 (xx7/)
(X.Tu) w
X
wi
T
'Ew.
M
o
0 4
(
7
+ Tr
M
-ME,
Ee,
M-1
o
x? X
=Tr M
M M-1
+ Tr
M
-1
M
Tr (M (M-1).
This completes the proof of Theorem
7
Observe that the local model of the i-th client, i.e., estimating 0, only from the local data X.). is given by:
0."h (xfx,) x
(52)
27

---

Published as a conference paper at ICLR 2023
Algorithm 4 Linear Regression GD
Input: Number of iterations T, local datasets (Y, X,) for E [m]] learning rate 7).
Initialize 06. for [m]] ph, o2.0, og
2: for = 1 to I do
3: On Clients:
4: for 1 to m: do
5: Receive and set μ = μ³, 0,4 = 000 - = 22,
6: Update the personalized model: 0 s 0 +1
2===1
2,1-
14
2.1
1-110
7: Update local version of mean: fo f ui
11-11
1f
21-
8,1
8:
Update local variance:
2.
2,1-1
17
2
2
Σj=1
(Yi, X1, 0 15
2( 2(m2,111) }
9:
Update global variance: 00i
2,1
00,
2
11
20
d
14
2(
0 112
10:
end for
At the Server:
12:
Aggregate mean: -²= 1 i= p
Aggregate global variance: 0g
2.t
0g
2.8
m7
14:
Aggregate local variance: x Broadcast μ²,, 00" 2,4 ,22
2.0
1
i==
m
01
2,1
15:
16:
end for
Output: Personalized models S7
T
where we assume the matrix X X; has full rank (otherwise, we take the pseudo inverse). This local estimate achieves the MSE given by:
Tr ((x? 0
E
(53)
we can prove it by following similar steps as the proof of Theorem 7 When of - oo, we can easily see that the local estimate (52) matches the personalized estimate
To make the regression problem more practical, we assume that the mean μe, the local variance of and the global variance oă are unknown. Hence, we estimate the personalized parameters by minimizing the negative log likelihood:
o....., 0m
arg min
log (po. (YiglX,y)) +
log (0,))
(0.),u,07,0 5=
= arg min (2g(2
nm
Y - 02)
md
(og(2mog))
|0:
2
202
2
20
1=1
(54)
Instead of solving the above optimization problem explicitly, we can optimize it through gradient descent (GD) and the resulting algorithm is presented in Algorithm 4 In addition to keeping the personalized models (0(), each client also maintains local copies of {nt, a., o and updates all
these parameters by taking appropriate gradients of the objective in (54) and synchronize them with the server to update the global copy of these parameters (Ht og. o
F PERSONALIZED LEARNING - LOGISTIC REGRESSION
As described Section 3 by taking P(T) = N (1u, allla) and pe, (Yi, X1,) = o((0,, (o))
o((0, (10,,,,)))) (1 where o(2) = 1/1-e- for any 2 E R, then the overall optimization problem becomes:
28

---

Published as a conference paper at ICLR 2023
m ΣΣ
arg min (0,). j=1
Yiy log
+ + +1--Vig log
e teeeo -0-()
1 + elo..Xis)
md
F 0:112
log() +
(55)
2
20
When 4 and og are unknown, we would like to learn them by gradient descent, as the linear regression case. The corresponding algorithm is described in Algorithm
Algorithm 5 Logistic Regression SGD
Input: Number of iterations T, local datasets (Y,, for E [m], learning rate 1).
1: Initialize 0. for [m], n², og
2.0
2: for /- = 1 to 7 do
3: On Clients:
4: for = to m: do
5: Receive (1² o0 2 from the server and set pa == , = 2.
6: Update the personalized model:
11 カ- 0
0 r 0
(p) CE (X/, Y))
2
0,
where (p)
'E denotes the cross-entropy loss.
1 1-1 11-1-80-1
7: Update local version of mean: po! f- pe t-1
-17
8: Update global variance: do. 00. 77
2, 2
d
1
11
3.1
2(
9: Send (1i, to the server
end for
11:
At the Server:
Receive ((u), 2.1) from the clients
12:
13: Aggregate mean: fu' = Σ μ
Aggregate global variance: 0 m Σ 00.
15:
Broadcast (He', ,0²1)) all clients
16:
end for
Output: Personalized models ..... 0
G PERSONALIZED LEARNING MIXTURE MODEL
In this section, present the linear regression problem as generalization to the estimation problem with discrete priors. This model falls into the framework studied in Marroo et al. (2021) and is illustrated show how framework also captures it.
Consider set of m clients, where the i-th client has a local dataset (X ......... (Xin, Y.n) of m samples, where Xij Rd denotes the feature vector and Yı; R denotes the corresponding response. Let Y, (Yi, .i...... Ya) R" and X; (Xar...., Xin) x denote the response vector and the feature matrix at the i-th client, respectively. Following the standard regression, we assume that the response vector Y, is obtained from linear model follows:
Y X,O, + wi:
(56)
where 0; denotes personalized model of the i-th client and w; ~ N' (0, ozIn) ) is a noise vector. The clients models are drawn i.idd. from a discrete distribution ....... O., P. where P = [pI..... Ps] such that pt Pr(O: [4]] for E [m] and / [k)].
29

---

Published as a conference paper at ICLR 2023
Our goal is to solve the optimization problem stated in ( (for the linear regression with the above discrete prior) and learn the optimal personalized parameters {0.}.
We assume that the discrete distribution P' and the prior candidates { are unknown to the clients. Inspired from Algorithm 3 for estimation with discrete priors, obtain Algorithm 6 for learning with discrete prior. Note that this is not new algorithm, and is essentially the algorithm proposed in Marfoq captures mixture model in Marloq et al. (2021) through this example.
(2021) applied linear regression. We wanted show how our framework
Description of Algorithm 6 Client i initializes its personalized parameters 0 0 = -X? which is the optimal as function of the local dataset at the i-th client without any prior knowledge.
In any iteration f, for a given prior information p(t)) {14 (t) the i-th client updates the personalized
(1) pii (1) where the weights a/ Pi (t) model as 0 Σ aj
and sends its exp [|x,,z ( -vll
20
current estimate of the personalized parameter 0 to the server. Upon receiving 0 0 O server will run Cluster algorithm to update the global parameters P, m1 ;.... (/) and broadcasts them to the clients.
(t)
Algorithm 6 Alternating Minimization for Personalized Learning
Input: Number of iterations T, local datasets (X;, Y,) for E [m]]
1: Initialize 0% -X? x,) x? Y; for E [m] (if X? X; not full-rank, take the pseudo-inverse).
2: for 1 to I do
3: On Clients:
4: for to m:
5: Receive p(t)
(0) from the server
6: Update the personalized parameters and the coefficients:
(t) Pi
X.m -X,1²
k
exp
20
0¹
1=1
and
ag
(4)
Σ -==1
ps
(1)
exp
|1N:115 1112
2n
7: Send ( to the server
8: end for
9: At the Server:
10: Receive 0 ,...., ( from the clients
11: Update the global parameters: IP(() M1 M + Cluster (0
(1)
(t)
1 k))
12:
Broadcast IP(() 11 M to all clients
end for
Output: Personalized models of..... OT
H PERSONALIZED LEARNING ADAPED
H.1 KNOWLEDGE DISTILLATION POPULATION DISTRIBUTION
In this section we discuss what type of a population distribution can give rise to algorihhms/robblems that include knowledge distillation (KD) (or KI. divergence) penalty term between local and global models. From Section 3 Equation (9), consider Po, (v|z) as randomized mapping from input space X to output class V parameterized by 0,. For simplicity, consider the case where [X] is finite, e.g.
for MNIST it could be all possible 28 x 28 black and white images. Every pe, (w|x) corresponds to a probability matrix (parameterized by 0,) of size | x |1'). where the (y, 'thh represents the probability of the class y (row) given the data sample (column). Therefore, each column is probability vector. Since we want to sample the probability matrix, it suffices to restrict our attention any set of y rows, the remaining row be determined by these [ 1 rows.
30

---

Published as a conference paper at ICLR 2023
Similarly, for global parameter μ4, let (z)()) define randomized mapping from X' to V parame- terized by the global parameter μa. Note that for a fixed global parameter μu, the randomized map (v(()z) is fixed, whereas, goal is to sample Po, (y]z) for i = I,..., m, for each client. For simplicity of notation, define Po, == po; (ylæ:) and Pμ = (. to be the corresponding probability matrices, and let the distribution for sampling po; (y/=²) be denoted by Ppμ, (po;). Note that different
mappings pe, (y)r) correspond to different 0,'s, so we define p(O,) (in Equation (9) as Pp (pe.),
which is the density of sampling the probability matrix po, (y)zz).
For the KD population distribution, we define this density Ppu. (po.) as:
Peu (po.) PD Ino, (vl=))
(57)
where is an 'inverse variance' type of parameter, c(i)) is a normalizing function that depends on (v), Pn), and DKL (p)))))))))) (ulær) Erex p(x:) Evey (n(v)z) log (po, (x/12z)
(allylr)
is the condi-
tional KL divergence, where p(x) denotes the probability of sampling data sample X. Now all we need is to find c(+)) given a fixed ju (and therefore fixed pn (y(z))) Here we consider DKL plp.)). but analysis can be extended to DKL (po. IIPx)) llpo. Ppll2 2 as well.
For simplicity and to make the calculations easier, we consider a binary classification task with )' = 10 and define (=()) ( = 1|X x) and (xx) pe, (y 1|X = z). We have:
DR DKL(Pu(ll=)lpo, (u/z))
Σ p(x) (())) (pl(=)(logPp(e))) log (x))
+ (1 (n(p)) -pp(-))p))))))))))))))))))) log(1 - q (x)))
Hence, after some algebra we have,
Pen (po.) = c(bb)c* E. (o) Mo)) Wol. (,0)))))))))00-)
Then,
(vv) e hateeH/nhhn....oooooooooaaaaaaad
dg.(2z) = 1.
2
Note that
J
Py (x)
- P((aa)
cootetlledde))laaaaooo log(1 (=)) B
1
ep((x)
<pp(x)
Accordingly, after some algebra, we obtain c(v)
- (ip
where H is binary
11, 13
Pu(e) Valay opte)
1-pute
Shannon entropy. Substituting this in (57.. we get
+ Σ. p(x)) (p)
Pou (po.) =
11. B(1 (a vp(z)*
1 I=pa(x) pp(()))
which is the population distribution that result in KD type regularizer. Note that when take the negative logarithm of the population distribution we obtain KL divergence loss and an additional
term that depends on and Pp- This is the form seen in Section 3.2 Equation
(1) for AdaPeD
(()))()
algorithm. For numerical purpose, take the additional term
log
to
II. B(I 11
be simple log(2;)). As mentioned in Section 3.2 this serves the purpose of regularizing v.. This is in contrast to the objective considered in Ozkara et al. (20T)) which only has the KL divergence loss as the regularizer, without the additional term
H.2 ADAPED WITH UNSAMPLED CLIENT ITERATIONS
When there is a flexibility in computational resources for doing local iterations, unsampled clients can do local training on their personalized models to speed-up convergence at no cost to privacy. This can be used in cross-silo settings, such inossinntttutional training for hospitals, where privacy is
31

---

Published as a conference paper at ICLR 2023
erucial and there available computing resources most of the time. We propose the algorithm for AdaPeD with with unsampled client iterations in Algorithm
Algorithm 7 Adaptive Personalization via Distillation (AdaPeD) with unsampled client iterations
Parameters: local variances [wr) personalized models {0)) local copies of the global
model {u]}. synchronization gap т, learning rates 7h 7a. 73- number of sampled clients K.
1: for = 0 - do if r divides t then
2:
3:
On Server do:
4: Choose subset IC' C [n] of K clients
5: Broadcast μz and v/a
6: On Clients E K (in parallel) do:
7: Receive 2e and wi set μ u², voj vit
8: end if'
9: On Clients $ K (in parallel) do:
10: Compute of == fi + Voy 1: (
where &y is the last time index where client i
20
received global parameters from the server Update: 0-+1 = 0 ngg
11:
12:
On Clients K (in parallef) do:
Vol Vo
13:
Compute g = V f((())
20/
14:
Update: 0++1 0 mi
V rot f: (0 wl
15:
Compute h1 ==
16:
Update: p 1 !r
n2h
17:
Compute Re = 200
1
2(00))
18:
Update: of+1 = vs- Task
19:
if divides t + then
20:
Clients send pet and vit to Server
21:
Server receives {Mr her and [wfhies
22:
Server computes 1 41 & Eiero u4 and w/+1 # Eiero ws
23:
end if
24:
end for
Output: Personalized models (0 ym
Of course, when client is not sampled for long period of rounds this approach can become similar local training: hence, it might be reasonable put an upper limit on the successive number of local iterations for each client.
I PERSONALIZED LEARNING DP-ADAPED
Proof of Theorem
Theorem (Restating Theorem 5p. After T iterations, DP DP-AdaPeD satisfies (ox, ((a))(())RDPP)) for a 1, where K denotes the sampling ratio of the clients at
where e(a) = ((K) 6 (T) Kop
c²
+
Ko
each global iteration.
Proof. In this section, we provide the privacy analysis of DP AP-AdaPeD. We first analyze the RDP of a single global round E [T] and then, we obtain the results from the composition of the RDP over total T global rounds. Recall that privacy leakage {wf) and we privatize both of these. In the following, we do the privacy analysis of privatizing {p}} and similar analysis could be done for {1/{) as well.
happen through communicating (H,) and
32

---

Published as a conference paper at ICLR 2023
At each synchronization round E [T], the server updates the global model p²*1 as follows:
++
Σ M4 SEKE
(58)
where 14 is the update of the global model at the i-th client that is obtained by running - local iterations at the i-th client. At each of the local iterations, the client clips the gradient hy with threshold C₁ and adds zero-mean Gaussian noise vector with variance o Lil When neglecting the noise added at the local iterations, the norm-2 sensitivity of updating the global model pa (-1 synchronization round & is bounded by:
at the
TC9 1 K2
Au max K'K
|| 11=+1
1
112
(59)
where K K', K C. [m] are neighboring sets that differ in only one client. Additionally, μ 4²+11 R Eiere iu and 4²++== K Liex' μr.. Since we add i.i.d. Gaussian noises with variance og at each local iteration at each client, and then, we take the average of theses vectors over K clients,
1
it is equivalent to adding single Gaussian vector to the aggregated vectors with variance ro" Thus, from the RDP of the sub-sampled Gaussian mechanism in (Mironov et al. 2019 Table 1), Bun et al. (2018), we get that the global model u²*1 of single global iteration of DP-AdaPeD is (ar, fz (1)(() (ax) -RDP, where <<(a)) bounded by:
K..
(a)
K
6aC2
(60)
Ko²
Similarly, we can show that the global parameter g 1 at any synchronization round of DP-AdaPeD is (a, Et (2) (a))-RDP, where (a(a) is bounded by:
K
6a
(61)
m
Ko
Using adaptive RDP composition (Mironov
2017 Proposition 1), we get that each synchronization
round of DP Dd-AdaPeD is (a, (1) (a) + (o))-RDP Thus, by running DP-AdaPeD over T/r
synchronization rounds and from the composition of the RDP, we get that DP AdaPeD is (a, (a,)(a))-
RDP, where <(a) = (H) (a) + & (o)). This completes the proof of Theorem
J EXPANDED RELATED WORK AND CONNECTIONS TO EXISTING METHODS
In Section D we mentioned that the our framework has connections to several personalized FL methods. In this appendix provide few more details related to these connections.
Regularization: As noted earlier using 9 with the Gaussian population prior connects to the use of
l2 regularizer in earlier personalized learning works Dinh et al. (2020): Ozkara et al. (2021) Hanzely & Richtárik (2020): Hanzely et al. (2020) Li et al. (2021). which also iterates between local and global model estimates. This form can be explicitly seen in Appendix EL where in Algorithm 4 see that the Gaussian prior along with iterative optimization yields the regularized form seen in these methods. In these cases IPT (N,,,,z)Lx) for unknown parameters I = {μ). Note that since the parameters of the population distribution are unknown, these need to be estimated during the iterative learning process. In the algorithm, fitt seen the μ plays the role of the global model (and is truly so for the linear regression problem studied in Appendix
Clustered FL: If one uses a discrete mixture model for the population distribution then the iterative algorithm suggested by our framework connects to (Zhang et al.) 2021 Mansour et al.) 2020 Ghosh jet al. 2020 Smith et al., (017)) Marfoq et al. [202]] particular, consider a population model with parameters in the m-diimensional probability simplex {a a [ai...., 0u) a; 0, Vi, E, a, 1} which describing a distribution. If there are m (unknown) discrete distributions {Pi..... Dm one can consider these the unknown description of the population model in addition a. Therefore,
One can generalize these by including oj the unknown parameters.
33

---

Published as a conference paper at ICLR 2023
each local data are generated either as a mixture in (Marfog et al. 2021 by choosing one of the unknown discrete distributions with probability a dictating the probability of choosing Di, when hard clustering is used (e.g.. (Mansour et al., 2020)). Each node chooses mixture probability a35) uniformly from the m-dimensiona. probability simplex. In the former case, it uses this mixture probability to generate a local mixture distribution. In the latter it chooses D, with probability a.")
As mentioned earlier, not all parametrized distributions can be written as mixture of finite number distributions, which is the assumption for discrete mixtures. Consider a unimodal Gaussian population distribution (as also studied in Appendix E). Since P(T) = (M,, aaTa), for node i, we sample
0, ~ P(T). We see that the actual data distribution for this node is po, (ylæz) ~a0 x. o²). Clearly the set of such distributions (po, (po((y(ar) (y] cannot be written as any finite mixture as 0g E TR and pe, (y/z) is a unimodal Gaussian distribution, with same parameter 0, for all data generated in node i. Essentially the generative framework of finite mixtures (as in (Marfoq et al. 2021) could be restrictive as it does not capture such parametric models.
The population distribution related to a regularizer based on Kullback- Leibler divergence (knowledge distillation) has been shown in Appendix[H] [H] Therefore this can be cast in terms of information geometry where the probability falls of exponentially with in this geometry. Hence these connect to methods such as Lin et al. (2020); Li & Wang (2019); [hhen et al.) (2020); Ozkara et al. (20TT) but the exact regularizer used does not take into account the full parametrization, and one can therefore improve upon these methods.
Knowledge distillation:
FL with Multi-task Learning (MTL): In this framework, a fixed relationship between tasks is usually assumed (Smith et al. 2017). Therefore one can model this as a Gaussian model with known parameters relating the individual models. The individual models are chosen from joint Gaussian with particular (known) covariance dictating the different models, and therefore giving the quadratic regularization used in FL-MTLL (Smith al. 2017). In this the parameters of the Gaussian model known and fixed.
The works in Du al, (2021) p Jain et al. 2021b) a linear model where ~~x (==T0,,' o²) can be considered a local generative model for node i. The common representation approach assumes that 0: وー= Bul for some i < d, where 0g Rd Therefore, one can parametrize a population by this (unknown) common basis B, and under mild assumption that the weights are bounded, we can choose a uniform measure in this bounded cube to choose to(() for each node The alternating optimization iteratively discovers the global common representation and the local weights done in Du et al. 2222 Jain et al. (202 Ib) (and references therein). This common linear representation approach was generalized in Du et al. (2021): Collins et al.) (202T) to neural networks, where set of parameters to obtain common representation ("head") at each client was obtained and each local client appendd it with a "tail" combining the representation to obtain the final model. This also fits into our statistical framework, where the common representation (head) parameters are chosen from a population model (like the common subspace in the linear case) and the tail parameters are independently chosen (again as in the linear case).
Common representations:
Empirical and Hierarchical Bayes: As mentioned in Section I our work is inspired by empirical Bayes framework, introduced in (Stein 1956, Robbins 1956, James & Stein 1961). which is the origin of hierarchical Bayes methods; see also (Gelman et al.) 2013 pp. 132). (teein 1956 James& & Stein 196T) studied jointly estimating Gaussian individual parameters, generated by an unknown (parametrized) Gaussian population distribution. They showed a surprising result that one can enhance the estimate of individual parameters based on the observations of a population of Gaussian random variables with independently generated parameters from unknown (parametrized) Gaussian population distribution. Effectively, this methodology advocated estimating the unknown population distribution using the individual independent samples, and then using it effectively as an empirical prior for individual estimates P This was studied for Bernoulli variables with heterogeneously generated individual parameters by Lord (1967) and the optimal error bounds for maximum likelihood estimates for population distributions were recently developed in (Vinayak et al., 2019). Hierarchical Bayes, builds on empirical Bayes framework and sometimes associated with fully Bayes method. Our choice to use empirical Bayes framework as the foundation is also because
This was shown to uni uniformly improve the mean-squared error averaged over the population, compared to an estimate using just the single local sample.
34

---

Published as a conference paper at ICLR 2023
it is more computationally feasible than fully Bayes method. The subtle difference between the two is that empirical Bayes uses a point estimate of (parametrized) prior, whereas, the terminology hierarchical Bayes often refers to a fully Bayes method where the (non-parametric) prior is estimated by computationally intensive methods like MCMC (see the discussion in (Blei et al. (003)). As mentioned in Section [ contribution of our work is connect well studied statistical framework of empirical (hicrarchical) Bayes to model heterogeneity in personalized federated learning. This statistical model yields a framework for personalized FL and leads to new algorithms and bounds especially in the local data starved regime.
K ADDITIONAL DETAILS AND RESULTS FOR EXPERIMENTS
K.1
IMPLEMENTATION DETAILS
In this section we give further details on implementation and setting of the experiments that were used Section
CIFAR-100 Experiment Setting. We do additional experiments on CIFAR- 100. CIFAR-100 is dataset consisting of 100 classes and 20 superclasses. Each superclass corresponds category of 5 classes (e.g. superclass flowers correspond to orchids, poppies, roses, sunflowers, tulips). To introduce heterogeneity we let each client sample data samples from super classes (the classification task is still to classify among 100 classes). For classification on CIFAR-10N dataset we consider 5-layer CNN with 2 convolutional layers of 64 filters and 5x5 filter size, following that we have fully connected layers with activation sizes of 192 and finally an output layer of dimension 100. We set number of local epochs to be 2, batch size to be 25 per client; number of clients is 50, client participation K 0.2, and number of epochs 200 (100 communication rounds). In this new dataset the classification task is more complex given the increased number of labels.
n
Hyperparameters. We implemented Per-FedAvg and pFedMe based on the code from GitHub 10 Other implementations were not available online, so we implemented ourselves. For each of the methods we tuned learning rate the set (0.3, 0.2, 0. 0.15, 0.125, 0.1, 0.075, 0.05) and have a decaying learning schedule such that learning rate is multiplied by 0.99 at each epoch. We use weight decay of le For MNIST and FEMNIST experiments for both personalized and global models we used 5-layer CNN, the first two layers consist of convolutional layers of filter size 5 x 5 with 6 and 16 filters respectively. Then we have fully connected layers of dimension 256 x 120, 120 x 84, 84 x 10 and lastly softmax operation. For CIFAR-10 10 experiments we use similar CNN, the only difference is the first fully connected layer is of dimension 400 x 120.
AdaPe el II We fine-tuned v/ in between 0.5 - 5 with 0.5 increments and set it to 3.5. We set 173 5e We manually prevent v becoming smaller than 0.5 so that local loss does not become dominated by the KD loss. We use 722 = 0.1 and 771 = 0.1. 12 When taking the derivative with respect to vi we observed sometimes multiplying the right term (consist of KD loss function) by some constant (5 in our experiments) gives better performance.
Per-FedAvg Fallah et al. (2020) and PFedMe Dinh et al. (2020): For Per-FedAvg, we used 0.075 as the learning rate and a 0.001. For pFedMe we used the same learning rate schedule for main learning rate, K = 3 for the number of local iterations; and we used À 0.5, 17 0.2.
QuPeD Ozkara et al. 22021) We choose Ap 0.25, / = 0.1 and 7/3 = 0.1 as stated.
Federated Mutual Learning Shen et al. (2020): Since authors do not discuss the hyperparameters in the paper, we used a = ;3 = 0.25 global model has the same learning schedule as the personalized models.
K.2 ADDITIONAL EXPERIMENTS
Convergence plots for AdaPeD. We put the experimental convergence plots (test accuracy no. of iteration) for AdaPeD in Figure
"/tttps://gite com/ woom/Charlieiini/peee
FFrr federated experiments we have used PyTorch's s Data Distributed Parallel package.
We use httpt:tt/////...... http://///ggtabb.cccaaaaa/aeeeee
ITT STT SS__ytoorchhhhhheeopspo__p_se import FEMNIST dataset.
35

---

Published as a conference paper at ICLR 2023
100
Test Accuracy %6)
90
Test Accuracy (in %)
80
40-
20
40
50
20
25
40
iteration
iteration
(a) AdaPeD Test Accuracy (in %) vs iteration on MNIST with 0.1 sampling ratio.
(b) AdaPeD Test Accuracy (in %) vs iteration on FEMNIST with 0.33 sampling ratio.
Figure 2: Convergence plots (test accuracy vs no. of iteration) for AdaPeD.
Personalized estimation: synthetic experiments in Bernoulli setting. For this setting, for we consider three distributions that (Tian et al. (017) considered: normal, uniform and '3-spike' which have equal weight at 1/4, 1/2, 3/4. Additionally, we consider Beta prior. We compute squared error of personalized estimators and local estimators (2: w.r.t. the true p; and report the average over all clients. We use 2017). Personalized estimator provides a decrease in MSE by 37.1 = 3.9%, 12.0 = 1.6%. 24.3 E 2.8%, 34.0 + 3. 3%,, respectively, for each aforementioned population distribution compared to their corresponding local estimators. Furthermore, as theoretically noted, less spread out prior distributions (low data heterogeneity) results in higher MSE gap between personalized and local estimators.
10000 clients and 14 local samples similar to (Tian et al.
Linear regression. For this, we create a setting similar to (Jain al. (021a). We set m 10, 000, 10; and sample client true models according to Gaussian centered at some randomly chosen with variance oz. We randomly generate design matrices X, and create Y, at each client by adding zero mean Gaussian noise with true variance of to X,O, We set true values o3 0.01, 0.05 and we sample each component of μ from a Gaussian with 0 mean and 0.1 standard deviation and each component of X from Gaussian with 0 mean and variance 0.05, both i.i.d. We measure the average MSE over all clients with and compare personalized and local methods. When = 50, personalized regression has an MSE gain of 8.0 0.8%, 14.8 + 1.2%, and when d 100, 9.11.. 2..3 compared to local and FedAvg regression, respectively. Moreover, compared personalized regression where μ1, Fe, ax are known, alternating algorithm only results in 1% and 4.7% increase in MSE respectively for d = 50 and d 100.
Estimation Experiments. We provide more results for the estimation setting discussed in Figure La In Figure 3a we have a setting with 1000 clients and 5 local samples and in Figure 33 500 clients and local samples per client. We observe with as the number clients increase DP-Personalized Estimator can converge to Personalized Estimator with less privacy budget. We also observe compared to Figure la] less number local samples increases the performance discrepancy between personalized and local estimator.
KSE (i te:2
ASE (in Ie
Local Extimeter Persorallted Extimater
Local Extimater
Personalized Extirater Entratte
DP Persono Ized Eximator
DP Persona Ized Estimator
In Figure la plot MSE vs. co for personalized esti- mation with different number of clients, this is the same setting as Figure La except the number of clients local samples.
Figure 3:
(a) Private Estimation with m=1000, Private Estimation with m=500,
36

---

Published as a conference paper at ICLR 2023
Additional Learning Experiments with Different Number of Clients. We do additional experi- ments with different number of clients. On FEMNIST we use the same model and same data sample per client as in Section4] number of clients is 30, total number of epochs is 30 and fix the local iteration to be 40 per epoch, we do full client sampling to simulate a cross-silo environment. As seen in Table 4 AdaPel) continues outperform the competing methods following the trend in Section
Table 4: Test accuracy (in %) for FEMNIST with m 30 clients.
Method
FEMNIST
FedAvg
95.91 + 0.78
FedAvg+fine tuning Jiang et al.
2019
96.22 + 0.57
AdaPeD (Ours)
98.10 + 0.09
DFedMe (Dinh et al. 2020)
96.03 = 0.50
Per-FedAvg Fallah al.
2020)
96.71 + 0.14
QuPeD (FP) Ozkara et al.
[202]
97.72 + 0.16
Federated ML (Shen et al.
2020
96.80 = 0.13
On CIFAR-10 10 we use the same model as in Section4] and divide the dataset 30 clients where each client has access to data samples from 4 classes. Total number of epochs is 250 and we fix the local iteration to be 40 per epoch; we set K 0.2 and number local epochs to be AdaPeD outperforms the competing methods in parallel to the experiments in Section as can be seen in T
n
Table 5: Test accuracy (in %) for CIFAR- 10 with m = 30 clients.
Method
CIFAR-10
FedAvg
53.92 + 0.94
FedAvg+fine uning Jiang al. 2019
67.44 + 1.11
AdaPeD (Ours)
73.86 + 0.39
PFedMe (Dinh et al. 2020
71.97 = 0.09
Per-FedAvg Fallah al.
2020)
64.09 + 0.46
QuPeD (FP) Ozkara et al.
2021
73.21 + 0.44
Federated ML (Shen
2020
72.53 + 0.36
Additional Experiment Implementation Details.
We use the same strategy in Appendix K.I to tune the main learning rates. We use le-4 weight decay.
AdaPeD: We fine-tuned & in between 0.5 5 with 0.5 increments and set it to for CIFAR-10/100 and to 3 for FEMNIST. We manually prevent becoming smaller than 1 so that local loss does not become dominated by the KD loss. We use 1/2 = 0.075 and = 0.075 for CIFAR-10 10 and CIFAR-100 and 172 0.1 and 77 0.1 for FEMNIST.
Per-FedAvg (Fallah et al.) 2020) and pFedMe (Dinh al. 2020): For Per-FedAvg, we used 0. as the learning rate and a 0.0001. For pFedMe we used the same learning rate schedule for main learning rate,
for the number of local approximation iterations; and used X 0.1,
1) = 0.1.
QuPeD Ozkara et al. (2021) We set Ap = -0.25, 77 = 0.1 for local learning rate and 7]2 = 0.1 for global learning rate.
Federated Mutual Learning Shen et al. (2020): Since authors do not discuss the hyperparameters in the paper, we used a = 8 = 0.25.
37


Reviews:
[{"review_id": "lAY7rH0RxQ", "reviewer": "Reviewer_MwhW", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors propose a statistical framework for personalized learned and estimation in a federated learning setting. The authors first explicitly state the modeling assumptions of how local model parameters are drawn from a global distribution of parameters. They then develop private and non-private estimation and learning algorithms. ", "summary_of_the_review": "While I think the technical contributions of the paper are quite novel, it is very hard to read. This is in large part because the authors have tried to fit too many things into a single paper. For instance, have the authors considered writing this as 2 separate papers on personalized learning and estimation? Alternatively, it might be better suited as a long-form journal paper (say at JMLR or TMLR). ", "strength_and_weaknesses": "Strengths: \n1) The modeling assumptions of how local model parameters are drawn from a global distribution of parameters seems quite reasonable, albeit a little restrictive. \n2) The proofs seemed correct. Although, I am not a theorist, so I wouldn't state this with a lot of certainty. \n3) The authors seemed to have given a lot of thought to the practical problems in federated learning setting and have tried to tackle a lot of them systematically. \n\nWeakness: \n1) The paper tries to do too much in my opinion, which makes it quite difficult to follow at times. \n2) The experiments seem sparse and handpicked, particularly for the personalized learning setting. Several questions that came to my mind are: what is the reason for picking m to be 50 and 66? Why didn't the authors try a range of values and reported all the results? \n3) Similarly, for the estimation task, I'd like to see more experiments. This can be done easily with different choices of synthetic parameters. \n4) Add more motivation for each estimation and learning setting. When are these problems relevant? Why should we care about them? This is not very clear from the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ExO9qPfcGO", "reviewer": "Reviewer_t7xg", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes algorithms that search for suitable personalized models in a client-server type federated learning setup. The algorithms are inspired by the classical theory of parametric Bayesian risk minimization. In the personalized parameter estimation regime, the authors assume two population distributions: Gaussian and Bernoulli. Under Gaussian distribution, they report that in case the parent population becomes degenerate (i.e., variation tending to nullity), the global average turns out to be the ‘best’ estimator. Moreover, the posterior personalized mean estimator in this setup also turns out to be optimal in general. If the parent population follows a Bernoulli law, having sufficient observations from local sub-populations suggests against collaborating. The following ‘personalization’ algorithms utilize different prior distributions and regularization schemes to ensure client privacy.", "summary_of_the_review": "The paper may be considered for acceptance provided the authors address the above listed concerns. ", "strength_and_weaknesses": "Strength:\n\nThe language of the article is lucid, and the presentation is also of good quality. The discussion leading up to the theoretical analyses and the algorithms is precise. I find the statistical analysis rigorous and very well represented. Prior works and relevant references are well-placed throughout the paper. \n\nWeakness/Issues:\n\nThe authors have altered the standard structure of the article, as guided by ICLR instructions. The abstract should not be full page-wide. This is a violation of the code and gives them an undue advantage over others. \n\nThe current article looks incomplete, lacking a ‘Conclusion’ section. Also, sufficient discussion regarding limitations and future work is missing.\n\nI suggest the authors present accompanying codes maintaining anonymity. \n\nIt would be very helpful if the problem statement is presented more precisely in the introduction. The authors provide a lot of references to prior work. However, amidst such a crowd, the motivation somehow fades. \n\nAs I have acknowledged, the discussion is quite rigorous. However, the is significant room for improvement when it comes to organization. \n\nThe empirical results seem insufficient, and I suggest the authors put more datasets to test if feasible.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8gV7C5pmcn4", "reviewer": "Reviewer_3hXR", "summary": "", "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": "", "summary_of_the_paper": "In this work, the authors developed a new Bayesian framework for personalized federated learning and derived theoretical bounds and novel algorithms for private personalized estimation. AdaPeD was proposed to use information divergence constraints along with adaptive weighting of local models and population models. AdaMix was proposed to adaptively weigh multiple global models and combines them with local data for personalization. Certain privacy analyses of new private personalized learning algorithms were done.", "summary_of_the_review": "The paper is clearly written, but the notations are heavy. The contribution is very technical from the perspective of Bayesian Federated Learning. ", "strength_and_weaknesses": "I think this paper is strong. It studies an important yet remarkably understudied problem that can build the bridge between Bayesian learning and federated learning. It gives two types of algorithms: AdaPeD and AdaMix. The algorithm and the theoretical results are sound. The algorithm is fairly natural in Bayesian perspective, which is to update the Gaussian posterior based on the prior and likelihood. The AdaPeD uses a knowledge distillation regularization. It shows we can federatedly train the model via MAP well when preserving user-level privacy.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "37JKlzGqRFf", "reviewer": "Reviewer_zS9y", "summary": "", "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": "", "summary_of_the_paper": "In this paper, authors develop a statistical framework for personalized federated learning, in which they study different choices of population distribution. They provide theoretical bounds and novel algorithms for private personalized estimation, design, and conduct privacy analysis of new private personalized learning algorithms. ", "summary_of_the_review": "I am generally positive about the paper ideas, but there are some issues that are worth correcting (see above).", "strength_and_weaknesses": "Strengths:\n* The paper is theoretically grounded. Authors provide theoretical results for different population models.\n* In contrast to many competitors, the paper considers privacy aspects of the problem and provides new algorithms with provable privacy guarantees\n\nWeaknesses:\n* \"Based on (Xi, Agg(q1, . . . , qm)), client i outputs an estimate \\hat{\\theta_i} of \\theta. \" Should be the estimate of \\theta_i ? Otherwise not clear what is \\theta as it is not defined before.\n* It seems that there is a missing opportunity to compare with another class of personalized models. Namely [1], when there is a split of shared and personalized parameters. Moreover, this model could be considered as a particular case of your statistical framework, when (for Gaussian population model) \\sigma_\\theta = [0,\\infty] where 0 corresponds to the shared (common) part of parameters, and \\sigma_x = 0. It is worth mentioning the paper in related work and comparing the results.\n* The choice of datasets for experiments seems a bit low-key. I suggest considering CIFAR100.\n\nMinor issues:\n* page 6 first appearance of FedAvg — no link\n*\"... given 6 election data we did 1-fold cross-validation. \" - what does 1-fold cross-validation mean? Did not you mean 6-fold cross-validation?\n\n\n[1] Collins L. et al. Exploiting shared representations for personalized federated learning //International Conference on Machine Learning. – PMLR, 2021. – С. 2089-2099.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster