SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing
This work addresses communication bottlenecks in federated learning for heterogeneous networks, offering a practical improvement for distributed optimization scenarios.
The authors tackled the problem of accelerating federated learning in heterogeneous networks with non-i.i.d. data and varied communication resources by proposing SHED, a Newton-type algorithm based on incremental Hessian eigenvector sharing, which achieved super-linear convergence and showed superior performance in communication rounds, data transmission, and Hessian computations compared to state-of-the-art methods like GIANT and FedNL.
There is a growing interest in the distributed 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 SHED, an original communication-constrained Newton-type (NT) algorithm designed to accelerate FL in such heterogeneous scenarios. SHED 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 eigendecomposition 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. For all these metrics, the proposed approach shows superior performance against state-of-the art techniques like GIANT and FedNL.