A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning Dario Filatrella, Ragnar Thobaben, and Mikael Skoglund Abstract We study expected generalization bounds for the Hierarchical Federated Learning (HFL) setup using Wasserstein distance. We introduce a generalized framework in which data is sampled hierarchically, and we model it with a multi-layered tree structure that induces dependencies among the clients’ datasets. We derive generalization bounds in terms of Wasserstein distance under the Lipschitz assumption on the loss function, by applying a supersample construction that allows us to measure the sensitivity of the algorithm to the change of a single node in the sampling tree. By leveraging the FL structure, we recover and strictly imply existing state-of-the-art conditional mutual information (CMI) bounds in the case of bounded losses. We also show that our bound can be applied together with Differential Privacy assumptions, to recover generalization bounds based on algorithmic privacy. To assess the tightness of our bounds, we study the Gaussian Location Model (GLM) and show that we recover the actual asymptotic rate of the generalization error . I Introduction Federated Learning (FL) is a machine learning setting where multiple clients (or nodes) collaboratively train a global model [ 6 ] . The term was introduced in 2016 by [ 11 ] , where the authors present the challenges and motivations of training models in a distributed manner, and propose the FedAvg algorithm. The two main motivations to train models in a distributed fashion are: (i) to distribute training resources for models that are exceptionally large and (ii) to distribute datasets in the case of privacy concerns or communication constraints. Motivation (i) is an engineering driven motivation, and for further details, we refer to [ 24 ] and [ 13 ] , which provide frameworks for training DNNs in a distributed manner. Motivation (ii) is what we aim to address with the random participation of clients. The idea of having a complex hierarchical data source, with non i.i.d. points, first appeared in classical statistics, specifically in the field of sampling techniques, when, in 1965, Kish introduced the concept of design effect and effective sample size [ 9 ] . There exist many classical references on sampling techniques, such as [ 3 ] . These results predate the modern learning theory framework, and aim to measure the heterogeneity of the data through variance-like quantities and indicators, such as the intraclass correlation coefficient , which are not compatible with modern learning theory approaches based on complexity measures and information theory. While generalization bounds for supervised learning (SL) could be applied, as the FL setup can be seen as a "black box" SL setup, they would lose the leverage of the FL structure, and, in some cases, they might also incur in clashing assumptions due to the non-i.i.d. nature of the data. Despite those reasons calling for the development of generalization bounds tailored for FL, the literature on this topic remains in its early stages. In our work, we primarily address motivation (ii), leaving flexibility to incorporate constraints about the computational power of each node. Our main contributions are: • A generalized framework that encompasses hierarchical sampling strategies and previous Federated Learning frameworks as special cases. • A generalization bound in terms of Wasserstein distance that holds for a wide range of loss functions and, in particular, is tighter than previous state-of-the-art CMI bounds for bounded losses. • A generalization bound under privacy assumptions on the local algorithms. • A case study of the Gaussian Location Model (GLM), where we show how our bound compares to the known generalization error. The remainder of the paper is organized as follows:. Section II reviews the related literature on FL and generalization bounds. Section III introduces the notation and our framework. Section IV presents our main results, including both Wasserstein distance bounds, Differential Privacy bounds, and a discussion on the implications of our results. Then, Section V presents the case study of the GLM. Finally, we include the proofs of every result and additional discussions in the appendix. II Related work II-A Generalization theory The literature for generalization bounds in the centralized setting is extensive, and dates back to the 70s and 80s starting with the PAC learning framework [ 17 ] and the Vapnik-Chervonenkis dimension [ 18 ] . Those approaches are based on the complexity of the hypothesis class, and, thanks to [ 22 ] , we know that those classical complexity measures are not sufficient to explain the generalization of modern deep learning models, where the number of parameters is often much larger than the number of training samples and the learning algorithms play a key role in the generalization performance. Subsequently, a new theory based on information measures was developed, with results such as [ 20 ] , where the authors established a bound in terms of information measures between the data and the output hypothesis of the learning algorithm, and has been improved numerous times, for example, in [ 2 ] . In 2020 [ 16 ] introduced the conditional mutual information (CMI) framework and the supersample construction, which we build upon in this work. This approach has yielded tighter bounds and has been extended to a larger class of losses using f -divergences and phi -divergences [ 4 ] and [ 5 ] . Of particular interest for our work is [ 14 ] which introduced a new approach based on Wasserstein distance, which implies the CMI bound as a special case for bounded losses. The Wasserstein distance is particularly interesting for its connection with optimal transportation and its ability to capture the geometry of the distributions [ 15 ] . II-B Federated Learning Due to the recency of FL, with the first ideas of training local models and averaging them appearing in [ 10 ] for the perceptron model, studies of the generalization performance of FL algorithms started to emerge in the literature only recently [ 21 ] , with the introduction of the concept of participation gap and Out-of-sample gap , which provide the foundations for our contributions. In this early work, both theoretical bounds and empirical measurements are provided for the two gaps, using common image classification datasets. Following this work, [ 8 ] introduces a hierarchical Bayesian structure with personalized models for each client. They prove a convergence rate and a generalization bound for a locally convex model, with the latter being a very strong limitation. An important aspect of FL is the communication structure, often summarized by the number of communication rounds (i.e. the number of times the nodes are allowed to exchange information). In the special case of the single round or one-shot setting, it is possible to derive specialized generalization bounds [ 12 , 23 ] . In [ 1 ] the authors introduce a mutual information bound for generic FL algorithms and then specialize it to the case of models that can be represented as Bregman divergences, including a bound with communication constraints and multi-round algorithms. In [ 7 ] the authors show that the generalization errors is lower when clients data sources are more heterogeneous, in the case of averaging local models, but their limitations are related to the lack of leverage of the FL structure, which we discuss further when showing how to recover their bounds as a special case of our framework. Overall, there is a lack of unified frameworks for FL that can ecompass different sampling strategies and communication structures. III Preliminaries III-A Notation We use capital letters for random variables (e.g., X ) and lowercase letters for their realizations (e.g., x ). We denote the distribution of a random variable X as P_{X} , and the conditional distribution of Y given X as P_{Y|X} . We denote the Wasserstein-1 distance between two distributions P and Q as \mathbb{W}(P,Q) (unless specified otherwise, we will always refer to the Wasserstein-1 distance). We use the notation i_{a:b} to denote the sequence of indices from a to b , i.e., i_{a},i_{a+1},\ldots,i_{b} . When writing \sum_{i_{l}^{1:l}} we mean the sum over all valid indices of "length" l , as understood from context. Whenever x_{i} is a sequence of object, we denote x to be the ordered collection of all the objects and |x| to be the number of objects in the sequence. When writing P\circ Q we mean the composition of the kernels, while P\otimes Q means the product distribution. We use P^{\otimes n} to denote the product distribution of n independent copies of P . III-B Hierarchical Federated Learning setup The Hierarchical Federated Learning setup is a supervised learning problem, where \mathcal{Z} is the data space, \mathcal{W} is the hypothesis space, and \ell:\mathcal{W}\times\mathcal{Z}\to\mathbb{R} is the loss function. We denote the dataset by \mu and the learning algorithm by P_{W|\mu} , which is a (not necessarily) random kernel that maps the dataset to a distribution over hypotheses. The federated nature of the setup is modeled by (i) the sampling structure of the dataset \mu and (ii) the assumptions on the algorithm P_{W|\mu} . In particular, our dataset \mu is indexed by a tree with a fixed topology that represents a hierarchical sampling strategy, hence the name. Given the constraints, we can index the nodes of the tree by their depth and position in the tree as follows: each node is indexed as \mu_{l}^{i_{1:l}} where l is the depth of the node and i_{1:l} is the position of the node in the tree as a sequence of positions of its ancestors (i.e. i_{1},i_{1:2},\ldots,i_{1:l-1} are the ancestors of i_{1:l} ). We also define L to be the depth of the tree. D \mu_{1}^{1} \mu_{2}^{1,1} \mu_{2}^{1,2} \mu_{2}^{1,n_{2}} \mu_{1}^{2} \mu_{2}^{2,1} \mu_{2}^{2,2} \mu_{2}^{2,n_{2}} \mu_{1}^{n_{1}} \vdots \cdots \cdots \cdots Fig. 1: Hierarchical sampling structure Formally the sampling is as follows: the first layer’s nodes are sampled i.i.d. from a meta-distribution D , meaning \mu_{1}^{i_{1}}\sim D for all i_{1} . For the lower layers we have \mu_{l}^{i_{1:l}}\sim\mu_{l-1}^{i_{1:l-1}}. (1) Consequently, \mu_{L}^{i_{1:L}}\in\mathcal{Z} is a data point, \mu_{L-1}^{i_{1:L-1}} is a distribution over data points, and so on. We can then write the sampling of a single data point as \mu_{L}\sim\mu_{L-1}\sim\cdots\sim\mu_{1}\sim D , where \mu_{l} is a random variable that takes values in the set of nodes at depth l . For simplicity we will also shorten the previous notation to \mu_{L}\sim\mu_{1} to indicate the whole chain of sampling from L to 1 . The intuitive motivation behind this dataset construction is the following: the leaves represent the actual data points, while the intermediate nodes represent clients or clusters, which are also assumed to be random, and in this setting they are indentified as distributions over the lower nodes (i.e. a cluster is a distribution over clients, a client is a distribution over data points). Regarding the algorithmic assumptions, our main results hold for a general kernel P_{W|\mu} that takes as input the whole tree without imposing any constraint (such as privacy mechanisms or communication constraints). Of course, such bounds can only get tighter when restricting to a smaller class of algorithms, but we are still able to recover the bounds of [ 19 ] and [ 7 ] . Their constraints consist of imposing each client to only communicate an hypothesis W_{l}^{i_{1:l}}\in\mathcal{W} to the parent node, which will then only act as an aggregation rule , which can be modeled by a Markov chain. In section IV-B we will explore such setting, and derive generalization bounds under privacy assumptions. For technical reasons discussed in the proof of Theorem 3 , we also assume constant branching factor at each layer, i.e. we assume that at layer l each node \mu_{l}^{i_{1:l}} has n_{l+1} children \mu_{l+1}^{i_{1:l+1}} . We can then denote N_{l}=\prod_{k=1}^{l}n_{k} as the number of nodes at depth l . Remark 1 . While the hypothesis W clearly depends on the intermediate nodes \mu_{l}^{i_{1:l}} for l