Foundations and Formal Taxonomy of Federated Learning

The tension between data privacy and machine learning progress has emerged as one of the most critical challenges of our decade. Regulations like the GDPR and CCPA have codified the principle that personal data should remain under the control of the data subject, while the economic and scientific value of collective AI training has never been higher. This fundamental conflict gave rise to federated learning (FL), a paradigm that reimagines the machine learning pipeline by decoupling model training from centralized data aggregation. However, the term "federated learning" is often used loosely, conflating distinct technical approaches and obscuring crucial design trade-offs. This chapter establishes a rigorous, formal foundation for the field, cutting through the hype to provide a precise taxonomy and analytical framework that will structure the entire book. We begin by defining FL not merely as a technique, but as a *system design principle*: a distributed approach to machine learning where multiple entities (clients) collaboratively train a shared model under the coordination of a central server or through a decentralized protocol, while keeping their local data decentralized and private. This definition immediately distinguishes FL from generic distributed learning by its explicit privacy mandate and from other privacy-preserving paradigms like differential privacy (DP) or secure multi-party computation (MPC), which are often *components* of an FL system rather than the system itself. Consider a hospital consortium aiming to train a diagnostic AI without sharing patient records. A naive distributed approach might simply parallelize gradient computation but still transmit raw gradients to a central node, failing the privacy test. Pure DP would add noise to queries but might degrade utility excessively. FL, in contrast, orchestrates local training on private data, exchanges only model updates (often encrypted or compressed), and aggregates them into a global model—the data never leaves its source.

To navigate the FL landscape systematically, we introduce a three-dimensional taxonomy that categorizes every design decision. The first dimension concerns data partitioning, which dictates the statistical relationship between clients' local datasets and the global learning objective. Horizontal federated learning (HFL) applies when clients share the same feature space but have disjoint sample spaces—think of different hospitals collecting patient records with identical lab tests but on different populations. Formally, for client $k$ with local dataset $\mathcal{D}_k = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n_k}$, we have $\mathcal{X}_k = \mathcal{X}$ and $\mathcal{Y}_k = \mathcal{Y}$ for all $k$, but $\mathcal{D}_k \cap \mathcal{D}_l = \emptyset$ for $k \neq l$. The global objective is $\min_w \sum_{k=1}^K \frac{|\mathcal{D}_k|}{|\mathcal{D}|} F_k(w)$, where $F_k(w) = \frac{1}{|\mathcal{D}_k|} \sum_{(\mathbf{x},y) \in \mathcal{D}_k} f(w; \mathbf{x}, y)$. Vertical federated learning (VFL) arises when clients possess the same sample IDs but different feature spaces—for instance, a bank and an e-commerce company sharing customers but with disjoint financial and behavioral data. Here, $\mathcal{X}_k \neq \mathcal{X}_l$ generally, but the sample sets overlap. The challenge shifts to feature alignment and gradient computation across partitioned features, often requiring cryptographic techniques like homomorphic encryption to compute gradients on aligned samples without revealing feature values. Federated transfer learning (FTL) extends VFL to scenarios with neither overlapping samples nor identical feature spaces, requiring representation learning to align embeddings—for example, training a disease predictor in one country using data from another country with different demographics and medical coding systems. This dimension is not merely academic; it determines the very feasibility of collaboration. Two hospitals using different diagnostic codes cannot engage in HFL without expensive feature engineering, but might succeed via VFL if they share overlapping patient cohorts.

The second dimension is system architecture, which defines the communication topology and aggregation logic. The centralized architecture, epitomized by the original FedAvg algorithm, employs a central server that selects clients, broadcasts the global model, receives local updates, and performs aggregation. Its simplicity belies profound implications: the server is a single point of failure and a privacy bottleneck, as it observes all model updates. Decentralized (or peer-to-peer) architectures eliminate this central server; clients communicate directly, often using gossip protocols or consensus algorithms like Byzantine fault tolerance. A client $i$ might update its model as $w_i^{t+1} = w_i^t - \eta \nabla F_i(w_i^t) + \sum_{j \in \mathcal{N}_i} a_{ij}(w_j^t - w_i^t)$, where $\mathcal{N}_i$ are neighbors and $a_{ij}$ are weights. This enhances robustness and can reduce communication latency in certain topologies but complicates convergence analysis and requires careful neighbor selection. Hierarchical architectures blend both, organizing clients into groups (e.g., by geography or organization) with local aggregators that first compute cluster-level models before updating the global model. This mirrors real-world structures like multinational corporations with regional data centers and is essential for scaling to millions of devices while respecting data sovereignty laws that restrict cross-border data flow.

The third dimension is participation model, which characterizes the client population. Cross-silo FL involves a small number (dozens to hundreds) of powerful, stable institutions (hospitals, banks) with rich, static datasets. Training can be synchronous, communication is relatively cheap, and the focus shifts to rigorous privacy guarantees and handling statistical heterogeneity (non-IID data). Cross-device FL involves millions of resource-constrained mobile devices with intermittent availability, small local updates, and extreme data heterogeneity (each user's data is highly unique). Here, the primary engineering challenges are client selection, straggler mitigation, and communication efficiency. A hybrid cross-community model is emerging, where a few cross-silo entities coordinate numerous cross-device participants—for instance, a hospital (silo) leveraging data from its patients' wearable devices.

These three dimensions interact in non-trivial ways, creating a vast design space. A cross-silo VFL scenario with decentralized architecture, for instance, might use secret sharing to compute gradients across vertically partitioned features without a central aggregator, but at the cost of increased computation. Understanding these interactions is the first step toward intentional system design.

Beneath this taxonomy lies the fundamental trilemma of FL: the inescapable trade-off among statistical efficiency (model accuracy, convergence speed), communication efficiency (rounds, bits transmitted), and privacy/security guarantees (formal leakage bounds, robustness to attacks). Improving one often degrades another. Consider local training: increasing the number of local epochs before communication (to reduce communication rounds) can lead to *client drift* in non-IID settings, harming statistical efficiency. Model compression techniques like quantization or sparsification save bandwidth but introduce approximation errors that may require more rounds to converge. Differential privacy (DP) adds calibrated noise to updates, shrinking the privacy budget $\varepsilon$ but also shrinking the useful signal, again hurting accuracy. Secure aggregation using MPC protects updates from a curious server but multiplies communication overhead. This trilemma is not a flaw but a fundamental constraint arising from the distributed, privacy