Towards Tight Communication Lower Bounds for Distributed Optimisation

This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the N machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that (Ndlog d/N") total bits need to be communicated between the machines to find an additive -approximation to the minimum of P