Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective

Masoud Kavian † \>{}^{\dagger} ∤ \>{}^{\nmid} Romain Chor † \>{}^{\dagger} ∤ \>{}^{\nmid} Milad Sefidgaran ∤ {}^{\>\nmid} Abdellatif Zaidi † \>{}^{\dagger} ∤ {}^{\>\nmid} · 2025

Read Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective by Masoud Kavian † \>{}^{\dagger} ∤ \>{}^{\nmid} Romain Chor † \>{}^{\dagger} ∤ \>{}^{\nmid} Milad Sefidgaran ∤ {}^{\>\nmid} Abdellatif Zaidi † \>{}^{\dagger} ∤ {}^{\>\nmid} (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01598.txt.

Introduction

Masoud Kavian, Romain Chor, Milad Sefidgaran, and Abdellatif Zaidi proved that mismatched client data hurts distributed learning more than expected in a 2025 paper. In one-round federated learning, many clients each train on their own samples, drawn from possibly different distributions, and a server averages their models. The authors measure how the discrepancy between client distributions inflates the generalization error of that averaged model, deriving expectation and tail bounds in terms of the distributions themselves.

The bounds extend the conditional mutual information framework from single-machine learning to any number of clients, and a detour through rate-distortion theory yields possibly tighter lossy versions. Applied to distributed classification, the theory quantifies the price of heterogeneity precisely. Data diversity across clients, the message goes beyond folklore, is a first-order term in the error budget.

Catalog record

CREATORMasoud Kavian † \>{}^{\dagger} ∤ \>{}^{\nmid} Romain Chor † \>{}^{\dagger} ∤ \>{}^{\nmid} Milad Sefidgaran ∤ {}^{\>\nmid} Abdellatif Zaidi † \>{}^{\dagger} ∤ {}^{\>\nmid}
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE141 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01598

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective Masoud Kavian † \>{}^{\dagger} ∤ \>{}^{\nmid} Romain Chor † \>{}^{\dagger} ∤ \>{}^{\nmid} Milad Sefidgaran ∤ {}^{\>\nmid} Abdellatif Zaidi † \>{}^{\dagger} ∤ {}^{\>\nmid} Abstract In this paper, we investigate the effect of data heterogeneity across clients on the performance of distributed learning systems, i.e., one-round Federated Learning, as measured by the associated generalization error. Specifically, K K clients have each n n training samples generated independently according to a possibly different data distribution, and their individually chosen models are aggregated by a central server. We study the effect of the discrepancy between the clients’ data distributions on the generalization error of the aggregated model. First, we establish in-expectation and tail upper bounds on the generalization error in terms of the distributions. In part, the bounds extend the popular Conditional Mutual Information (CMI) bound, which was developed for the centralized learning setting, i.e., K = 1 K=1 , to the distributed learning setting with an arbitrary number of clients K ≥ 1 K\geq 1 . Then, we connect with information-theoretic rate-distortion theory to derive possibly tighter lossy versions of these bounds. Next, we apply our lossy bounds to study the effect of data heterogeneity across clients on the generalization error for the distributed classification problem in which each client uses Support Vector Machines (DSVM). In this case, we establish explicit generalization error bounds that depend explicitly on the data heterogeneity degree. It is shown that the bound gets smaller as the degree of data heterogeneity across clients increases, thereby suggesting that DSVM generalizes better when the dissimilarity between the clients’ training samples is bigger. This finding, which goes beyond DSVM, is validated experimentally through several experiments. MnLargeSymbols’164 MnLargeSymbols’171 I Introduction Amajor 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 emergence of new applications in which resources are constrained, data is distributed, or the need to preserve privacy. Examples of such algorithms include the now popular Federated Learning [ 1 , 2 , 3 ] , the Split Learning of [ 4 ] , or the so-called in-network learning of [ 5 , 6 ] . Some of these algorithms enable collaborative training across multiple devices by distilling knowledge (features) locally, i.e., without sharing the raw data. This has given rise to privacy-preserving machine learning [ 7 , 8 ] and has led to rapid advancements in communication-efficient and privacy-aware distributed learning algorithms, such ass differential privacy mechanisms [ 9 , 10 , 11 ] . Despite its importance, however, little is known about the generalization guarantees of distributed statistical learning algorithms, including a lack of proper definitions [ 3 , 12 , 13 , 8 ] . Notable exceptions include the related works [ 14 , 15 , 16 , 17 , 18 , 19 ] and [ 20 ] or the works [ 21 , 22 , 23 ] which essentially adapt classical bounds to account for partitioned data and constrained communication [ 21 , 22 , 23 ] using PAC-Bayes theory. The lack of understanding of what really controls generalization in distributed learning settings is even more pronounced when the (training) data exhibits some degree of heterogeneity across participating clients or devices. That is, when the underlying probability distributions (if there exist such distributions!) vary across those clients. From an algorithmic perspective, works appeared that combine personalized federated learning with clustered training methods in an attempt to adapt models to heterogeneous data across clients while maintaining collaborative learning benefits [ 24 , 25 , 26 ] . In essence, these approaches strike a balance between global model performance and local data specificities. Also, compression and sparsification strategies were proposed and shown to partly alleviate the effect of data heterogeneity [ 27 , 28 , 29 ] . The question of the effect of data heterogeneity on the performance of statistical learning algorithms is not yet fully understood from a theoretical perspective, however. This is true even from a convergence rate analysis viewpoint, a line of work that is more studied comparatively. For example, while it has been reported that non-independently and/or non-identically distributed (non-IID) data slow down convergence in FL-type algorithms [ 30 , 31 , 32 ] , optimal rates are still unknown in general; and, how that slowness relates to the behavior of the generalization error is yet to be un-explored. Fig. 1 : Studied distributed learning problem In this paper, we study the distributed learning system shown in Fig. 1 . Here, there are K clients; each having access to a training dataset S_{k}=\{Z_{k,1},\dots,Z_{k,n}\}\in\mathcal{Z}^{n} of size n , where the data samples \{Z_{k,1},\dots,Z_{k,n}\} are generated independently from each other and other clients’ training samples according to a probability distribution \mu_{k} . The probability distributions \{\mu_{k}\}_{k=1}^{K} are possibly distinct, i.e., heterogeneous across clients. In the special case in which \mu_{k}=\mu for all k=1,\ldots,K , we will refer to the setting as being homogeneous . Client k applies a possibly stochastic learning algorithm A_{k}:\mathcal{Z}^{n}_{k}\rightarrow\mathcal{W}_{k} . This induces a conditional distribution P_{W_{k}|S_{k}} , which together with \mu_{k} induce the joint dataset-hypothesis distribution P_{W_{k},S_{k}}=\mu_{k}^{\otimes n}P_{W_{k}|S_{k}} . The server receives (W_{1},\ldots,W_{K}) and picks the hypothesis \overline{W} as the arithmetic average \overline{W}=\frac{1}{K}\sum\limits_{k=1}^{K}W_{k}. (1) We investigate the effect of the discrepancy between the clients’ data distributions on the generalization performance of the aggregated model \overline{W} . In particular, for given loss function \ell:\mathcal{Z}\times\mathcal{W}\to[0,1] used to evaluate the quality of the prediction and a proper definition of the generalization error (see formal definitions in Section II ), we ask the following question: How does the generalization error of the aggregated model \overline{W} evolve as a function of a measure of discrepancy between the data distributions \mu_{1},\ldots,\mu_{K} ? I-A Main contributions The main contributions of this paper are as follows: • We establish (general) in-expectation and tail upper bounds on the generalization error in terms of the distributions (\mu_{1},\ldots,\mu_{K}) . In part, the bounds extend the Conditional Mutual Information (CMI) bound, which was developed for the centralized learning, i.e., K=1 in [ 33 ] , to the distributed learning setting of Fig. 1 . • We use a connection between the theory of generalization of statistical learning algorithms and information-theoretic rate-distortion theory that was introduced in [ 17 ] and subsequently used and elaborated on in [ 34 , 35 , 36 ] , to obtain possibly tighter lossy versions of these bounds. Furthermore, we also provide improved bounds that are based on the Jensen-Shannon divergence. • We apply our established lossy bounds to study the effect of data heterogeneity across clients on the generalization error for a distributed classification problem in which each client uses Support Vector Machines (SVM). In this case, we establish in-expectation generalization bounds that depend explicitly on the degree of data heterogeneity across clients; and, by comparing them, we show that the bounds get better (i.e., smaller) as the degree of data heterogeneity across clients increases. Also, the bounds increase as the total variation between the distributions becomes smaller. • We report experimental results that validate the theoretical results of this paper in various settings. This involves

Read the complete text