Linear Speedup in Federated Optimization

44 concepts40 papers1 proposal

When we scale up machine learning training from a single machine to a distributed network, our primary goal is efficiency. Ideally, if we increase the number of participating clients by a factor of $K$, the time or number of iterations required to reach a target accuracy should decrease by that same factor of $K$. This ideal scaling behavior is known as a linear speedup.

In centralized parallel training, achieving a linear speedup is straightforward because it is driven by variance reduction. When $K$ independent workers compute stochastic gradients in parallel, averaging those gradients reduces the variance of the estimator by $1/K$. In a Federated Learning (FL) environment, however, maintaining this linear speedup is exceptionally difficult. Clients do not just compute gradients in parallel; they perform multiple local updates on non-identically distributed (non-IID) data and communicate over unreliable, resource-constrained networks.

Understanding why a linear speedup can still be achieved—and how different algorithms preserve it across complex optimization landscapes—requires looking at how distributed systems balance variance reduction against client drift and gradient bias.

The Geometric Bottleneck of Heterogeneity

The core tension in federated optimization is between local computation and global alignment. To save communication bandwidth, clients perform multiple local steps of Stochastic Gradient Descent (SGD) before sending their updates back to a central server. Because each client's local data distribution is different, their models naturally drift toward local minima rather than the global optimum.

This client drift introduces a geometric bottleneck. As Charles demonstrates, when client data is highly heterogeneous, the updates computed by different clients can become nearly orthogonal to one another. When the server averages these orthogonal updates, their norms cancel out and shrink by a factor of $\sqrt{K}$ rather than scaling cleanly by $K$. This geometric cancellation leads to diminishing returns as more clients are added to a training round.

To overcome this bottleneck and preserve a linear speedup, algorithms must exploit structural properties of the model or introduce explicit bias-correction mechanisms. For example, Song et al. show that if a multi-layer neural network is sufficiently overparameterized, the global optimization landscape becomes highly favorable. This architectural overparameterization allows vanilla Federated Averaging (FedAvg) to overcome data heterogeneity and converge exponentially fast to zero training loss.

Alternatively, researchers can mathematically correct for the bias introduced by local steps. Mangold et al. provide a refined analysis showing that if the number of local updates is properly constrained, the systemic bias introduced by data heterogeneity decreases inversely with the number of participating clients. This ensures that scaling the network directly translates into a linear speedup in model accuracy.

Scaling Minimax and Saddle-Point Problems

The challenge of maintaining a linear speedup intensifies when moving beyond standard loss minimization to minimax optimization. Minimax frameworks are essential for competitive objectives, such as training Generative Adversarial Networks (GANs), optimizing fair classifiers, or building models with adversarial robustness. In these settings, parameters are optimized to find a saddle point rather than a local minimum, meaning updates can easily oscillate or diverge.

Proving that a distributed system can achieve a linear speedup for non-convex minimax problems is a major theoretical hurdle. Without strict coordination, local updates for the player maximizing the objective can drift completely out of sync with the player minimizing it. Sharma et al. and Wu et al. resolved this by proving that distributed minimax processes can scale efficiently, reducing the total sample complexity and iteration count proportionally to the number of active clients.

To sustain this speedup when clients possess highly heterogeneous data and varying hardware capabilities, algorithms must actively prevent gradient distortion:

  • Update Normalization: Sharma et al. demonstrate that normalizing client updates based on the actual amount of local work performed prevents the global model from drifting toward a biased objective.
  • Gradient Tracking: Sun et al. utilize a gradient-tracking scheme to eliminate the variance caused by client heterogeneity entirely, allowing constant stepsizes to achieve fast, linear convergence to the exact global saddle point.

Modern machine learning paradigms frequently involve nested mathematical structures. These include bilevel optimization (where an outer optimization task depends on the solution of an inner task, as seen in meta-learning and hyperparameter tuning) and compositional optimization (where the objective is a function of another function, such as maximizing the Area Under the Curve (AUC) on highly imbalanced datasets).

In these scenarios, computing a clean stochastic gradient is impossible because the outer gradient is inherently biased by the incomplete solution of the inner problem. This bias threatens to destroy the $1/K$ variance reduction that drives the linear speedup.

