FedNL: Making Newton-Type Methods Applicable to Federated Learning

Abstract

Inspired by recent work of Islamov et al (2021), we propose a family of Federated Newton Learn (FedNL) methods, which we believe is a marked step in the direction of making second-order methods applicable to FL. In contrast to the aforementioned work, FedNL employs a different Hessian learning technique which i) enhances privacy as it does not rely on the training data to be revealed to the coordinating server, ii) makes it applicable beyond generalized linear models, and iii) provably works with general contractive compression operators for compressing the local Hessians, such as Top-$K$ or Rank-$R$, which are vastly superior in practice. Notably, we do not need to rely on error feedback for our methods to work with contractive compressors. Moreover, we develop FedNL-PP, FedNL-CR and FedNL-LS, which are variants of FedNL that support partial participation, and globalization via cubic regularization and line search, respectively, and FedNL-BC, which is a variant that can further benefit from bidirectional compression of gradients and models, i.e., smart uplink gradient and smart downlink model compression. We prove local convergence rates that are independent of the condition number, the number of training data points, and compression variance. Our communication efficient Hessian learning technique provably learns the Hessian at the optimum. Finally, we perform a variety of numerical experiments that show that our FedNL methods have state-of-the-art communication complexity when compared to key baselines.

arXiv comment65 pages, 7 algorithms, 14 figures --- Accepted to ICML 2022

References in corpus (21)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Optimization in Heterogeneous Networks
• Sparsified SGD with Memory
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Adaptive Federated Optimization
• Distributed Learning with Compressed Gradient Differences
• Optimal Client Sampling for Federated Learning
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• On Biased Compression for Distributed Learning
• Distributed learning with compressed gradients
• DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
• Linearly Converging Error Compensated SGD
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Proximal and Federated Random Reshuffling

Cited by in corpus (4)

• Distributed Computation for Marginal Likelihood based Model Choice
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• On Second-order Optimization Methods for Federated Learning