# Convergence Theory of Generalized Distributed Subgradient Method with Random Quantization

arXiv: https://arxiv.org/abs/2207.10969 · HTML: https://mlsanity.com/paper/2207.10969/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 23 references that are in the map.
- First posted on arXiv 22 Jul 2022.

## Builds on (most cited first, 8 of 8)

- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2110.09993/) (2021)
- [Wireless Communications with Unmanned Aerial Vehicles: Opportunities and Challenges](https://mlsanity.com/paper/1602.03602/) (2016)
- [An Exact Quantized Decentralized Gradient Descent Algorithm](https://mlsanity.com/paper/1806.11536/) (2018)
- [Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems](https://mlsanity.com/paper/2011.05082/) (2020)
- [Decentralized Non-Convex Learning with Linearly Coupled Constraints](https://mlsanity.com/paper/2103.05378/) (2021)
- [Early Stopping for Nonparametric Testing](https://mlsanity.com/paper/1805.09950/) (2018)

## Built on by (most cited first, 1 of 1)

- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)

## Abstract (arXiv)

The distributed subgradient method (DSG) is a widely discussed algorithm to cope with large-scale distributed optimization problems in the arising machine learning applications. Most exisiting works on DSG focus on ideal communication between the cooperative agents such that the shared information between agents is exact and perfect. This assumption, however, could lead to potential privacy concerns and is not feasible when the wireless transmission links are not of good quality. To overcome the challenge, a common approach is to quantize the data locally before transmission, which avoids exposure of raw data and significantly reduces the size of data. Compared with perfect data, quantization poses fundamental challenges on loss of data accuracy, which further impacts the convergence of the algorithms. To settle the problem, we propose a generalized distributed subgradient method with random quantization, which can be intepreted as a two time-scale stochastic approximation method. We provide comprehensive results on the convergence of the algorithm and derive upper bounds on the convergence rates in terms of the quantization bit, stepsizes and the number of network agents. Our results extend the existing results, where only special cases are considered and general conclusions for the convergence rates are missing. Finally, numerical simulations are conducted on linear regression problems to support our theoretical results.