Modern distributed training relies heavily on communication compression to
reduce the communication overhead. In this work, we study algorithms employing
a popular class of contractive compressors in order to reduce communication
overhead. However, the naive implementation often leads to unstable convergence
or even exponential divergence due to the compression bias. Error Compensation
(EC) is an extremely popular mechanism to mitigate the aforementioned issues
during the training of models enhanced by contractive compression operators.
Compared to the effectiveness of EC in the data homogeneous regime, the
understanding of the practicality and theoretical foundations of EC in the data
heterogeneous regime is limited. Existing convergence analyses typically rely
on strong assumptions such as bounded gradients, bounded data heterogeneity, or
large batch accesses, which are often infeasible in modern machine learning
applications. We resolve the majority of current issues by proposing EControl,
a novel mechanism that can regulate error compensation by controlling the
strength of the feedback signal. We prove fast convergence for EControl in
standard strongly convex, general convex, and nonconvex settings without any
additional assumptions on the problem or data heterogeneity. We conduct
extensive numerical evaluations to illustrate the efficacy of our method and
support our theoretical findings.

本文研究了在现代分布式训练中，使用一种受欢迎的压缩算法类来减少通信开销，提出了一种新的机制 EControl，以调节误差补偿并证明其在标准凸性、一般凸性和非凸性等设置下的快速收敛性。

EControl: 基于压缩和误差控制的快速分布式优化

EControl: Fast Distributed Optimization with Compression and Error  Control

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 算法，该算法在温和条件下实现所建立的理论下限。

分布式随机优化中的下限与通信压缩加速算法

Lower Bounds and Accelerated Algorithms in Distributed Stochastic  Optimization with Communication Compression

Modern large-scale machine learning applications require stochastic
optimization algorithms to be implemented on distributed compute systems. A key
bottleneck of such systems is the communication overhead for exchanging
information across the workers, such as stochastic gradients. Among the many
techniques proposed to remedy this issue, one of the most successful is the
framework of compressed communication with error feedback (EF). EF remains the
only known technique that can deal with the error induced by contractive
compressors which are not unbiased, such as Top-$K$. In this paper, we propose
a new and theoretically and practically better alternative to EF for dealing
with contractive compressors. In particular, we propose a construction which
can transform any contractive compressor into an induced unbiased compressor.
Following this transformation, existing methods able to work with unbiased
compressors can be applied. We show that our approach leads to vast
improvements over EF, including reduced memory requirements, better
communication complexity guarantees and fewer assumptions. We further extend
our results to federated learning with partial participation following an
arbitrary distribution over the nodes, and demonstrate the benefits thereof. We
perform several numerical experiments which validate our theoretical findings.

本文提出了一种新的构造方法，可以将任何收缩压缩器转化为感应无偏压缩器，从而大大减少了内存要求，提高了通信复杂性保证和使用的方法，特别是在对合同收缩压缩器进行处理时，相对错误反馈（EF）有更好的理论和实践效果。