Convergence Analysis in Federated Learning (Part 5)

0x00 Preface

Part 3¹ analyzed mini-batch SGD, Part 4² discussed synchronous and asynchronous distributed updates. This article turns to federated learning: clients not only hold different data but also perform multiple consecutive updates between a single communication round. Therefore, local stochastic gradients being unbiased for the local objective does not imply that the aggregated direction is unbiased for the current global gradient.

Starting from FedAvg’s update rule, this article provides a simplified proof that can be verified step-by-step: first analyzing the model under full participation, equal-weight clients, and identical local steps, then deriving extensions for uniform partial participation and discussing inconsistent aggregation weights. The non-convex part guarantees the average gradient norm decreases; the strongly convex part additionally employs the PL inequality. These two conclusions must not be mixed.

The original FedAvg algorithm is described in McMahan et al., 2017³. The constant bounds below are conservative bounds derived by this paper under explicit assumptions; they are not copied from any theorem in another paper, nor do they pursue optimal complexity.

0x01 Objective and FedAvg Updates

Global Objective

Suppose there are $N$ clients, and the local objective for the $i$-th client is

If one wishes for each sample to have equal weight, typically set $p_i=n_i/\sum_j n_j$; if one wishes for each client to have equal weight, then set $p_i=1/N$. These are two distinct optimization objectives, not interchangeable implementation details. Data not being uploaded does not automatically imply differential privacy guarantees; this article only discusses optimization error.

The main theorem later fixes the use of $p_i=1/N$. Weighted objectives and partial participation are discussed later and are not included by default in the main theorem.

Local Steps and Communication Rounds

$t$ denotes communication rounds, and $k$ denotes local update steps within a round. All clients start each round from the same server model and execute $E\ge1$ local SGD steps:

$\eta$ is the fixed local learning rate; the server directly averages the models without multiplying by an additional server learning rate. Define the effective step size per round as $\alpha=\eta E$, and the aggregation direction as

Here, $E$ is the number of updates, not the number of local epochs. If clients have different data volumes, the same number of epochs often corresponds to different numbers of updates and cannot be directly substituted into this model. Over a total of $T$ rounds, each client performs $ET$ local updates; the entire system computes a total of $NET$ batch gradients.

0x02 Assumptions and Error Decomposition

Smoothness and Lower Bound

Each $f_i$ is a $L$-smooth function on Euclidean space, so the average objective $f$ is also $L$-smooth. Assume $f(w)\ge f_{\inf}>-\infty$, define $\Delta_0=f(w_0)-f_{\inf}$, and treat $w_0$ as a deterministic initial value. Non-convex analysis does not require $f_{\inf}$ to be attained by any parameter.

Conditional Gradient Noise

Let $\mathcal F_t$ contain the history before the start of round $t$; $\mathcal H_{t,k}$ further includes all clients’ parameters and history before the sampling of step $k$ within that round. Write

$b$ is the batch size per step, and $\sigma^2$ is a uniform upper bound on the variance of single-sample noise. For the same step across different clients, the noise is also required to be conditionally uncorrelated. No unconditional independence is required between different steps of the same client; conditional unbiasedness ensures that noise increments form a martingale difference sequence.

The reduction of $1/b$ within a batch requires independent sampling or corresponding covariance conditions. If directly traversing the same random permutation, selecting samples based on loss, or if the sampling process is affected by dropout mechanisms, the above conditions must be re-verified; one cannot assume the conditions hold simply because “SGD was used”.

Bounded Gradient Heterogeneity

Adopt the following unified heterogeneity upper bound:

$\sigma^2$ describes random noise within a single client, while $\zeta^2$ describes target differences between clients. Increasing the batch size reduces the former but does not automatically eliminate the latter. From $\sum_i(\nabla f_i-\nabla f)=0$, we have

This is a strong assumption, not automatically implied by the description “non-IID data”. It requires a uniform bound on differences across all parameters, not just near the optimal point. If it holds only in a specific region, one must also prove that all relevant iterations remain within that region. This article does not take “globally uniformly bounded gradients” as an additional assumption.

Noise and Local Drift

Let $h_t=\nabla f(w_t)$, and decompose the aggregation direction precisely into

$r_t$ is the drift caused by the local path, and $e_t$ is the average random noise. Conditional unbiasedness and mutual uncorrelatedness yield

The cross terms of asynchronous noise vanish via iterated conditional expectations. However, $r_t$ depends on local parameters, which in turn depend on previous noise, so one generally cannot assert $\mathbb E\langle r_t,e_t\rangle=0$. The subsequent proof retains this correlation and controls it via norm inequalities.

