Communication compression is an essential strategy for alleviating
communication overhead by reducing the volume of information exchanged between
computing nodes in large-scale distributed stochastic optimization. Although
numerous algorithms with convergence guarantees have been obtained, the optimal
performance limit under communication compression remains unclear.
In this paper, we investigate the performance limit of distributed stochastic
optimization algorithms employing communication compression. We focus on two
main types of compressors, unbiased and contractive, and address the
best-possible convergence rates one can obtain with these compressors. We
establish the lower bounds for the convergence rates of distributed stochastic
optimization in six different settings, combining strongly-convex,
generally-convex, or non-convex functions with unbiased or contractive
compressor types. To bridge the gap between lower bounds and existing
algorithms' rates, we propose NEOLITHIC, a nearly optimal algorithm with
compression that achieves the established lower bounds up to logarithmic
factors under mild conditions. Extensive experimental results support our
theoretical findings. This work provides insights into the theoretical
limitations of existing compressors and motivates further research into
fundamentally new compressor properties.

本文研究了利用通信压缩的分布式随机优化算法的性能上限，并提出了 NEOLITHIC 算法，该算法在温和条件下实现所建立的理论下限。