FedZeN: Towards superlinear zeroth-order federated learning via
  incremental Hessian estimation
Alessio Maritan Subhrakanti Dey Luca Schenato
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.