{
  "id": "2104.07365",
  "version": "v1",
  "published": "2021-04-15T10:47:27.000Z",
  "updated": "2021-04-15T10:47:27.000Z",
  "title": "D-Cliques: Compensating NonIIDness in Decentralized Federated Learning with Topology",
  "authors": [
    "Aurélien Bellet",
    "Anne-Marie Kermarrec",
    "Erick Lavoie"
  ],
  "categories": [
    "cs.LG",
    "cs.AI",
    "cs.DC"
  ],
  "abstract": "The convergence speed of machine learning models trained with Federated Learning is significantly affected by non-independent and identically distributed (non-IID) data partitions, even more so in a fully decentralized setting without a central server. In this paper, we show that the impact of local class bias, an important type of data non-IIDness, can be significantly reduced by carefully designing the underlying communication topology. We present D-Cliques, a novel topology that reduces gradient bias by grouping nodes in interconnected cliques such that the local joint distribution in a clique is representative of the global class distribution. We also show how to adapt the updates of decentralized SGD to obtain unbiased gradients and implement an effective momentum with D-Cliques. Our empirical evaluation on MNIST and CIFAR10 demonstrates that our approach provides similar convergence speed as a fully-connected topology with a significant reduction in the number of edges and messages. In a 1000-node topology, D-Cliques requires 98% less edges and 96% less total messages, with further possible gains using a small-world topology across cliques.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-15T10:47:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "decentralized federated learning",
      "compensating noniidness",
      "global class distribution",
      "local class bias",
      "local joint distribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}