{
  "annotation_id": "d7b9c513-824a-4e28-8318-cb485f1a2c0d",
  "date_created": "2026-02-17T05:53:08.660000Z",
  "date_modified": "2026-02-17T05:53:08.660000Z",
  "file_hash": "422801e2e644104716d8ab21fbdb4502bea2a03cabe95b02746fe1326d19d7a9",
  "private": false,
  "record": {
    "abstract": "We propose a novel analysis of the Decentralized Stochastic Gradient Descent (DSGD) algorithm with constant step size, interpreting the iterates of the algorithm as a Markov chain. We show that DSGD converges to a stationary distribution, with its bias, to first order, decomposable into two components: one due to decentralization (growing with the graph\u0027s spectral gap and clients\u0027 heterogeneity) and one due to stochasticity. Remarkably, the variance of local parameters is, at the first-order, inversely proportional to the number of clients, regardless of the network topology and even when clients\u0027 iterates are not averaged at the end. As a consequence of our analysis, we obtain non-asymptotic convergence bounds for clients\u0027 local iterates, confirming that DSGD has linear speed-up in the number of clients, and that the network topology only impacts higher-order terms.",
    "arxiv_id": "2601.07021",
    "authors": [
      "Lucas Versini",
      "Paul Mangold",
      "Aymeric Dieuleveut"
    ],
    "categories": [
      "cs.LG"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "Tight Analysis of Decentralized SGD: A Markov Chain Perspective",
    "url": "https://arxiv.org/abs/2601.07021",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "41db7985-7c51-4be2-a06c-169429cbc246",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}