Research map / Federated learning and privacy / Communication-efficient FL

FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning

AAAI 2024 · Federated learning and privacy › Communication-efficient FL · approach: Federated optimization algorithms · 4 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes FedNS and FedNDES, federated Newton methods that communicate SRHT-sketched square-root Hessians (plus gradients) instead of full Hessians, with FedNDES adapting sketch size to the empirical effective dimension and using Armijo line search, claiming super-linear convergence in communication rounds.

Problem

Newton-type federated learning achieves fast convergence in rounds but communicating local Hessians costs O(M^2) per round, which is impractical; first-order methods communicate cheaply but converge slowly.

Approach

Federated Newton update where each worker uploads a sketched square-root Hessian S_j H_j^{1/2} (k x M) and local gradients, and the server sums them to form an approximate global Hessian; FedNDES further shrinks the sketch size to the empirical effective dimension and uses backtracking Armijo line search with adaptive sketch sizes.

Key results

• FedNS and FedNDES are reported to reach super-linear convergence in communication rounds, with FedNDES converging faster than FedNS and comparable to FedNewton in experiments on regularized logistic regression.
• Theory: FedNDES needs sketch size k = Omega(effective dimension d_lambda) and T = O(log log(1/delta)) rounds, with per-round communication O(kM) instead of O(M^2).
• Experiments on phishing, cod-rna, covtype and SUSY (logistic regression, averaged over 10 trials) show a larger sketch size gives better generalization, and small sketch sizes (k << M) still retain considerable accuracy.

Measured effects reported in the paper

Surprising findings

• Sketching without line search does not reduce communication cost, since FedNS needs k of order M, so the line-search variant FedNDES is required for savings.

Limitations

• Convergence guarantees rely on assumptions (strong convexity, Lipschitz Hessian, self-concordance) and constants unknown in practice; FedNS requires an initialization condition.
• Effective dimension and sketch-size bounds are not estimated in practice; experiments limited to regularized logistic regression on four datasets.
• The SHED baseline was excluded from experiments due to lack of public code.

Experimental setup

Datasets: phishing cod-rna covtype SUSY

Benchmarks: phishing cod-rna covtype SUSY

Metrics: optimality gap L(w_t)-L(w*) predictive accuracy vs sketch size loss discrepancy vs communication rounds

Baselines: FedAvg FedNew FedNL FedNewton global Newton's method

Builds on: Newton sketch FedNew FedNL FedAvg FedProx

Closest papers by meaning

• FedNL: Making Newton-Type Methods Applicable to Federated Learning (ICML 2022 · similarity 0.90)
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients (NeurIPS 2021 · similarity 0.89)
• FetchSGD: Communication-Efficient Federated Learning with Sketching (ICML 2020 · similarity 0.88)
• Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.88)
• Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis (NeurIPS 2024 · similarity 0.86)
• FedQS: Optimizing Gradient and Model Aggregation for Semi-Asynchronous Federated Learning (NeurIPS 2025 · similarity 0.86)