FedNova

Standard FedAvg minimizes a weighted sum of local objectives, but when clients perform different numbers of local SGD steps, the global stationary point diverges from the true target. FedNova identifies this as objective inconsistency and corrects it by normalizing each client's pseudo-gradient before aggregation, ensuring the global model converges to the true empirical risk minimizer regardless of heterogeneous local computation budgets.

The core mechanism replaces simple weighted averaging with a normalized averaging operator. For each client k, the local update is scaled by a factor τ_eff (effective step size) that accounts for:

• Number of local epochs performed
• Local learning rate and momentum settings
• Batch size used during local training

This ensures clients that perform more local work do not disproportionately bias the global model update direction.

FedNova generalizes to support advanced local optimizers:

• FedNova-Prox: Incorporates a proximal term identical to FedProx, stabilizing convergence on non-IID clinical data while maintaining normalization benefits
• FedNova-Momentum: Extends the framework to clients using SGD with momentum, correctly accounting for the accumulated velocity term in the normalization factor

Both variants preserve the unbiased convergence guarantee of the base algorithm.

In asynchronous federated settings, updates arrive with varying staleness (delay between local computation and server aggregation). FedNova naturally extends to handle staleness by adjusting the normalization factor based on the age of each update, preventing stale gradients from corrupting the global model. This makes it robust for cross-device FL where mobile or edge devices may have intermittent connectivity.

FedNova provides rigorous non-asymptotic convergence analysis proving:

• Linear speedup: Convergence rate improves proportionally with the number of clients
• Bounded client drift: The normalization factor prevents unbounded divergence from the global optimum
• Smooth non-convex objectives: Guarantees hold for standard deep neural network loss landscapes

These proofs establish FedNova as a principled alternative to heuristic weighted averaging.

FedNova requires no additional communication overhead compared to standard FedAvg. The normalization is performed entirely on the server side using metadata already available:

• Number of local steps taken by each client
• Local learning rate configuration

This makes it a backward-compatible upgrade for existing federated learning deployments in healthcare networks, requiring no changes to client-side training pipelines.