0x03 Bounding Local Drift

This section provides the key estimates required for the theorems that follow. Let $q=E-1$, and define the average displacement under the history at the start of the round:

Here we only need to control the parameters of $k=0,\ldots,E-1$, as these are the points where gradients are computed. When $E=1$, we have $q=0$, and thus $M_t=r_t=0$.

Expand the local updates to separate the gradient mean from the noise. Using $|a+c|^2\le2|a|^2+2|c|^2$, $|\sum_{s<k}a_s|^2\le k\sum_{s<k}|a_s|^2$, and the martingale difference property of the noise, we obtain

Then apply smoothness and the heterogeneity bound from the previous section:

Taking the maximum over $0\le k\le q$ yields

From now on, we uniformly adopt the step-size condition $0<\eta LE\le1/8$. Thus $4\eta^2L^2q^2\le1/16$; rearranging terms and loosening the constants gives

By Jensen’s inequality and the smoothness of the local objectives:

This also explains why “treating the $NEb$ samples in one round as a single large batch” is insufficient: while the noise average does enjoy a $1/(NE)$ reduction, the gradients are computed at different local parameters, so one must also control $r_t$.

0x04 A Non-convex Convergence Bound

One-round Descent

Using the smoothness of $f$ and $w_{t+1}=w_t-\alpha v_t$,

First take the expectation conditioned on $\mathcal F_t$. $h_t$ is measurable, $\mathbb E[e_t\mid\mathcal F_t]=0$, so the inner product of $h_t$ with the noise vanishes. For the drift term, use

Here we do not assume that $r_t$ and $e_t$ are independent. Denoting $R_t=\mathbb E[|r_t|^2\mid\mathcal F_t]$, we have

Since $L\alpha=L\eta E\le1/8$, the descent coefficient of the first term is at least $1/2$, and $1+2L\alpha\le5/4$. Substituting the drift bound, the new coefficient for the gradient term is at most

Therefore, we can conservatively retain a descent amount of $\alpha/4$. Define

This yields the core recursion of the entire proof:

Stationarity Guarantee

defination

Under the aforementioned assumptions, equal-weight aggregation with full participation, and $0<\eta\le1/(8LE)$, running $T\ge1$ communication rounds gives

$$ \begin{aligned} \frac1T\sum_{t=0}^{T-1}\mathbb E\|\nabla f(w_t)\|^2 &\le\frac{4\Delta_0}{\eta ET}+4A\\ &=\frac{4\Delta_0}{\eta ET} +\frac{4L\eta\sigma^2}{bN} +\frac{20L^2\eta^2(E-1)\sigma^2}{b} +40L^2\eta^2(E-1)^2\zeta^2. \end{aligned} $$

The proof only requires taking the total expectation of the core recursion and summing over $t=0,\ldots,T-1$: the function value terms cancel out, and then we apply $\mathbb E[f(w_T)]\ge f_{\inf}$. If we independently and uniformly select one $w_R$ from these $T$ initial parameters of the rounds, the left-hand side equals exactly $\mathbb E|\nabla f(w_R)|^2$.

This is an average stationary point bound, not a guarantee for the last round’s $w_T$, nor a guarantee of reaching the global optimum. A small gradient does not imply high test accuracy.

Reading the Four Terms

Under a fixed step size, the last three terms do not automatically vanish by increasing $T$. They are residuals in the upper bound, not precise lower bounds on the algorithm’s actual error. Even if $\zeta=0$, random noise may still produce drift via different local paths; even if $\sigma=0$, heterogeneity may still cause bias.

If we fix $N,E,b$ and choose $\eta=c/\sqrt T$ for a run of length $T$, where $0<c\le1/(8LE)$, this bound yields $O(T^{-1/2})+O(T^{-1})$. Here, a fixed step size is still used within each run; this is not a proof for online-changing $\eta_t$. When $E$ or $N$ grows with $T$, one must re-substitute all terms and cannot continue to hide them in constants.

When $E=1$, the drift terms vanish completely, and the algorithm recovers full-participation synchronous mini-batch SGD. The constants in the above general bound are relatively loose; directly using the unbiased gradient proof from Part 3 ¹ yields better constants. If the squared norm of the objective gradient is $\epsilon$, this bound can only provide a guarantee when $\epsilon>4A$ by increasing $T$.

0x05 Strongly Convex Objectives

If we further assume $f$ is $\mu$-strongly convex and an optimal solution $w^\ast$ exists, let $f^\ast=f(w^\ast)$ and $\mathcal E_t=\mathbb E[f(w_t)]-f^\ast$. Applying the PL inequality

The core recurrence becomes

