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

Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates

ICML 2024 · Federated learning and privacy › Communication-efficient FL · approach: Client participation analysis · 0 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.

Analyzes robust federated averaging (FedRo) under client subsampling and multiple local steps, giving sufficient subsampling conditions, a diminishing-returns threshold, and showing Byzantine error shrinks with more local steps.

Problem

Robust aggregation in federated learning has been studied mainly under full participation and single local steps; it is unclear how client subsampling (which raises the effective Byzantine fraction) and multiple local steps affect convergence of robust FedAvg under Byzantine clients.

Approach

Derives a KL-divergence-based sufficient condition on sample size and tolerated Byzantine count per round so that Byzantine clients in the sample stay bounded w.h.p., then proves a convergence bound for FedRo with a non-vanishing Byzantine error term that decreases with local steps K and scales with b/n, and identifies a sample-size threshold beyond which returns diminish.

Key results

• Sufficient subsampling threshold Hat-n_th derived; with n=150, b=30 FedRo fails when fewer than about 30 clients are sampled per round (empirical threshold, FEMNIST).
• Asymptotic Byzantine error term scales as (b/n)(sigma^2/K + zeta^2), decreasing with the number of local steps K for suitably chosen client step-size.
• Diminishing returns: beyond Hat-n_opt, increasing sample size does not improve the order of the asymptotic error.

Measured effects reported in the paper

Surprising findings

• Byzantine error can decrease as the number of local steps increases, contrary to the increasing-error intuition from non-Byzantine FL analyses.
• Robust FL does not always benefit from sampling more clients; improvement saturates beyond a threshold.

Limitations

• Lower-order convergence term and gap of O(kappa sigma^2) to optimal bound remain open in the federated setting.
• Analysis assumes bounded heterogeneity and smooth non-convex losses; experiments are limited to two image datasets with a small CNN.

Experimental setup

Datasets: FEMNIST CIFAR-10

Benchmarks: FEMNIST CIFAR-10

Metrics: test accuracy

Baselines: FedAvg Byz-VR-MARINA Krum geometric median coordinate-wise trimmed mean

Builds on: FedAvg NNM Krum coordinate-wise trimmed mean

Closest papers by meaning

• Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients (NeurIPS 2025 · similarity 0.89)
• FedAdaVR: Adaptive Variance Reduction for Robust Federated Learning under Limited Client Participation (NeurIPS 2026 · similarity 0.88)
• From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity (NeurIPS 2026 · similarity 0.88)
• Byzantine-robust Decentralized Federated Learning via Dual-domain Clustering and Trust Bootstrapping (CVPR 2024 · similarity 0.88)
• Federated Learning with Extremely Noisy Clients via Negative Distillation (AAAI 2024 · similarity 0.87)
• A Huber Loss Minimization Approach to Byzantine Robust Federated Learning (AAAI 2024 · similarity 0.87)