betaFeedback

WorksMathematics

On Federated Averaging with Partial Participation under a General Variance Condition

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.

Paper details

vlnc:W_7y9546fs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…