Since $\mu\le L$, the step-size condition guarantees $\rho=1-\alpha\mu/2\in(0,1)$. Expanding the geometric series:

defination

$$ \mathcal E_T\le\rho^T\mathcal E_0 +\frac{2A}{\mu}(1-\rho^T). $$

With fixed local step sizes, the transient term contracts geometrically, but this bound typically only guarantees $\limsup_T\mathcal E_T\le2A/\mu$. Only when the residual vanishes does this recurrence yield geometric convergence to the exact optimal value.

If $0<2A/\mu<\epsilon<\mathcal E_0$, the sufficient number of rounds is

When $A=0$, directly use $\rho^T\mathcal E_0$; when the objective falls below the residual upper bound, the above round formula cannot provide guarantees. For a more detailed strongly convex analysis with decaying step sizes, see Li et al., ICLR 2020⁴, but note that the assumptions, time indexing, and aggregation scheme in that paper require item-by-item alignment; one cannot simply replace the theorem here with a single $O(1/T)$ conclusion from it.

0x06 A Deterministic Drift Example

The residual mentioned earlier is merely an upper bound. Below, we use a noiseless example to show that local drift can genuinely exist, rather than being an artifact of proof techniques.

Consider two equally weighted clients, $0<a<1/\sqrt2$:

Both local objectives are $L$-smooth and strongly convex; we can take $L=1+\sqrt2a$ and local strong convexity parameter $1-\sqrt2a$. The heterogeneity bound holds over the entire space:

Starting from the global optimum $w_t=0$, each client performs two steps of deterministic GD. The first step reaches $-\eta a$ and $\eta a$ respectively; averaging the models after the second step yields exactly

For sufficiently small positive step sizes, this is not zero: FedAvg can even move away from the global optimum. Conversely, when $E=1$, the two local gradients at $w=0$ completely cancel out.

If $0<\eta\le1/L$, each local GD mapping is a contraction; the average of the two-step mappings remains a contraction. Thus, this fixed-step-size FedAvg mapping has a unique attracting fixed point, and since it does not map zero to zero, the fixed point is not equal to the global optimum. This example satisfies the heterogeneity assumptions of the main theorem; additionally, taking $\eta\le1/(16L)$ also satisfies the main theorem’s step-size constraints for $E=2$.

The following Python code verifies the one-round formula and the fixed point; it runs directly without third-party libraries:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from math import cos, sin, sqrt

a, eta = 0.25, 0.04
assert eta * 2 * (1 + sqrt(2) * a) <= 1 / 8


def fedavg_round(w, steps=2):
    local = []
    for sign in (1, -1):
        x = w
        for _ in range(steps):
            x -= eta * (x + sign * a * (cos(x) - sin(x)))
        local.append(x)
    return sum(local) / 2


assert abs(fedavg_round(0) + eta * a * sin(eta * a)) < 1e-12
assert abs(fedavg_round(0, steps=1)) < 1e-12
w = 0.0
for _ in range(2000):
    w = fedavg_round(w)
assert abs(w) > 1e-6
assert abs(fedavg_round(w) - w) < 1e-12
print(f"FedAvg fixed point: {w:.8f}; global optimum: 0")

This is a numerical check for the analytical example, not a substitute for a general convergence proof via experiments.

0x07 Partial Participation and Aggregation Weights

Client Sampling Adds Another Variance Term

Now consider only $E=1$, still optimizing the equally weighted objective. Each round, we select $m$ clients uniformly and without replacement from $N>1$ clients. Selection occurs before batch sampling and is independent of the noise in the new samples for that round. If the aggregation direction is $\hat g_t=m^{-1}\sum_{i\in S_t}g_i(w_t)$, then

The second term is the finite population sampling variance, distinct from the stochastic gradient noise within clients. We derive this coefficient below. Given $\mathcal F_t$, denote $a_i=\nabla f_i(w_t)-\nabla f(w_t)$ and $I_i=\mathbf 1_{{i\in S_t}}$; in this case, $\sum_i a_i=0$. Uniform sampling without replacement satisfies

Expanding the square and taking expectations separately for diagonal and off-diagonal terms:

The sample gradient noise has zero mean given $S_t$, so the cross-terms with the client sampling bias here vanish, yielding the aforementioned total variance bound. When $m=N$, the sampling term is zero; with sampling with replacement, the heterogeneity coefficient becomes $1/m$, and the finite population correction for sampling without replacement cannot be applied.

Thus, for $0<\eta\le1/L$, directly applying the one-step descent from Part 3 gives

