We analyze asynchronous-type algorithms for distributed SGD in the
heterogeneous setting, where each worker has its own computation and
communication speeds, as well as data distribution. In these algorithms,
workers compute possibly stale and stochastic gradients associated with their
local data at some iteration back in history and then return those gradients to
the server without synchronizing with other workers. We present a unified
convergence theory for non-convex smooth functions in the heterogeneous regime.
The proposed analysis provides convergence for pure asynchronous SGD and its
various modifications. Moreover, our theory explains what affects the
convergence rate and what can be done to improve the performance of
asynchronous algorithms. In particular, we introduce a novel asynchronous
method based on worker shuffling. As a by-product of our analysis, we also
demonstrate convergence guarantees for gradient-type algorithms such as SGD
with random reshuffling and shuffle-once mini-batch SGD. The derived rates
match the best-known results for those algorithms, highlighting the tightness
of our approach. Finally, our numerical evaluations support theoretical
findings and show the good practical performance of our method.

异步类型算法在异构设置中被分析，提出了统一的收敛理论，并介绍了基于工人洗牌的新型异步方法，数值评估支持理论发现并展示了该方法的良好实际性能。

AsGrad: 异步 SGD 算法的锐利统一分析

AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms

It is well understood that client-master communication can be a primary
bottleneck in Federated Learning. In this work, we address this issue with a
novel client subsampling scheme, where we restrict the number of clients
allowed to communicate their updates back to the master node. In each
communication round, all participating clients compute their updates, but only
the ones with "important" updates communicate back to the master. We show that
importance can be measured using only the norm of the update and give a formula
for optimal client participation. This formula minimizes the distance between
the full update, where all clients participate, and our limited update, where
the number of participating clients is restricted. In addition, we provide a
simple algorithm that approximates the optimal formula for client
participation, which only requires secure aggregation and thus does not
compromise client privacy. We show both theoretically and empirically that for
Distributed SGD (DSGD) and Federated Averaging (FedAvg), the performance of our
approach can be close to full participation and superior to the baseline where
participating clients are sampled uniformly. Moreover, our approach is
orthogonal to and compatible with existing methods for reducing communication
overhead, such as local methods and communication compression methods.

本文通过一种新的客户端子采样方案解决联邦学习中客户端 — 主节点通信的瓶颈问题，并提供了适用于分布式随机梯度下降和联邦平均等方法的简单算法，可优化客户端参与度，且不危害客户隐私，从而在减少通信开销的同时实现了准确的全局模型更新。

联邦学习的最优客户采样

Optimal Client Sampling for Federated Learning

In this paper, we propose a unified analysis of variants of distributed SGD
with arbitrary compressions and delayed updates. Our framework is general
enough to cover different variants of quantized SGD, Error-Compensated SGD
(EC-SGD) and SGD with delayed updates (D-SGD). Via a single theorem, we derive
the complexity results for all the methods that fit our framework. For the
existing methods, this theorem gives the best-known complexity results.
Moreover, using our general scheme, we develop new variants of SGD that combine
variance reduction or arbitrary sampling with error feedback and quantization
and derive the convergence rates for these methods beating the state-of-the-art
results. In order to illustrate the strength of our framework, we develop 16
new methods that fit this. In particular, we propose the first method called
EC-SGD-DIANA that is based on error-feedback for biased compression operator
and quantization of gradient differences and prove the convergence guarantees
showing that EC-SGD-DIANA converges to the exact optimum asymptotically in
expectation with constant learning rate for both convex and strongly convex
objectives when workers compute full gradients of their loss functions.
Moreover, for the case when the loss function of the worker has the form of
finite sum, we modified the method and got a new one called EC-LSVRG-DIANA
which is the first distributed stochastic method with error feedback and
variance reduction that converges to the exact optimum asymptotically in
expectation with a constant learning rate.

本文提出了一种统一的分析分布式 SGD 各种变体的方法，涵盖了不同的量化 SGD、误差补偿 SGD 和延迟更新 SGD 变体，并通过一个定理推导了其所有方法的复杂度结果。在此基础上，我们开发了 16 种新的方法，其中包括第一种基于误差反馈和梯度差分量化的 EC-SGD-DIANA 方法和第一种具有误差反馈和方差缩减的分布式随机方法 EC-LSVRG-DIANA。

线性收敛误差补偿 SGD

Linearly Converging Error Compensated SGD

Communication-efficient SGD algorithms, which allow nodes to perform local
updates and periodically synchronize local models, are highly effective in
improving the speed and scalability of distributed SGD. However, a rigorous
convergence analysis and comparative study of different communication-reduction
strategies remains a largely open problem. This paper presents a unified
framework called Cooperative SGD that subsumes existing communication-efficient
SGD algorithms such as periodic-averaging, elastic-averaging and decentralized
SGD. By analyzing Cooperative SGD, we provide novel convergence guarantees for
existing algorithms. Moreover, this framework enables us to design new
communication-efficient SGD algorithms that strike the best balance between
reducing communication overhead and achieving fast error convergence with low
error floor.

本文提出了一个统一的框架 —— 合作 SGD (Cooperative SGD)，它包含了现有的高效通信 SGD 算法，如周期平均、弹性平均和分散 SGD。通过分析 Cooperative SGD，我们为现有算法提供了新的收敛保证。此外，该框架使我们能够设计新的高效通信 SGD 算法，以在降低通信开销和实现低误差下的快速误差收敛之间取得最佳平衡。