Abstract
Inspired by the recent work FedNL (Safaryan et al, FedNL: Making Newton-Type Methods Applicable to Federated Learning), we propose a new communication efficient second-order framework for Federated learning, namely FLECS. The proposed method reduces the high-memory requirements of FedNL by the usage of an L-SR1 type update for the Hessian approximation which is stored on the central server. A low dimensional 'sketch' of the Hessian is all that is needed by each device to generate an update, so that memory costs as well as number of Hessian-vector products for the agent are low. Biased and unbiased compressions are utilized to make communication costs also low. Convergence guarantees for FLECS are provided in both the strongly convex, and nonconvex cases, and local linear convergence is also established under strong convexity. Numerical experiments confirm the practical benefits of this new FLECS algorithm.
Introduction
Federated Learning (FL) typically involves a central server and thousands of edge devices collaborating to train a global model. While first-order methods like SGD are the standard due to their low computational overhead, they often suffer from slow convergence and sensitivity to poorly scaled data. Second-order methods, which utilize the Hessian matrix, offer faster and more robust convergence but are traditionally impractical for FL because the Hessian size scales quadratically with the number of parameters ($d \times d$). For modern models, storing and communicating these matrices exceeds the memory and bandwidth constraints of edge devices. FLECS (Federated LEarning Second-Order Framework via Compression and Sketching) addresses these bottlenecks to make Newton-type optimization viable in distributed settings.
The FLECS Framework
FLECS introduces three primary innovations to bridge the gap between second-order performance and edge device constraints:
- Server-Side Hessian Storage: Unlike previous methods like FedNL, FLECS shifts the burden of storing Hessian approximations entirely to the central server. This reduces additional worker memory overhead to zero.
- Sketching for Dimensionality Reduction: Workers compute a "sketch"—a low-dimensional projection ($d \times m$, where $m \ll d$)—rather than a full Hessian. This reduces the required Hessian-vector products per worker from $d$ to $m$.
- Aggressive Compression: The framework utilizes both biased (e.g., Top-K) and unbiased (e.g., random dithering) compression to minimize the bits transmitted from workers to the server.
As shown in the comparison table above, FLECS significantly improves upon the state-of-the-art FedNL by eliminating worker storage requirements and reducing communication costs from $O(d^2)$ to $O(md)$.
Theoretical and Practical Insights
FLECS exploits the inherent asymmetry of FL systems, where the server is typically a powerful cloud resource and workers are resource-constrained devices. By shifting $O(d^3)$ matrix operations to the server, the framework removes the bottleneck from the edge.
Furthermore, the use of sketching demonstrates that a full Hessian is not required to achieve a "Newton-like" direction; a few random directions often capture sufficient curvature information. To ensure stability, FLECS employs spectral decomposition and eigenvalue truncation, ensuring the search direction remains a descent direction even in non-convex landscapes.
Experimental Evaluation
The authors evaluated FLECS using regularized logistic regression on standard LIBSVM benchmarks, including a9a, gisette-scale, and real-sim. In the large-scale real-sim dataset (over 20,000 features), FLECS reached high precision while communicating orders of magnitude fewer bits than baselines like DIANA and FedNL.
Theoretical proofs confirm that FLECS achieves global linear convergence for strongly convex problems and converges to a stationary point in non-convex settings, matching or exceeding the guarantees of more resource-intensive methods.
Conclusion and Future Work
FLECS demonstrates that second-order optimization can be made practical for Federated Learning by carefully balancing server-side computation with worker-side sketching and compression. While the server still faces $O(d^3)$ complexity in some variants, the framework successfully enables edge devices to participate in advanced optimization without prohibitive memory costs. Future research may explore adaptive sketching sizes and more sophisticated sketching matrices to further enhance scalability for models with millions of parameters.
Summary updated