Standard Optimization:       Loss = f(w)          -> Unbiased Gradients
Compositional Optimization:  Loss = f( g(w) )     -> Biased Gradients (Inner function g must be estimated)
Bilevel Optimization:        Loss = f( w, v*(w) ) -> Biased Gradients (Inner optimum v* must be tracked)

To maintain scaling efficiency despite this gradient bias, federated algorithms must simultaneously track and update both the inner and outer variables. Huang et al. and Yang et al. proved that federated bilevel optimization can achieve a linear speedup even under realistic client sampling conditions. To make these methods practical for resource-constrained devices, Zhang et al. developed a fully first-order gradient framework that eliminates the need for expensive second-order Hessian matrices while retaining the linear convergence speedup.

For deep compositional problems like AUC maximization, the data coupling across different nodes can be severe. Guo et al. show that an active-passive decomposition can decouple these pairwise risks across machines without sharing raw data, preserving the linear speedup. Furthermore, Gao as well as Zhang et al. and Zhang et al. leverage recursive stochastic gradient methods to handle multi-level nested functions, proving that expanding the worker pool successfully compresses the training duration for highly complex compositional models.

Robustness to Real-World System Constraints

In mathematical theory, clients are often treated as idealized processors that participate uniformly and communicate perfectly. In reality, federated systems operate over messy wireless networks where clients have irregular participation, limited battery life, and restricted bandwidth. If a linear speedup requires perfect synchronization, it will fail in practice due to stragglers and communication overhead.

The strength of modern federated optimization theory lies in its ability to maintain the linear speedup while accommodating these real-world constraints:

Irregular Participation and Selection

When some clients participate far more frequently than others, the global model can become heavily biased. Wang et al. show that tracking participation history and applying adaptive weighting weights can correct this bias on the fly, preserving the linear speedup even with highly irregular client availability. From a system-level perspective, Pandey et al. demonstrate that linear-complexity admission control algorithms can select optimal cohorts efficiently, ensuring that large-scale crowdsourcing frameworks remain scalable as the client pool grows.

Hardware and Network Heterogeneity

Devices with weaker processors take longer to complete local steps, creating a bottleneck. Xiao et al. address this by allowing devices to dynamically scale their local learning rates based on available computing power, maintaining a linear speedup despite imbalanced updates. When communicating over non-ideal wireless channels, Shi et al. prove that the linear speedup can be sustained even under quantization noise and transmission outages, provided that bandwidth and quantization levels are managed jointly to ensure uniform outage probabilities.

Non-Smoothness, Compression, and Exploding Gradients

The mathematical guarantees of linear speedup have also been extended to handle aggressive algorithmic optimizations and unstable loss landscapes:

  • Adaptive and Non-Smooth Optimizers: Shen et al. demonstrate that federated adaptive optimizers (like Adam) can achieve a linear speedup when amended locally. For non-smooth regularizers (such as $L_1$ norms), Bao et al. preserve the speedup by leveraging a dual-averaging scheme combined with a multi-stage homotopy strategy.
  • Communication Compression: To save bandwidth, updates must be compressed. Chen et al. prove that distributed algorithms can combine aggressive communication compression with gradient perturbation to escape saddle points in non-convex landscapes, all while maintaining a linear speedup relative to the number of workers.
  • Unbounded Smoothness: When training models like Recurrent Neural Networks (RNNs) where gradients can explode, Crawshaw et al. show that combining historical state-tracking with an episodic clipping strategy successfully safeguards the linear speedup.

Ultimately, the reason linear speedup works across these diverse settings is that the underlying mechanism remains robust: as long as an algorithm can prevent local client drift from permanently distorting the global update direction, aggregating updates across a larger pool of devices will always act as a powerful variance reducer, accelerating convergence and driving down total training time.

Key Foundational Work

Distributionally Robust Federated Averaging (2020) — contributed 1 concept elements to this direction.
Network delay-aware load balancing in selfish and cooperative distributed systems (2012) — contributed 1 concept elements to this direction.
A Crowdsourcing Framework for On-Device Federated Learning (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_speedup_in_federated_learning_28e40f33,
  title = {linear speedup in federated learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-speedup-in-federated-learning/rdr_28e40f3360aa45569926763fbec16e5a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_speedup_in_federated_learning_28e40f33_v1,
  title = {linear speedup in federated learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-speedup-in-federated-learning/rdr_28e40f3360aa45569926763fbec16e5a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake