Federated learning (FL), as an emerging edge artificial intelligence
paradigm, enables many edge devices to collaboratively train a global model
without sharing their private data. To enhance the training efficiency of FL,
various algorithms have been proposed, ranging from first-order to second-order
methods. However, these algorithms cannot be applied in scenarios where the
gradient information is not available, e.g., federated black-box attack and
federated hyperparameter tuning. To address this issue, in this paper we
propose a derivative-free federated zeroth-order optimization (FedZO) algorithm
featured by performing multiple local updates based on stochastic gradient
estimators in each communication round and enabling partial device
participation. Under non-convex settings, we derive the convergence performance
of the FedZO algorithm on non-independent and identically distributed data and
characterize the impact of the numbers of local iterates and participating edge
devices on the convergence. To enable communication-efficient FedZO over
wireless networks, we further propose an over-the-air computation (AirComp)
assisted FedZO algorithm. With an appropriate transceiver design, we show that
the convergence of AirComp-assisted FedZO can still be preserved under certain
signal-to-noise ratio conditions. Simulation results demonstrate the
effectiveness of the FedZO algorithm and validate the theoretical observations.

本文提出了一种基于随机梯度估计器的多次本地更新和部分设备参与的无导数联邦零阶优化算法（FedZO），并介绍了一种适用于无线网络的空气计算辅助 FedZO 算法。在非凸设置下，研究了 FedZO 算法的收敛性能，并表征了本地迭代次数和参与边缘设备数量对收敛性的影响。

基于随机零阶优化的联邦学习通信高效实现

Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning

Federated learning enables a large amount of edge computing devices to
jointly learn a model without data sharing. As a leading algorithm in this
setting, Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent
(SGD) in parallel on a small subset of the total devices and averages the
sequences only once in a while. Despite its simplicity, it lacks theoretical
guarantees under realistic settings. In this paper, we analyze the convergence
of \texttt{FedAvg} on non-iid data and establish a convergence rate of
$\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$
is the number of SGDs. Importantly, our bound demonstrates a trade-off between
communication-efficiency and convergence rate. As user devices may be
disconnected from the server, we relax the assumption of full device
participation to partial device participation and study different averaging
schemes; low device participation rate can be achieved without severely slowing
down the learning. Our results indicate that heterogeneity of data slows down
the convergence, which matches empirical observations. Furthermore, we provide
a necessary condition for \texttt{FedAvg} on non-iid data: the learning rate
$\eta$ must decay, even if full-gradient is used; otherwise, the solution will
be $\Omega (\eta)$ away from the optimal.

本文中，我们分析了在非独立同分布数据上的 FedAvg 算法的收敛性，并在强凸和平滑问题上建立起一个 O (1/T) 的收敛率，研究了部分设备参与的不同平均方案，结果表明数据的异质性会降低收敛速度，并提供了一个必要条件，即遇到非独立同分布数据时，学习率需要衰减否则结果将偏离最优解。