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

We propose STARS, a randomized derivative-free algorithm for unconstrained
optimization when the function evaluations are contaminated with random noise.
STARS takes dynamic, noise-adjusted smoothing step-sizes that minimize the
least-squares error between the true directional derivative of a noisy function
and its finite difference approximation. We provide a convergence rate analysis
of STARS for solving convex problems with additive or multiplicative noise.
Experimental results show that (1) STARS exhibits noise-invariant behavior with
respect to different levels of stochastic noise; (2) the practical performance
of STARS in terms of solution accuracy and convergence rate is significantly
better than that indicated by the theoretical result; and (3) STARS outperforms
a selection of randomized zero-order methods on both additive and
multiplicative-noisy functions.

STARS 是一种基于随机化的无导数优化算法，适用于函数评估受到随机噪声干扰的情况。该算法通过动态噪声自适应平滑步长来最小化真实方向导数与其有限差分估计之间的最小二乘误差，并提供了用于求解具有加性或乘性噪声的凸问题收敛速率分析。实验结果显示，STARS 相对于不同级别随机噪声表现出的噪声不变行为；在解决加性和乘性噪声函数方面，其实际性能在解决方案精度和收敛速度方面显著优于理论结果，并且 STARS 在随机零阶方法的选择上表现出卓越优势。