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

Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up

ICML 2025 · Federated learning and privacy › Communication-efficient FL · approach: Federated optimization algorithms · 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.

Shows that stochastic Scaffold's global iterates and control variates form a geometrically ergodic Markov chain, proves Scaffold achieves linear speed-up in the number of clients (up to higher-order terms), and derives a first-order non-vanishing bias term.

Problem

Understanding how stochastic gradient noise affects Scaffold in federated learning, in particular whether its convergence benefits from more clients (linear speed-up) and what bias remains under heterogeneity.

Approach

Views Scaffold's global parameters and control variates as a Markov chain with a contractive operator under a weighted norm, yielding a Wasserstein-convergent stationary distribution; a covariance analysis of this stationary distribution then shows the parameter variance scales as 1/N, giving linear speed-up without global step sizes.

Key results

• Scaffold's stationary parameter covariance scales as gamma/N up to higher-order terms in the step size, establishing linear speed-up in the number of clients (up to a limit on N that is infinite for quadratic objectives).
• Scaffold's iterates converge geometrically in W2 at rate (1 - gamma mu/4)^{Ht}.
• Scaffold retains a non-vanishing bias of order gamma/N times gradient noise covariance, which does not decrease with N; numerical experiments show error decreasing with N up to saturation in logistic regression.

Measured effects reported in the paper

Surprising findings

• Scaffold's global iterates remain biased under stochastic gradients, with bias not decreasing as the number of clients grows, even though heterogeneity bias is corrected.
• The control variate covariances do not decrease with the number of clients for a single client, so the speed-up relies on cross-client covariances.

Limitations

• Linear speed-up holds only up to a maximum number of clients that depends on third-derivative bound Q (finite unless quadratic).
• Analysis uses fixed-step-size stationary regime and higher-order terms in gamma^{3/2} and gamma^3 H; the number of rounds carries a factor L/mu, not sqrt(L/mu).
• Experiments are small synthetic linear and logistic regression; logistic regression saturates beyond N=1000.

Experimental setup

Datasets: scikit-learn make_regression synthetic data scikit-learn make_classification synthetic data

Benchmarks: synthetic l2-regularized linear regression synthetic l2-regularized logistic regression

Metrics: squared error of global iterates in stationary regime

Baselines: FedAvg SCAFFOLD (Karimireddy et al.) ProxSkip ScaffLSA

Builds on: SCAFFOLD FedAvg ProxSkip SGD as Markov chain

Closest papers by meaning

• SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning (NeurIPS 2024 · similarity 0.89)
• A New Theoretical Perspective on Data Heterogeneity in Federated Optimization (ICML 2024 · similarity 0.89)
• Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.89)
• Momentum Benefits Non-iid Federated Learning Simply and Provably (ICLR 2024 · similarity 0.88)
• Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averaging (ICML 2025 · similarity 0.88)
• FedGPS: Statistical Rectification Against Data Heterogeneity in Federated Learning (NeurIPS 2025 · similarity 0.88)