Many popular distributed optimization methods for training machine learning\nmodels fit the following template: a local gradient estimate is computed\nindependently by each worker, then communicated to a master, which subsequently\nperforms averaging. The average is broadcast back to the workers, which use it\nto perform a gradient-type step to update the local version of the model. It is\nalso well known that many such methods, including SGD, SAGA, and accelerated\nSGD for over-parameterized models, do not scale well with the number of\nparallel workers. In this paper we observe that the above template is\nfundamentally inefficient in that too much data is unnecessarily communicated\nby the workers, which slows down the overall system. We propose a fix based on\na new update-sparsification method we develop in this work, which we suggest be\nused on top of existing methods. Namely, we develop a new variant of parallel\nblock coordinate descent based on independent sparsification of the local\ngradient estimates before communication. We demonstrate that with only $m/n$\nblocks sent by each of $n$ workers, where $m$ is the total number of parameter\nblocks, the theoretical iteration complexity of the underlying distributed\nmethods is essentially unaffected. As an illustration, this means that when\n$n=100$ parallel workers are used, the communication of $99\\%$ blocks is\nredundant, and hence a waste of time. Our theoretical claims are supported\nthrough extensive numerical experiments which demonstrate an almost perfect\nmatch with our theory on a number of synthetic and real datasets.\n