Distributed Subgradient Method With Random Quantization and Flexible Weights: Convergence Analysis

The distributed subgradient (DSG) method is a widely used algorithm for coping with large-scale distributed optimization problems in machine-learning applications. Most existing works on DSG focus on ideal communication between cooperative agents, where the shared information between agents is exact and perfect. This assumption, however, can lead to potential privacy concerns and is not feasible when wireless transmission links are of poor quality. To meet this challenge, a common approach is to quantize the data locally before transmission, which avoids exposure of raw data and significantly reduces the size of the data. Compared with perfect data, quantization poses fundamental challenges to maintaining data accuracy, which further impacts the convergence of the algorithms. To overcome this problem, we propose a DSG method with random quantization and flexible weights and provide comprehensive results on the convergence of the algorithm for (strongly/weakly) convex objective functions. We also derive the upper bounds on the convergence rates in terms of the quantization error, the distortion, the step sizes, and the number of network agents. Our analysis extends the existing results, for which special cases of step sizes and convex objective functions are considered, to general conclusions on weakly convex cases. Numerical simulations are conducted in convex and weakly convex settings to support our theoretical results.