math.OCNov 10, 2026

On Federated Averaging with Partial Participation under a General Variance Condition

Authors: Ziming Wang, Kun Huang, Karl Henrik Johansson, Shi Pu

Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · Department of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, and Digital Futures, Stockholm, Sweden

Abstract

In this paper, we study the convergence of Federated Averaging (FedAvg) with partial participation under a general variance condition. In each communication round, the server samples SS of the nn clients uniformly at random without replacement. The stochastic gradients are assumed to satisfy the so-called ABC condition, which allows their variance to grow with the local objective gaps. For smooth nonconvex objectives, we establish a finite-time stationarity bound in terms of the heterogeneity measure σf⋆:=f⋆−1n∑i=1nfi⋆σ_f^\star:=f^\star-\frac{1}{n}\sum_{i=1}^n f_i^\star and the client sampling factor IS:=(n−S)/(n−1)I_S:=(n-S)/(n-1). Here, f⋆f^\star and fi⋆f_i^\star denote the infima of the global average objective and client ii's local objective, respectively. The bound exhibits a linear speedup in the number of sampled clients SS and recovers the full-participation result when S=nS=n. Under diminishing stepsizes, we further prove that the gradient norm converges to zero both in expectation and almost surely. Notably, compared with existing analyses of FedAvg with partial participation, our results require no additional data heterogeneity assumption such as bounded gradient dissimilarity (BGD), and the sampling-induced term in our bound is not amplified by the number of local updates at the leading order. The importance of removing the BGD assumption is illustrated by an example that is smooth and lower bounded but violates BGD, yet is covered by our analysis.

Figures & tables

Explore similar work

Sep 17, 2026

FedeRage: Provably Convergent Agnostic Federated Learning under General Client Drift

Federated learning (FL) enables collaborative model training without sharing raw data, but its performance degrades under non-IID data and stochastic client participation. Remedies built on classical Federated Averaging (FedAvg) typically presuppose that client participation probabilities are known to the server, which is rarely the case in deployed systems. We first discuss and then characterize the optimization problem that distributionally agnostic FedAvg actually solves when participation is entirely unknown, possibly highly skewed, and of variable size across rounds: uniform aggregation is shown to minimize a well-defined stochastic objective, weighted by the participation-induced marginal, at a standard O(1/T)\mathcal{O}(1/\sqrt{T}) rate for convex and possibly nonsmooth losses. Building on this characterization, we propose Federated Risk-Averse Averaging (FedeRage), a risk-averse extension of FedAvg that embeds the Conditional Value-at-Risk (CVaR) into the local objective within a natural distributionally robust optimization (DRO) framework. FedeRage implicitly upweights high-loss and infrequently participating clients while adding only a single scalar per-client, and admits an O(κ/T)\mathcal{O}(κ/\sqrt{T}) rate in which the factor κκ is the upper bound on the ``price" of risk aversion. In contrast with aggregation-alignment schemes based on optimal transport, which require the availability distribution as an input, FedeRage remains agnostic to it. Several experiments on three heterogeneous benchmarks indicate consistent improvements over state-of-the-art methods in accuracy, fairness, and convergence speed.
Jan 29, 2026

FedAdaVR: Adaptive Variance Reduction for Robust Federated Learning under Limited Client Participation

Federated learning (FL) encounters substantial challenges due to heterogeneity, leading to gradient noise, client drift, and partial client participation errors, the last of which is the most pervasive but remains insufficiently addressed in current literature. In this paper, we propose FedAdaVR, a novel FL algorithm aimed at solving heterogeneity issues caused by partial client participation by incorporating an adaptive optimiser with a variance reduction technique. This method takes advantage of the most recent stored updates from clients, even when they are absent from the current training round, thereby emulating their presence. Furthermore, we propose FedAdaVR-Quant, a server-side memory compression variant that stores historical client updates in quantised form (while keeping client-server communication in full precision), reducing the server memory footprint of FedAdaVR by 50% (FP16), 75% (Int8), and 87.5% (Int4) while maintaining highly competitive, and occasionally superior model performance. We analyse the non-convex convergence behaviour of FedAdaVR with Adagrad and prove that our proposed framework eliminates the first-order partial client participation bias while improving monotonically with cohort size. Extensive experiments conducted on multiple vision and NLP datasets demonstrate that FedAdaVR consistently outperforms state-of-the-art baseline methods.
May 16, 2025

Heterogeneity-Aware Client Sampling for Optimal and Efficient Federated Learning

Federated learning (FL) commonly involves clients with diverse communication and computational capabilities. Such heterogeneity can significantly distort the optimization dynamics and lead to objective inconsistency, where the global model converges to an incorrect stationary point potentially far from the pursued optimum. Despite its critical impact, the joint effect of communication and computation heterogeneity has remained largely unexplored, due to the intrinsic complexity of their interaction. In this paper, we reveal the fundamentally distinct mechanisms through which heterogeneous communication and computation drive inconsistency in FL. To the best of our knowledge, this is the first unified theoretical analysis of general heterogeneous FL, offering a principled understanding of how these two forms of heterogeneity jointly distort the optimization trajectory under arbitrary choices of local solvers. Motivated by these insights, we propose Federated Heterogeneity-Aware Client Sampling, FedACS, a universal method to eliminate all types of objective inconsistency. We theoretically prove that FedACS converges to the correct optimum at a rate of O(1/R)O(1/\sqrt{R}), even in dynamic heterogeneous environments. Extensive experiments across multiple datasets show that FedACS outperforms state-of-the-art and category-specific baselines by 4.3%-36%, while reducing communication costs by 22%-89% and computation loads by 14%-105%, respectively.