Leveraging Low-Rank Hessian Structures for Communication-Efficient Federated Learning

Communication dominates the cost of federated learning (FL), and second-order curvature can reduce the number of rounds needed to reach a target accuracy. Existing federated second-order methods, however, largely face a dilemma: approaches that operate on curvature at full-Hessian scale incur memory and computation costs quadratic in the parameter count and are therefore restricted to shallow models, whereas lightweight diagonal approximations remain inexpensive but discard cross-coordinate curvature. To address this dilemma, we propose FHaN, a federated optimization method that builds second-order updates from a few locally sampled Hessian columns. Each client selects the columns in a gradient-guided manner and builds from them a compact low-rank correction capturing part of the cross-coordinate curvature. Because the solve is confined to the sampled subspace, neither the full Hessian nor its inverse is ever formed; the only inversion required is that of a small matrix, stabilized by smoothing its singular values. The result is a model-sized update vector per client, so the per-round payload matches that of first-order methods, and the efficiency gain comes from reaching target accuracy in fewer rounds. We show that FHaN converges linearly whenever the aggregated update satisfies a contraction condition, and identify a regime of data heterogeneity and sampling error in which this condition is feasible. On MNIST, Fashion-MNIST, CIFAR-10 and CIFAR-100, FHaN's advantage concentrates where curvature matters: federated fine-tuning of frozen pretrained backbones gains up to +13.2 final accuracy points with up to $6\times$ fewer rounds to target, and FC-dominated models trained from scratch gain up to +23.9 points, while saturated tasks, benign convex problems, and end-to-end convolutional training mark its boundaries.