Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems

We develop two compression based stochastic gradient algorithms to solve a class of non-smooth strongly convex-strongly concave saddle-point problems in a decentralized setting (without a central server). Our first algorithm is a Restart-based Decentralized Proximal Stochastic Gradient method with Compression (C-RDPSG) for general stochastic settings. We provide rigorous theoretical guarantees of C-RDPSG with gradient computation complexity and communication complexity of order O( (1+δ)4 frac1L2kappaf2kappag2 frac1ε ), to achieve an ε-accurate saddle-point solution, where δ denotes the compression factor, kappaf and kappag denote respectively the condition numbers of objective function and communication graph, and L denotes the smoothness parameter of the smooth part of the objective function. Next, we present a Decentralized Proximal Stochastic Variance Reduced Gradient algorithm with Compression (C-DPSVRG) for finite sum setting which exhibits gradient computation complexity and communication complexity of order O left((1+δ) max kappaf2, √δkappa2fkappag,kappag logleft(frac1εright) right). Extensive numerical experiments show competitive performance of the proposed algorithms and provide support to the theoretical results obtained.