SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Optimization
Navjot Singh, Deepesh Data, Jemin George, Suhas Diggavi
Abstract
In this article, we propose and analyze SParsified Action Regulated Quantized–Stochastic Gradient Descent (SPARQ-SGD), a communication-efficient algorithm for decentralized training of large-scale machine learning models over a graph with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> nodes, where communication efficiency is achieved using <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">compressed</i> exchange of local model parameters among neighboring nodes, which is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">triggered</i> only when an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">event</i> (a locally computable condition) is satisfied. Specifically, in SPARQ-SGD, each node takes a fixed number of local gradient steps and then checks if the model parameters have significantly changed compared to its last update; only when the change is beyond a certain threshold (specified by a design criterion), it compresses its local model parameters using both quantization and sparsification and communicates them to its neighbors. We prove that SPARQ-SGD converges as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(\frac{1}{nT})$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(\frac{1}{\sqrt{nT}})$</tex-math></inline-formula> in the strongly convex and nonconvex settings, respectively, matching the convergence rates of plain decentralized SGD. This demonstrates that we get communication efficiency achieved by aggressive compression, local iterations, and event-triggered communication essentially for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">free</i> . We evaluate SPARQ-SGD over real datasets to demonstrate significant amount of savings in communication over the state-of-the-art while achieving similar performance.