When $N=1$, one must take $m=1$ and not compute formulas containing $N-1$. For $E>1$, one cannot simply replace the main theorem’s $N$ with $m$; one must simultaneously control local drift and client selection.

Extending the Bound to Multiple Local Steps

We still use uniform sampling without replacement, independent of the new sample noise each round. All selected clients start from $w_t$, execute the same $E$ steps, and the server performs an equal-weight average of these $m$ local models. Define

$u_t$ is the client sampling error on the common round-initial parameters and cannot be absorbed into the local sample noise. Treating $z_t=u_t+e_t^{(m)}$ as a composite noise for one round, and using the sampling variance and martingale difference properties from the previous subsection, we have

Here we used $\mathbb E[e_t^{(m)}\mid\mathcal F_t,S_t]=0$, so the cross-terms between $u_t$ and $e_t^{(m)}$ are zero. The cross-terms between drift $r_t^{(m)}$ and $z_t$ are still not assumed to be zero.

We also need to verify whether the drift bound is preserved. Define the expected average displacement of the selected clients

At the start of each round, local gradients do not depend on $S_t$, and the selection probability for each client is $m/N$, so

Therefore, by first expanding the path for selected clients and then taking expectations over selection and noise, $D_{t,k}^{(m)}$ satisfies the same recurrence as 0x03. By Jensen’s inequality, we obtain

Now we can repeat the descent proof from 0x04: substitute $z_t$ for $e_t$, preserving its correlation with drift, and replace the noise variance with $\chi_m\zeta^2+\sigma^2/(bmE)$. Define

defination

Under the above uniform without-replacement partial participation model and $0<\eta\le1/(8LE)$,

$$ \frac1T\sum_{t<T}\mathbb E\|\nabla f(w_t)\|^2 \le\frac{4\Delta_0}{\eta ET}+4A_m. $$

If the strong convexity condition also holds, then the same $\rho=1-\eta E\mu/2$ yields

$$ \mathcal E_T\le\rho^T\mathcal E_0+\frac{2A_m}{\mu}(1-\rho^T). $$

When $m=N$, $\chi_m=0$ and $A_m=A$ recover the full participation results. When $E=1$, the structure of “noise plus sampling error” is also recovered, but the step-size constraints and constants here are more conservative; the precise drift-free analysis from the previous subsection should be prioritized. When $N=m=1$, $\chi_m=0$ is defined separately.

The additional $L\eta E\chi_m\zeta^2$ is a client sampling term, which has a different scale from the original $\eta^2(E-1)^2\zeta^2$ local drift term. Increasing $m$ can reduce sampling error, but one cannot thereby claim that local drift also vanishes according to $1/m$. Non-uniform selection depending on training state, consecutive participation of the same batch of clients over multiple rounds, weighted aggregation, and varying numbers of local steps are not directly covered by this extension.

Weighting Can Change the Target

If the goal is $f=\sum_i p_i f_i$, but in each round a single client is chosen uniformly and its update is fully adopted, then the expected gradient at $E=1$ is $N^{-1}\sum_i\nabla f_i$, and not necessarily $\nabla f$.

For example, $p_1=0.9,p_2=0.1$, $f_1(w)=w^2/2$, $f_2(w)=(w-2)^2/2$. The optimum of the weighted objective is $0.2$, while the optimum of the equal-weight objective is $1$. The issue here is not “slow convergence,” but rather optimizing a different objective.

If client $i$ has a selection probability of $\pi_i>0$, then when computing gradients on the same $w$, the unbiased Horvitz–Thompson form is

This requires the selection mechanism and new sample noise to satisfy corresponding conditions. Ratio estimators obtained by randomly dividing by “the sum of weights of selected clients” are generally no longer strictly unbiased; importance weighting may also increase variance. The actual FedAvg aggregation scheme requires specific analysis and cannot be assumed equivalent to the above estimator across all implementations.

Selecting clients based on online rate, completion speed, or loss may similarly alter the objective and noise conditions. ² remains applicable here regarding the warning about “selecting the fastest clients.”

0x08 Communication, Drift, and Corrections

Local Work Is Not Free Progress

When the total number of local updates $H=ET$ is fixed, the optimization term in the main bound is $4\Delta_0/(\eta H)$. Increasing $E$ can reduce the number of communication rounds, but the drift term increases, and the step size must also satisfy $\eta LE\le1/8$. Therefore, when comparing different $E$, one cannot compare only the number of communication rounds or retain only the first term in the bound.

