Research map / Optimization / Implicit bias and generalization

Convergence Analysis of Federated Learning Methods Using Backward Error Analysis

AAAI 2025 · Optimization › Implicit bias and generalization · approach: Implicit regularization of SGD · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Uses backward error analysis to derive implicit regularizers of FedAvg, FedSAM and SCAFFOLD on non-IID data, explaining FedAvg's dispersion-induced bias and the partial/complete bias removal by FedSAM and SCAFFOLD.

Problem

Explaining why federated learning methods (FedAvg, FedSAM, SCAFFOLD) converge differently on non-IID data, where convex-optimization convergence analyses are loose or hard to make tight in non-convex settings.

Approach

Extends implicit regularization / backward error analysis from centralized GD/SGD to federated local-SGD-based methods, deriving a modified loss for each algorithm; the FedAvg modified loss contains a "dispersion term" that increases client-gradient variance, which FedSAM partially and SCAFFOLD fully remove at first order.

Key results

• FedAvg without the dispersion term converges faster and matches SGD and SCAFFOLD on MNIST and FEMNIST, with much lower client gradient variance.
• Switching FedSAM's epsilon to E*eta/2 mid-training on MNIST and Fashion-MNIST made it converge faster than the original FedSAM, which stayed below E*eta/2.
• On CIFAR-10 with Dirichlet 0.05, SCAFFOLD is close to SGD but still inferior, indicating high-order terms remain a bias.

Measured effects reported in the paper

Surprising findings

• Reducing client gradient variance does not improve performance; the bias from the implicit regularizer, not gradient noise, is the main cause of FedAvg's slowdown.
• SGD has higher gradient variance than FedAvg without the dispersion term yet converges faster.

Limitations

• Analysis requires a learning rate small enough that high-order terms are negligible, an assumption that is extreme in practice.
• Full client participation assumed for the main derivations; partial participation only treated in the appendix.
• Secondary (higher-order) analysis relies on approximations such as a >> 1 and expectation-level paths.

Experimental setup

Datasets: MNIST FEMNIST Fashion-MNIST CIFAR-10

Benchmarks: MNIST FEMNIST Fashion-MNIST CIFAR-10

Metrics: test accuracy client gradient variance mini-batch gradient variance

Baselines: FedAvg SCAFFOLD FedSAM SGD

Builds on: implicit regularization of SGD backward error analysis FedAvg FedSAM SCAFFOLD

Closest papers by meaning

• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients (NeurIPS 2021 · similarity 0.89)
• Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.89)
• A New Theoretical Perspective on Data Heterogeneity in Federated Optimization (ICML 2024 · similarity 0.87)
• FedQS: Optimizing Gradient and Model Aggregation for Semi-Asynchronous Federated Learning (NeurIPS 2025 · similarity 0.86)
• Improving Generalization in Federated Learning with Model-Data Mutual Information Regularization: A Posterior Inference Approach (NeurIPS 2024 · similarity 0.86)
• Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.86)