Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
Authors: Milad Sefidgaran
Romain Chor
Abdellatif Zaidi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed learning
Generalization error
Rate-distortion
SVM

Abstract: In this paper, we use tools from rate-distortion theory to establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there are $K$ clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's algorithm while keeping other clients' algorithms un-compressed, and leveraging the fact that small changes in each local model change the aggregated model by a factor of only $1/K$. Adopting a recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, enables smaller rate-distortion terms which are shown to translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $\mathcal{O}(\sqrt{\log(K)/K})$. This finding is validated also experimentally. A similar conclusion is obtained for a multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD).

Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning
Milad Sefidgaran', Romain Chor', Abdellatif Zaidi
Paris Research Center, Huawei Technologies France
Université Paris-Est, Champs-sur-Mamee 77454, France
(milad. sef segiaaran,, romain chor) Chuawei. com, abdellatif zaidi@u-pem.
Abstract
In this paper, we tools from rate-distortion theory establish new upper bounds on the generalization error of statistical distributed learning algorithms. Specifically, there K clients whose individually chosen models are aggregated by a central server. The bounds depend on the compressibility of each client's s algorithm while keeping other clients' algorithms un-compressed, and leveraging the fact that small changes in each local model change the aggregated model by a factor of only 1/K. Adopting recently proposed approach by Sefidgaran et al., and extending it suitably to the distributed setting, enables smaller rate- vate-distortion terms which are shown translate into tighter generalization bounds. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error the distributed setting decays faster than that of the centralized one with factor of ( /log( ).) This finding validated also experimentally. A similar conclusion is obtained for multiple-round federated learning setup where each client uses stochastic gradient Langevin dynamics (SGLD).
1
Introduction
key performance indicator of any stochastic learning algorithm that uses a given finite set of data points is how well it performs points that are outside that set, i.e., unseen data. This is often captured through the so-called generalization error. The questions of what really controls the generalization error of given stochastic algorithm, and how to make it sufficiently small, are still not yet well understood, however. For example, while classic approaches [SSBD14 suggest that algorithms with over- peeemetrmetee models are likely to overfit, is known that there exist few such ones which do generalize well [ZBH+17] Common approaches to studying the generalization error a statistical learning algorithm often consider the effective hypothesis space induced by the algorithm, rather than the entire hypothesis space, or the information leakage about the training dataset. Examples include wwwoormmtiontthoreeeeee (mutual information) approaches [RZ16, XR17, HRVSG21, HDMR21, NHD 20, SZ20], compression- conpression-based approaches [AGNZ18, SAN20, HJTW21, BSE 21, KLG-211 or fractal based approaches I$SDE20, BLGŞ21, HşKM21]. Recently, novel approach [SGRS22] that generalizes the notion of algorithm compressibility by using lossy covering from source coding concepts was used show that the compression error rate of an algorithm is strongly connected to its generalization error both in-expectation and with high probability: and, consequently, establish new rate-die www.diiiitoo-baaate based bounds on the generalization error. The bounds of [SGRS22] were shown to possibly improve strictly upon those of [XR17, BZV20] and [SZ20]. The approach also has the advantage to offer unifying perspective on mutual information, compressibility, and fractal-based frameworks.
and parinsic-dimensee
Another major focus of machine learning research over recent years has been the study of statistical learning algorithms when applied in distributed (network or graph) settings. In part, this is due to the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

emergence of new applications in which resources are constrained, data is distributed or the need to preserve privacy [VWK's 1 20, MMR $ 17. KMY 16. KLN' 11]. Reducing the computational com- plexity by offloading the model training using algorithms such as parallel stochastic gradient descent another reason for the popularity of these algorithms. Generally, that results in extra communication costs, however [77.1,, AGL 17, CCB+ 18, LM22, WI.C2]]. Example such algorithms include the now popular Federated Learning [YAE+ + 18, KMA+ 19, LSTS20, RCZ++00, KKM 20, YZR21], the Split Learning of [GR18), Group Alternating Direction Method of Multipliers [EPB* + 20], and the so-called in-network learning of [AZ19, MZ21J. Despite its importance, however, little is known about the generalization guarantees of distributed statistical learning algorithms. In fact, in the distributed learning setting the technical challenges are numerous, including the lack of a proper definition of the generalization error in this case (YMNS22, MSS19]. Notable exception works in this direction include [YDVP20] and [BDP2 In [YDVP20], information-theorrtic upper bounds on the generalization error of distributed statistical learning algorithms are obtained merely by viewing the entire distributed system, from the input data to each (local) algorithm to the output aggregated model, single (centralized) algorithm and applying to it the bounds of [XR17, BZV20J. While somewhat useful this, however, has left the difference between the bounds for the distributed learning setting and their counterparts for the centralized learning setting implicit in the involved mutual information terms. The problem of studying the generalization error of distributed statistical learning algorithms was further studied in the recent [BDP22). Therein, using results from [BZV20], the authors establish bounds on the expectation of the generalization error for two special cases. For the first, linear or location models with Bregman divergence loss, the proposed bound on the generalization error for the distributed setup [BDP22, Theorem 4] is shown better (i.c., smaller) than its counter-pant -prt for the centralized learning setting by a factor of (L/VK)) ), where K is the number of clients. This result, however, relies strongly on the assumed linearity of the loss with respect to the hypothesis. For the second, Lipschitz continuous loss [BDP22, Theorem 5], similar behavior is shown by reducing the problem to the centralized case and using the triangle inequality.
In this work, we study the generalization error of distributed statistical learning algorithms. Essentially we extend suitably the approach of [SGRS22] to establish rate-distortion theoretic upper bounds on the generalization error. In doing so, we bring the analysis of the distributed architecture of the learning problem into the bounds. The bounds, which hold with high probability and in-expectation, allow to only consider the compressibility of each local algorithm - the latter having an effect with a factor of only 1/K on the aggregated model order-wise. This is shown to result in a more relaxed distortion criterion for the local algorithm compressibiliry, smaller rate- rite-distortion terms; and, in turn, better generalization bounds. Furthermore, we apply our results to the distributed support vector machines (DSVM). The obtained bounds suggest that for the non-separable data, the generalization error of the distributed setting decays faster than that of the centralized one with a factor of Vlog( ())gK)K We conducted experiments on DSVM that confirm this finding. We also consider the related Federated learning setting, and derive bounds on the generalization error in two setups: when each client applies the stochastic gradient Langevin dynamics (SGLD) method and locally deterministic algorithms with Lipschitz loss (in Appendix C.I). In all cases, our bounds suggest a decreasing behavior for the generalization performance as K grows.
Notation. Random variables, their realizations, and their domains are denoted respectively by upper-case, lower-case, and calligraphy fonts, e.g., X, x, and X. Their distributions and expectations are denoted by Px and E[X]. The random variable X is called o-subgaussian if for all E R. E E[eep((((X - E[X])]] & exp(o" e.g., if X E [a, b]. then X is h- -u--subaausi A vector -2
of m E N numbers (or random variables) (T1 (01.-..... vm) .m)) are denoted by either 2i:m or { de- pending on the context, and the vector (Z1,.... Z1- #.41...... Imm is denoted by Z1sm/i Similarly 22.m: In.1..... .,,,,,.....,.,, is denoted by Iimm,I or (zi, to he]p]] or {xt (mimn]]jemm) where [n] {1, ,I,.... n). .n]..., Parts of our results are stated in terms of information-theereti quantities: for random variables X and Y. we denote the differential entropy of X by h(X), ), the conditional differential entropy of X given Y by h( and the mutual information between them by T(X; Y). Moreover, the Kullback-Leibler (KL. divergence between distributions Q and P is denoted by (Q] For more details, we refer the reader to |CT06, PW WW14].
for n, m N, a vector (.1,1,..., Lm. 22,
2 Preliminaries and problem setup
For convenience, we start with a brief review of the standard (centralized) statistical learning setup together with few definitions and recent results associated with it. Let the input data Z be
2

---

distributed according to an unknown distribution μ over the data space 2. A training dataset S = (Zi...., .,. Zn,) ur"n consists of samples {Zi} generated independently each according to j.. A possibly stochastic learning algorithm A: 2" - W (e.g., stochastic gradient descent) assigns an hypothesis A(S) W chosen from the hypothesis class W = R.d every S E 2". The map A induces a conditional distribution Pw|s which together with j induce the joint dataset-hypothesiss distribution Ps.w 1 Pwis- The quality of the prediction is measured using loss function f: 2 x W - R+. The generalization error of an algorithm A is defined as gen(s, w)) :- [(w) [(s, w) where [(w)= == Ez~ni((2, w)] denotes the population risk and L(s, w) = 1
n Exann ((23, w) denotes the empirical risk. Note that the generalization error depends on the loss function f(2, w), underlying distribution μ4, the sample size n, and also the learning algorithm Pwis. In the binary classification context, where 2 = X' ) and y +-1,+1], we often consider the 0-1 loss function fo(2, w) :=
<0), where the sign of f faz w), f: X W + R. the label prediction by hypothesis w and 1 is the indicator function. In this setup, it is common to assess the empirical risk with respect to 0-1 loss function with margin 0 R+ defined as (1 w) == II fyfl( =))(), w)-=6) while using 0-1 loss function for the population risk evaluation. We denote the corresponding empirical risk as La(s, w) == 1. [}j[m]]
to (Z),, w) and the generalization error as geng (s, w) == [(w) Lo(s, w).
The exact analysis of the generalization error gen(S, W) seems out of reach; and, for this reason, as already mentioned upper bounds on it were developed using an information -ethorrtnttchtiiiccccc approach. Essentially, such an approach connects the generalization error of statistical learning algorithm A with the mutual information between the input data sample S and the algorithm output W = A(S). For details, the reader may refer line of work that was initiated by Russo and Zou [RZ16] and Xu and Raginsky [XR17] and since then improved by using various conditional versions of mutual information. Other approaches rely on the observation that the output W can be compressible in some suitable sense [AGNZI8] or the algorithm might generate a fracial structure [$SDE20].
Very recently, approach [SGRS22] that relies probabilistic e-covering from source coding concepts was proposed and shown to possibly improve strictly over the aforementioned. seemingly unrelated, approaches, while offering a unifying framework to them. The upper bounds of [SGRS22] are rate ante-distortion theoretic. Specifically, let W be the alphabet of the compressed hypothesis and è: Z W + R. loss function (possibly different from f). Accordingly, for á W and s z", let gen(s, w) be defined with respect to f. For every distribution Q defined over x W, the rate-distortion function with respect to W is defined as
inf RD(Q,)) c) = inf Pins T(S W),
s.t. (len)- -)]-BBs, Qs [gen(S, W)] e.
(I)
where Qs is the Q-marginal of S, and the infimum is taken over all Markov kernels (conditional distributions) of a random variable We e W given S. Note that Ps.w induced by the algorithm A is particular case of Q. In the following, we shortly discuss the related intuition and concept behind the above terms. The reader is referred to Appendix A for more details on this.
This vate-distortion function RD (2( e) is the adaptation of the rate-distortion function emerged in the lossy source compression context [Ber75, CT06) to stochastic learning algorithms [SGRS22]. In the lossy source compression context [Ber75, CT066, this function quantifies the fundamental compression rate of a source X Px to within some desired average distortion level e. To this end, infinitely many i.i.d. instances of the source [x.]ss]m], X; ~ Px, and m - oc) are compressed (quantized) simultaneously. The joint compression approach is known as the block-coding technique. In the learning context, this term quantifies the lossy algorithu compressibility [SGRS22), with the following intuition for the case where Z and W are finite sets. Each Pwis denotes a learning
algorithm and the distortion criterion E[gen( S, W) the difference between the generalization error of the original algorithm Pw1s and that of the "compressed" algorithm Pwis does not exceed e, The rate-distortion term RD w, e) quantifies the lossy compressibility of the algorithm Pwis in the following sense: for large m E N and every admissible Pürss a compressed hypothesis space of size Nm, R (s( can be found such that, with high probability, for each m i.i.d. instances of the original algorithm Pw there exists at least one compressed hypothesis for which the difference between the average generalization error over
(S, W]] < guarantees that in average
3

---

the m i..d. instances of Pw]s at hand and that of the found hypothesis does not exceed Recall the tail bound on the generalization eπror [SGRS22, Theorem 10].
Theorem 1 ([SGRS22, Theorem 10] ). Suppose that the learning algorithm A(S) induces Ps,w and suppose that for all i W, E(Z,, úi) is a-subgaausiian Then, for any fixed E RR and 5 > 0, with probability at least - 6, gen(S, W) & (2,2 e) + log(1/0))/n++ where Rp e) == sup Q: D
(Q, e) and the supremum is over all possible distributions over S x W.
The above bound depends not only RD(sss e) but also RD (Q, E) terms for all distributions Q that are close enough to P. In other words, to guarantee a good generalization performance, the compressibility of the algorithm under every such small perturbation of Ps, needs to be considered.
Remark 1. The reader may notice two (minor) differences between Theorem as stated here and [SGRS22, Theorem 10]. First, we here express the rate-distortion terms with respect to the distortion function d( w. 8) = gen(s, w) gen(ss, w) instead of a possibly smaller distortion function d' (w W; s) in (de==")))ppp)()) Q) gen(s', - u) that was considered in [SGRS22], where supp(Q) denotes the support of Q. Even though the latter could possibly lead to stronger results, we do not consider it here because it is less amenable to computations. Second, in Theorem 1 the loss function f(2, @t) is allowed to differ from the original f(2, w); and this possibly leads to some (rather small) improvement of the result of [SGRS22, Theorem 10]. The mentioned two small differences, however, do not require any change in the proof of (SGRS22, Theorem 10].
Remark 2. Similar to [SGRS22, Theorem 10], most of our results that will follow in this paper require the subgaussianity assumption of the loss function to hold. In both cases the assumption used property bound the moment generating function (MGF) of specific zero-mean random variable using the Hoeffding inequality (see (SGRS22, Section E.6.2] ] for the details). Alternatively, this MGF can be upper bounded using approaches similar to [BZV20].
Problem setup. this work, we consider a homogeneous distributed learning setup that exploits the participation of K clients, described in the following. Each client i E [K] has access to a training dataset S, (Z,1)-... Zen e of size n,
drawn independently of each other and indepen- dently of other clients' training datasets from the same distribution p. The local learning algorithm A, at each client picks hypothesis A(S),) We E W; W according to Pw.1.s: The in- duced joint distribution of (S,, Wa) is denoted by Pss. W.. The server receives the hypotheses WIKK and picks the hypothesis W as
Server
W
evenaging
W
W (W1 + Wk)/K.
W
WK
We denote the distributed learning al- gorithm as AI.x((S.K) the joint distribution W... Pwiw,,x [he[k] Ps..,, where Ps. = 10 and P Pwiw = 1 +WW= Similar to (YDVP20, BDP22], the population and empirical risks are defined
Client
Client K
It induces
S
W
Sk
Figure
The considered distributed setup.
1 Σ K E
Ez),=Ez, w)], [(s
C(s;, w).
(2)
The main goal of the paper is to upper bound the generalization error gen( (0u(81:73) 3) = L(T)
-
[S1:K w for the described (one-round) distributed learning setting as well as multi-round extension of it, i.e., Federated Learning. Results for the latter stated in Section 5.
3 Information-theeortic bounds on the generalization error
In this section, we establish information- theoretic bounds on the generalization error of any stochastic distributed learning algorithm defined as in the previous section. It is important to note that the

---

bounds hold for W being any stochastic function of WI:K. For the ease of the exposition, however, we only focus on the deterministic average case. The bounds are applied later for the DSVM and federated SGLD, suggesting a decreasing generalization error behavior as the number of clients increases.
3.1 Tail bound
trivial approach that was already considered and used in [YDVP20] to establish in-expectation bounds for the problem studied therein consists in thinking of distributed learning algorithm that is composed of K local algorithms and an aggregator at the server as a single centralized algorithm. In other words, consider the end-to-end system from the input at each local algorithm to the final aggregated model W PWIS..'' The idea also applies to tail bounds. Hence, known tail and in-expectation bounds the generalization error of centralized learning algorithms translate trivially into (generally loose) counter-pad part bounds for the distributed learning setting. Accordingly, the next theorem follows easily using the result of the above Theorem 1.
Theorem 2. Suppose that the distributed learning algorithm AI.K(S...) induces P.L..W .. and suppose that for all T E W, iZZ, T) is o-subgaussian. Then, for any fixed e E and ê 3 with probability at least 1- gen (SLKk W) E v HD(Q, c) and the supremum over all possible distributions over
e) + (og(L/)))(mm))t. where (p(8,e) c) ==
sup
Q: Dx s... (log((11/))
W x TT [Teck]] S.
In the distributed setup, for every i [K] only the hypothesis W; depends on the dataset S,, which has then the effect with factor of 1/K on W. The result of Theorem 2, however, does not explicitly take the structure of the distributed learning problem into account and, instead, it considers the joint compressibility of all local algorithms and W Thus, the dependency of the bound on the structure of the problem is considered only implicitly, via the conditional distribution PWIs.x" In this work, we establish an alternate bound that is tailored specifically for the considered distributed
setup. First, for every i E [K] we let the compressed hypothesis W; of W to depend on both S, and W1. (recall that W 1: is independent from S,). We then establish upper bound on the generalization error in terms of the maximum (over all clients i E [K]) of the minimum achievable compressibility using Pi.. S.WW The advantage can exemplified as follows. For E [K].
consider only compressing the local algorithm Pw.ss. and pick some W; while keeping Wi:Kh, un-compressed. Let W; be average of W, and WI.KY-- W. has the effect with factor 1/K on W, in order to meet the distortion constraint E[gen(S, W) - gen((, S., a) & e a more relaxed distortion criterion would be needed in compressing the local algorithm Pw, (s.. More precisely, for example when the loss is L-Lipschitz with -ornomm, i.e., [((2, w) [[2 w']l | < El[ - w/ll2, local distortion of k results into only distortion in the aggregated model. Hence, this translates into smaller rate-distottion terms and, in turn, tighter bounds on the generalization error.
Now, to formally state the result, introduce some definitions. Let gen(s;; w) [(w) L(s w). Besides. as in the centralized case, let W be the alphabet of the compressed hypothesis and é: Z W R+ a loss function (possibly different from E). Accordingly, for @ e W and s 2", let gen(s, ()) and gen (s,, @) be defined similarly with respect é. For a distribution Q defined over W x [T W.), let
RD )D,((,))
inf P Wi,ss.Waaacs
T(S;; W (.I...
E gen (S., W) gen St 17:)] &
s.t.
where the infimum is taken over all Markov kernels (conditional distributions) of a random variable W.e E V given (S,, WL.)))). Note that the mutual information and expectations are with respect to For non- Lonshiise losses, such as 0-1 loss, the analysis is less trivial. An example can be found in Section D.2.
5

---

Wa. W.I.,, (1S., and QP W.W.S, W.I... respectively, where WL.ss Low is the Q- Q-marginal of (St, WI:K())
Theorem 3. Suppose that the distributed learning algorithm AL. (SiK) induces P Wi W and suppose that for all E W, L(Z, T) is o-subgaussian. Then, for any fixed IR and 8 2 0, with probability least 1-
20 (maxicc11 Rp(ô, e, + log(1/8))/n+t gen (S W) & 2
(5)
c, =
Q: Dws.iilPss..se... W (1/)) (Q,,),
sup
(6)
where the supremum is over all possible distributions over [ig[k] W.).
The theorem is proved in Appendix D.I. In the binary classification setup, the result also holds for the margin generalization error geng (Si.K: W) by letting geng (S., W) L(W) (S., W).
While the advantage of this result was already stated in part above, it should be noted that the denominator in the result of Theorem is rather than nK in Theorem 2. In fact, none of the two results of Theorem 2 and Theorem 3 outperforms the other in general. For the case of distributed SVM which will be considered in the next section, it can be shown that the result of Theorem results in a bound that decays with K faster than one that uses Theorem 2. Moreover, as will become clearer from the sequel the bounds for DSVM require strict lossy compression, i.e., + and do not seem to be obtainable with a lossless compression framework, illustrating the utility of our rate-distortion based approach in general.
Remark 3. For the ease of the presentation, the results of this work, including Theorem 3, are stated for the homogeneous case where the underlying data distribution μr is same for all clients. However, the result can be extended straightforwardly to the heterogeneous case, by considering S; and (Q, e), [K]. with respect to pú.
3.2 In expectation bound
Similar to Theorems 2 and 3, we establish upper bounds on the expectation of the generalization error of any distributed stochastic learning algorithm.
Theorem 4. Suppose that the distributed learning algorithm AL. induces P PSSx W.. W and suppose that for all w e W. Ê(Z, wi) is o-subgaussian. for every fixed e E IR we have:
gen (Si.k. W)]
Σ
1202912
P2n,. (. 4
+6, Σ de [
20 max RD. (P2,(P2., WiN. (W;
K
ic[R]
Je [n]
[=[K]
Vn V 22 (Ps S. o/K + tc, C.v
min
202 max HD
WI. +
(8)
The first terms of the minimization in (7) and (8) follow easily by an application similar in Theorem 2. In particular, setting e = in the first term of the minimization in (7) one recovers the result of [YDVP20, Thoerem under the assumed subgaussianity. The second terms of the minimization in (7) and (8) are derived in manner that is essentially similar to in the proof of Theorem 3. The details are omitted for brevity.
In Appendix C.2, it is shown that under the assumed subgaussianity, the upper bounds in [BDP22, Theorems 4 & 5] also be recovered from Theorem 4. The results of [BDP22] are derived using the stability approach and by applying the leave-one-out expansion lemma.
4 Distributed support vector machines
In this section, we establish upper bounds on the generalization error of Support Vector Machines (SVM) [Vap06, CV95] when applied in distributed learning setting. The algorithm is called hereafter

---

as Distributed SVM (DSVM). SVMs are popular and widely used for binary classification problems. They can be combined with different kemels computationally efficient way [BGV92, GKL20J. An easy application of SVM consists in finding a hyperplane based on a training dataset that separates the data with the smallest possible average margin error. Formally, let 2 X V/ where X e Rd and 3 = {-1, +13. The hypotheses are vectors w Rd, which represent hyperplanes. For the simplicity of the exposition, we only consider the case with zero bias. The hyperplane predicts a label of data v according to the sign of the inner product (z, w). The 0-1 loss and margin loss functions are thus defined as fo(z, w) = (((e, =))= and Eø(z, w) == 1 (1((,,0)==)) respectively. In the distributed learning setup, each client E [K] has access to dataset S and picks the vector W;; and the server node computes the aggregated model as W = (Wi +.... + Wx) )/K [Car20]. In this section, we study the generalization gap, which we denote hereafter as gen (S1.k. W), defined as the difference between the population risk L(w) calculated using fo and the margin empirical risk R [K] Ca (S., W) calculated using lg. It should be noted that the results of [BDP22, Theorems 4 & 5] require the loss function to be either a Bregman divergence or Lipschitz of some order; and, as such, they are not applicable to the DVSM setup that we consider here. This is because the 0-1 loss function is neither Bregman divergence, nor Lipschitz loss.
Theorem 5. Let d N+ and P([ < B) = 1 for some > Consider DSVM with K clients each using any arbitrary local learning algorithm such that P(I]W,]] & 1) = i, [K].
i) For any 5= > 0, with probability at least 1 - -8
gens (S W) & $0
{(1 nKVR +V
2 log(nK VK) log(max
B (k))
KB ()) + log(111 (1/5)
ii) Also,
B² Blgg(nK K V VK) log (max K0 BB' 2))
Elgeng (Su. W) & O nK K
n nK202
This theorem is proved in Appendix D.2, by bounding the corresponding rate-distortion terms in Theorem 3 (for the part i.) and in the second term of (8) (for part ii.). To establish such bounds, we show the existence of proper P W.ISs,Wi.e using techniques and results developed in [GKL220],
and in particular by making use of the Johnson-Lindenssee Lindenstrauss transformation [JL84].
The above bound on the expectation of the generalization error of the DSVM decreases with K with important to note that the in-expectation bound for clients
a rate of log( K)/K /K/ Moreover, each having data samples is smaller than that of the counterpart centralized learning algorithm that has nk input data samples by factor of order O (ooooKK)KK) This also holds for the tail bound, as long log(1/5)/n / is not the dominant term in the square root. Note that in general /Tgg /18)/n is very small, corresponding to the generalization error of an dataset-independen algorithm [XR17]. Remark 4. The tail bound in Theorem 5 for K 1 does not recover the best known upper bound to the margin generalization error of SVMs. More precisely, for a centralized setup with dataset of size nK, |GKL20. Theorem 2] states
Ba log(nK)
2 log(nK) + log(1/6) Lo(S. +08g(1/0(coss.
geng(S, W) & O
nK02
nn
This is particularly important for the separable training dataset, where Lo(s, w) O. which makes the bound of order ( ((n())(((K(K)) For the non-separable case, this term is asymptotically lower bounded by (W"),, where W is the optimal population risk minimizer when μ is known. However, in the distributed learning setup, even if Lo(s,, w.) = 0, Lo(s,, w) is not necessarily zero. Remark 5. The proof of Theorem 5 shows how our generalization bounds exploit the particular topology of the distributed learning setup. In particular, we show that for a fixed non-zero distortion level in (4) an upper bound on the rates in (4) scales O ((log K) {/))).. When for which the rate-distortion approach reduces to the mutual information- basedd approach (see the discussion right after Theorem 4), that upper bound scales only as (1). In part this explains the benefits brought up by the rate-distortion approach upon the mutual information based one.
O, a case
7

---

Federated stochastic gradient Langevin dynamics
this section, we consider a homogeneous federated learning setup, denoted as FSGLD, where local learning algorithms use stochastic gradient Langevin dynamics (SGLD) method [WHGC21]. For the case of the centralized learning algorithm, [WHGC21] has proposed a new tractable upper bound on the generalization еттоr, that describes well the generalization behavior, by using results of [BZV20] and by connecting SGLD to the Gaussian channels.
We consider multiple-roun distributed learning algorithm. At beginning of each round / e [T]. the central server sends the updated hypothesis at the end of the previous round Wr R to the clients, where W is a randomly initialized hypothesis. Then, each client i E [K] performs locally one iteration of SGLD, as explained later, and outputs W. The central server upon receiving these hypotheses choices, let Wr (W1, + .... + WK,))KK The final hypothesis W is chosen deterministic function of {W [e)eeen An example of such choices is Polyak averaging [PJ92], where W = (W1 + ......... + Wx Wr/TT.
Now, explain the local SGLD algorithm applied by each client [GM91, WT11, WHGC21]. Each client e [K]. partitions its dataset S; into m disjoint mini-batches [Sa1..... Sa.m), ). each one having equal size b with elements Sig {Zi,j...... Z...)- Then, client i at round I, by receiving W Wr-1 from the central node, let Wi, be
2n
W
V Wi-1) +
V.
V B,
Here, th is the learning rate, 3r the inverse temperature, V a d-dimensional random variable with distribution NV(0,a), where I is the d x d identity matrix, je e [m] is the mini-batch index, l: W IR+ is a surrogate loss function, and
1 W W = b Eveyy VullZis Wr-1).
In the following [YDVP20, Thoerem 2)). to derive bound on the expectation of the generalization error of FSGLD. Note that the first term of (7) established by viewing the whole learning algorithm black-box, and hence it applies for the multiple-round federated learning setup as well, by considering S as the training dataset and W as the chosen hypothesis.
the first term of (7) with
(which is reduced to the upper bound in
Theorem Suppose that for euch w W, the loss E(Z,w) is o-subgaussian. The expected generalization error of FSGLD is upper bounded by
V2ba
gen (LLK W)]
Σ
Σ
E
Σ 1ET.
Ben Var SintVa((v... (.. W w-.)
2nK
jc[m] ic[K]
where the set Tr.j contains the indices such that jr = j at client i, and
Var (n Ww.1) = I 1 V W. 1.
where e, == E V.. We Wc-1
This result for the case of K = 1 is reduced in /WHGC21, Theorem 1] and it can be proved for any K e N along the same lines of the proof of [WHGC21, Theorem 1]. Indeed,
Theorem
W. W
Σ [E[K]
+
1
21
V
(10)
VK
B
where V is a d-dimensional random variable with distribution. (/ Lz). Now, proceeding similar to the proof of [WHGC21, Theorem 1] concludes the result. The reason behind the extra factor 1/v K in the bound is that, when K independent Gaussian noises added, their variances added up linearly with K. Thus, while in (10), the gradient divided by K, the noise term is divided by VK,

---

(a) n 100
(b) n2 300
Figure 2: The generalization error for distributed and centralized SVM
which results in an extra / K term in the denominator of the upper bound. The proof is omitted for brevity.
The established bound is decreasing with K, as far as the variance of the gradient with training data size n is not smaller than the variance of the gradient with training data size n, divided by K. Note that the variance of the gradient is correlated with the sharpness of the loss landscape and becomes small the algorithm converges [WHGC2I].
6 Experiments
This section aims at showing, through simulations, the evolution of the generalization error of the distributed SVM with the number K of clients and the size of each individual training dataset. We will provide also comparison with the centralized setup, having training dataset of size nk, and also with the bounds on the generalization error as predicted by our analysis. We also provide further experiments and discussions on the comparison of the empirical and population risks of the distributed and centralized SVM. The details of the experiments are explained in Appendix B and here, we discuss our experimental findings.
Figure shows the evolution of the generalization error (with zero margin) of the distributed setup (K clients, each having data samples) as function of the number K of used clients for two values of n, n 100 (Subfigure 2a) and n 300 (Subfigure 2b). Also shown for comparison, the generalization performance of the associated centralized setup with dataset of n samples.
On the generalization error:
The figure also depicts the evolution of the bound of our Theorem 5 (computed using part ii) of the theorem and with the value of the parameter 0 set to 0.2). For the centralized learning setting, the theoretical bound is obtained by applying the result of Theorem 5 (part ii) with the substitution K. and n. nK.
Observe that, as predicted by our theoretical analysis of Section4, the system generalizes better the distributed setup.
On the empirical and population risks: While considering the empirical risk L(sik. == I Eicigg L(s,, w) is motivated by previous works (YDVP20, BDP22), it differs from the average local empirical risks minimized at clients, i.e..
[(sL:K, w1:k)
1 K
E 2ee
[(st, w/).
(11)
Denote the difference of these empirical risks as
AL(SI: Wi:K. w) == [(six, w) - L(81:K
(12)
Then, the population risk can be written
L w
Ī(SI. wi:k) + gen(s1:K, W) + AL(SI:K W1.K W)
(13)
The first term the RHS of Eq. (13) can be made sufficiently small by minimizing the local empirical loss at each client. The second term is the generalization term considered in this paper, which is shown to decrease faster than the corresponding centralized case. In what follows, we study the evolution of the last term of the RHS of (13) with K.

---

3 527
2.00
50
334
16
(a) 100
(b) n 300
Figure 3: The population risk and empirical risk differences for distributed and centralized SVM
Indeed, as shown in Fig 3, while the considered generalization error decreases with K, the population risk of the centralized setup is smaller than the distributed setup. Also, the latter decreases more slowly with K. This is caused by the increase of term AL(S WI.K, W) with K (note that this term is zero for the centralized setting). As it will become clearer from the rest of this section, the distributed setup the term gen (S W) decreases with K specified by our Theorem 5 and the term AC(S).K K.K, Wi.K. K. W) increases with K (the term [(S K. Wi.K) + gen( S1.K, W) as defined by (11) can be made negligible for both centralized and distributed settings if local models are trained well enough, an assumption which will be made throughout hereafter). For the distributed case, the net effect is a decrease of the population risk with K, but which is slower than in the corresponding centralized setup. In what follows, we will show that as K becomes large, the clients use the same algorithm, i.e., Pw.ss. Pw.ss, for all i E [K]. and they trained well enough minimize their respective empirical risks É(;; W;) then the population risk in the distributed case tends to a constant that depends only on and the used local algorithms, but not on K.
More formally, fix training data size n N and suppose that all clients use the same local learning algorithm Pw Pw.lst- This empirical risks difference term is zero for K 1, as W W1. By increasing K, W departs further from W,. In particular, as K - oc, W - Ew, [Wi]. where the expectation is with respect the marginal distribution Pw; (induced by Pw, s, 14 (n) and the convergence is almost surely due to the strong law of large numbers. Note the for fixed data distribution μr, the marginal distribution Pw, function of n and local algorithms PW,1s, Hence,
Ew, Ews [Wa1) | lim AL(SI.K WI.K, W) - ES pmm [(1 K-
B(S.,W))-Ps,N Ps,m - [(S), ((S),W))
Ezzz (e, Rw, [Wi])] Fss..W.) Poy. [(S)] Wi)]
= -C(Ew,(Wi]) B(s,,
((S)) Wi)].
(14)
The above illustrated in Fig.3, where visible from therein the population risk for the distributed setting (as computed experimentally) approaches the limit given by the RHS of (14) as K gets large.
7 Concluding remarks
In this work, we established rate-distortion theoretic tail and in-expectation bounds on the generaliza- tion eтror of the distributed learning algorithms. Unlike previous approaches to this problem, our bounds, which are more general comparatively, are tailored specifically for the distributed setup. In particular, when applied to distributed SVM and FSGLD our results suggest a decreasing behavior of the generalization error with respect to the number of clients. The conducted experiments on DSVM are in accordance with the analytical results. Also, we partly investigated the evolution of the population risk with the number of clients and the size of the dataset. The analysis revealed the presence of a bias term. Possible directions for future works include (i) further investigation of the effect of the aforementioned bias term, (ii) study of the tightness of the proposed general bounds (experimentally), (iii) extension of the results to the setting in which the data distribution is not identical across the clients or when the training data samples are not independent, (iv) multiple-round scenarios, and (v) study of associated computational and communication costs.
10

---

References
[AGL" 17] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication--fficiene sgd via gradient quantization and encoding. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[AGNZI8] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254 263. PMLR, 2018.
[Ari72] Suguru Arimoto. An algorithm for computing the capacity of arbitrary discrete memo- ryless channels. IEEE Transactions Information Theory, 18(1):14-20, 1972.
[AZ19] Inaki Estella Aguerri and Abdellatif Zaidi. Distributed variational representation learning. IEEE transactions on pattern analysis and machine intelligence, 43(1):120- 138, 2019.
[BBO5] Mayank Bakshi and Rakesh K. Bansal. On error exponent in lossy source coding, 2005.
[BDP22] L. P. Barnes, A. Dytso, and H. V. Poor. Improved information theoretic generalization bounds for distributed and federated learning. In 2022 IEEE International Symposium Information Theory (ISIT), pages 1465-1470, 2022.
[Ber75] Toby Berger. Rate Distortion Theory and Data Compression", bookTitle= "Advances in Source Coding, pages 1-39. Springer Vienna, Vienna, 1975.
[BGV92] Bernhard
Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computa- tional learning theory, pages 144-152, 1992.
[Bla72] Richard Blahut. Computation of channel capacity and rate-distortion functions. IEEE transactions on Information Theory, 18(4):460-45) 473, 1972.
[BIGŞ21] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli. Intrinsic dimension, persistent homology and generalization neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[BSE 21] Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gaël Richard, and Umut Şimşekli. Heavy tails in SGD and compressibility of overparametrized neural networks. In Thirty-Fifth Conference Neural Information Processing Systems, 2021.
[BZV20] Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information- based bounds on generalization error. IEEE Journal Selected Areas in Information Theory, 1(1):121-130 May 2020.
[Car20] Robert Carlsson. Privacy-prese preserved federated learning: A survey of applicable machine learning algorithms in a federated environment, 2020.
[CCB 18] Chia- Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakrishnan. Adacomp: Adaptive residual gradient compression for data-parallel distributed training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[CK11] Imre Csiszår and Jànos Körner. Information Theory: Coding Theorems for Discrete Memoryless Systems. Cambridge University Press, 2 edition, 2011.
[CT06] Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.
[CV95] Corinna Cortes and Vladimir Vapnik. Support-vector networks, Machine learning. 20(3):273-297, 1995.

---

[EGK11] Abbas El Gamal and Young- Han Kim. Network Information Theory. Cambridge University Press, 2011.
[EPB 20] Anis Elgabli, Jihong Park, Amrit S Bedi, Mehdi Bennis, and Vaneet Aggarwal. Gadmm: Fast and communication efficient framework for distributed machine learning. J. Mach. Learn. Res., 21(76):1-39, 2020.
[GKL20] Allan Grønlund, Lior Kamma, and Kasper Green Larsen. Near-tight margin-based based generalization bounds for support vector machines. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Reseurch, pages 3779-3788. PMLR, 13-18 Jul 2020.
[GM91] Saul В Gelfand and Sanjoy K Mitter. Recursive stochastic algorithms for global optimization in r'. SIAM Journal on Control and Optimization, 29(5):999-1018, 1991.
[GR18] Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 116:1-8, 2018.
[Han00] Te Sun Han. The reliability functions of the general source with fixed-length coding. IEEE Transactions on Information Theory, 46(6):2117-2132, 2000.
[HDMR21] Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Daniel M. Roy. To- wards unified information-theoortiee framework for generalization. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[HJTW21] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference on Learning Representations, 2021.
[HRVSG21] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information- theoretic generalization bounds for black-box learning algorithms. Advances in Neural Information Processing Systems, 34, 2021.
[HŞKM21] Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W Mahoney, Gen- eralization properties of stochastic optimizers via trajectory analysis. arXiv preprint 11Xi::208:000811 2021.
[Iri05] Kiminori Iriyama. Probability of error for the fixed-length lossy coding of general sources. IEEE Transactions on Information Theory, 51(4):1498-1507 2005.
[JL84] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space 26. Contemporary mathematics, 26:28, 1984.
- Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132- 5143. PMLR, 2020.
[KLG~21] Lorenz Kuhn, Clare Lyle, Aidan N. Gomez, Jonas Rothfuss, and Yarin Gal. Robustness to Pruning Predicts Generalization in Deep Neural Networks. arXiv:2103.06002 [cs, stat]. March 2021.
[KLN~11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What we learn privately? SIAM Journal Computing, 40(3):793-888 826,88266222 2011.
KMA 19] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. Rafael G. L. D' Olivera,,, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu,
12

---

Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ozgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun. Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, 2019.
[KMY- 16] Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon, Federated learning: Strategies for improving communication efficiency. arXiv preprini arXiv: 1610.0542. 2016.
[LCBI0] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. at&t labs, 2010.
[LM22] Rui Liu and Barzan Mozafari. Communication-effiiieenn distributed learning for large batch optimization. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato, editors. Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13925- 13946. PMLR, 17-23 Jul 2022.
[LSTS20] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learn- ing: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):00-60, 2020.
[Mar74] Katalin Marton. Error exponent for source coding with a fidelity criterion. IEEE Transactions on Information Theory, 20(2):17-1199 1974.
[MMR 17] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--effiieeee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[MSS19] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference Machine Learning, pages
PMLR, 2019.
[MZ21] Matei Moldoveanu and Abdellatif Zaidi. In-network learning for distributed training and inference in networks. In 2021 IEEE Globecom Workshops (GC Wkshps), pages 1-6. IEEE, 2021.
[NHD 20] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy. informationntthoreteee generalization bounds for sgld via data-dependent estimates, 2020.
[P192] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838-88) 855, 1992.
[PVG-11] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
[PW14] Yury Polyanskiy and Yihong Wu. Lecture notes information theory. Lecture Notes for ECE563 (UIUC) and, 6(2012-2016):7, 2014.
[RBKI8] Erwin Riegler, Helmut Böleskei, and Günther Koliander. Rate-distortion theory for general sets and measures. In 20/8 IEEE International Symposium on Information Theory (ISIT), pages 101-105. IEEE, 2018
[RCZ. 20) Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003 2003000990000 2020.
[RZ16] Daniel Russo and James Zou. Controlling bias in adaptive data analysis using infor- mation theory. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1232-1240, Cadiz, Spain, 09-11 May 2016. PMLR
13

---

[SAN20] Tajji Suzuki, Hiroshi Abe. and Tomoaki Nishimura. Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network. In International Conference on Learning Representations, 2020.
[SGRS22] Milad Sefidgaran, Amin Gohari, Gaël Richard, and Umut Simsekli. Rate-distortion theoretic generalization bounds for stochastic learning algorithms. In Conference on Learning Theory, pages 4416-4463. PMLR, 2022.
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[$SDE20] Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5138-5151. Curran Associates, Inc., 2020.
[SZ20] Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437-3452. PMLR, 09-12 Jul 2020.
[Vap06] Vladimir Vapnik. Estimation of dependences based on empirical data. Springer Science & Business Media, 2006.
[VWK-20] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys (CSUR), 53(2):1-33, 2020.
[WHGC21] Hao Wang. Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of sgld using properties of gaussian channels. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 24222 24234. Curran Associates, Inc., 2021.
[WLC22] Yujia Wang, Lu Lin, and Jinghui Chen. Communication-effiiin adaptive federated learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22802-22838. PMLR, 17-23 Jul 2022.
[WT11] Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-1I), pages 681-688 Citeseer, 2011.
[XR17] Aolin Xu and Maxim Raginsky. Information-theoree analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[YAE 18] Timothy Yang. Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXi:: 2018
[YDVP20] Semih Yagli, Alex Dytso, and H. Vincent Poor. Information theoretic bounds on the generalization error and privacy leakage in federated learning. In 2020 IEEE 2 International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1-5, 2020.
[YMNS22] Honglin Yuan, Warren Richard Morningstar, Lin Ning, and Karan Singhal. What do we mean by generalization in federated learning? In International Conference on Learning Representations, 2022.
[YZR21] Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. In International Conference on Machine Learning, pages 2253-122266 PMLR, 2021.
14

---

[ZBH 17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Con- ference on Learning Representations, 2017.
[ZZ15] Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pages 1-9, Lille, France, 07-09 Jul 2015. PMLR.
Checklist
1. For all authors...
i. Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
ii. Did you describe the limitations of your work? [Yes] We establish bounds on the generalization suggesting decreasing behavior with number of clients. However, for a rigorous analytical conclusion, a lower bound also required, which is notoriously a hard problem. iii. Did you discuss any potential negative societal impacts of your work? [N/A] Our work deals with theoretical investigation of the generalization behavior fo the distributed case and their comparison with the corresponding centralized case. We believe this work does not have any potential negative social impact.
iv. Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
i. Did you state the full set of assumptions of all theoretical results? [Yes] Please see Sections 2-5.
ii. Did you include complete proofs all theoretical results? [Yes] The proofs are stated in Appendix D)
3. If you ran experiments...
i. Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URLJ? [Yes] We provided these in the supplementary materials.
ii Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes] These are provided in Appendix B.
ii. Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] This item is not needed in our experiments, as explained in the appendices.
iv. Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provided these in Appendix B.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
i. If your work uses existing assets, did you cite the creators? [Yes]
ii Did you mention the license of the assets? [Yes]
iii. Did you include any new assets either in the supplemental material or as URL? [Yes] The code used for experiments in this paper was made accessible through supplementary materials.
iv. Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use publicly available and non-personal data only. Please
see Appendix B.
Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use publicly available and non non-personal data only. Please see Appendix B.
5. If you used crowdsourcing conducted research with human subjects...
15

---

i. Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] This item applicable for our research.
Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] This item is not applicable for our research.
ii.. Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] This item applicable for our research.
16


Reviews:
[{"review_id": "hpMHSozquvM", "reviewer": "Reviewer_7D8T", "summary": "The paper examines the generalization error of distributed learning using rate-distortion theory and compares the theoretical results with existing information-theoretical generalization bounds. For implication, the theory justifies the advantage of distributed learning by showing that the generalization error of the DSVM decreases with the client number K and is smaller than that of the counterpart centralized learning algorithm.", "questions": "- What if the sub-Gaussian assumption is removed?\n\t- Some work [1] shows that the parameters' distribution is heavy-tailed in multiple settings.\n- What is the advantage of rate-distortion bounds over other generalization bounds (e.g., bounds via algorithmic stability or PAC-Bayes theory), especially in the distributed setting? \n- How tight are the upper bounds derived in the paper? How big is $R_p$ in theorem 2 and theorem 3? Would $R_p$ be prohibitively large for deep complex models? \n- In real-world settings, a fundamental challenge is that data may not be i.i.d.  across the workers. However, the generalization theory of distributed learning algorithms is mainly based on the assumption that the data is i.i.d. over clients. Can the results in this paper be extended to **non-i.i.d.** settings?\n\nReference\n\n[1] Gurbuzbalaban, M., Simsekli, U. &amp; Zhu, L.. (2021). The Heavy-Tail Phenomenon in SGD. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research.\n\n", "limitations": "No negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The writing of the paper is good. The advantage of the technical approach adopted in this paper (i.e., the rate-distortion theory) is well discussed.\n- As mentioned in the paper, previous results do not explicitly consider the structure of the distributed learning problem. The generalization bound derived in this paper is explicitly tailored for the considered distributed setting rather than a direct extension of the previous rate-distortion theoretic generalization bounds.\n- The theory implies exciting and novel results: The generalization error of DSVM decreases with the client number K and is smaller than that of the counterpart centralized learning algorithm.\n\nNo major concerns. \nMinor issue\n- Line 264-265 seem to be missing something.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dMwko3ksAq", "reviewer": "Reviewer_8roe", "summary": "This is an information theoretical paper that considers distributed machine learning problems. New upper bounds on the generalization error of distributed learning algorithms are derived and applied to distributed support vector machines. In particular, a very surprising result is that the generalization error of the distributed SVM decays faster than that of the centralized SVM with a factor of O(log(K)/sqrt(K)), where K is the number of groups the whole data set is distributed.\n\n======================\n\nAfter studying the authors' response, I am happy to see that the background on rate-distortion theory is added, and the typos I found are taken care of. For these updates, I am happy to raise my score to 6.", "questions": "* Line 93, please clarify: is the output of Algorithm A random? That is, given exactly the same set of data and run A twice, would it be possible that A generates different output hypotheses (e.g., for the purpose of differential privacy etc.)? If not, how should we understand the conditional distribution P_{W|S} since it would then be a degenerated trivial distribution? If yes, would the author(s) provide more details on how the infimum between lines 116 and 117 is defined? Also, what is then the motivation of using a random algorithm in this paper?\n* There seems to be one reference item missing in Line 147. Also, I think that the author(s) should declare that the distance d(w;w'|s) is not a distance in the mathematical sense since it lacks symmetry: d(w;w'|s) != d(w';w|s).\n* Line 93, I guess that $\\mathcal{W}\\in\\mathbb{R}^d$ should be $\\mathcal{W}\\subset\\mathbb{R}^d$.\n* Line 117: what is $\\hat{\\mathcal{W}}$?\n* How is a Markov kernel defined?\n* Line 138, is epsilon fixed or random?\n* The assumption in Line 190 (sigma-subGaussian) is very difficult for me to follow. Is there any example of this (example that the assumption holds true, and also an example that the assumption is not true)?\n* It seems that the function \"gen(s,w)\" not only depends on s and w, but also on the loss function, the distribution mu, and the sample size n. In particular, we see that in lines 117--118, the function \"gen\" depends on a new loss function $\\hat{\\ell}$ where it is emphasized that this may be different from $\\ell$. Would it be possible that all the dependent elements be listed explicitly in different places where the function \"gen\" is used?\n* Some long sentences need to be divided into shorter ones. For example the 4-line long sentence in Lines 107-110, the sentence in Lines 211-215, among others.\n* In the definition of RD(Q,epsilon) between lines 116 and 117, what is the relation between $S$ and Q? What is the definition of $\\hat{\\mathcal{W}}$? How is Q deciding $\\hat{W}$? What is the expectation taken with respect to? In particular, if the expectation is taken with respect to all the randomness, by definition E[gen(S,W)]=0, which is trivial. What is the role $W$ plays in the infimum? (See also my comments in the \"Strengths And Weaknesses\" section.)\n* Equation (9), should [K] be [m]?\n* how is the claim \"the generalization error of the distributed setting decays faster than that of the centralized one with a factor of O(log(K)/sqrt(K))\" supported by, e.g., Theorem 5?", "limitations": "There is no negative societal impact observed. The limitations focus on that we doubt if all the claimed results are well supported.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* solid theoretical analysis\n* the results on distributed SVM are very surprising\n\nWeaknesses:\n* one of the key tools used throughout the paper, the function RD, is not defined clearly enough (see comments below in the \"Questions\" section), rendering the whole paper very difficult to follow.\n* From bounds on the generalization error of some machine learning algorithm, readers could expect to quickly find out how the generalization error converges to zero (or not), as the training sample size tends to infinity, or while other variables are changing. However, in this paper, such reading is not easy. For example, in Theorem 2, the right-hand side of the bound contains Rp(delta, epsilon), which is defined in a highly complex way such that even telling whether this quantity would be O(1) is extremely difficult. Theorems 3 and 4 are similar.\n* I am not sure if the claimed results are well supported.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Tdu7vrdg4OH", "reviewer": "Reviewer_HoVj", "summary": "This paper uses tools from rate-distortion theory to establish new generalization error upper bounds for distributed learning algorithms. The bounds depend on the compressibility of each client’s algorithm while keeping other clients’ algorithms un-compressed and leveraging the fact that small changes in each local model change the aggregated model by a factor of only $1/K$, where $K$ is the number of independent clients. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $O(\\sqrt{\\log(K)/K})$.", "questions": "My biggest concern in the paper is comparing the generalization error between distributed and centralized settings. It is stated after Theorem 5 that in expectation bound for $K$ clients, each having $n$ data samples is smaller than that of the counterpart centralized learning algorithm that has $nK$ input data samples by a factor of order $O(\\sqrt{\\log(K)/K})$. However, [BDP22, Theorem 4] states that the improvement is of order $O(1/\\sqrt{K})$, which is even better. Furthermore, it is shown in Appendix B.3.2 that the upper bounds of [BDP22, Theorems 4 & 5] can be recovered as special cases and are subsumed by Theorem 4 in this paper. Thus, I believe that more explanation on the comparisons is needed.\n\nMinor comments:   \n1.\tIn the abstract, it is said that “the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $O(\\log K/\\sqrt{K})$.” I believe that it should be $O(\\sqrt{\\log(K)/K})$ as stated in Theorem 5.   \n2.\tThere is a missing reference in Remark 1 on Line 147.\n\n---------------------\nPost rebuttal:\nThanks for the clarification about the comparison with [BDP22, Theorem 4]. I did not notice the difference in the assumptions. It is a good paper, and I would like to maintain my original rating.\n\n\n", "limitations": "I think the authors addressed the limitations and potential negative societal impact of their work.\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies the generalization error of distributed learning algorithms using a novel tool of rate-distortion theoretic generalization bound developed by [SGRS22], which is sufficiently original. However, it is a bit unsatisfying to me that the results in this paper only tell us that the generalization error of a distributed algorithm is better than its centralized counterparts, but no more discussion on the computational and communication costs, and population risk. To my understanding, these aspects are the main reason to adopt distributed learning algorithms in practice instead of improving the generalization error.\n\nThe organization of the paper can be improved. I feel that some crucial contents are provided only in the Appendix, e.g., empirical validation, results of SGLD, and comparison with related prior art results. The proof details provided in Section 5 are not very informative (basically follows from [SGRS22] and [GKL 20]) and can be replaced by the additional results in Appendix.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept