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.

提出了一种名为 Federated Newton Sketch 方法（FedNS）的算法，通过通信 sketched square-root Hessian 来逼近中心化的 Newton's 方法，以此解决了 Hessian 矩阵的通信复杂性问题，实现了快速收敛率，并首次达到了超线性收敛率。