Large neural network models present a hefty communication challenge to\ndistributed Stochastic Gradient Descent (SGD), with a communication complexity\nof O(n) per worker for a model of n parameters. Many sparsification and\nquantization techniques have been proposed to compress the gradients, some\nreducing the communication complexity to O(k), where k << n. In this paper, we\nintroduce a strategy called two-level gradient averaging (A2SGD) to consolidate\nall gradients down to merely two local averages per worker before the\ncomputation of two global averages for an updated model. A2SGD also retains\nlocal errors to maintain the variance for fast convergence. Our theoretical\nanalysis shows that A2SGD converges similarly like the default distributed SGD\nalgorithm. Our evaluation validates the theoretical conclusion and demonstrates\nthat A2SGD significantly reduces the communication traffic per worker, and\nimproves the overall training time of LSTM-PTB by 3.2x and 23.2x, respectively,\ncompared to Top-K and QSGD. To the best of our knowledge, A2SGD is the first to\nachieve O(1) communication complexity per worker for distributed SGD.\n