Foundations of Federated Learning: Motivation, History, and Problem Setting

Chapter 1: Foundations of Federated Learning: Motivation, History, and Problem Setting

1.1 The Data-Lake Assumption and Its Quiet Collapse

For two decades, the dominant mental model of machine learning infrastructure was a siphon: raw data flows from a multitude of edge systems into a single, well-funded "data lake," where it is cleaned, joined, and fed to increasingly large models. This mental model underwrote the success of search-ranking systems, ad click prediction, recommender systems, and the first wave of deep learning breakthroughs in computer vision and natural language processing. The siphon is still, today, the most common way to train a model. It is also, increasingly, the wrong way.

Three forces have made centralized collection less attractive as a default. The first is legal. After the European Union's General Data Protection Regulation came into force in May 2018, the California Consumer Privacy Act followed in 2020, China's Personal Information Protection Law in November 2021, and a thickening braid of sector-specific rules such as HIPAA in the United States, the ePrivacy framework in the EU, and India's Digital Personal Data Protection Act, the legal cost of moving personal data has risen substantially. Each of these regimes imposes some combination of purpose limitation, data minimization, lawful basis for processing, and—most importantly for machine learning—restrictions on cross-border transfer. The 2020 *Schrems II* ruling by the Court of Justice of the European Union invalidated the EU–US Privacy Shield and made standard contractual clauses harder to rely on, materially raising the cost of "spin up a cluster in Virginia and pull European user data into it." A 2023 EU–US Data Privacy Framework exists, but its durability is itself uncertain. The legal landscape is not stable; it is in motion, and engineering decisions made in 2020 are already being re-evaluated in 2025.

The second force is commercial. The very organizations that historically pooled data—banks, insurers, telecom operators, hospital systems, large retailers—now regard their data as a competitive moat. A regional bank no longer hands its transaction ledger to a credit-scoring vendor; the bank's data is the moat, and a model trained on it is the most valuable output. Industrial data from factories, telemetry from fleets of vehicles, clickstreams from e-commerce platforms: in nearly every vertical, the people who own the data have learned that sending it to someone else's server is giving away the asset while keeping the liability. The rise of "data clean rooms" and privacy-enhancing technologies is, in part, an attempt to square this circle. Federated learning is another.

The third force is technical, and it is the one most often overlooked. There are settings in which centralized collection is not merely inadvisable but impossible. A modern smartphone generates a continuous stream of keystrokes, sensor readings, and app usage patterns, but the bandwidth, battery cost, and user-experience cost of streaming all of this to a server is prohibitive and unnecessary if the model can be improved on device. A hospital MRI scanner produces gigabytes of imaging data per patient, but the cost of uploading, deduplicating, and storing the corpus for thousands of patients is a non-trivial budget line. In many industrial control systems, raw signals never leave the plant floor because the latency of round-tripping them is incompatible with real-time control. In these settings, the data lake is not a policy choice; it is a physical impossibility.

These three forces—legal, commercial, technical—do not always pull in the same direction, but they converge on a single observation: a meaningful class of machine learning problems must now be solved *without* the data leaving its origin. The interesting question is how. Federated learning is the most prominent and most thoroughly engineered answer to that question, and the rest of this book is about the engineering that makes it work.

1.2 A Formal Statement of the Federated Learning Problem

Federated learning is best introduced as a constrained optimization problem, because the constraints are what make it interesting. Let there be $N$ clients, indexed $i = 1, \ldots, N$, and a coordinating server (sometimes called the *aggregator* or the *coordinator*). Each client $i$ holds a local dataset $\mathcal{D}_i$ of size $n_i = |\mathcal{D}_i|$, drawn from a local data distribution $\mathcal{P}_i$ that may differ from client to client. The total data volume is $n = \sum_i n_i$. A model is parameterized by a vector $w \in \mathbb{R}^d$, and each client defines a local loss

$$ F_i(w) \;=\; \mathbb{E}_{(x, y) \sim \mathcal{D}_i}\big[\ell(w; x, y)\big], $$

where $\ell$ is a sample-level loss such as cross-entropy or squared error. The *federated objective* is the weighted average of local objectives, with weights proportional to the local data sizes:

$$ \min_{w \in \mathbb{R}^d}\; F(w) \;=\; \sum_{i=1}^{N} p_i\, F_i(w), \qquad p_i \;=\; \frac{n_i}{n}. $$

The reader should immediately notice what is missing from the problem statement: the server never sees $\mathcal{D}_i$. The server only sees what clients choose to upload, and the protocol specifies what that is. In the canonical algorithm introduced by McMahan et al. (2017), the protocol is *Federated Averaging* (FedAvg). At the start of round $t$, the server broadcasts the current model $w_t$ to a sampled subset of clients. Each sampled client computes one or more local stochastic gradient steps, producing an updated local model $w_t^{(i)}$, and uploads it. The server aggregates the updates,

$$ w_{t+1} \;=\; \sum_{i \in \mathcal{S}_t} p_i\, w_t^{(i)}, $$

and broadcasts again. The protocol is simple; the engineering is not. The remainder of this section unpacks the choices that the formal statement leaves implicit.

The communication model. Federated learning is a *communication-bounded* optimization problem. Uploading a model with $d$ parameters costs at least $d \times |\text{float32}|$ bytes per client per round, and a single round of training may require many such uploads. The bandwidth budget, the client availability, and the heterogeneity of network conditions are first-class concerns. Federated training proceeds in *rounds* rather than *steps*; this shift in vocabulary is itself a clue that the bottleneck is the network, not the arithmetic.

Synchrony assumptions. The simplest analysis assumes *synchronous* rounds: every round waits for a fixed number of clients to upload before aggregating. This is unrealistic in cross-device settings where clients disconnect, lose connectivity, or run on drained batteries. *Asynchronous* variants allow the server to incorporate each update as it arrives. Asynchrony reduces wall-clock time but introduces staleness: an update computed against a stale $w_t$ is biased with respect to the current $w_{t'}$. The FedAsync, FedBuff, and similar algorithms quantify this bias and propose corrections.

Client sampling and participation. In cross-device settings, only a small fraction of clients are online in any given round, and the server cannot force participation. The algorithm must be robust to the fact that the set of contributing clients $\mathcal{S}_t$ is itself a random variable, possibly correlated with the data the clients hold. A medical app whose heaviest users are sicker will produce a sampled client population that is not representative. The mathematics of this *participation bias* is subtle and is taken up in Chapter 3.

Local computation vs. communication. Each client may take multiple local steps between communication events. If $E$ local steps are taken before the next upload, the communication cost per round is amortized over $E$ gradient evaluations, but local progress in any one direction can drift away from the global objective. The hyperparameter $E$ trades communication efficiency for client drift, and the