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

Decentralized learning often breaks down when data is distributed unevenly across agents (non-IID). This paper introduces Cross-Gradient Aggregation (CGA), a novel algorithm that uses "cross-gradients"—how one agent's model performs on a neighbor's data—and quadratic programming to find update directions that satisfy the entire neighborhood. This approach leads to significantly better performance and stability in highly heterogeneous data environments.

The Challenge of Non-IID Data

In traditional Federated Learning, a central server orchestrates the training of a global model. Decentralized learning removes this bottleneck, allowing agents (like mobile phones or edge sensors) to learn collaboratively by communicating only with their immediate neighbors.

However, there is a major catch: most decentralized algorithms assume that data is IID (Independently and Identically Distributed). In the real world, data is almost always non-IID. For example, one camera in a security network might only see cars, while another only sees pedestrians. When data is this lopsided, standard decentralized methods suffer from "consensus error"—local models diverge so sharply that averaging them leads to a mediocre model that performs poorly for everyone.

Introducing Cross-Gradient Aggregation (CGA)

To tackle this, the authors propose Cross-Gradient Aggregation (CGA). Inspired by techniques in continual learning (where models try to learn new tasks without forgetting old ones), CGA fundamentally changes how agents update their parameters.

Overview of the Cross-Gradient Aggregation process

The CGA process operates in a few key steps:

  1. Cross-Gradient Computation: In each iteration, an agent doesn't just calculate its own gradient. It receives the model parameters from its neighbors and calculates how their models would perform on its local data. This is the "cross-gradient."
  2. Quadratic Programming (QP) Projection: Instead of simply averaging gradients, CGA treats the update as an optimization problem. It uses QP to find a single gradient direction that is as close as possible to the local gradient while remaining "positively correlated" with all the cross-gradients from the neighborhood. Essentially, it finds a direction that helps the local agent without hurting its neighbors.
  3. CompCGA for Efficiency: Recognizing that swapping models and gradients is communication-heavy, the authors also introduce a compressed version (CompCGA) that uses signed gradients and error feedback to reduce the number of bits transmitted without sacrificing much accuracy.

Experimental Setup

The researchers evaluated CGA and CompCGA on standard computer vision benchmarks, including MNIST and CIFAR-10. To simulate real-world difficulty (the "Non-IID Twist"), they partitioned the data such that each agent only held 1 or 2 specific classes (e.g., Agent A only has "trucks," Agent B only has "frogs").

Key Insights and Results

Most algorithms try to force models to be identical. CGA, instead, focuses on making sure the update direction is beneficial for the whole neighborhood's data distribution. While standard decentralized SGD uses linear averaging, CGA’s QP-based projection is non-linear, allowing it to navigate conflicting gradients that would otherwise cancel each other out.

Accuracy comparison of CGA against baselines across different topologies and agent counts

The experimental results highlight several major advantages:

  • Superior Accuracy: On non-IID CIFAR-10 with 5 agents, CGA achieved 68.4% accuracy, outperforming state-of-the-art methods like SwarmSGD (67.3%) and SGP (66.4%).
  • Stability in Extremes: In the most difficult non-IID scenarios, the standard baseline (DPMSGD) often diverged (failed to learn entirely), while CGA remained stable and reached high accuracy.
  • Robustness to Topology: CGA is remarkably robust across different network shapes (Fully-connected, Ring, or Bipartite). Interestingly, sparser networks (like Rings) sometimes converged faster because they reduced the "noise" of too many conflicting updates at once.
  • Efficiency and Speedup: CGA reached lower loss values in fewer communication rounds compared to its competitors. The authors also theoretically proved and empirically showed that CGA achieves a "linear speedup," meaning training time decreases proportionally as more agents are added. Even the compressed version, CompCGA, maintained a significant lead over non-compressed baselines.

Limitations and Future Work

  • Communication Overhead: Even with compression, CGA is "chatty." It requires agents to send model parameters to neighbors and then receive gradients back from them. This two-way exchange is more demanding than simple gossip protocols.
  • Synchronicity: The current theoretical analysis assumes all agents are perfectly synchronized. In real-world edge computing, some agents are slower than others ("stragglers"), and future work needs to address how CGA handles asynchronous updates.
  • Scalability: While tested with up to 40 agents, the computational cost of solving a QP at every step for every agent might become a bottleneck in massive networks with thousands of nodes.

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 algorith...
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