Abstract

Large-scale distributed training of neural networks is often limited by network bandwidth, wherein the communication time overwhelms the local computation time. Motivated by the success of sketching methods in sub-linear/streaming algorithms, we introduce S KETCHED -SGD4 , an algorithm for carrying out distributed SGD by communicating sketches instead of full gradients. We show that S KETCHED -SGD has favorable convergence rates on several classes of functions. When considering all communication – both of gradients and of updated model weights – S KETCHED SGD reduces the amount of communication required compared to other gradient compression methods from where d is the number of model parameters and W is the number of workers participating in training. We run experiments on a transformer model, an LSTM, and a residual network, demonstrating up to a 40x reduction in total communication cost with no loss in final model performance. We also show experimentally that S KETCHED -SGD scales to at least 256 workers without increasing communication cost or degrading model performance.