Federated learning is a distributed learning framework that allows a set of
clients to collaboratively train a model under the orchestration of a central
server, without sharing raw data samples. Although in many practical scenarios
the derivatives of the objective function are not available, only few works
have considered the federated zeroth-order setting, in which functions can only
be accessed through a budgeted number of point evaluations. In this work we
focus on convex optimization and design the first federated zeroth-order
algorithm to estimate the curvature of the global objective, with the purpose
of achieving superlinear convergence. We take an incremental Hessian estimator
whose error norm converges linearly, and we adapt it to the federated
zeroth-order setting, sampling the random search directions from the Stiefel
manifold for improved performance. In particular, both the gradient and Hessian
estimators are built at the central server in a communication-efficient and
privacy-preserving way by leveraging synchronized pseudo-random number
generators. We provide a theoretical analysis of our algorithm, named FedZeN,
proving local quadratic convergence with high probability and global linear
convergence up to zeroth-order precision. Numerical simulations confirm the
superlinear convergence rate and show that our algorithm outperforms the
federated zeroth-order methods available in the literature.

本研究使用增量 Hessian 估计器在协同训练集中设计第一个估计全局目标曲率的零阶联邦学习算法，以达到超线性收敛，通过在 Stiefel 流形中对随机搜索方向进行采样以提高性能。我们通过使用同步的伪随机数生成器以一种通信高效和隐私保护的方式，在中央服务器上构建梯度和 Hessian 估计器。我们对我们的算法进行了理论分析，命名为 FedZeN，证明了具有高概率的局部二次收敛和全局线性收敛的零阶精度。数值模拟验证了超线性收敛速率，并表明我们的算法优于文献中可用的零阶联邦学习方法。

FedZeN：通过增量 Hessian 估计实现超线性零阶联邦学习

FedZeN: Towards superlinear zeroth-order federated learning via  incremental Hessian estimation

The adaptive momentum method (AdaMM), which uses past gradients to update
descent directions and learning rates simultaneously, has become one of the
most popular first-order optimization methods for solving machine learning
problems. However, AdaMM is not suited for solving black-box optimization
problems, where explicit gradient forms are difficult or infeasible to obtain.
In this paper, we propose a zeroth-order AdaMM (ZO-AdaMM) algorithm, that
generalizes AdaMM to the gradient-free regime. We show that the convergence
rate of ZO-AdaMM for both convex and nonconvex optimization is roughly a factor
of $O(\sqrt{d})$ worse than that of the first-order AdaMM algorithm, where $d$
is problem size. In particular, we provide a deep understanding on why
Mahalanobis distance matters in convergence of ZO-AdaMM and other AdaMM-type
methods. As a byproduct, our analysis makes the first step toward understanding
adaptive learning rate methods for nonconvex constrained optimization.
Furthermore, we demonstrate two applications, designing per-image and universal
adversarial attacks from black-box neural networks, respectively. We perform
extensive experiments on ImageNet and empirically show that ZO-AdaMM converges
much faster to a solution of high accuracy compared with $6$ state-of-the-art
ZO optimization methods.

该研究提出了一种名为 ZO-AdaMM 的零阶梯度黑盒优化方法，它将 AdaMM 通用于无梯度形式的场景，并阐述了它的收敛率问题以及在非凸约束优化问题中的适用性，最终通过 ImageNet 数据的两个实验应用证明了 ZO-AdaMM 的高精确度和快速收敛能力。