Network Gradient Descent Algorithm for Decentralized Federated Learning

Shuyuan Wu, Danyang Huang, Hansheng Wang

Abstract

We study a fully decentralized federated learning algorithm, which is a novel gradient descent algorithm executed on a communication-based network. For convenience, we refer to it as a network gradient descent (NGD) method. In the NGD method, only statistics (e.g., parameter estimates) need to be communicated, minimizing the risk of privacy. Meanwhile, different clients communicate with each other directly according to a carefully designed network structure without a central master. This greatly enhances the reliability of the entire algorithm. Those nice properties inspire us to carefully study the NGD method both theoretically and numerically. Theoretically, we start with a classical linear regression model. We find that both the learning rate and the network structure play significant roles in determining the NGD estimator's statistical efficiency. The resulting NGD estimator can be statistically as efficient as the global estimator, if the learning rate is sufficiently small and the network structure is well balanced, even if the data are distributed heterogeneously. Those interesting findings are then extended to general models and loss functions. Extensive numerical studies are presented to corroborate our theoretical findings. Classical deep learning models are also presented for illustration purpose.

Introduction

Standard Federated Learning (FL) typically relies on a "hub-and-spoke" model where a central server aggregates gradients from various clients. This architecture introduces significant challenges, including privacy risks due to a single point of failure, system fragility if the master server fails, and bandwidth bottlenecks at the central node. Decentralized FL offers a solution by allowing clients to communicate only with their neighbors. However, previous research often relied on restrictive assumptions, such as doubly stochastic communication matrices or perfectly homogeneous data. This paper introduces the Network Gradient Descent (NGD) algorithm to address these limitations under more realistic, heterogeneous conditions.

Theoretical Framework and Comparison

The NGD method involves local gradient descent steps followed by neighborhood averaging. Instead of a central server, each client updates its parameter estimate by taking a weighted average of its "one-hop" neighbors' estimates. A key innovation is the use of a Weakly Balanced Matrix (WBM) for weighting, which is less restrictive than the standard doubly stochastic requirement.

The theoretical analysis focuses on two types of convergence: Numerical Convergence (NCR), which ensures the algorithm reaches a stable solution, and Statistical Convergence (SCR), which measures how close that solution is to the global estimator (the "Gold Standard").

Comparison of the proposed NGD method with existing literature

As shown in the table above, the proposed NGD method distinguishes itself by supporting both homogeneous and heterogeneous data distributions while providing theoretical guarantees for both numerical and statistical convergence under the flexible WBM assumption.

Experimental Validation

The authors validated NGD using simulations (Linear, Logistic, and Poisson regression) and classical benchmarks including MNIST (LeNet architecture) and CIFAR-10 (MobileNet architecture). To test robustness, data was intentionally sorted by labels to create "extremely heterogeneous" environments.

Key Findings

  • Efficiency Parity: The NGD estimator can achieve the same efficiency as global Ordinary Least Squares (OLS) or Maximum Likelihood Estimators (MLE) if the learning rate is small and the network is weakly balanced.
  • Topology Impact: Network structure is critical. Circle-Type Networks are highly efficient due to perfect balance. Fixed-Degree Networks (randomly connected) offer a practical middle ground, becoming highly efficient with at least 6 neighbors per node. Conversely, Star Networks are the least efficient for decentralized learning due to massive imbalance.
  • Heterogeneity Resilience: The algorithm successfully converges to the global optimum even when different clients see entirely different data distributions, provided the network remains well-connected.

Conclusion and Future Work

The NGD algorithm provides a robust, decentralized alternative to traditional FL. While it achieves statistical efficiency comparable to centralized models, it currently assumes synchronous updates. Future research will focus on asynchronous NGD to accommodate "straggler" devices and dynamic learning rate scheduling to better balance the trade-off between convergence speed and final accuracy. Additionally, extending these theoretical proofs to the non-convex landscapes of complex neural networks remains a key objective.

Summary updated

Abstract

We study a fully decentralized federated learning algorithm, which is a novel gradient descent algorithm executed on a communication-based network. For convenience, we refer to it as a network gradient descent (NGD) method. In the NGD method, only statistics (e.g., parameter estimates) need to be communicated, minimizing the risk of privacy. Meanwhile, different clients communicate with each other directly according to a carefully designed network structure without a central master. This greatly enhances the reliability of the entire algorithm. Those nice properties inspire us to carefully study the NGD method both theoretically and numerically. Theoretically, we start with a classical linear regression model. We find that both the learning rate and the network structure play significant roles in determining the NGD estimator's statistical efficiency. The resulting NGD estimator can be statistically as efficient as the global estimator, if the learning rate is sufficiently small and the network structure is well balanced, even if the data are distributed heterogeneously. Those interesting findings are then extended to general models and loss functions. Extensive numerical studies are presented to corroborate our theoretical findings. Classical deep learning models are also presented for illustration purpose.
BibTeX
@article{wu2022network,
  author = {Shuyuan Wu and Danyang Huang and Hansheng Wang},
  title = {{Network Gradient Descent Algorithm for Decentralized Federated Learning}},
  journal = {Journal of Business and Economic Statistics},
  year = {2022},
  doi = {10.1080/07350015.2022.2074426},
}
Figure