On Convergence of Federated Averaging Langevin Dynamics
Authors: Wei Deng
Qian Zhang
Yian Ma
Zhao Song
Guang Lin
Venue: Submitted to ICLR 2023 (2023)
Keywords: Langevin dynamics
federated learning
posterior inference
MCMC
stochastic gradient Langevin dynamics
differential privacy

Abstract: We propose a federated averaging Langevin algorithm (FA-LD) for uncertainty quantification and mean predictions with distributed clients. In particular, we generalize beyond normal posterior distributions and consider a general class of models. We develop theoretical guarantees for FA-LD for strongly log-concave distributions with non-i.i.d data and study how the injected noise and the stochastic-gradient noise, the heterogeneity of data, and the varying learning rates affect the convergence. Such an analysis sheds light on the optimal choice of local updates to minimize communication cost. Important to our approach is that the communication efficiency does not deteriorate with the injected noise in the Langevin algorithms. In addition, we examine in our FA-LD algorithm both independent and correlated noise used over different clients. We observe there is a trade-off between the pairs among communication, accuracy, and data privacy. As local devices may become inactive in federated networks, we also show convergence results based on different averaging schemes where only partial device updates are available. In such a case, we discover an additional bias that does not decay to zero.

Under review as a conference paper at ICLR 2023
ON CONVERGENCE OF FEDERATED AVERAGING LANGEVIN DYNAMICS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose federated averaging Langevin algorithm (FA-LD) for uncertainty quantification and mean predictions with distributed clients. In particular, we generalize beyond normal posterior distributions and consider a general class of models. We develop theoretical guarantees for FA-LD for strongly log-concave distributions with non-i.i.d data and study how the injected noise and the stochastic- gradient noise, the heterogeneity of data, and the varying learning rates affect the convergence. Such an analysis sheds light on the optimal choice of local updates to minimize communication cost. Important to our approach is that the commu- nication efficiency does not deteriorate with the injected noise in the Langevin algorithms. In addition, we examine in our FA-LD algorithm both independent and correlated noise used over different clients. We observe there trade-off between the pairs among communication, accuracy, and data privacy. As local devices may become inactive in federated networks, we also show convergence results based on different averaging schemes where only partial device updates are available. In such case, we discover an additional bias that does not decay zero.
INTRODUCTION
Federated learning (FL) allows multiple parties jointly train consensus model without sharing user data. Compared to the classical centralized learning regime, federated learning keeps training data on local clients, such as mobile devices or hospitals, where data privacy, security, and access rights are matter of vital interest. This aggregation of various data resources heeding privacy concerns yields promising potential in areas of internet of things (Chen al., 2020), healthcare (Li al., 2020d; 2019b), text data (Huang et al., 2020), and fraud detection (Zheng et al., 2020).
standard formulation of federated learning distributed optimization framework that tackles communication costs, client robustness, and data heterogeneity across different clients (Li et al., 2020a). Central to the formulation is the efficiency of the communication, which directly motivates cnnntunicaatincffffiiete federated averaging (FedAvg) (McMahan al., 2017). FedAvg introduces global model to synchronously aggregate multi-step local updates on the available clients and yields distinctive properties in communication. However, FedAvg often stagnates at inferior local modes empirically due to the data heterogeneity across the different clients (Charles & Konečný, 2020; Woodworth et al., 2020). To tackle this issue, Karimireddy et al. (2020); Pathaky & Wainwright (2020) proposed stateful clients to avoid the unstable convergence, which are, however, not scalable with respect to the number of clients in applications with mobile devices (Al-Shedivat et al., 2021). In addition, the optimization framework often fails to quantify the uncertainty accurately for the parameters of interest, which are crucial for building estimators, hypothesis tests, and credible intervals. Such problem leads to unreliable statistical inference and casts doubts on the credibility of the prediction tasks or diagnoses in medical applications.
To unify optimization and uncertainty quantification in federated learning, we resort to a Bayesian treatment by sampling from a global posterior distribution, where the latter is aggregated by infrequent communications from local posterior distributions. We adopt popular approach for inferring posterior distributions for large datasets, the stochastic gradient Markov chain Monte Carlo (SG- MCMC) method (Welling & Teh, 2011; Vollmer et al., 2016; Teh al., 2016; Chen et al., 2014; Ma et al., 2015). which enjoys theoretical guarantees beyond convex scenarios (Raginsky et al., 2017; Zhang et al., 2017; Mangoubi & Vishnoi, 2018; Ma et al., 2019). In particular, examine

---

Under review as a conference paper at ICLR 2023
in the federated learning setting the efficacy of the stochastic gradient Langevin dynamics (SGLD) algorithm, which differs from stochastic gradient descent (SGD) in an additionally injected noise for exploring the posterior. The close resemblance naturally inspires to adapt the optimization-baal FedAvg to a distributed sampling framework. Similar ideas have heen proposed in federated posterior averaging (Al-Shedivat al., 2021), where empirical study and analyses Gaussian posteriors have shown promising potential of this approach. Compared to the appealing theoretical guarantees of optimization-bant based algorithms in federated learning (Pathaky & Wainwright, 2020; Al-Shedivat et al., 2021), the convergence properties of approximate sampling algorithms in federated learning is far less understood. To fill this gap, we proceed by asking the following question:
Can we build unified algorithm with convergence guarantees for sampling in FL?
In this paper, we make a first step in answering this question in the affirmative. We propose the federated averaging Langevin dynamics for posterior inference beyond the Gaussian distribution. We list our contributions as follows:
We present novel moptosy convergence analysis for FA-LD from simulating strongly log-concel log-concave distributions on non-i.i.d data when the learning rate is fixed. The frequently used bounded gradient assumption of lg norm in FedAvg optimization not required.
The convergence analysis indicates that injected noise, data heterogeneity, and stochastic- gradient noise are all driving factors that affect the convergence. Such an analysis provides concrete guidance on the optimal number of local updates to minimize communications.
We can activate partial device updates avoid straggler's 'ss effects in practical applications and tune the correlation of injected noises to protect privacy.
We also provide differential privacy guarantees, which shed light the trade-off between data privacy and accuracy given limited budget.
For related works of other federated learning approaches, we refer interested readers section H.
PRELIMINARIES
2.1
AN OPTIMIZATION PERSPECTIVE ON FEDERATED AVERAGING
Federated averaging (FedArg) is standard algorithm in federated learning and is typically formulated into a distributed optimization framework as follows
min (()) = ΣN (0) (0
1(0; (0,)),
(1)
>e The
where 0 e RRd, ((0; xo.)) is certain loss function based on 0 and the data point Tegi
FedAvg algorithm requires the following three iterate:
Broadcast:
The center server broadcasts the latest model, 0g. to all local clients.
Local updates: For any E [N]. the c-th client first sets the auxiliary variable 0 02 and then conducts K 2 local steps: f6+1 = 3 n. V)o())), where vj is the learning rate and V the unbiased estimate the exact gradient V
Synchronization: The local models are sent to the center server and then aggregated into unique model 0x+K En Poof+ where Pe as the weight of the e-th client such that Pe E. 10 and n. is the number of data points in the e-th client.
From the optimization perspective, Li et al. (2020c) proved the convergence of the FedAvg algorithm on non-i.i.d data such that a larger number of local steps K and a higher order of data heterogeneity slows down the convergence. Notably, (1) can be interpreted maximizing the likelihood function, which a special case of maximum a posteriori estimation (MAP) given a uniform prior.
2.2 STOCHASTIC GRADIENT LANGEVIN DYNAMICS
Posterior inference offers the exact uncertainty quantification ability of the predictions. A popular method for posterior inference with large dataset is the stochastic gradient Langevin dynamics
2

---

