Cross-Gradient Aggregation for Decentralized Learning from Non-IID data

Yasaman Esfandiari, Sin Yong Tan, Zhanhong Jiang, Aditya Balu, Ethan Herron, Chinmay Hegde, Soumik Sarkar

TL;DR

This paper introduces Cross-Gradient Aggregation (CGA), a novel decentralized learning algorithm designed to overcome the challenge of non-IID (non-independently and identically distributed) data across agents. CGA achieves superior performance on non-IID data by having each agent aggregate "cross-gradients" (derivatives of its model with respect to its neighbors' datasets) and using quadratic programming to project these into an aggregated gradient for updates.

What Problem Does This Paper Address?

Decentralized learning allows multiple agents to collaboratively train a model without a central server. While effective, existing methods often assume that data is IID across all agents. This assumption is frequently violated in real-world scenarios, leading to significant performance degradation. The paper tackles this critical gap by proposing a method that explicitly handles non-IID data distributions, which is a major bottleneck for practical decentralized learning applications.

Methods

The core innovation is the Cross-Gradient Aggregation (CGA) algorithm. Key aspects include:

  • Cross-Gradient Calculation: Each agent computes not only its own local gradient (self-gradient) but also "cross-gradients." These are calculated by evaluating the loss function of a neighbor agent using the current agent's model parameters.
  • Quadratic Programming (QP) Projection: The self-gradient and the aggregated cross-gradients are then fed into a quadratic programming solver. This QP projection finds a descent direction that is simultaneously aligned with the agent's own gradient and positively correlated with all the cross-gradients from its neighbors. This projection is crucial for navigating the complexities introduced by non-IID data.
  • Momentum: A momentum term is incorporated into the update rule to accelerate convergence.
  • Compressed Variant (CompCGA): To address communication overhead, a compressed version of CGA is proposed, utilizing error feedback mechanisms.

Datasets

The authors evaluated their algorithms on:

  • MNIST: A widely used dataset for image classification.
  • CIFAR-10: Another standard image classification dataset, used with both a CNN and a more complex VGG11 architecture.

The non-IID data distributions were created by assigning different classes of data to different agents, representing an extreme form of non-IIDness.

Key Insights and Ideas

  • The Power of Cross-Gradients: The paper highlights that simply averaging local gradients (as in standard decentralized methods) is insufficient for non-IID data. Aggregating "cross-gradients" provides a richer signal about how neighboring models are learning from their local data, which is essential for robust learning.
  • QP as a Navigator: Using quadratic programming to project gradients is a novel approach in this context. It allows for a more sophisticated update direction that balances local learning with information from neighbors, effectively mitigating the negative effects of data heterogeneity.
  • Robustness to Non-IIDness: CGA demonstrates significantly better performance on non-IID data compared to existing state-of-the-art methods, suggesting that its approach to gradient aggregation is more resilient to data distribution shifts.
  • Sparser Topologies Can Be Beneficial: Interestingly, for non-IID data, sparser communication topologies (like ring or bipartite) sometimes led to slightly better final performance than fully connected ones, possibly due to more focused communication and less gradient variance.

Key Results

  • Superior Accuracy on Non-IID Data: CGA consistently achieved higher testing accuracy on both MNIST and CIFAR-10 datasets under various non-IID settings, outperforming DPMSGD, SGP, and SwarmSGD. For example, on CIFAR-10 with 40 agents and non-IID data, CGA achieved accuracies in the range of 40-77%, while other methods often diverged or performed much worse (e.g., DPMSGD diverged, SGP around 11-46%, SwarmSGD around 10-30%).
  • Comparable Performance on IID Data: On IID data, CGA's performance was comparable to or slightly better than existing methods, especially with fewer agents.
  • Theoretical Convergence: The paper provides theoretical analysis showing that CGA achieves convergence rates comparable to the best known for decentralized learning, even under non-IID conditions.
  • CompCGA Effectiveness: The compressed variant, CompCGA, maintained good performance while reducing communication overhead, though slightly less accurate than the uncompressed CGA.

Limitations and Future Work

  • Communication Overhead: The original CGA algorithm has a higher communication cost than some baselines due to the exchange of model parameters and cross-gradients. While CompCGA addresses this, it comes with a slight performance trade-off.
  • Scalability with Sparse Topologies: The authors note that future research will focus on addressing performance reduction in scenarios with a large number of agents communicating over sparse graph topologies. This is an area where CGA's performance might degrade, and further investigation is needed.
  • Complexity of QP: While effective, the QP projection step adds computational complexity at each agent.

Summary updated

Abstract

Decentralized learning enables a group of collaborative agents to learn models using a distributed dataset without the need for a central parameter server. Recently, decentralized learning algorithms have demonstrated state-of-the-art results on benchmark data sets, comparable with centralized algorithms. However, the key assumption to achieve competitive performance is that the data is independently and identically distributed (IID) among the agents which, in real-life applications, is often not applicable. Inspired by ideas from continual learning, we propose Cross-Gradient Aggregation (CGA), a novel decentralized learning algorithm where (i) each agent aggregates cross-gradient information, i.e., derivatives of its model with respect to its neighbors' datasets, and (ii) updates its model using a projected gradient based on quadratic programming (QP). We theoretically analyze the convergence characteristics of CGA and demonstrate its efficiency on non-IID data distributions sampled from the MNIST and CIFAR-10 datasets. Our empirical comparisons show superior learning performance of CGA over existing state-of-the-art decentralized learning algorithms, as well as maintaining the improved performance under information compression to reduce peer-to-peer communication overhead. The code is available here on GitHub.
BibTeX
@inproceedings{esfandiari2021cross,
  author = {Yasaman Esfandiari and Sin Yong Tan and Zhanhong Jiang and Aditya Balu and Ethan Herron and Chinmay Hegde and Soumik Sarkar},
  title = {{Cross-Gradient Aggregation for Decentralized Learning from Non-IID data}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=wLLiAe2eIO},
}
Figure