2019/02/01 by Anastasia Koloskova, Koloskova, Anastasia, Sebastian U. Stich +3 · 55 citations
Computer Science · #Stochastic Gradient Optimization Techniques #Privacy-Preserving Technologies in Data #Distributed Control Multi-Agent Systems
paper · pdf · doi:10.48550/arxiv.1902.00340
We consider decentralized stochastic optimization with the objective function\n(e.g. data samples for machine learning task) being distributed over n\nmachines that can only communicate to their neighbors on a fixed communication\ngraph. To reduce the communication bottleneck, the nodes compress (e.g.\nquantize or sparsify) their model updates. We cover both unbiased and biased\ncompression operators with quality denoted by \ω \≤ 1 (\ω=1\nmeaning no compression). We (i) propose a novel gossip-based stochastic\ngradient descent algorithm, CHOCO-SGD, that converges at rate\n\O\(1/(nT) + 1/(T \δ2 \ω)2\) for strongly convex\nobjectives, where T denotes the number of iterations and \δ the\neigengap of the connectivity matrix. Despite compression quality and network\nconnectivity affecting the higher order terms, the first term in the rate,\n\O(1/(nT)), is the same as for the centralized baseline with exact\ncommunication. We (ii) present a novel gossip algorithm, CHOCO-GOSSIP, for the\naverage consensus problem that converges in time\n\O(1/(\δ2\ω) \log (1/\ε)) for accuracy \ε >\n0. This is (up to our knowledge) the first gossip algorithm that supports\narbitrary compressed messages for \ω > 0 and still exhibits linear\nconvergence. We (iii) show in experiments that both of our algorithms do\noutperform the respective state-of-the-art baselines and CHOCO-SGD can reduce\ncommunication by at least two orders of magnitudes.\n