Under review as a conference paper at ICLR 2023
(SGLD) (Welling & Teh, 2011), which injects additional noise into the stochastic gradient such that 0x+1 = 0x T + V2TT( where is the temperature and &x is standard Gaussian vector. f(0) := -m= (0) is an energy function. V f is an unbiased estimate of V f()). the longtime limit, 8g converges weakly to the distribution T(f) exp((f(()/T) (Tch et al., 2016) as 1) O.
3 POSTERIOR INFERENCE VIA FEDERATED AVERAGING LANGEVIN DYNAMICS
The increasing concern for uncertainty estimation in federated learning motivates us to consider the simulation of the distribution T (0) x exp( (xp(-f(0)/r) with distributed clients.
Problem formulation We propose the federated averaging Langevin dynamics (FA-LD) based on the FedAvg framework in section 2.1. We follow the same broadcast step and synchronization step but propose to inject random noises for local updates. particular, we consider the following
scheme: for any [N], the e-th client first sets f% = 0g and then conducts K' 2 1 local steps:
Local updates: P2+1 = 0% V (0%) + 2
(2)
16+1
if + 1 mod K + 0
Synchronization: 0,+11
Ee Pe i + mod K = 0.
where ()( = VZ)) =
is the unbiased estimate of V (0); Ei is some Gaussian vector
in (6). Summing (2) from clients e 1 to N and setting 02 (0) . ), we have
B&+1 02 v(Om)) + ER
N 6₂=
N v((x)) Σ ( &
where
Br = >>eo PoSt. =
Σ Poble
Σ
p. (4)
By the nature of synchronization, we always have 3g = 02 for any 2 and the process follows
o 02 1) ((O)) 2
(5)
which resembles SGLD except that have a different "gradient" operator V and O2 is not accessible when k mod K & O. Since our target is to simulate from (0) xx exp(- we expect &N is a standard Gaussian vector. By the concentration of independent Gaussian variables, is natural to set
E E /Pc.
(6)
where & = - c== VP and <G is also standard Gaussian vector. Now we present the algorithm based on independent inject noise (p = 0) and the full-device update (3) in Algorithm 1, where p is the the correlation coefficient and will further studied in section 4.3.3. We observe Eq.
N
maintains temperature T T/P. > to converge to the stationary distribution и. Such mechanism may limit the disclosure of individual data and shows a potential to protect the data privacy.
Algorithm Federated averaging Langevin dynamics Algorithm (FA-LD)), informal version of Algorithm 4. Denote by og the model parameter in the e-th client at the k-tth step. Denote the one-step intermediate result by SC. <g is an independent standard d-dimensional Gaussian vector at iteration for each client e E [N]; &N is d-dimensional Gaussian vector shared by all the clients; denotes the correlation coefficient. Sy is sampled according to a device device-sampling sampling rule based on scheme or II.
8 0% ( + p + 2 (1 -P))
if mod K #0
0
Hstevice (8
if l: + mod K = 0.
where I (g En Pe for full device and = Eees,,, 1 for partial device.
3

---

Under review as a conference paper at ICLR 2023
4 CONVERGENCE ANALYSIS
In this section, we show that FA-LD converges to the stationary distribution π (0) in the 2- Wasserstein (W2) distance a rate O(1/v'A for strongly log-concave and smooth density. The W2 distance is defined between a pair of Borel probability measures and on R as follows
(2 v) =
inf T'Coupling((x..))
where || 1/2 denotes the &g norm on IR and the pair of random variables (B,r Bv)) E IRd x R is coupling with the marginals following ((3,) μ and L(Br) v. Note that L()) denotes distribution of a random variable.
4.1 ASSUMPTIONS
We make standard assumptions on the smoothness and convexity of the functions f2....... f.N which naturally yields appealing tail properties of the stationary measure и. Thus, we no longer require a restrictive assumption et al. (2019); et al. (2020c). addition, to control the distance between V and Vfs, we also assume bounded variance of the stochastic gradient in assumption 4.3.
the bounded gradient in & norm as Koloskova et al. (2019); Yu
Assumption 4.1 (Smoothness). For each E [N], f L-smooth for some L>0
L =Iv x Vx, Rd..
( S fz) (Vf x) + Assumption 4.2 (Strongly convexity). For each E [NV] f is m-strongly convex for some m >> 0
2
2 (3) (V) + 4) + 2 bly =1,3 V
Assumption 4.3 (Bounded variance). For each [NV. the variance of noise in the stochastic gradient (x) in each client upper bounded such that [[IVv((()) (=)))
<dd, Ve E Rdd
Quality of non-i.id data Denote by 6. the global minimum f. Next, we quantify the degree of the non-i.i.d data by y == max,g[N] V (fx))))l, which is non-negative and yields a larger scale if data less identically distributed.
4.2 PROOF SKETCHI
The proof hinges on showing the one-step result in the W2 distance. To facilitate the analysis, we first define an auxiliary continuous-time process (0.) that synchronizes for almost any time 2 0
dØ, - -V )di + /2rdW,.
where 0, DN PeOf. VS( De Pe V ( Of is the continuous-time variable client and W is d-dimensional Brownian motion. The continuous-tims algorithm known converge to the stationary distribution (0) x e f(() where f(0) Σ Pef (0). Assume that d simulates
from the stationary distribution then it follows that 0g ~ for any t 2 0.
4.2.1 DOMINATED CONTRACTION FEDERATED LEARNING
The first target to show a certain contraction property || vy (B)()) ( based on distributed clients with infrequent communications. Consider a standard decomposition
|| - (V)( ((0) = ||3 011 2n (3 0, V ( - (S +1/ [V V (())
Z
Using (4), we decompose I and apply Jensen's inequality to obtain a lower bound of I. In what follows, have the following lemma.
As such, Of EN PeB O. for VL 2 and Ve [N]. It also indicates =N Pe (0)) DN Pe (0))) hence the process recovers the standard Langevin diffusion and naturally converges to I. See details appendix A.1.1
4

---

Under review as a conference paper at ICLR 2023
Lemma 4.4 (Dominated contraction property, informal version of Lemma B.1). Assume assumptions 4.1 and 4.2 hold. For any learning rate E (0, Liml any {8)) [N Je=1 {33)
Je=1 E R. we have
Pe [1 312 1 011 1 ( f(0) (1-mm) || 112--122 L Σ
divergence
Ea P.O VS(3) = E Pe and VS(0) Ee P. (( It implies that long the local parameters 8r, 8 and global 0, B don't differ each other too much, we can guarantee the desired convergence. special case when the communication is conducted at every iteration, the divergence term disappears and recovers the standard contraction (Dalalyan & Karagulyan, 2019).
where 3
- PoB
4.2.2 BOUNDING DIVERGENCE
The following result shows that given a finite number of local steps K, divergence between in local client and in the center is bounded in &g norm. Notably, since the Brownian motion leads to lower order term (1)) instead of ((n²). a naive proof framework such as Li et al. (2020c) may lead to crude upper bound for the final convergence.
Lemma 4.5 (Bounded divergence, informal version of Lemma B.3). Assume assumptions 4.1, 4.2, and 4.3 hold. For any 1j (0, 2/m) and 110g 0.112 dD² for any e [N] and some constant D. we have the & upper bound of the divergence between local clients and the center
Σ P 0x112 S O((K ( 1)) + 11)nd).
The result relies on uniform upper bound in l norm, which avoids bounded gradient assumptions.
4.2.3 COUPLING TO THE STATIONARY PROCESS
Note that 0, is initialized from the stationary distribution æ. The solution to the continuous-time process (8) follows:
0. = 0o I Vf V2T W.,
V 2
Set t + (A: + 1)n and 0g - On, for (9) and consider synchromous coupling such that W ((k+1)n Wky == / T& is used to cancel the noise terms, we have
(k+1)m
((++1)) Okn
ff(,)dds + 2
(10)
km
Subtracting (5) from (10) and taking square and expectation on both sides yield that
1 + divergence term + time error. E| 0l00ui1 - 1x+1l s (1 r/m/2) E B
Eventually, we arrive at the one-step error bound for establishing the convergence results.
Lemma 4.6 (One step update, informal version of Lemma B.5). Assume assumptions 4, 4.2, and 4.3 hold. Consider Algorithm I with any 1) E (0, Σ() and ||0g - 0-112 < dDD2, 0. and full device participation for any c [N), where 0. is the global minimum for the function Then
W (2 T) < (1-1mm mm/2) (2 + O(K) 1)² +)),
where μig denotes the probability measure of 0g and k Lf /m is the condition number.
Given small enough 17. the above Lemma indicates that the algorithm will eventually converge
5

---

Under review as a conference paper at ICLR 2023
4.3 FULL DEVICE PARTICIPATION
4.3.1 CONVERGENCE BASED ON INDEPENDENT NOISE
When the synchronization step is conducted at every iteration k; the FA-LD algorithm is essentially the standard SGLD algorithm ( (Welling & Teh, 2011). Theoretical analysis based on the 2- Wasserstein distance has been established in Durmus & Moulines (2019); Dalalyan (2017); Dalalyan & Karag- ulyan (2019). However, in scenarios of K > with distributed clients, a divergence between the global variable 0g and local variable o appears and unavoidably affects the performance. The upper bound on the sampling error is presented as follows.
Theorem 4.7 (Main result, informal version of Theorem B.6), Assume assumptions 4.1, 4.2, and 4.3 hold. Given Algorithm I with 1j E (0, 1 p = full device, and well initialized {06] cD we have
N
() (1-mm/44) ( (V2d(D+ + Vr/m)) -300s/mmm: v(KK 1)2 + Ho.
where pe denotes the density of 0% at iteration k, K is the local updates, == L/m, == max (0.) and Ho = D2 + max,e[M]
I + mdd mp:
We observe that the initialization, injected noise, data heterogeneity, and stochastic gradient noise all affect the convergence. Similar Li al. (2020c), FA-LD with K-local steps resembles the one-step SGLD with a large learning rate and the result is consistent with the optimal rate (Durmus & Moulines, 2019), despite multiple inaccessible local updates. Nevertheless, given more smoothness assumptions. we may obtain better dimension dependence (Durmus & Moulines, 2019; Li et al., 2022). Bias reduction (Karimireddy et al., 2021) can be further adopted to alleviate the data heterogeneity.
Optimal choice of K. To achieve the precision c based on the learning rate 17, we can set
30k^ 30k//mmd npdd. V(K2 + Ho S E//2, exp (- (- T.)
T.. v2d(DD + VT/m) S E/22
T. 2 Ω Iog(d/c)
This readily leads to 1pm < 0
dr((k2+x)H
myy
Denote by T. the number of iterations achieve the target accuracy e. Plugging into the upper bound of mym, it suffices to set T. = 2xx + Ho log(d/c)). Note that Hg = ?((D), ), thus the
number of communication rounds is of the order K = 2 K + where the value of f first
decreases and then increases w.r.t. K, which indicates setting K either too large too small leads to high communication costs. Ideally, K should be selected in the scale of O (KVK). Combining the definition of T., this shows that the optimal K for FA-LD is in the order of O(TT), which matches the optimization-basel results (Stich, 2019; Li et al., 2020c).
4.3.2 CONVERGENCE GUARANTEES VIA VARYING LEARNING RATES
Theorem 4.8 (Informal version of Theorem B.7). Assume assumptions 4.1, 4.2, and 4.3 hold.
Consider Algorithm I with p O. full device, an initialization satisfying |g0| 0_11 < dD2 for any C [N), and the varying learning rate following Tik-
2L+(1/12mm- Then for any k. 2 we have
W2 T) < 45x ((K - 1)2 +K) (nwmd) 1/2 Vk 2 O.
To achieve the precision e, we need Wz(us; m) S e, i.e. W2(HE, S 45k 45k (K2 H) 1/2
We therefore require 2(E-2d) iterations achieve the precision e, which
(1/12mm
improves the QiE ode-"d log(//e)) rate for FA-LD with fixed learning rate by O(log(//e) factor.
4.3.3 PRIVACY-ACCURACY OFA VIA CORRELATED NOISES
The local updates in (2) with 3 / yp requires all the local clients to generate the indepen- dent noise ç.. Such mechanism enjoys the implementation convenience and yields a potential to protect the data privacy and alleviates the security issue. However, the large scale noise inevitably

---

Under review as a conference paper at ICLR 2023
slows down the convergence. To handle this issue, the independent noise can be generalized to correlated noise based on a correlation coefficient between different clients. Replacing Eq.(7) with
$ 0% - (BE) + V + 22n(11 p²)T//eEi
(11)
where & is a d-dimensional standard Gaussian vector shared by all the clients at iteration k and É is independent with &g for any с [M. Following the synchronization step based on Eq.(3), we have
0 = 0g - f(0x)) + 22
(12)
where E = pcx + that εu follows the standard d-dimensional Gaussian distribution. The correlated noise implicitly reduces the temperature and naturally yields a trade-off between federation and accuracy.
vP-Eg- Since the variance of i.i.d variables is additive, it is clear
Since the inclusion of correlated noise doesn't affect the iterate of (1.(1 the algorithm property maintains the same except the scale of the temperature т and efficacy of federation are changed. Based on a target correlation coefficient p 2 0, (q1( is equivalent to applying a temperature 0 leads to Te,0 T/Pe. which exactly recovers Algorithm I; however, setting p leads to T,,1 = т, where the injected noise in local clients is reduced by 1 1/Pc times. Now we adjust the analysis as follows
Tepp = Tpp + +(1 (1-pp)/pe p²)) In particular, setting
Theorem 4.9 (Informal version of Theorem B.8). Assume assuamptions 4.1, 4.2, and 4.3 hold. Consider Algorithm / with p E [0, 1). 7) E (0, z and 100 -0.13 S dD2 for any E [N] we have
(v2d + vT/m) + +30n /1nd/dddd---- V((K 1)2 + R. H) W2(14, n) S (1- (1-nm/4)
where U* denotes the probability measure of 0z. Hp = D2 + max Te.p + m'd + mz
Such mechanism leads to trade-off off between data privacy and accuracy and may motivate us to exploit the optimal p under differential privacy theories (Wang et al., 2015).
4.4 PARTIAL DEVICE PARTICIPATION
Full device participation enjoys appealing convergence properties. However, it suffers from the straggler's 's effect in real-world applications, where the communication is limited by the slowest device. Partial device participation handles this issue by only allowing small portion of devices in each communication and greatly increased the communication efficiency in a federated network.
The first sevice-sampling scheme I (Li et al., 2020b) selects total of S devices, where the c-th device is selected with a probability pe- The first theoretical justification for convex optimization has been proposed by Li et al. (2020c). The second device-sampling scheme II is to uniformly select S devices without replacement. We follow Li et al. (2020c) and assume S indices are selected uniformly without replacement. In addition, the convergence also requires an additional assumption on balanced data (Li et al., 2020c). Both schemes are formally defined in section C.I.
Theorem 4.10 (Informal version of Theorem C.3). Under mild assumptions.
Algorithm 1 with p [o, 1], a fixed n (0, 2/1 and ||06- 0x ll2 I dDD for any e [N), we have W2(uu, 7) < (1 m/m44)*. // (v2d(D VT/m)
+ +K) + 0 d
+ +330 300 mmd (H,(K++))
(O NN1
where Css = for Scheme I and Cs = N-1
N-S for Scheme II.
Partial device participation leads to an extra bias regardless of the scale of 17. To reduce it, we suggest to consider highly correlated injected noise, such p 1, to reduce the impact of the injected noise. Further setting O (dddS) e/3 and following a similar 77 in section 4.3.1, precision within Q(E 2d 2deeeddoog((e (og(/))) iterations given enough devices satisfying S = 2((==ad)
achieve the
The sampling scheme I provides a viable solution to handle the straggler's effect, which is rather robust to the data heterogeneity and doesn't 't require the data to be balanced. In more practical cases where a system can only operate based on the first S messages for the local updates, Scheme II achieve reasonable approximation given more balanced data with uniformly sampled device. If = 1, our Scheme II matches the result in the Scheme I; If S N, then our Scheme II recovers the result in the full device setting; If 5 = N o(N), our Scheme II bound is better than scheme I.
7

---

Under review as a conference paper at ICLR 2023
5 DIFFERENTIAL PRIVACY GUARANTEES
We consider the (e, diiffferrntt privacy with respect to the substitute-one relation ~ (Balle et al., 2018). Two datasets S =, S' if they have the same size and differ by exactly data point. For c 2 0 and 8 E [0. 1]. a mechanism M is (c, -ifffferrett private w.r.t. =, if for any pair of input datasets S =, S", and every measurable subset E Range(JM), have
P(M(S) E E| S c'P(M((S) E E] +
(13)
Since partial device participation is more general, we focus on analyzing the differential privacy guarantee based on updates with partial devices. Here, we present the result under scheme II. For the result under scheme I, please refer to Theorem G.3 in the appendix.
Theorem 5.1 (Partial version of Theorem G.3). Assume assumptions G.I and G.2 holds. For any óu E 1), in E (o. =(1--")>² min, Pe tten Algoritium under scheme II is ( (313 8(3) of log(1 25/
(KT))
K.T K.T)
differentially private w.r.t. =9 after (T- = ÉK with E N, E 1) iterations where
KKT EK min {
(3)
(V
2T K
log
(1) (1))
TS(e - 1)
KN
K
T
S N 7T8o + KN
TS
ò1 82,
with εx- log (1 +
8
(e - 1)), <K min V log(11 (1/6)) 6))+ + K(e - 1)) K).
N
61 201/
n1 noog(1 (5/6/ F(I-1 mincelN]
and 61, 82 E 10,
to Theorem 5.1 and section G. ( log (1 + & (eee 1)), N TTn) differentially private. O 7(1 ) min.r P. log(1/6s)) A752T (1/bg) (og()/);)
According
Algorithm
is at least
Moreover, if 1)
then (3)
KK = 0 SA
log 1/50) log( log( 1/2)) (1-p") [in
(3) There is trade-off off between privacy and utility. By Theorem 5.1, C,T is increasing function of 11 & N and T. K,T is an increasing function of S. 7, and T, However, by Theorem 4.10, the アリー
upper-bound of W2(Pr, 14) is a decreasing function of T, S and is an increasing function of 7 and N. There is optimal 17 to minimize W2 ()) for fixed T while we make 'K arbitrarily small by decreasing 7) for any fixed T. In practice, users can tune hyper-parameters based DP and accuracy budget. For example, under some DP budget (c., 8.), we can select the largest E [o, 1] (3) and S E [N] such that KT S E+ and ((3) K.T I 8. to achieve the target error W2(HT, 14).
(3)
6 EXPERIMENTS
Simulations For each c E [N], where N = 50, we sample 0g from a 2d Gaussian distribution
-2 NN, and sample n. points from ((6,, E), where -2 1 Thus, 1(6: w2.5) = (0
(e,,) Σ T - I.,I) 1og(2 (0) E E 1(0 The temperature is T 1. The target
density is (u, Σ) with u = 1 EN Ene Te,i We choose Gaussian posterior to facilitate the calculation of the W2 distance verify theoretical properties. Other details are detailed in section I.
pd5
4CM
140
C00
020
400
4.0
400
200 100 (a) Study
side
20 30
18c
450
Aapo
(b) Study of
(c) Study of p
(d) True density
(e) Empirical density
Figure 1: Convergence of FA-LD based on full devices. In Figure 1(a), points may coincide.
Optimal local steps: We study the choices of local step K for Algorithm based on = 0, full device, and different a's, which corresponds to different levels of data heterogeneity modelled by 7. We
8

---

Under review as a conference paper at ICLR 2023
choose a = 0, 1, 10, 100, 1000 and the corresponding y is around 1 x 10 4 .4x 10 4 10 and x 10 respectively. We fix 1) = 10-? We evaluate the (log) number of communication rounds to achieve the accuracy = 10 3 and denote it by T.. As shown in Figure I(a), small K leads to an excessive amount of communication costs; by contrast, a large K results in large biases, which in turn requires high communications. The optimal K that minimizes communication is around 3000 and the communication savings can be as large as 30 times.
Data heterogeneity and correlated noise: We study the impact of y on the convergence based on O, full device, different 7 from {I x 10", 4 x 10t1, 4 x 10 4 x 10th, and 4 x 10"4). We set K 10. As shown in Figure 1(b), the W2 distances under different y all converge to some levels around 10 10-3 after sufficient computations, Nevertheless, a larger does slow down the convergence, which suggests adopting more balanced data to facilitate the computations. In Figure 1(c), we study the impact of p on the convergence of the algorithm. We choose K = 100 and 10 and observe that a larger correlation slightly accelerates the computation, although it risks in privacy concerns.
Approximate samples: In Figure I(e), we plot the empirical density according to the samples from Algorithm with o = 0, full device, K = 10 and 7 = 10 '7 = 10-7, For comparison, we show the true density plot of the target distribution in Figure ((d). The empirical density approximates the true density very well, which indicates that the potential of FA-LD in federated learning.
For the convergence based on partial device participation, we refer interested readers section I.
(Fashion) MNIST To evaluate the performance of FA-LD under different local steps K on real- world datsets, we apply FA-LD to train a logistic regression model with the cross entropy loss on the MNIST and Fashion-MNIST dataset. The training dataset is split uniformly at random into N = 10 subsets of equal size for 10 clients. In each setting, we collect one parameter sample after every 10 communication rounds and average the predicted probabilities made by all the previous collected parameter samples to calculate three test statistics, accuracy, Brier Score (BS) (Brier et al., 1950), and Expected Calibration Error (ECE) (Guo et al., 2017) on the test dataset. We tune the step sizes 1) for the best performance and plot the curves of those test statistics against communication rounds under different local steps K 1, 10, 20, 50, 100 in Figure 2. Other details are provided in section J.
(a) Accuracy (M)
(b) BS (M)
(c) ECE (M)
(d) Accuracy (F)
(e) BS (F)
(1) ECE (F)
Figure 2: Convergence of FA-LD on the MNIST (M) and Fashion- (F) dataset.
According to Figure 2, under the same communication budget, FA-LD with K (i.e. the standard SGLD algorithm) performs the worst in terms of all three test statistics, which indicates the necessity of multiple local updates federated learning. Moreover, for different test statistics, the optimal local step K could be different; e.g., for the MNIST dataset, the optimal K in terms of accuracy is between 50 and 100 (Figure 2(a)), while the optimal K in terms of BS is around 20 (Figure 2(b)). To better visualize the convergence, consisting of the first 500 communication rounds is removed. Such results are detailed in section J.
also plot the curves of accuracy, BS, and ECE when warmup period
7 CONCLUSION
We propose a novel convergence analysis for federated averaging Langevin dynamics (FA-LD) with distributed clients. Our results no longer require the bounded gradient assumption in & norm as in the optimization-driven literature in federated learning. The theoretical guarantees yield a concrete guidance on the selection of the optimal number of local updates to minimize communication costs. In addition, the convergence highly depends on the data heterogeneity and the injected noises, where the latter also inspires us to consider correlated injected noise and partial device updates to balance between differential privacy and prediction accuracy with theoretical guarantees.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring. In Proc. of the International Conference on Machine Learning (ICML), 2012.
Sungjin Ahn, Babak Shahbaba, and Max Welling. Distributed Stochastic Gradient MCMC. In International Conference on Machine Learning (ICML), 2014.
Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms. In ICLR, arXiv:2010.05273,
2021.
Dmitrii Avdyukhin and Shiva Prasad Kasiviswanathan. Federated Learning under Arbitrary Com- munication Patterns. In Proc. of the International Conference on Machine Learning (ICML), 2021.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, volume 31, 2018.
Glenn W Brier et al. Verification of forecasts expressed in terms of probability. Monthly weather review, 78(1):1-3, 1950.
Zachary Charles and Jakub Konečný. On the Outsized Importance of Learning Rates in Local Update Methods. arXiv:2007.00888, 2020.
Changyou Chen, Nan Ding, and Lawrence Carin. On the Convergence of Stochastic Gradient MCMC Algorithms with High-order Integrators. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2278-2286, 2015.
Changyou Chen, Nan Ding, Chunyuan Li, Yizhe Zhang, and Lawrence Carin. Stochastic Gradient MCMC with Stale Gradients. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Hong-You Chen and Wei-Lun Chao. FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning. In International Conference on Learning Representatiioss (ICLR), 2021.
Mingzhe Chen, Zhaohui Yang, Walid Saad, Changchuan Yin, H Vincent Poor, and Shuguang Cui. A Joint Learning and Communications Framework for Federated Learning over Wireless Networks. IEEE Trans. Wireless Communications, 2020.
Tianqi Chen, Emily B. Fox, and Carlos Guestrin. Stochastic Gradient Hamiltonian Monte Carlo. In Proc. of the International Conference on Machine Learning (ICML), 2014.
Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael Jordan. Underdamped Langevin MCMC: A con-asymptotic analysis. In Conference on Learning Theory (COLT), pp. 300-323.
PMLR, 2018.
Arkabandhu Chowdhury and Chris Jermaine. Parallel and Distributed MCMC via Shepherding Distributions. In AISTAT, 2018.
Arnak S. Dalalyan. Further and Stronger Analogy Between Sampling and Optimization: Langevin Monte Carlo and Gradient Descent. In Conference on Learning Theory (COLT), June 2017.
Arnak S Dalalyan and Avetik Karagulyan. User-friendly Guarantees for the Langevin Monte Carlo with Inaccurate Gradient. Stochastic Processes and their Applications, 129(12):5278-53) 5311, 2019.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Mare' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large Scale Distributed Deep Networks, In Advances in neural information processing systems (NeurIPS), pp. 1223-1231, 2012.
Wei Deng, Qi Feng, Liyao Gao, Faming Liang, and Guang Lin. Non- Convex Learning via Replica Exchange Stochastic Gradient MCMC. In Proc. of the International Conference on Machine Learning (ICMI), 2020. 2020.
10

---

Under review as a conference paper at ICLR 2023
Alain Durmus and Éric Moulines, High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm. Bernouli, 25(4A):2854-25) 2882, 2019.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 51-60. IEEE, 2010.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 93-44)211-407,, 2014.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Mert Gürbüzbalaban, Xuefeng Gao, Yuanhan Hu, and Lingjiong Zhu. Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo. arXiv:2007.005900 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the Convergence of Local Descent Methods in Federated Learning. 2019.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. FL-NTK: Neural Tangent Kernel-based
Framework for Federated Learning Convergence Analysis. In International Conference Machine Learning (ICML), 2021.
Yangsibo Huang. Zhao Song, Danqi Chen, Kai Li, and Sanjeev Arora. TextHide: Tackling Data Privacy in Language Understanding Tasks. In EMNLP, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernl:: Convergence and Gener- alization in Neural Networks. In Advances neural information processing systems (NeurIPS), pp. 8571-8580, 2018.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sehastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic Controlled Averaging for Federated Learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In International Conference on Machine Learning (ICML), 2021.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First Analysis of Local GD on Heterogeneous Data. arXiv: (90::09995.59 2019.
Anastasia Koloskova, Sebastian U.Stich, and Martin Jaggi. Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication. In Proc. of the International Conference on Machine Learning (ICML), 2019.
Nikita Kotelevskii, Maxime Vono, Eric Moulines, and Alain Durmus. FedPop: A Bayesian Approach for Personalised Federated Learning. In Advances in neural information processing systems (NeurIPS), 2022.
Chunyuan Li, Changyou Chen, Yunchen Pu, Ricardo Henao, and Lawrence Carin. Communication- Efficient Stochastic Gradient MCMC for Neural Networks. Proc. of the National Conference on Artificial Intelligence (AAAI), 2019a.
Ruilin Li, Hongyuan Zha, and Molei Tao. Sqrt(d) dimension dependence of langevin monte carlo. In Proc. of the International Conference Learning Representation (ICLR), 2022.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated Learning: Challenges, Methods, and Future Directions. IEEE Signal Processing Magazine, 37(3):50- 60. 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Federated Optimization Heterogeneous Networks. In Proceedings of the 3rd MLSys Conference, 2020b.
11

---

Under review as a conference paper at ICLR 2023
Wenqi Li, Fausto Milletari, Daguang Xu, Nicola Ricke, Jonny Hancox, Wentao Zhu, Maximilian Baust, Yan Cheng, Sébastien Ourselin, M Jorge Cardoso, et al. Privacy-preservngg Federated Brain Tumour Segmentation. In International Workshop on Machine Learning in Medical Imaging, pp. 133-141. Springer, 2019b.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the Convergence of FedAvg Non-IID Data. In Proc. of the International Conference on Learning Representation (ICLR), 2020c.
Xiaoxiao Li, Yufeng Gu, Nicha Dvornek, Lawrence Staib, Pamela Ventola, and James $ Duncan. Multi-site fMRI Analysis using Privacy-preserving Federated Learning and Domain Adaptation: ABIDE Results. Medical Image Analysis, 2020d.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning Non-IID Features via Local Batch Normalization. In International Conference Learning Representations (ICLR), 2021.
Xuechen Li, Denny Wu, Lester Mackey, and Murat A. Erdogdu. Stochastic Runge-Kutte Accelerates Langevin Monte Carlo and Beyond. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7746-7758, 2019c.
Y.-A Ma, E. B. Fox, T. Chen, and L. Wu. Irreversible samplers from jump and continuous Markov processes. Stal. Compul., pp. 1-26, 2018.
Y.-A Ma, N. S. Chatterji, X. Cheng, N. Flammarion, P. L. Bartlett, and M. Jordan. Is there an analog of Nesterov acceleration for MCMC? Bernoulli, 27:1942-1992, 2021.
Yi-An Ma, Tianqi Chen, and Emily B. Fox. A Complete Recipe for Stochastic Gradient MCMC. In Neural Information Processing Systems (NeurIPS), 2015.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael I. Jordan. Sampling Can Be Faster Than Optimization. PNAS, 2019.
Oren Mangoubi and Nisheeth K. Vishnoi. Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing. In Proc. of Conference on Learning Theory (COLT), 2018.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcceent learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
H. McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated Learning of Deep Networks using Model Averaging. 2016.
Khaoula Mekkaoui, Diego Mesquita, Paul Blomstedt, and Samuel Kaski. Federated Stochastic Gradient Langevin Dynamics. In Proc. of the Conference Uncertainty in Artificial Intelligence (UAI), 2021.
S. Minsker, S. Srivastava, L. Lin, and D. B. Dunson. Scalable and Robust Bayesian Inference via the Median Posterior. In International Conference on Machine Learning (ICML), 2014.
Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm. Journal of Machine Learning Research (JMLR), 22:1-41, 2021.
W. Neiswanger, C. Wang, and E. Xing. Asymptotically Exact, Embarrassingly Parallel MCMC. 131 2013.
Y. Nesterov. Introductory Lectures on Convex Optimization, in: Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004.
R. Nishihara, I. Murray, and R. P. Adams. Parallel MCMC with Generalized Elliptical Slice Sampling. Journal of Machine Learning Research, 15(1):2087-2122 2014.
Reese Pathaky and Martin J. Wainwright. Fedsplit: An Algorithmic Framework for Fast Federated Optimization, 0585088, 2020.
12

---

Under review as a conference paper at ICLR 2023
Vincent Plassier, Alain Durmus, and Eric Moulines. Federated averaging langevin dynamics: Toward a unified theory and new algorithms. ArXiv e-prints 2211.00100v1, 2022.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex Learning via Stochastic Gradient Langevin Dynamics: Nonasymptotic Analysis. In Conference on Learning Theory, June 2017.
R. Shen and Y. T. Lee. The randomized midpoint method for log- eee-oncavee sampling. In Advances in Neural Information Processing Systems, pp. 2098-202200 2009, 2019.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving Deep Learning. In SIGSAC conference on computer and communications security (CCS). ACM, 2015.
Sebastian U. Stich. Local SGD Converges Fast and Communicates Little. arXiv: |0o::00005.9753 2019.
Yee Whye Teh, Alexandre Thiery, and Sebastian Vollmer. Consistency and Fluctuations for Stochastic Gradient Langevin Dynamics. Journal of Machine Learning Research, 17:1-33, 2016.
Sebastian J. Vollmer, Konstantinos C. Zygalakis, and Yee Whye Teh. Exploration of the (Non-) Asymptotic Bias and Variance of Stochastic Gradient Langevin Dynamics. Journal of Machine Learning Research, 17(159):1 48, 2016.
Maxime Vono, Vincent Plassier, Alain Durmus, Aymeric Dieuleveut, and Éric Moulines. QLSD: Quantísed Langevin Stochastic Dynamics for Bayesian Federated Learning. arXin:2066.007772 2021.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive Federated Learning in Resource Constrained Edge Computing Systems. IEEE Journal on Selected Areas in Communications, 37(6):200--122 2019.
Xiangyu Wang and David B. Dunson. Parallelizing MCMC via Weierstrass Sampler.
Yu- Xu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo. ICML, pp. 2493-2502, 2015.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3469, 2020.
Max Welling and Yee Whye Teh. Bayesian Learning via Stochastic Gradient Langevin Dynamics. In International Conference on Machine Learning, 2011.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs Local SGD for Heteroge- neous Distributed Learning. arXiv:2006. 04735, 2020.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning. In Proc. of Conference on Artificial Intelligence (AAAI), 2019.
Xu Zhang, Yinchuan Li, Wenpeng Li, Kaiyang Guo, and Yunfeng Shao. Personalized Federated Learning via Variational Bayesian Inference. In International Conference on Machine Learning (ICML), 2022.
Yuchen Zhang, Perey Liang, and Moses Charikar. Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. In Proc. of Conference on Learning Theory (COLT), pp. 1980-2022, 2017.
Wenbo Zheng, Lan Yan, Chao Gou, and Yue Wang. Federated meta-learning for fraudulent credit card detection. In Proceedings of the Twenty-inth International Joint Conference on Artificial Intelligence (IJCAI), 2020.
13

---

Under review as a conference paper at ICLR 2023
APPENDIX
Roadmap. In Section A, we layout the formulation of the algorithm, basic notations, and definitions. In Section B, we present the main convergence analysis for full device participation. We discuss the optimal number of local updates based on a fixed learning rate, the acceleration achieved by varying learning rates, and the privacy- -accrry trade-off through correlated noises. In Section C, we analyze the convergence of partial device participation through two device-sanee samppiig schemes. In Section D, provide lemmas to upper bound the contraction, discretization and divergence for proving the main convergence results. In Section E, we include supporting lemmas to prove results in the previous section. In Section F, we establish the initial condition. In Section G, we prove differential privacy guarantees. In Section H, we discuss the related work and literature. In Section I, we include additional experiments.
A PRELIMINARIES
A.1 BASIC NOTATIONS AND BACKGROUNDS
Let N denote the number of clients. Let T. denote the number of global steps to achieve the precision Let K denote the number of local steps. For each [N] (1, .N. use f and f denote the loss function and gradient of the function f in client c. Notably, f is not a standard gradient operator acting f when multiple local steps are adopted (K 1). For the stochastic
gradient oracle, we denote by V (-) the unbiased estimate of the exact gradient f of client In addition, we denote Pe as the weight of the c-th client such that Pa 2 0 and > Pe = 1. Eg is an
independent standard d-dimensional Gaussian vector at iteration k for each client [N] and & is unique Gaussian vector shared by all the clients.
Algorithm 2 Federated averaging Langevin dynamics algorithm (FA-LD). Denote by of the model parameter in the e-th client the k-th step. Denote the immediate result of one step SGLD update from 0% by 3 Eg is an independent standard d-dimensional Gaussian vector at iteration i for each client e E [N]. global synchronization is conducted every K steps. This is a transformed version of Algorithm I with p = 0 and full device participation for ease of analysis.
3 = 0g
(02) + / 2nT /PeSe:
(14)
if k + mod K + 0
(15)
Ee Pefie
if k + mod K = 0.
Inspired by Li et al. (2020c), we define two virtual sequences
Ba Σ POPS
O2 - ->-D
(16)
which are both inaccessible when & mod K of O. For the gradients and injected noise, we also define
N
N
N
ff((k) Σ (90)) F((02)
Σ
Pe (0)).
O:
0 &k Σ
VpoLt.
(17)
In what follows, is clear that EV ((0) = EN P. EV f(() for any 0 E Rd and any E [N]. Summing (14( from clients 1 to N and combining (16 and (1.() we have
Bx+1 = = - "/ v/ (())) + /
(18)
Moreover, we always have 3g = 02 whether & mod K 0 or not by Eq.(15) and Eq.(16). In what follows, we can write
0ct1= = 02 ((O.)) + /
(19)
which resembles the SGLD algorithm (Welling & Teh, 2011) except that the construction of stochastic gradients is different and 0g is not accesxible when l mod K + 0.
14

---

Under review as a conference paper at ICLR 2023
A.1.1 FEDERATED AVERAGING LANGEVIN DIFFUSION
To facilitate the analysis, we define the federated averaging Langevin diffusion for any E [M]
d = - ( + 2T D2//d,WW 220,
e
0:
it
where 0f is the continuous-time variable at time for client and 8f is the immediate result; W is d-dimensional Brownian motion and mutually independent for different e; and IID are two sets that follow Rzo = $ U D such that
s
V
E VI
of.
DD
{1l
1i
2
where Vi E IR+ denotes the synchronization frequency.
Starting from some > 0 and 6 >> 0 such that E S and +
Vi
1
va(
Vi
44
+1
+1))
we
have for any c [N]
2++
V (r) = 1. /2T/p.dW."
Bi+s
0g
We take the weighted average and obtain
B4s Σ Pa Oe 00- - Σ P S. V2rdW
where 3, = -E Pepf. 0, Em Pelli W a d-imensioon Brownian motion. Sending Vt + 0.
c=
the continuity implies that
0 0:N¹ =
N
N Σ P. p
P. (. (. Σ
c=1
Since the synchronization is conducted via Vt + in continuous time, we recover an auxiliary Langevin diffusion (0.) for any E S
d3, lim 3r 8-0
0 Vf + /2rdW,.
Moreover, always have 0, B, E Pep on both the set ID of measure 0 and set S. It equivalent to studying the standard Langevin diffusion (0.)220
dØ. (0.)dtt 22rdW..
(20)
which converges to the stationary distribution (0) x (ap(-f(00//) and f(0) = E (0)
A.2 ASSUMPTIONS AND DEFINITIONS
Assumption A.1 (Smoothness, restatement of Assumption 4.1). For each e E [N], we say f is L-smooth if for some L > 0
(0) S (x) + (Vf x) + + x12 Vz, y E Rd.
Note that the above assumption is equivalent to saying that
(V) - < Tlly x112, Va, y Rdd
15

---

Under review as a conference paper at ICLR 2023
Assumption A.2 (Strong convexity, restatement of Assumption 4.2). For each [N]. f is m-strongly convex if for some m
Vx, E R (x) (リ) + (V) v) 21 211
An alternative formulation for strong convexity is that
(v) Vf y) 2 || 2l Va, y E RR..
Assumption A.3 (Bounded variance, restatement of Assumption 4.3). For each e [N], the variance of noise in the stochastic gradient V (z) in each client is upper bounded such that
< odd, Var ER.
The bounded variance in the stochastic gradient is a rather standard assumption and has been widely used in Cheng al. (2018); Dalalyan & Karagulyan (2019); Li et al. (2020c). Extension of bounded variance unbounded cases such as V 5 E [0. 1) is quite straightforward and has been adopted in assumption A.4 stated in Raginsky et al. (2017). The proof framework remains the same.
v (>) < 8(L22² 2 B²) for some M and
Quality of non-i.i.d data Denote by 0₂ the global minimum of f. Next, we quantify the degree of the non-i.i.d data by ? == maxce]N] |/ (9(0))ll which is non-negative constant and yields smaller scale if the data is more evenly distributed.
Definition A.4.
We define parameter Te.p Hp. R. and 7?
Te, = T(p² + (1 pp2))/))))
r² m
Hp = D2
max Te,p m cE[N]
m&d data beterogeneity
initialization
injected noise
stochastic
K L/m,
22 = max
[ cE|N]
B FULL DEVICE PARTICIPATION
B.1 ONE-STEP UPDATE
Wasserstein distance define the Wasserstein distance between a pair of Borel probability measures i and on Rdd as follows
(/11.. Bul
W (2(,v))
inf TECouplins((a..))
where || ||2 denotes the lg norm on Rdd and the pair random variables (Sp, E Id x Id is coupling with the marginals following L(B,) μ and L(3r) = v. L(-) denotes a distribution of random variable.
The following result provides erucial contraction property based distributed clients with infre- quent synchronizations.
Lemma B.1 (Dominated contraction property, restatement of Lemma 4.4). Assume assumptions A. and A.2 hold. For any learning rate 7) E (0, (0,, any N Je=1 {3o)
E IRd, we have
|| 8 - < (1 mm) || 0112 4mL Σ Pe (11 3112 + 1 +112)
where 3 = EN Pof. = Mn p.O. v) = ΣN P. ( and Vf(3) = IN (B8
We postpone the proof into Section D.1. The above result implies that
16

---

Under review as a conference paper at ICLR 2023
long as the local parameters 0% and global 0, don't differ each other too much, guarantee the desired convergence.
The following result ensures bounded gap between 0 and 0 in &g norm for any 0 and E [N]. We postpone the proof of Lemma B.2 into Section D.2.
n. #1
Lemma B.2 (Discretization error). Assume assumptions I, A.2, and A.3 hold. For any 2 0, any learning rate (0, 2/m) and |00 0-112 S. dD² for any E [N]. the iterates of (0.) based on the continuous dynamics of (20) satisfy the following estimate
E
0
0 a1 11 2n/ dnLT + 161dT /pc.
The following result shows that given finite number of local steps K, the divergence between 6 in local client and in the center is bounded in & norm. Notably, since the non-differentiable Brownian motion leads lower order term (v)) instead of (1))) in e norm, naïve proof may lead to crude upper bound. We delay the proof of Lemma B.3 into Section D.3.
Lemma B.3 (Bounded divergence, restatement of Lemma 4.5), Assume assumptions A.I, A.2, and A.3 hold. For any learning rate 1) E (0, 2/m) and |00 0-12 S dD² for any c E [N], we have the l2 upper bound of the divergence between local clients and the center as follows
Σ P.E 0x112 S 112(K - 1)3 + 8(K 1)m + + (2)),,
where Hp, and x² are defined as Definition A.4.
The following presents a standard result for bounding the gap between V (0))) and ((()). We delay the proof of Lemma B.4 into Setion D.
Lemma B.4 (Bounded variance). Given assumption A.3, we have
(0) V 7(0))12 < d o², Y
Having all the preliminary results ready, now we present a crucial lemma for proving the convergence of all the algorithms.
Lemma B.5 (One step update, restatement of Lemma 4.6). Assume assumptions A. A.2, and A.3 hold. Consider Algorithm with independently injected noise p = O, any learning rate i (0, ZL dD² for any E [N), where O., is the global minimum for the function f. Then
and |10g 0. 112 <
(2 S (1-2) 1pm
(2 + 400m AT. Ho((H (1) +6),
where μt denotes the probability measure of Ho, K and 22 are defined as Definition A.4.
Proof. The solution the continuous-tima process (2.) follows that
0, = 00 / (f(Oddds+ 2 W.,
Vt 0.
(21)
Set + (A: + 1)n and d + ben for (21) and consider synchronous coupling such that W W(x+1)n Wkn = VTEE
(k+1)n
0(t+1m Oen
Vs(0.)ds + V - WEy)
Jkn
(1++13
= 0 km
(f(0)dds + / 2T
(22)
17

---

Under review as a conference paper at ICLR 2023
We first denote Ss= = f((x)))
f((x). Subtracting (q.(19) from Eq.( yields that
((r+1)n 0x+1
JKn f (k+1))
=0kn Ox 1/ f(0x)
(0,)ds
(k+1)n
=8kn 0% 17
f(tk +0km 0k. V f((h.)
Vf(0.) vf((en) )ds (23)
(k+1)n
Okn 0k vf(0k + Okn 0%) f((s))
V)((.)) vS(DEn) ds +rISk.
x
Taking square and expectation on both sides, we have
E1(0(++1)m 0x+1 12
El O2 ,xx Yu 2/2 +
EEl 11 2n B(Oan 02 xxx Yus Ck)
=C==0 and mutual independence
$ (1 + q) Bllōkn 0% x (1 1/9) B 1 121221133 11
$ (1 + 9) ((1 - -mm) E A,y 0x112 + 1n > Pe (E KkT, 112 El 0x112) )
+ +1+ 1/9) 1 + 772 odd
$ (1+
(1 mm) 0k 00113
(488)2(KK- 1 + 32((K - 1ynddeTN)
+ (1++1/)) E| + +
(24)
where the first inequality follows by the AM-GM inequality for any >> 0, the second inequality follows by Lemma B.1 and Assumption A.3. The third inequality follows by Lemma B.3 with p = 0: moreover, the continuous-ting process conducts synchronization at any time step, hence &k Aan-
Since the learning rate follows 1 I m+I and Lemma B.3 is clearly satisfied.
<
2, the requirement of the learning rate for Lemma B.1 n
Recall that ø rym, we get
1+
1 1 1mm. Choose q = 1+ so that (1 + +g9 (1+6)
2
2Φ
1 1m. In addition, have 1
1
lta
1+0
2 It follows that
I-
mm
1
2 mm
2
(1 4) (1 7m) < 1
2 nm,
1 + q
1.5, (1 - mn
(25)
1 mm
where the second inequality holds because E (0, 27. < 2m
For the term Y| in (24), we have the following estimate
(k+1))
E
Y&
E
Vf((.)) (7(0.)-Vf(8))) ds
km
(k+1)
< 17
Bl((f((.) V ((kn)) Lds
E
(M+1)m
< nL?
(2n2dkl + 16nd7 X ds
2n d. Ho 161) L2
(26)
where the first inequality follows by Hölder's inequality, the second inequality follows by Jensen's 's inequality, the third inequality follows by Assumption A. and the last inequality follows by Lemma B.2. The last equality holds since Lr & LmHHo and m.
18

---

Under review as a conference paper at ICLR 2023
Plugging (25) and (26 into (2.( have
E (1]0()+ Ok+ 112 S (1
)) Bl 02112
+ 672n) d(K - 11) Ho d8 1)LTN
TM + 12=02. + 4n mndLLHHo + 32n d I?
m
Choose the specific Langevin diffusion in stationary regime, we have W (1k π) = Ell0kn 02112 and W (1K+1, R) < El| 02+1 11 Arranging the terms, we have
(3 S (1 m
(2 T) + 400n/² dL HLLHoolKK 1)² + k))
where 17 I 27. K 2 1, mr & Lr & L & [ Tao & LmHo, and 0² S L Ho are
1
applied to the result.
B.2 CONVERGENCE VIA INDEPENDENT NOISES
Theorem B.6 (Restatement of Theorem 4.7). Assume assumptions A.1, A.2, and A.3 hold. Consider
Algorithm 2 with a fixed learning rate 1) (0, 1.J and ||08 0.11 S dD2 for any c [N], we have
3 k
(VZal + VT/m) + 30xv aml 1)² KK
W2(0n, T) S
where μt denotes the probability measure of O2. Ho. K and 72 are defined as Definition A.4. Proof. Iteratively applying Theorem B.5 and arranging terms, we have that
W2 (Mk, 7) S (1
7m k <
W2 (po, T)
1 - (1
17 y Mi Ho0 1)2 x)
(1 2
rm
W2 (No, T)
+ mm
400m² dL Hol(K - 1)2 + +10)
2
mm k
W (No, π)
800~>"mm((K 1))2 + H))
(27)
where K L. we have that
By Lemma F.1 and the initialization condition |00 00 s dD² for any [N]
m
W2(M4: x) S 2d + Vr/m).
Applying the inequality (1
S (1 1m
ccmpletees the proof.
Discussions
Optimal choice of K. To ensure the algorithm to achieve the precision based on the total number of steps T. and the learning rate we can set
(V((K-1) 112 H)
30m / 1pd
5
(v2d(D+ vT/m)
T. T.
5
This directly leads to
m
o
d (KK- 1)2 x)HH }
22
log (1) mn
m)m min
T. 2 Ω
21
dk
19

---

Under review as a conference paper at ICLR 2023
Plugging into the upper bound of 17, it implies that to reach the precision level c, it suffices to set
T =2 dx ((K
1)3 3 k) Ho log
(28)
2²
Since Hg Q(D2 ),,, we observe that the number of communication rounds around the order
T.
= 1 K
K
K
where the value of first decreases and then increases with respect to K, indicating that setting K either too large or too small may lead to high communication costs and hurt the performance. Ideally, K should be selected
scale of (KF)). Combining the definition of T. in (28, this suggests an interesting result that the optimal K' should be the order OVVT).. Similar results have been achieved by Stich (2019); Li et al. (2020c).
B.3 CONVERGENCE VIA VARYING LEARNING RATES
Theorem B.7 (Restatement of Theorem 4.8), Assume assumptions A.1, A.2, and A.3 hold. Consider Algorithm with an initialization satisfying |106 0.112 S dD² for any c E [N] and varying learning rate following
2T. + (1/12)mk Tik
== 1,2,
Then for any 2 0, we have
W2(px. < 45mv ((K 1)2 Ko (mmmd) 1/2
4k: 2 0,
Proof. We first denote
C₁ = 30 ((K 1)2 2 Ho
Next, we proceed to show the following inequality by the induction method
d
1/2
1.5C (nama) 1/2
W2(Mu, R) S 1.5Cx 2L + (1/12)mk
Ak 2 0,
(29)
where the decreasing learning rate follows that
2L + (1/12)mk
(i) For the case of k 0, since
C₂ 2 AVRV Ho 2 A
D2 + max Teo 2 4/n/d (VDD= + +1 cE[N]
max Tau m cE[N]
2 A//ddW2Ppp. T),
(30)
where the last inequality follows by Lemma F.I and |105 -0.112 < dD² for any c e [N].
It is clear that (2 T) < HC
md I. < 1.5C, mo by Eq.(30).
(ii) If now that (29) holds for some A: 0, it follows by Lemma B.5 that
W3 (px+1, S
m
w (2k, T7 + 400 Ho((K - 1)2 + k))
2
Tim2²
<
m
WW x)
Chd
2
2
<
m
2.250 mmmd +
Tmm
2.250%
2
3
< mmmm
2.2502yamd..
20

---

Under review as a conference paper at ICLR 2023
Since (1
Num 12
have
W2(H++1. S (1-
7hm,
1,50 (nemd)))m))) 1/22
12
To prove W2 (2( & 1.50, (TNCCn(T++mm00 (m=+1md)* 1/2
it suffices to show (1
Te 1/2
Mk
S 7h++1, which is
detailed as follows
mh
1/2
V12(24L + mk m)
1/4
12
(24L mk)33/2
VI2(24L + mk m) 1/2
24T. + mk:
12
(24L + m(k + 1)) 7k+1
where the last inequality follows since
(24L + mk m)(24L + mk + m)) S (24L + mk))
The above result implies that achieve the precision e, we require
md
1/2
W2(UR, x) S 1.5C, 2L + (1/12)mk
S.
The means that we only require ho -2( 4
achieve the precision c. By contrast, the fixed learning
rate requires T. = - log (d/c)) ) which is much slower than the algorithm with varying learning rate by Ollog (d/e)) times.
B.4 PRIVACY-ACCURACY TRADE-OF OFF VIA CORRELATED NOISES
Note that Algorithm 2 requires all the local clients to generate the independent noise Eg Such mechanism enjoys the convenience of the implementation and yields potential to protect the privacy of data and alleviates the security issue. However, the scale of noises maximized and inevitable slows down the convergence. For extensions, it can be naturally generalized to correlated noise based on hyperparameter, namely the correlation coefficient p between different clients. Replacing (q.( with
86-1 - 2 /2n((1 - p2)1-ppf
(31)
where & is d-dimensional standard Gaussian vector shared by all the clients at iteration k, E is unique d-dimensional Gaussian vector generated by client [N] only. Moreover, &N is dependent with Eg for any E [N]. Following the same synchronization step based Eq5(1 we have
Ok+1 02 1/ (((.)) /21TER
(32)
where & PEx + - EN
Lc=l VP Since the variance of i.i.d variables is additive, it is clear that EN follows the standard d-dimensional Gaussian distribution. The inclusion of the correlated noise implicitly reduces the temperature and naturally yields a trade-off between federation and accuracy. We refer to the algorithm with correlated noise as the hybrid Federated Averaging Langevin dynamics (gFA-LD) and present it in Algorithm 3.
Since the inclusion of correlated noise doesn't affect the formulation of Eq.( the algorithm property maintains the same except the scale of the temperature and federation are changed. Based on a target correlation coefficient p 2 0, Eq.(31) is equivalent to applying a temperature Te,p Tpp + p²)/pe). In particular, setting P 0 leads to Te,0 (1 -0²) /Pp which exactly recovers Algorithm 2; however, setting = leads to T.,1 = т. where the injected noise in local clients is reduced by 1/p. times. Now adjust the analysis follows
21

---

Under review as a conference paper at ICLR 2023
Theorem B.8 (Restatement of Theorem 4.9). Assume assumptions A.I, A.2. and A.3 hold. Con- sider Algorithm 3 with a correlation coefficient p E [0,1], a fixed learning rate dj E (0, 2L |166 - 0.11 I dD² for any [M, we have
and
W2(Me, x) - (1- x (vzalD VT/m)) 300k/mmm V((K- K)H
where Hi denotes the probability measure of On. Hp, and 72 are defined as Definition A.4.
Proof. The proof follows the same techniques as Theorem B.6 except that Ho is generalized to HP accommodate the changes of the injected noise. The details are omitted.
Algorithm 3 Hybrid federated averaging Langevin dynamics algorithm. Denote by 0g the model parameter in the e-th client the k-th step. Denote the immediate result of one step SGLD update from & by 36. Eg is an independent standard d-dimensional Gaussian vector at iteration is for each client [N] and & is d-dimensional standard Gaussian vector shared by all the clients. p denotes the correlation coefficient of the injected noises. A global synchronization is conducted every K steps. This is clean version of Algorithm based on full device updates for ease of analysis.
8h
0% f (6%) + 2 + v 2m(( 1 p²)T/poEk.
P8++1
if k: + 1 mod K + 0
0
0
Emm Po5k+1
if + 1 mod K = 0.
C PARTIAL DEVICE PARTICIPATION
Full device participation enjoys appealing convergence properties. However, it suffers from the straggler's effect in real-world applications, where the communication is limited by the slowest device. Partial device participation handles this issue by only allowing small portion of devices in each communication and greatly increased the communication efficiency in a federated network.
C.I UNBIASED SAMPLING SCHEMES
The first device-sampling scheme (Li et al., 2020b) selects a total of S devices. where the c-th device selected with probability Pe. The first theoretical justification for convex optimization has been proposed by Li et al. (2020c).
(Scheme I: with replacement). Assume S₃ = {m1, n2, ... .nn)) where n, E [N] is a random number that takes value of with a probability p. for any j f1.2.....55 S). The synchronization step follows that 0g = 3 Eces. 0%.
Another strategy is to uniformly select devices without replacement. We follow Li al. (2020c) and assume S indices are selected uniformly without replacement and the synchronization step is the same as before. In addition, the convergence also requires an additional assumption on balanced data (Li et al., 2020c).
(Scheme I:: without replacement). Assume Sş = (2 ... .ns). where n, E [N] is random number that takes a value of e with a probability & for any j E (1, ... S).. Assume
the data balanced such that P1 = = PN = $. The synchronization step follows that
0g- = E.es, Petf = Eees, 0% Lemma C.1 (Unbiased sampling scheme). For any mod K 0 based scheme or II, we have
E0g
E Σ
0 3
Po
CES,
22

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Hybrid federated averaging Langevin dynamics algorithm with partial device partici- pation. &% is the independent Gaussian vector proposed by each client E [N] and & is unique Gaussian vector shared by all the clients. denotes the correlation coefficient. A global synchroniza- tion is conducted every K steps. Sy, is subset that contains S indices according device-sampling rule based on scheme or II. This is a clean version of Algorithm for ease of analysis.
8h+1 0g ( + 22TTp" 22 /2)T/
l: + mod + 0
xx =
Ecesen
1 SP8+1
if k + 1 mod K = 0.
Proof. According to the definition of scheme or II, we have 02 = Eces, 0g. In what follows,
E0, & LE 0g 3/8 Ennes Ee-IPoBE PoBl De Polf, where pı p2 PN for scheme il in particular.
C.2 BOUNDED DIVERGENCE BASED PARTIAL DEVICE
Lemma C.2 (Bounded divergence based on partial device). Assume assumptions A.1, A.2, and A.3 hold. Consider Algorithm 4 with a correlation coefficient E [0, 1]. any learning rate E (0, m/) and ||06 11 S dD² for any [N), we have the following results
For Scheme I. the divergence between 03 and Bk upper bounded by
8 112 K3 k2, Kndd( + N(1 -²))--
ElIA 0x112 < 5
For Scheme II, assuming the data is balanced such that P1 = =.. PN 0g and 3% is upper bounded by
1 Ni the divergence between
El 0u113
N S(N 11)
(122K 8K + N(1 - -(21)
where H and x are defined as Definition A.4.
Proof. We prove the bounded divergence for the two schemes, respectively.
For scheme with replacement, 0s = Eees, 3 for subset of indices Sg. Taking expectation
with respect to Sk, we have
N
1
0 :3.112
Bl Bell2
1 8& 11
(33)
52
S
where the first equality follows by the independence and unbiasedness of 6hh for any i [S].
To further upper bound E33(33,, we follow the same technique as in Lemma B.3. Since & mod = O.
kn k K is also the communication time, which yields the same 0%, for any e [N]. in what
follows,
N
N
Pe |13
Ball2
=
| - 0%h - (8x 0k.
c=1
<
Pe |1 8k 11.
(34)
1
23

---

Under review as a conference paper at ICLR 2023
where the last inequality follows by Bk Ee= PePk and E|| Er12 B| Combining E33( and Eq.(34), we have
N
E110
Bx 2
Pe
1
0kk 12
5
N
|1
-0% 11
Pe
8 c0
1 N
h-1
2K (F 1 4KKdd (
E
Σ
+(1 - p²)/pc)
8
k=ko
N
k-1
V (0)) | AKKdT(pp + (1 - p²) p²)/pc)
Σ
Pe
Σ
2Kn
8
28
$ s
k2n + 3
Kidd + N(1 p²))
where the last inequality follows similar argument in Lemma B.3.
For scheme II, given P1 = P2 PN
N. we have 02 = 1/2 Eces, 8g. which leads to
N
2
1
Bl - Bx112 = E
3
B6
IcESs - Bkb)
S
S2
CES,
2
where T is an indicator function that equals to if the event happens.
Plugging the facts that PPcc E Sy)) the above equation, we have
s N
and P(c1, E Sx)
S(S-1) N(N-I) for any # 02 E [N] into
E 0
1x
Σ
P(cE St) 113 - Bull2+ + Σ
P(c Sk)(B BB. 28 -Ba)
S
CE[N]
1 SN
10g -xx111
+ Σ
S 1
(300 - Bk, 88 BBa)
SN(N - 1)
01
1
S
N
N
1 3e1l2
S(N 1) 1)
where the last equality holds since EcE(M] 11 Ball2 + Eoitos (86) BK, -Ba) ||3 Bx = 0.
Eventually, we have
N S S
N
E 0 Ball2
S(N - 1) F
| Bxl12
N
N S
N
<
|| - 0h012
S(N - 1)
N
N - S
28K 2T. + 4Kndr (0² + N(1 - -11))
S(N 11)
where the first inequality follows similar argument as in (34) and the last inequality follows by Lemma B.3.
24

---

Under review as a conference paper at ICLR 2023
C.3 CONVERGENCE VIA PARTIAL DEVICE PARTICIPATION
Theorem C.3 (Restatement of Theorem 4.10). Assume assumptions A.I. A.2, and A.3 hold. Con- sider Algorithm 4 with correlation coefficient p E [0, 1}, a fixed learning rute 1] E (0, 2L and
|10 - 0.112 S dDd for any E [N], we have
W2(HK, x) & 4 & (vza(D + vT/m)
Cxdt
+ 30k /ii//mmmd... v Hp((K 1)2 n2) + +21
(p² + +N1(1 -
Sm
where Cк
Cs = for Scheme I and Cs = N for Scheme II.
mnk
1-
Proof. Note that
E (k+11 - 01-1112
[1(0(++11 - 3x+1 + Bk+1 0k+1 l12
(B10(u+1)n - 3x+1 1- + B111 0x+1 11 E2 (2(0 3x41, - 0k+1)
=B10(++1)m - 9x+1 - Ell 0x+1112.
where the last equality follows by the unbiasedness of the device- scheme in Lemma C.I.
0u+1ll O. Following the same argument as in Lemma B.5, both schemes lead to the one-step iterate as follows
If lfk+1 mod K of O, we always have 34+1 0k+1 and B|| 1
(2 S 1)mm
W2 T) + 400s/² dt, HT,2H, 1)² k))
(35)
2
If + mod combining Lemma C.2 and Lemma B.5, we have
am 2 W2 m) + 250 + k) + 4KdmT
(2 S (1
(0² + N(1 - C)))ss
S
(36)
where Cs for Scheme and Cs N-1 for Scheme II.
Repeatedly applying (35) and (36) and arranging terms, have that
1 & 2
(3 πT) 1
W3 (4O: x) + Tpm
450r Hp + +n))
(1 (1
mmm K KKLK/K]
(AKdar (0² + N(1 13))Cs
2n) )K
mmm
W (MO, ④) + 900mmdn' 2o00mdx>HHol( Ho[(K - 1)) + k)
mmK
4Kd
(0² + +N(++11112 ( mMK
Cx
mm
W T) 9000mdn Ho((K - 1)2 + K)
2
4C dt
(0² + N(1 - ->)))sss
Sm
where the second inequality follows by (1 - r) < r for any 2 0.
25

---

Under review as a conference paper at ICLR 2023
D BOUNDING CONTRACTION, DISCRETIZATION, AND DIVERGENCE
D.I DOMINATED CONTRACTION PROPERTY
Proof of Lemma B.1 Given client index E [NT] applying Theorem 2.1.12 (Nesterov, 2004) leads
to
mL + m
(y x, -r-v-/---VV
1y x:12 + 4+m. m
Va,, y E RR.
(37)
In what follows, we have
|| 0 - -
- 012 1 2n (8 0,V V (()) +>) IV/(3) //0)
(38)
For the second item in the right hand side, we have
N
Σ
Pc - -
N
Po(B 8 + 00 00 -, - V
1=1
N
((8- 8, 8. - V)((8)) (0 00, -
c=1
(B 8 VB) (f))
Pe ((m + L) 11 - -111 (m L)) 110c -11
/V (19))))
2(m + L)
N
mb
+
Σ
Pe
1110-8093 +
[V)((E)) V (((
L + m
L + m
c=1
2 - (m (m
+ L)
Pe (113c- - 1001-~112++ 1 - 01
+ mL
|| -111
L +
1=1
VS(3) ((0))
(39)
2(L m)
where the first inequality follows by the AM-GM inequality and Eq.(37), respectively; the last inequality follows by Jensen's inequality such that
N
N
Pel g
8013
Σ
(g
80) = 1| 01
( VF )( = -V/(()) -V/(0)))
Po (
Σ Pe
V
26

---

Under review as a conference paper at ICLR 2023
Plugging (39) into Eq.(38), have
|| - 8 - -7 (Vf(3) - f(
$ (1 21mmL.
m + |13 0|12 + n 1 m +
-
soing mtz
N
+ (m + L)
Σ
Pe (118 - B112 + 1100 -
c=1
$ (1 mm) ||B 0112 + 4nL Σ Pe (115 - -112 + -100 0112)
where the last inequality follows by m-L 2 1, m 1 L, 1 - 2a S (1 - a)²
21
for any a, and
" E (0, mir)
D.2 DISCRETIZATION ERROR
Proof of Lemma B.2. In the continuous-time diffusion (20), the synchronization is conducted in infinitesimal time Vi. - 0. It follows that ( = Pe for any 0 RRd and it is straightforward to verify that I satisfies both Assumption A.1 and A.2 with the same smoothness factor and convexity constant m when Vt
(it does not hold for federated settings with
non-trivial synchronization frequency, ie. Vt > 0).
For any 8 E [0, x)), there exists certain & N+ such that E [K77, (k + 1)1). By the continuous dynamics of (2.() we have
(f, + 2 lpt l dW,
8. 8 1
kon
kn
which suggests that
|10, 10.-0 12tll s 11 /
1 kn
2T Lo dw, 22
sup (E(
sup sE(Kon 1)n)
2
We first square the terms both sides and take Young's inequality and expectation
/ (B))
1. kon
E
sup BE (k+ 1)m)
||o, 1,,;,,11222 S 21E
+ 2E
sup
kmn
2
se (R++ 1)m)
Then, by Cauchy Schwarz inequality and the fact that Is knl S we have
E sup (k+1g))
100 0 s 2n
|
fl 0, dtt [a +
Σ
E 27 1p.dt
kn
1=1
Jnn
2nj² sup E. V (0.) 1|
16nd7
Ipce
(40)
where the last inequality follows by Borkholder-Davis-Guune inequality (50) and Itô isometry.
By Young's 's inequality, the smoothness assumption A.1 and (f.))) = when Vt - 0, we have
sup BlP sup E V (0.) V ff
L sup 0.11
1 2 dr
(41)
27

---

Under review as a conference paper at ICLR 2023
where the second inequality follows by Theorem 17 (Cheng al., 2018) since 8g is simulated from the stationary distribution π and 8, is stationary. Combining (40) and Eq.(41), we have
E
sup sc (k+1,)))))))
10 1 2n kLdr 16ndT Spc.
D.3 BOUNDED DIVERGENCE
Proof of Lemma B.3. For any k 2 0, consider ko- = -K such that k < ku and 6% = 0kg for any k 2 is clear that k ku S K 1 for all k 2 Consider the non-increasing learning rate such that T/K I 21I; for all k ko S K 1.
By the iterate (19( we have
9xll2
N
16 tk. - (0x 1k,))1
1. - 0kul1
Σ E.
2(K 1)ni V (02) (89 ||- 4(K 1)m + (1-1p)) p²)/pc) Σ
À=ko
N
h-1
Σ 2(K 1) v (82)
2 | + +4(K - 1)M,, + (1 - (000-22)/pp p²)/
Pe
2
c=1
k=
S 112(K - 1)² 2 dT. Hp + 8(K d) (p² N(1 - -}))
where the first inequality holds by B110 BØll < 10100 for stochastic variable 0; the second inequality follows by (EKT a,)² < (K 1) > a;: and ni < 4np Ho is defined in Definition A.4.
K- the last inequality follows by Lemma E.2
D.4 BOUNDED VARIANCE
Proof of Lemma B.4. By assumption A.3, we have
N
v f
E
Σ
Pe
-
-
N
Σ
(F)
Vj((BC) |
1=
N
N 2
< do 2
p < 2
Σ
Pe
= do?.
[=]
28

---

Under review as a conference paper at ICLR 2023
E UNIFORM UPPER BOUND
E.1 DISCRETE DYNAMICS
Lemma E.1 (Discrete dynamics). Assume assumptions A.I, A.2, and A.3 hold. We consider the generalized formulation in Algorithm 3 with the temperature
To -(p² (1-p2)/pe)
given a correlation coefficient For any learning rate E (0, 2/m) and |0g E [N), we have the E2 norm upper bound as follows
0.112 S dD² for any
6d
+ a²
72
sup 1 0-12 S dD²
max CE[N]
Te.p
md
m
m
where y [ V (0.))ll) and 0. denotes the global minimum, for the function f.
Proof. First, consider the k-th iteration, where E (1,2.
(K 1)-3 and (K 1)
denotes the (K - stsp before synchronization. Following the iterate of Eq. (14) in local client of c E [IV] we have
B|| 10%+ 0- 11
= El0g 0. - V (8E)) B 0. - (()))(())) Ex) + ElIxx,E
Ell0E 0. - 2rddTa..
(42)
where the last equality follows from Efg- and the conditional independence of 02 - 0. - (O( and Ek. Note that
0 - - (
0 0- -VVV (0) (0
+ 27/EEE - 0. 77 (f)). (0)) - (F((
0g 0- - 7 (0)) (
0. -' no
(43)
where the first step follows from simple algebra, the second step follows from the unbiasedness of the stochastic gradient. and the last step follows from Assumption A.3. For any q >> we can upper bound the first term of (43) as follows
Elle 8, f (05)
= =E 0, f (0C) (O.)) - (
< (1 + E - 0, - (VF v) + [ (1+2) (VF
$ (1 (1+9)) q)
1
17m 2
0 0.112 + n² [+ (1+1) x2
(44)
2
where the first inequality follows by the AM-GM inequality; the second inequality special case of Lemma B.I based on Assumption A.2, where no local steps is involved before the syn- chronization step. Similar results have been achieved in Theorem 3 (Dalalyan, 2017). In addition,
maxxe[N] | (0-))l))
Choose q ( j² so that (1 + g)1p2 (1+1)²
Moreover, since v 1 - mm
2
we get
1+ 1m.. In addition, we have +
149
(1+w)²
It follows that S mm
2
(I-VX1+30)
1
2n
2
(45)
m
29

---

Under review as a conference paper at ICLR 2023
Combining Eq.( (4.) (44), and (4., have the following iterate
E 0 k+1 0.112 <
mm [1
B
0.112 2nddTa.p no² 2ny²
4
m
= (()
Note that 1-9(r) = (1 mny S given E (0, =) Recursively applying the above equation
times, where l E 21.2.... K K- and K_ denotes the K-step without synchronization, follows that
0 0.112 S 061)*1165 0.112
1 9-((1)*
(2ndTT + 17
207 (46)
g(n)
m
$ 1106 - 0.113 +
3
(2ndTa. c.p + 1/ddo?
2mp²
17m.
m
S dD2 + 6d
0²
2
max cE[N]
Te,p
m
md
where the second inequality holds by g(7) I 1, the third inequality holds because |10| 0.112
- dD²
for any c E [AV] and < 2. In particular, the K-th step before synchromization yields that
Bll0k_ 11 < dD² +U.
(47)
Having all the results ready, for the K-local step after synchronization, applying Jensen's 's inequality
N
E110% - 0011 = E
Σ
Poff - 0x
N
<
B. 0
1x112
c=1
< d
+U,
(48)
Now starting from iteration K, we adapt the recursion of E4, for the k-th step, where k E {K + 1, 2K 1, ( and (2K)- denotes the 2t-step without synchronization, have
El10g - 0-112
* K, 1 0.112 + 1 -
2nd max Te,p + 172 2077 cE[N]
1 9(1)
m
Sg(1)* - K (NDD2 + +U) 1 1-((n)) KK mm U
mn/3 3
<dD2 + (1 k
-KU
<dD² +U,
(49)
where the second inequality follows by Eq.)4 the fact that - g(n) 2 mm/33 and r7 S 2, definition of U. The third one holds since g(n) S 1.
m. and the
By repeating (48) and (49), we have that for all 2 0, we can obtain the desired uniform upper bound.
Discussions: Since the above result is independent of the learning rate 77, it can be naturally applied to the setting with decreasing learning rates. The details are omitted.
30

---

Under review as a conference paper at ICLR 2023
E.2 BOUNDED GRADIENT
Lemma E.2 (Bounded gradient in E2 norm). Given assumptions A.I, A.2, and A.3 hold, for any
client e and any learning rate 1) E (0, 2/m) and 110g 0-11 - dD² for any c E [N], we have the E norm upper bound as follows
/ & 14d1. Hpr
where H. DD2 + m To. . m
Proof. Decompose the &g of the gradient follows
(09) || = (0)) V
(7 - v/((2)
+ + ((()))
S < 0²d
= V - + (f o²d
- (0)) - V 2E ( + o²d
< 2112B 0 2y² + ozd
12dL2 2dT.2D2 +
a²
72
max T
+
+
+222 o2d
m
cE[N]
m
md
?
a²
S 14dL?.
D2
max Te,p +
m == 14dL Hp:
m cE[N]
m²d
where the first inequality follows by Assumption A.3; the second inequality follows by Young's inequality; the third inequality follows by Assumption A.1 and the definition that y max.c [N] (V=) the fourth inequality follows by Lemma E.1; the last inequality follows
by
L 2 1.
F INITIAL CONDITION
Lemma F.1 (Initial condition). Let μi denote the Dirac delta distribution at Og. Then, have
W2(uo, +) < V2([ - 0-112 + v dr/m).
Proof. By Cheng et al. (2018), there exists an optimal coupling between pi and i such that
W3 (Mo, m) < a 110 - -1131
- 2E [1100 0.112] + 2E m. |||0 0x
= 20 0-13 + 2. 1110 0-132
< 2 00
0. 1 + 2dT/m,
where the second step follows from triangle inequality, the last step follows from Lemma 12 (Durmus Moulines, 2019) and the temperature 7 is included to adapt to the time scaling.
Burkholder- Barkholder-DDvis-Gunnde Davis-Gundy inequality Let Φ [0, 00) + R for some positive integers and In addition, we assume E [ 2ds < oo and let Z()) So (s)dW,, where W, is a d-dimensional
Brownian motion. Then for all 2 0, we have
sup [Z(s) 05e5t
< 4E Ps.
(50)
31

---

Under review as a conference paper at ICLR 2023
G MORE ON DIFFERENTIAL PRIVACY GUARANTEES
We make the following assumptions for the analysis of DP.
Assumption G.1 (Bounded fz-sensitivity). The gradient of loss function 1 Rd x X + R, (0,x) +
x)) w.r. has uniformly bounded Ez-sensitivity for v0 R
A sup sup [V((0;=) VI(0; ll2 < ock I
(51)
For example, when ((0:-) is M-Lipschitz for any 0 E RR A S 2M. Following the tradition of DP guarantees, we assume that the unbiased gradient is computed as follows.
Assumption G.2 (Unbiased gradient estimates), The unbiased estimate of (0) calculated using subset (denoted by 8*) of { sampled uniformly random from all the subsets of size My of Ne.a)=n
vf
1 _
Σ vi(0;ze.))
(52)
YPc iES
Theorem G.3. Assume assumptions G.I and G.2 holds. For any 60 E (0, if (0, =(1-p²)>? min.ein) then Algorithm is (,,,T (33) diffeerrneey d 5/1og(1 1og(11255600 25/66)
private w.r.t. ~ after
executed for T (T EK with E EEN,EE E iterations where
(3) K.T TK min {
2T (V
T( - 1) T
log
+
K
62
K
K
(33
T 8x + 62.
K.T K
with
log 1 1 - (1- (1) (exx-)))
under scheme 1,
ēK
log
(1 n (E ( 1)) under scheme II,
Σ (s) (1) (
S-8 8k.s: under scheme I, (K + +1), under scheme 11, N
(1 ---
8x
5
8K.6 = (eex 1) 6KKK0 eex/s -
1/5²
80
kK 1.25Kg
+ 81,
1.25
eK E min
1/2 2K log(1/81) + K(Eei - 1), K
17 1log(1.25/5m) 255/o))
===2. =222
7(1 p²) min NN] Pe
and 81, 82 |0, 1).
Proof. Let De := (xe.) denote the dataset of the e-th client for e E [N]. Let Uce[N] Da denote the whole dataset.
As FedAvg algorithms can be divided into the processes of local updates, synchronization, and broadcasting with risks of information leakage in synchronization (local model uploading and aggregation) and broadcasting, we consider the differential privacy guarantees in synchronization and broadcasting similar to Wei al. (2020). Since there is no involvement of data in model aggregation and broadcasting, they are proc-proc processes. Thus, it suffices to analyze the differential privacy guarantees in local model uploading.
32

---

Under review as a conference paper at ICLR 2023
For any two datasets D 2 D', there exists [M] such that De = D' and De D for any E [N]
Consider the function m 0
- - 0- I
"Po E (1) with S ym (|A)
denotes the cardinality of set A). By Assumption G.I, for any 0 E Rdd the sensitivity of (D 0) is
A., = sup [Imc(S;;)) (S
" A Pe
(53)
S.
For the mechanism Mc(S;0) == m):)s V 2nrppg+ + 22 /T)/T with and being two independent standard d-dimensional Gaussian vector, since & broadcasted all the clients, can be treated as some known constant which does not contribute to the differential privacy. Thus, the standard deviation of the added Gaussian noise is 22/T(1 - p²)/pe at each dimension. Then, according to the Gaussian mechanism Dwork al. (2014), Me(Da; 0) (co,e, dnffdifferentially private for any 8 IRd with
60,c c(0o)
A V 2p (1 -1- p2)' d(o) 2 (.225/0))))) E (0, 1).
"
(54)
For S sampled uniformly at random from all the subsets of size yn, of Des define M, (Dxi = Mc(S;;) 0). Then, according to Theorem 9 in Balle et al. (2018), Mo is (log (1 + 7(e00 - 1)) 700)-
differentially private. Notice that for any c0.c E 10 (i.e., S n S 2p. (1-1""²)" ) we have
Afc(00]
0 < 50.- -1 1 I 250.e and
21 por(1- -p2) =: G1
log (1 + ( 1)) S log (1 2yco,e) S 2yco, c660)4r
(55)
Define
2n
1 1log(1.22 1.25/80)
6 :- c(60)
T(1 - p2) min Pe -24 25/1 r(1 p²) minee(N) Pe
(56)
Then, we have maXce[N] 61.0 = 61 and maxce[N] CD.o E 10,
2r - p²²)² min 7(1 - م² min Pe 05
(57)
A7c(50)2
A7 (og((.25/8))
m Pe Mc(D::)) is (E1, A (0g(1)25/66)
Thus, for 0 S <
private for any
I E R. From now on, assume that 57 holds.
Define M (Da; to be the K-fold composition of Me(DD:)) According to the composition rules of (c, diffferrrtlt privacy (Theorem 3.1 and 3.3 in Dwork et al. (2010)), M. (Da:0) is (cK, 5g) -differentially private with
= min { [22 log(1/61)s + Kei(en 1), Kei)
(58)
6x = Kyd0 + 81.
(59)
for any E [0, 1).
By 56, if
log² 7(1 1²) min Pe 2A/c(50)2
(1 (1+1
log((1 (1/81)
0 OsnS
(60)
K
we have el E 0, 1+
1/51) K
which implies that Kei 1) 2K 1og(1//1)e
and
< < 2 22/2Kllg log(1/8))es
(61)
33

---

Under review as a conference paper at ICLR 2023
In the synchronization process, S clients selected via device-sampling scheme or II send their local models to the center. Thus, for scheme (with replacement) and scheme II (without replacement), according Theorem 10 and Theorem in Balle et al. (2018) respectively, each synchronization process is (EK: 8x -differenttilly private with
Tx {
log [1 + (1- (1- x))) [e - 1)) under scheme I,
(62)
log (1 + (e< - 1)) under scheme II.
Σs
N (1- )) 5 ōk.. under scheme I,
8x
(63)
5 N
(K 70u + +6))
under scheme II.
N
where
du 1/6²
(e - 1) 1)0K,au òK,=
6K,3,0 1.25K>
+ 81.
eck/s
1.25
The aggregation and broadcasting process is post-processing and preserves the guarantees of dif- ferential privacy (Proposition 2. in Dwork et al. (2014)). When executed T iterations, Algorithm 1 is the T/K-fold composition of local updates, synchronization, and broadcasting. According to the composition rules of (e, diffferrrrtt privacy (Theorem 3.1 and 3.3 in Dwork et al. (2010)),
g(3) Algorithm is (e K, K,T) ).T)) J-differentially private after iterations with
T K
T _
K,
(3)
min {V
2 K
log(1/62)Ex + FE
-1),
K
(64)
T
8 KT
5x + 82.
(65)
for 81,82 E 1) and 60 (0, 1). Notice that under scheme II, exx
8 N(e 1), thus,
K.T = ēx min V 2 log(1 (1/52) + TS
KN (e - 1), K and (3) 8
K.T N 7
81 + 82. + KN
TS
Discussion on the differential privacy guarantees of Algorithm under scheme II By 58, 59, 62, 63, 64, and 65, by letting 81, 62 O, we have that Algorithm least $ ( log (1 N (eeKe - 1)), N --TTo)--iiffreentillly private.
S
2K log 1/62)
Ēk 5 log 1+
(66)
T
have Fex(E²K - V 2 (gg(1/52)Ex and therefore
(3) K.T
T S 2/22 log(1 = -2
T
(1+ [(((((xx))
(67)
Now assume satisfies 60, then by 61 and 67,
(eV22
KTT I 2/22 1og(1/52)log log + N
(68)
K
Notice that if
log
1 5
2K log(1/62)
7(1 p²) min Pe
2 2ogg(11/5 (1/8)
0 < 17
min log2
1+
2A7c(6))2
K
8K log 1/61)
(69)
34

---

Under review as a conference paper at ICLR 2023
by 56, 61, 62, and 63, we have
1 + 5 2k (1/()
log
E1 S
(70)
2 2K 2
log(1/6)) (1/0))
N
2K log(1/5g)
ek S 2K (og(1/61)er S log
1+
(71)
S
T
2K log(L/òg)
Tx s log 1+
(72)
T
Thus, we have 68 holds. Plugging 56 into 68, we have
2 2 T K.T
S
n log(1/5))
1)
1
(3)
log(1/5g log 1 N
exp
4c(6))=11 7(1 p²) minoelN] Pe:
K
(73)
For any K 1, if kk
<<
and T >>>> using log(1 + x) = and e² when |x| <
can write 69 as
T(1 - -22) min |M Pe log(1//2)
05 =0
(74)
A75 log
and 73 as
SA
rTT (1)m)) log( 1/6, log 1/62)
(3) K.T
0
(75)
N
r(1 0²) minee(N] Po.
H RELATED WORK
Federated Learning Current federated learning follows two paradigms. The first paradigm asks every client to learn the model using private data and communicate in model parameters. The second one uses encryption techniques to guarantee secure communication between clients. In this paper, we focus on the first paradigms Dean al. (2012); Shokri & Shmatikov (2015); McMahan al. (2016; 2017); Huang et al. (2021). There is long list of works showing provable convergence algorithm for FedAvg types of algorithms in the field of optimization Li et al. (2020c; 2021); Huang al. (2021); Khaled et al. (2019); Yu et al. (2019); Wang et al. (2019); Karimiredyy et al. (2020). One line of research Li et al. (2020c); Khaled et al. (2019); Yu et (2019); Wang et al. (2019); Karimireddy et al. (2020) focuses standard assumptions in optimization (such as, convex. smooth, strongly- convex, bounded gradient). The other line of work et al. (2021); Huang et al. (2021) proves the convergence in the regime where the model of interest is an over-parameterized neural network (also called NTK regime Jacot et al. (2018)). Extensions to general partial device participation, and arbitrary communication schemes have been well addressed in Avdyukhin & Kasiviswanathan (2021); Haddadpour & Mahdavi (2019).
Scalable Monte Carlo methods SGLD Welling & Teh (2011) is the first stochastic gradient Monte Carlo method that tackles the scalability issue in big data problems. Ever since, variants of stochastic gradient Monte Carlo methods were proposed to accelerate the simulations by utilizing more general Markov dynamics Ma et al. (2015; 2018); Chen et al. (2014), Hessian approximation Ahn et al. (2012), parallel tempering Deng et al. (2020), as well as higher-order numerical schemes Chen et al. (2015); Li et al. (2019c); Cheng et al. (2018); Ma et al. (2021); Mou et al. (2021); Shen & Lee (2019).
Distributed Monte Carlo methods Sub-posterior aggregation was initially proposed in Neiswanger et al. (2013); Wang & Dunson; Minsker et al. (2014) to accelerate MCMC methods to cope with large datasets. Other parallel MCMC algorithms Nishihara et al. (2014); Ahn et al. (2014); Chen et al. (2016): Chowdhury & Jermaine 22018); Li et al. (2019a) propose to improve the efficiency of Monte Carlo computation in distributed or asynchronous systems. Gürbüizalabaa et al. (2021) proposed stochastic gradient Monte Carlo methods in decentralized systems. Al- et al. 1); Mckkaoui et al. (2021); Chen Chao (2021) introduced empirical studies of posterior averaging in federated learning.
35

---

Under review as a conference paper at ICLR 2023
A Concurrent Work Parallel to work, QLSD Vono et al. (2021) also studied the convergence of SGLD in federated settings and a compression operator was proposed to alleviate the communication overhead. By contrast, follow the tradition in the FL community and achieve this target by solely conducting multiple local steps to balance accuracy and communication. Other interesting Bayesian federated learning algorithms can be found in Kotelevski et al. (2022); Zhang et al. (2022). Our averaging scheme is deterministic and may be limited when activating all the devices is costly; we also refer interested readers to the study of federated averaging Langevin dynamics based probabilistic averaging scheme in Plassier et al. (2022).
1 SIMULATIONS
Experimental details We repeat each experiment R 300 times. At the k-th communication
round, we obtain set of R simulated parameters {0k. 1 1- where fx. denotes the parameter the k-th round in the j-th independent run. The underlying distribution (4 round k is approximated by Gaussian variable with the empirical mean ui Er= Ok.j and covariance matrix Eg
R Ej=1(0n.)) (Ok. (0k, ux)
Wensmmes 2011
Gren aiciiiiiiinn
Conmunciios maide
Conmusiiiias madie
(a) Full devices: m 50 (b) Scheme T: m 40
(c) Scheme TI: S 40
(d) Scheme S m 30
(c) Scheme II: S 30
Figure 3: Convergence of FA-LD based on different device-sampling schemes.
Partial device participation We study the convergence of two popular device-sampling schemes I and II. We fix the number of local steps K = 100 and the total devices N = 50. We try to sample S devices based different fixed learning rates 17. The full device updates are also presented for fair evaluation. As shown in Figure 3(a), larger learning rates converge faster but lead to larger biases; small learning rates, by contrast, yield diminishing biases consistently, where is in accordance with Theorem 4.7. However, in partial device scenarios, the bias becomes much less dependent on the learning rate in the long run. We observe in Figure 3(b), Figure 3(c), Figure 3(d), and Figure 3(e) that the bias caused by partial devices becomes dominant as we decrease the number of partial devices S for both schemes. Unfortunately, such a phenomenon still exists even when the algorithms converge. which suggests that the proposed partial device updates may be only appropriate for the early period of the training or simulation tasks with low accuracy demand.
J EXPERIMENTS ON THE MNIST AND FASHION DATASET
Experimental details For both the MNIST and Fashion-MNIS. dataset, the temperature 7 is set to be 0.05. We split the training dataset of size 60000 into 10 non-overlapping subsets uniformly at random for 10 clients. During the training, the stochastic gradient of the energy function at cach step is calculated with batch size of 200 for each client.
Warmup period To better observe the convergence under different local steps K with the existence of warmup period, we use warmup period of 500 communication rounds for different local steps K = 1, 10, 20, 50, 100. Specifically, in each setting, after the first 500 communication rounds, we collect one parameter sample every 10 communication rounds and average the predicted probabilities made by all the previous collected parameter samples to calculate three test statistics, accuracy, Brier Score (BS), and Expected Calibration Error (ECE), the test dataset. We tune the step sizes n for the best performance and plot the curves of those test statistics against communication rounds in Figure 4.
36

---

Under review as a conference paper at ICLR 2023
(a) Accuracy (M) (b) BS (M)
(c) ECE (M)
(d) Accuracy (F)
(e) BS (F)
(i) ECE (F)
Figure 4: Convergence of FA-LD on the MNIST (M) and MaShion-MNIST (M) dataset with a warmup
period of the first 500 communication rounds.
According Figure 4, for the MNIST dataset, FA-LD with K = 1 performs the worst in terms of all three test statistics. For the Fashion-MNIST dataset, FA-LD with A = 1 performs the worst in terms of accuracy and BS and does not perform the best terms of ECE. Thus, is beneficial to have multiple local updates in federated learning under fixed communication budget.
Among K 1, 10, 20, 50, 100, according to Figure 4(a), 4(b), and 4(c), for the MNIST dataset, the optimal local step K is 20 in terms of accuracy, BS, and ECE. According to Figure 4(d), 4(e). and 4(f), for the Fashion-MNISS
dataset, the optimal K in terms of aceuracy is 20, the optimal in terms of BS is 10, while the optimal K' in terms of ECE is 50.
is worth mentioning that the optimal K with warmup period could be different from the optimal K without warmup period (see Figure 2). For example, the optimal K in terms of BS for the Mushion-MNIST dataset 100 without a warmup period (Figure 2(e)) but is with a warmup period of 500 communication rounds (Figure 4(e)), which indicates that the budget of communication also plays rule in determining the optimal local step K because the optimal K changes when the samples in the first 500 communication rounds not collected.
37


Reviews:
[{"review_id": "tgoKxYjGvt", "reviewer": "Reviewer_PJdt", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper extend Langevin Monte Carlo into federated learning setting with non-i.i.d. data and partial participation. Authors tried to develop convergence guarantee for this algorithm under assumption that the target distribution is strongly log-concave. According to their results, the convergence of their algorithm depends on data heterogeneity, learning rate, gradient noise and correlation between Gaussian vectors among clients. A differential privacy guarantee is also provided.", "summary_of_the_review": "My main concern is the soundness of the theoretical analysis.", "strength_and_weaknesses": "**Strength**:\n\nSome claims in this paper appear to be new, including the convergence of FA-LD with correlated Gaussian noise and partial participation.\n\n**Main Weakness**:\n\nThe soundness of the theoretical analysis is questionable.\n\nAuthors define the auxiliary continuous-time processes\n$$\n\\mathrm{d} \\bar{\\theta}_t=-\\nabla f\\left(\\bar{\\theta}_t\\right) \\mathrm{d} t+\\sqrt{2 \\tau} \\mathrm{d} \\bar{W}_t\n$$\nand authors claim that \"continuous-time algorithm is known to converge to the stationary distribution $\\pi(\\theta) \\propto e^{-\\frac{f(\\theta)}{\\tau}}$\".\n\nWhen the term $\\nabla f\\left(\\bar{\\theta}_t\\right)$ means the gradient of function $f$ at point $\\bar{\\theta}_t$, I agree the above SDE converge to the Gibbs distribution.\n\nHowever, authors interpret that term as \n$\n\\nabla f\\left(\\bar{\\theta}_t\\right)=\\sum\\_{c=1}^N p_c \\nabla f^c\\left(\\bar{\\theta}_t^c\\right)\n$.\n\nThe first problem is that, author left out the dynamics for $\\bar{\\theta}_t^c$ on each client, so the above SDE is not well-defined.\nIn Section D.1, authors use $\\bar{\\theta}\\_s^c=-\\int\\_{k \\eta}^s \\nabla f^c\\left(\\bar{\\theta}\\_t^c\\right) d t+\\sqrt{2 \\tau / p_c} \\int\\_{k \\eta}^s \\mathrm{~d} \\bar{W}\\_t$, and claim this equation is a consequence of eq. (20) (which is the SDE above for $\\bar{\\theta}_t$). But that is not true. Eq. (20) only defines dynamics for $\\bar{\\theta}_t$ but not for $\\bar{\\theta}_t^c$.\n\nThe second problem is that, even if we append the missing definition, the convergence claim is still wrong.\nLet's choose following SDE for $\\bar{\\theta}_t^c$ (which matches the integral authors used in Section D.1):\n$$\n\\mathrm{d} \\bar{\\theta}_t^c=-\\nabla f^c\\left(\\bar{\\theta}_t^c\\right) \\mathrm{d} t+\\sqrt{2 \\tau/p_c} \\mathrm{d} \\bar{W}_t\n$$\nIt is clear that the distribution of $\\bar{\\theta}_t^c$ converge to $\\pi^c(\\theta) \\propto e^{-\\frac{p_c f^c(\\theta)}{\\tau}}$.\n\n$\\bar{\\theta}_t$ is weighted average of $\\bar{\\theta}_t^c$, thus the distribution of $\\bar{\\theta}_t$ will converge to some kind of mixture of $\\pi^c$, but not $\\pi(\\theta) \\propto e^{-\\frac{f(\\theta)}{\\tau}}$.\n\nIn summary, the auxiliary continuous-time processes defined in this paper doesn't converge to desired distribution $\\pi$, and all convergence theorems w.r.t. $\\pi$ are wrong.\n\n**Other questions**:\n\nThe assumption G.1 is clearly in conflict with assumption 4.2, thus Theorem 4.7 and Theorem 5.7 cannot hold at same time, or more specifically, we can guarantee either convergence or privacy, but not both. Is there any possible mitigation to that dilemma?\n\nLemma 4.4 is called \"informal version of Lemma B.1\". Which part of its statement is informal?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bBa-rJNnx1A", "reviewer": "Reviewer_mK8G", "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": "The paper studies non-asymptotic convergence of federated averaging Langevin dynamics in 2-Wasserstein distance, where the target is log strongly concave. The authors consider stochastic gradient, constant and varying learning rates, privacy-accuracy trade-off, partial device participation. They also discuss differential privacy guarantees. ", "summary_of_the_review": "The paper is a theory paper that provides non-asymptotic convergence results for federated averaging Langevin dynamics. It would be better if the authors can make the technical contributions more clear and also comment about the quality of their non-asymptotic convergence results as I mentioned previously. ", "strength_and_weaknesses": "This is a solid theory paper, and the analysis seems to be rigorous. \n\nHowever, just in my opinion, I feel that the authors should highlight a bit more about their technical contributions. For example, under the log-strongly-concave setup for overdamped Langevin, the method to obtain convergence is well known, see e.g. Arnak S Dalalyan and Avetik Karagulyan (2019) \"User-friendly Guarantees for the Langevin Monte Carlo with Inaccurate Gradient.\" The authors perhaps should comment on what is the technical difficulty under the federated averaging setting and how they overcome it. Right now, the impression I have is that even though the authors discusses many model setups, for non federated averaging case, they are known in the literature, so the current paper is just a collection of many results, where the only novelty is the presence of the federated averaging. \n\nAlso, the authors mentioned that The frequently used bounded gradient assumption of $\\ell_{2}$ norm in FedAvg optimization is not required. It would be nice if the authors can elaborate more on this point and why they can remove this assumption. Also, if they can remove this assumption for Langevin dynamics for sampling, does that mean their techniques can be used to remove this assumption for optimization as well?\n\nMoreover, I am just wondering whether the non-asymptotic convergence is sharp in the current paper. For example, there have been many works in recent years, and one of them is Li et al. (2021) \"Sqrt(d) Dimension Dependence of Langevin Monte Carlo\", where they used mean-square analysis to obtain better dependence on the dimension d. I am wondering whether that is possible in the federated averaging setting. At least, the authors should make some comments on whether the convergence rates they obtained are optimal or not depending on the model parameters. For example, if you reduce your results to the special case for standard SGLD, are your results sharp according to the literature? This will help the readers understand how good the results are presented in the current paper. \n\nI am also wondering what is the technical difficulty if you consider non-convex $f$, as in Raginsky et al. (2017). It is possible that non-convex setting is very challenging for the federated averaging setting, but that can also help the readers appreciate the log-strongly-concave assumption made in the paper and make it more clear about the technical challenge in the federated averaging setting. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "FIXapUx_hko", "reviewer": "Reviewer_Nk8K", "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": "This paper studies a federated version of stochastic gradient Langevin dynamics (SGLD) that the authors dub FA-LD. Motivated by the shortcoming of existing federated optimization research which do not allow for uncertainty quantification, they consider a Bayesian version of the federated optimization problem where one wishes to sample from a posterior, and the negative log density of the posterior is distributed across multiple devices. They study the analog of federated averaging in this setting, where each device does a few steps of SGLD locally before the weight vectors are re-aggregated across devices. Their main findings are convergence bounds in $W_2$ for the law of the iterates, including for fixed learning rate, varying learning rate, correlated noise, and partial device participation. The authors also provide a result giving some differential privacy guarantees for their algorithm, as well as some empirical exploration of their method, including comparisons to vanilla SGLD.", "summary_of_the_review": "This work provides novel theoretical guarantees for a federated version of SGLD. While they do give several theoretical bounds, they generally suffer from an additive term that does not go to zero and it is difficult to judge their significance.  Moreover, their experiments are not extensive and don't incorporate a use of uncertainy quantification fitting their motivation of studying a Bayesian setting. Also, there are definitely issues with clarity of presentation and likely issues with correctness. Overall, I think that the work is not suitable for acceptance.", "strength_and_weaknesses": "Strengths:\n\n- This work provides rigorous theoretical guarantees for a federated sampling algorithm using SGLD.\n\n- The theoretical guarantees are extensive: they include fixed and varying learning rate, correlated and un-correlated noise, and full and partial device participation.\n\n- It includes a result addressing differential privacy of their algorithm\n\n- The authors mention that they do not require $\\ell_2$ bounds on the gradients as in the federated averaging optimization framework. I am not familiar enough with the federated averaging literature, nor their proof, to judge if this is significant or not\n\nWeaknesses:\n\n- Their algorithm and setting are not novel, having been already considered in the work Al-Shevidat et al 2020 (the authors address this in their paper; I am by no means saying they missed this reference)\n\n- Their upper bounds (except for the upper-bound for varying learning rate) involve a term that does not go to zero as iterations go to infinity, apparently due to the independent SGLD steps\n\n- The paper is written in a confusing fashion, it is difficult to understand what the definitions of the continuous time dynamics are. Also there is significant repetition between the appendix and main text, with the appendix basically being an extended version of the main text. The related work is in the appendix.\n\n- While there are many results, it is not clear which is most important, what the key difficulties in establishing those results are, and none explain why FA-LD might outperform SGLD (the bounds as-is suggest that with more independent SGLD steps the algorithm performs worse)\n\n- The experiments are not in a setting where the data is non-i.i.d. (in this context meaning the devices see fundamentally different portions of the data distribution). In fact, the data is split randomly between devices, undermining the need for federation\n\n- Issues with correctness (added after reading reviewer PJdt's review): I agree that there seem to be major issues with correctness, greatly compounded by confusing definitions of the continuous time dynamics. I interpret them to be using continuous time dynamics where at all times t, the gradients are shared, which seems to be what they are indicating on the footnote on page 4 as well as in section A.1. As in the footnote on page 4, this means that\n$$\n\\bar \\theta_t^c = \\bar \\theta_t\n$$ for all $t \\in \\mathbb{R}$ and $c \\in [N]$. It follows, therefore, that\n$$\n\\sum_{c = 1}^n p_c \\nabla f^c (\\bar \\theta^c_t) = \\sum_{c = 1}^n p_c \\nabla f^c (\\bar \\theta_t) = \\nabla f(\\bar \\theta_t),\n$$ where the last gradient is in the usual sense. Hence the continuous time dynamics do indeed converge to the correct distribution. However, as reviewer PJdt points out, the integral formula for $\\bar \\theta_t^c$ seems to be using only the local dynamics\n $$\nd \\bar \\theta^c_t = - \\nabla f^c(\\bar \\theta^c_t) + \\sqrt{2\\tau/p_c} dW_t.\n$$ These are obviously at odds with one another and seem to be a major problem with the proof of the discretization error bound in Lemma B.2. That said, the authors also have some continuous time variables $\\beta$ which only follow the local gradients defined in subsection A.1, and it may be that the authors mean to prove Lemma B.2 with these alternate variables (which may not resolve their issues). Clarification on this point is seriously needed.\n\n\nAl-Shedivat, Maruan, et al. \"Federated learning via posterior averaging: A new perspective and practical algorithms.\" arXiv preprint arXiv:2010.05273 (2020).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject