A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning

• URL: http://arxiv.org/abs/2605.03499v1
• Date: Tue, 05 May 2026 08:35:05 GMT
• Title: A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning
• Abstract summary: We study expected generalization bounds for the Hierarchical Federated Learning (HFL) setup using Wasserstein distance.<n>We derive generalization bounds in terms of Wasserstein distance under the Lipschitz assumption on the loss function.<n>We show that our bound can be applied together with Differential Privacy assumptions, to recover generalization bounds based on privacy.
• Score: 23.580547146143612
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• On Multi-Step Theorem Prediction via Non-Parametric Structural Priors [50.16583672681106]
  In this work, we explore training-free theorem prediction through the lens of in-context learning (ICL)<n>We propose Theorem Precedence Graphs, which encode temporal dependencies from historical solution traces as directed graphs, and impose explicit topological constraints that effectively prune the search space during inference.<n>Experiments on the FormalGeo7k benchmark show that our method achieves 89.29% accuracy, substantially outperforming ICL baselines and matching state-of-the-art supervised models.
  arXiv  Detail & Related papers  (2026-03-05T06:08:50Z)
• Understanding Generalization from Embedding Dimension and Distributional Convergence [13.491874401333021]
  We study generalization from a representation-centric perspective and analyze how the geometry of learned embeddings controls predictive performance for a fixed trained model.<n>We show that population risk can be bounded by two factors: (i) the intrinsic dimension of the embedding distribution, which determines the convergence rate of empirical embedding distribution to the population distribution in Wasserstein distance, and (ii) the sensitivity of the downstream mapping from embeddings to predictions, characterized by Lipschitz constants.
  arXiv  Detail & Related papers  (2026-01-30T09:32:04Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• Tree-Preconditioned Differentiable Optimization and Axioms as Layers [0.0]
  "Axioms-as-Layers" paradigm embeds axiomatic structure of Random Utility Models directly into deep neural networks.<n>"Axioms-as-Layers" paradigm eliminates the structural overfitting inherent in penalty-based methods.
  arXiv  Detail & Related papers  (2025-12-03T04:47:37Z)
• Architecture independent generalization bounds for overparametrized deep ReLU networks [0.9687141267566189]
  We prove that overparametrized neural networks are able to generalize with a test error independent of the level of overparametrization.<n>For overparametrized deep ReLU networks with a training sample size bounded by the input space dimension, we explicitly construct zero loss minimizers without use of gradient descent.
  arXiv  Detail & Related papers  (2025-04-08T05:37:38Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data.<n>We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• A New Family of Generalization Bounds Using Samplewise Evaluated CMI [14.147617330278662]
  We present a new family of information-theoretic generalization bounds, in which the training loss and the population loss are compared through a jointly convex function. We demonstrate the generality of this framework by extending previously known information-theoretic bounds. In some scenarios, this novel bound results in a tighter characterization of the population loss of deep neural networks than previous bounds.
  arXiv  Detail & Related papers  (2022-10-12T17:15:44Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI) Contrary to other CMI bounds, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning.
  arXiv  Detail & Related papers  (2022-07-01T17:58:29Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  We study a constraint-based representation of neural network architectures. We investigate a simple optimization procedure that is well suited to fulfil the so-called architectural constraints.
  arXiv  Detail & Related papers  (2020-02-18T16:47:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.