FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning
This addresses communication bottlenecks in federated learning for distributed systems, offering a novel method with improved efficiency.
The paper tackles the high communication cost of Hessian matrices in Newton-type federated learning by proposing FedNS, which uses sketched square-root Hessians to reduce complexity while achieving super-linear convergence rates in communication rounds.
Recent Newton-type federated learning algorithms have demonstrated linear convergence with respect to the communication rounds. However, communicating Hessian matrices is often unfeasible due to their quadratic communication complexity. In this paper, we introduce a novel approach to tackle this issue while still achieving fast convergence rates. Our proposed method, named as Federated Newton Sketch methods (FedNS), approximates the centralized Newton's method by communicating the sketched square-root Hessian instead of the exact Hessian. To enhance communication efficiency, we reduce the sketch size to match the effective dimension of the Hessian matrix. We provide convergence analysis based on statistical learning for the federated Newton sketch approaches. Specifically, our approaches reach super-linear convergence rates w.r.t. the communication rounds for the first time. We validate the effectiveness of our algorithms through various experiments, which coincide with our theoretical findings.