SHED: a Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing

DOI10.1016/J.AUTOMATICA.2023.111460MaRDI QIDQ6152580zbMATH OpenFDO

Authors Nicolò Dal Fabbro, Subhrakanti Dey, Michele Rossi, Luca Schenato

Publication date 13 February 2024

Published in Automatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2202.05800

zbMATH Keywords

Newton methoddistributed optimizationheterogeneous networkssuper-linear convergencefederated learningnon i.i.d. data

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 7307473
• Communication-efficient distributed cubic Newton with compressed lazy Hessian
• Federated primal dual fixed point algorithm
• Communication-efficient distributed optimization of self-concordant empirical loss

Cites work

• scientific article; zbMATH DE number 432503 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Advances and Open Problems in Federated Learning
• Analysis and Linear Algebra: The Singular Value Decomposition and Applications
• Distributed adaptive Newton methods with global superlinear convergence
• On the limited memory BFGS method for large scale optimization

This page was built for publication: SHED: a Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6152580)