A Newton-type algorithm for federated learning based on incremental
  Hessian eigenvector sharing
  There is a growing interest in the decentralized optimization framework that
goes under the name of Federated Learning (FL). In particular, much attention
is being turned to FL scenarios where the network is strongly heterogeneous in
terms of communication resources (e.g., bandwidth) and data distribution. In
these cases, communication between local machines (agents) and the central
server (Master) is a main consideration. In this work, we present an original
communication-constrained Newton-type (NT) algorithm designed to accelerate FL
in such heterogeneous scenarios. The algorithm is by design robust to non
i.i.d. data distributions, handles heterogeneity of agents' communication
resources (CRs), only requires sporadic Hessian computations, and achieves
super-linear convergence. This is possible thanks to an incremental strategy,
based on a singular value decomposition (SVD) of the local Hessian matrices,
which exploits (possibly) outdated second-order information. The proposed
solution is thoroughly validated on real datasets by assessing (i) the number
of communication rounds required for convergence, (ii) the overall amount of
data transmitted and (iii) the number of local Hessian computations required.
For all these metrics, the proposed approach shows superior performance against
state-of-the art techniques like GIANT and FedNL.
