Federated SVRG

The defining feature of Federated SVRG is its use of a control variate (or reference gradient) to reduce variance. Each client stores a snapshot of its local gradient computed at a common reference model (e.g., the global model from the start of a communication round). During local training, the client computes the difference between its current stochastic gradient and this stored reference, then adds back the full reference gradient. This variance-reduced update provides a much more stable descent direction than standard SGD, accelerating convergence.

Federated SVRG operates in epochs. At the start of each epoch (or communication round), the server broadcasts the current global model to participating clients. Each client sets this model as its new reference point and computes a full-batch or mini-batch gradient over its local data at this point. This gradient becomes the client's new control variate. This periodic resetting prevents the control variates from becoming stale and ensures they remain correlated with the current global optimization objective.

A major challenge in federated learning is client drift, where local models diverge due to optimization on heterogeneous data. Federated SVRG directly counters this. The control variate acts as an anchor, pulling local updates back towards the global objective. By correcting the local stochastic gradient with the reference gradient, the algorithm ensures that the average update direction across clients is a low-variance estimate of the true global gradient, even when local data distributions differ significantly.

The classic SVRG algorithm assumes frequent access to a full dataset to compute the reference gradient. Federated SVRG modifies this for the decentralized setting:

• Reference Gradient Computation: Clients compute the reference gradient locally using only their own data. The global control variate is implicitly defined as the average of these local references.
• Communication Pattern: The algorithm fits the standard federated round structure: synchronize reference model, compute local control variates, perform multiple local variance-reduced steps, then communicate updates.
• Compatibility: It can be combined with techniques like secure aggregation and gradient compression.

Federated SVRG provides strong theoretical convergence properties under standard assumptions (smoothness, convexity or Polyak-Łojasiewicz condition). Key guarantees include:

• Linear Convergence Rate: For strongly convex objectives, it achieves a linear (geometric) convergence rate, requiring fewer communication rounds than Federated Averaging (FedAvg) to reach a given accuracy.
• Robustness to Heterogeneity: The convergence rate has a weaker dependence on data heterogeneity (non-IID degree) compared to FedAvg, making it particularly suitable for realistic federated scenarios.
• Variance Reduction: The theory formally bounds the gradient variance, explaining its stable performance.

Federated SVRG is closely related to the SCAFFOLD algorithm. Both use control variates to correct for client drift, but with key differences:

• Update Frequency: SCAFFOLD updates its control variates every local step, while Federated SVRG updates them only at epoch boundaries.
• Storage: SCAFFOLD maintains and communicates two sets of variables (model parameters and control variates). Federated SVRG typically only communicates model updates after local epochs.
• Computation: Federated SVRG requires a full pass (or large batch) over local data to compute the new reference gradient at the start of each epoch, which can be more computationally intensive per round but leads to fewer rounds overall.

SCAFFOLD (Stochastic Controlled Averaging for Federated Learning) is a foundational variance reduction algorithm for federated learning. It introduces control variates—correction terms stored on both the server and each client—to explicitly counteract client drift. By estimating the difference between the local and global gradient directions, SCAFFOLD provides a more accurate update, leading to significantly faster convergence than FedAvg under data heterogeneity. Federated SVRG builds upon this core principle of using control variates to reduce gradient variance.

Federated Variance Reduction is a class of optimization techniques adapted from classical machine learning to the decentralized setting. Key methods include:

• SVRG (Stochastic Variance Reduced Gradient): Uses a snapshot of full-batch gradients as a control variate.
• SAGA: Maintains a table of historical gradients for each data point.

These methods reduce the variance of stochastic gradients, which is exacerbated in federated learning due to small local datasets and non-IID data. By providing lower-variance update directions, they require fewer communication rounds to converge, directly addressing the high communication cost of federated systems.

Client Drift is the phenomenon where local client models diverge from the global objective during Local SGD. This occurs because clients perform multiple optimization steps on their own statistically heterogeneous (non-IID) data, causing their local models to move towards their local minima rather than the global one. Drift is a primary cause of slow and unstable convergence in federated learning. Algorithms like Federated SVRG and SCAFFOLD are explicitly designed to mitigate drift by using control variates to correct local update directions, anchoring them closer to the global optimization path.

The FedOpt (Federated Optimization) Framework generalizes the server-side aggregation step of Federated Averaging. Instead of a simple weighted average of client updates, FedOpt applies adaptive optimizer updates (like those used in centralized deep learning) to the global model. Key algorithms in this family include:

• FedAdam: Applies the Adam optimizer to client updates.
• FedYogi: A variant of FedAdam with more stable updates for noisy gradients.
• FedAdagrad: Applies per-parameter adaptive learning rates.

While Federated SVRG focuses on variance reduction on the client-side, FedOpt focuses on adaptive aggregation on the server-side. The two approaches can be complementary.

Local SGD is the fundamental client-side training procedure in federated learning. In each round, each selected client performs E local epochs of standard Stochastic Gradient Descent on its private dataset. The final model update (the difference between the initialized and final local model) is then sent to the server. The choice of E creates a trade-off: more local steps reduce communication frequency but increase client drift. Federated SVRG modifies this core Local SGD loop by incorporating a variance-reduced gradient estimator within the local training process to make each local step more effective.

Heterogeneous Client Optimization refers to strategies designed to handle the inherent variations in federated networks, which include:

• Statistical Heterogeneity (Non-IID Data): Clients have data from different distributions.
• System Heterogeneity: Variations in device hardware, compute power, and network connectivity.

Algorithms like Federated SVRG, FedProx, and SCAFFOLD are specifically engineered for statistical heterogeneity. They may incorporate techniques like proximal terms (FedProx) or control variates (SVRG/SCAFFOLD) to stabilize training. Handling system heterogeneity often involves asynchronous protocols or tiered selection strategies.