If the effective step size $\alpha=\eta E$ is fixed, then substituting into $\eta=\alpha/E$, the heterogeneity term’s $\eta^2(E-1)^2$ approaches $\alpha^2$ and will not automatically vanish even if the number of local steps increases indefinitely. For wall-clock time, one must also account for the durations of downloading, uploading, local training, and waiting; this can be combined with the ideas in Efficiency Analysis⁵, but the homogeneous worker time model in that paper cannot directly represent mobile devices.

Choosing Parameters from the Bound

Step size, number of local steps, and number of participants are not three parameters that can be independently increased without limit. Treating an experiment as a run with fixed $T,E,m,b$, the non-convex bound for partial participation has the following structure:

If $c_0>0$ and $c_1+c_2>0$, the unconstrained minimum is determined by the unique positive root of the following equation:

The left-hand side is strictly increasing on the positive half-axis, so the root can be found via bisection, and then the smaller value with $1/(8LE)$ is taken. When $c_2=0,c_1>0$, we obtain $\eta=\sqrt{c_0/c_1}$; when $c_1=c_2=0$, the bound decreases as the step size increases, so the upper limit within the allowed interval suffices. When $c_0=0$, the notion of a unique positive root cannot be applied directly; the residual starting from the optimum must be checked separately.

This explains why tuning parameters solely based on $\eta\propto1/\sqrt T$ is not always sufficient: when heterogeneity is high and the number of local steps is large, the quadratic term cannot be ignored. The above formula is used to understand the upper bound, not as a directly copy-pasteable practical optimal learning rate; $L,\Delta_0,\sigma^2,\zeta^2$ is typically unknown, and theoretically allowed step sizes are often conservative.

For practical training, one can treat a single local update step as a baseline, then add $E$ and inspect the training curves. When comparing, fix a single budget, such as the total number of local updates or total wall-clock time, and report the number of communication rounds simultaneously; if a set of experiments increases both local computation and communication rounds, comparing only the final accuracy cannot demonstrate whether local updates are more effective.

Distinguishing Error Sources in Experiments

Furthermore, inconsistent label distributions, inconsistent sample sizes, and inconsistent optima are not the same thing. $\zeta^2$ measures gradient differences at the parameter location, not parameters for a specific data partition. When partitioning data using a Dirichlet distribution, the concentration parameter can control the partitioning method, but it cannot unconditionally be written as an analytical expression of $\zeta^2$.

One can estimate gradients for each client on the server parameters $w_t$, then observe the differences between gradients; however, differences computed from a finite batch still contain sample noise and cannot be directly treated as true heterogeneity. Repeated sampling, larger diagnostic batches, or explicit noise estimation all help distinguish between the two. In real cross-device training, such additional diagnostics incur communication and data access costs.

FedProx and SCAFFOLD

FedProx⁶ adds a proximal term to the local objective within a round:

It imposes a cost for local parameters deviating from server parameters. The proximal term cannot guarantee exact elimination of drift in all problems solely based on its form; its analysis also involves objective conditions and local solution accuracy. It is also not the unmodified FedAvg update rule presented in this paper.

⁷ uses control variates to correct the direction:

If $c_i=\nabla f_i(w_t)$ and $c=\nabla f(w_t)$ are ideally chosen at the start of the round, the mean of the corrected gradients at $w_i=w_t$ exactly equals the global gradient; after local parameters move, there remains error arising from the positional change. The actual algorithm maintains estimates of control variates and must also analyze estimation error, update mechanisms, and sampling. Here we explain the correction mechanism without treating it as a proven SCAFFOLD convergence theorem.

0x09 What the Analysis Guarantees

The main conclusions of this paper are built upon full participation, equal weighting, synchronization, identical local step counts, conditionally unbiased noise, and a unified heterogeneity bound. For non-convex settings, the conclusion is a guarantee of average stationary points; for strongly convex settings, it is geometric contraction toward an error upper bound under a fixed step size. Extensions for partial participation cover uniform without-replacement sampling per round and equal-weight models with identical local step counts; the discussion on weighted sampling addresses objective consistency and does not claim to be a comprehensive theorem covering all FedAvg implementations.

When training different neural networks, one must also check whether smoothness, sampling, batch correlation, participation mechanisms, and optimizers align with the model. Adam, momentum, varying local step counts, asynchronous servers, and non-smooth activations do not automatically satisfy the assumptions of this paper just because the algorithm is also called FedAvg. Verifying accuracy, generalization, fairness, and privacy is also not directly guaranteed by the optimization bounds presented here.

For a practical experiment, I would first record the target weights and $N,m,E,b,\eta$, then separately observe client sampling, local drift, and communication latency. Distinguishing these quantities clearly reveals whether one is improving the optimization direction, reducing stochastic noise, or trading more local computation for less communication.

Reference

Sources: ⁸.