LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Client drift under FedAvg gradient dissimilarity

Statement

Let $N \geq S \geq 1$ , $K \geq 1$ , and let $f_{i} : R^{d} \to R$ be convex differentiable functions with $β$ -Lipschitz gradients, $β > 0$ . Put $f = N^{- 1} \sum_{i} f_{i}$ and suppose $x^{⋆}$ minimizes $f$ . At a fixed FedAvg round start $x$ , each sampled client performs $K$ local updates as in the uniform-client analysis mode of the FedAvg algorithm, with local step $η_{l} > 0$ , global scale $η_{g} \geq 1$ , and conditionally unbiased local stochastic gradients of variance at most $σ^{2}$ at every queried point. The client sample is uniform without replacement and independent of the fresh local-oracle randomness. Suppose $B \geq 1$ , $G \geq 0$ , and for every $z \in R^{d}$ , $\frac{1}{N} \sum_{i = 1}^{N} ∥ \nabla f_{i} (z) ∥_{2}^{2} \leq G^{2} + 2 β B^{2} (f (z) - f^{⋆}) .$ Alternatively, assume the standard $(G, B)$ -bounded gradient-dissimilarity condition $\frac{1}{N} \sum_{i} ∥ \nabla f_{i} (z) ∥_{2}^{2} \leq G^{2} + B^{2} ∥ \nabla f (z) ∥_{2}^{2} (z \in R^{d}) .$ Either assumption gives all the conclusions below with the same $G, B$ and stepsize restrictions. Let $\tilde{η} = K η_{l} η_{g}$ , write $y_{i, k}$ for the local path initialized at $y_{i, 0} = x$ , and define the query-point drift $E = \frac{1}{K N} \sum_{i = 1}^{N} \sum_{k = 1}^{K} E ∥ y_{i, k - 1} - x ∥_{2}^{2},$ where, for each client, the local path has the same local-oracle law whether it is sampled or represented by a hypothetical copy, and those fresh path draws are independent of the client sample. Independence among different clients' oracle draws is not required. If $0 < \tilde{η} \leq \frac{1}{8 (B^{2} + 1) β},$ then $3 β \tilde{η} E \leq \frac{2 \tilde{η}}{3} (f (x) - f^{⋆}) + \frac{{\tilde{η}}^{2} σ^{2}}{2 K η_{g}^{2}} + 18 β {\tilde{η}}^{3} G^{2} .$

Statement references

Standard and gap forms of bounded client gradient dissimilarity

Standard client dissimilarity implies the gap form with unchanged parameters

Karimireddy et al., SCAFFOLD, Appendix D.3, Lemma 8 and its proof

Facts & Assumptions

Given: The equal-client objective, local paths and stochastic-gradient assumptions in the Statement.

[F1]

Federated averaging (FedAvg): each local update is $y_{i, k} = y_{i, k - 1} - η_{l} g_{i} (y_{i, k - 1})$ .

[F2]

Gradient steps of smooth convex functions are nonexpansive: if $η_{l} \leq 2 / β$ , then $y \mapsto y - η_{l} (\nabla f_{i} (y) - \nabla f_{i} (x))$ does not increase the distance from $x$ .

[F3]

Relaxed inequalities for squared Euclidean norms and The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : squared norms expand bilinearly and $∥ u + v ∥_{2}^{2} \leq (1 + a) ∥ u ∥_{2}^{2} + (1 + a^{- 1}) ∥ v ∥_{2}^{2}$ for $a > 0$ .

[F4]

Filtration and filtered probability space, Conditional expectation as an ae class, Basic algebra and order properties of conditional expectation, Taking out what is known, Expectation of a nonnegative or integrable random variable, and Linearity, monotonicity, and the modulus bound for expectation: conditional expectations at each local query are linear, preserve the integrable bounds, and take history-measurable vectors out of the conditional expectation.

[F5]

The population gradient second moment obeys the dissimilarity bound in the Statement.

[F6]

Standard client dissimilarity implies the gap form with unchanged parameters: under the stated common smoothness and attained finite minimum, the standard condition implies the displayed gap form with unchanged $G, B$ .

[A1]

Each oracle draw is conditionally unbiased given the full history before that draw and has conditional variance at most $σ^{2}$ .

[A2]

Assume the Axiom of Choice. It is used only to invoke the published conditional-expectation-as-an-a.e.-class interface in [F4].

Proof

1.1F6F1F2F3F4A1A2giveninductionalgebra

In the standard-condition branch, [F6] supplies the displayed gap-form assumption with unchanged $G, B$ ; in the original gap-form branch it is already assumed. If $K = 1$ , every query point is $x$ and $E = 0$ . Suppose $K \geq 2$ . For a [given] fixed client, put $d_{k} = y_{i, k} - x$ , $g = \nabla f_{i} (x)$ , and $ξ_{k} = g_{i} (y_{i, k - 1}) - \nabla f_{i} (y_{i, k - 1})$ . Define $T_{i} (y) = y - η_{l} (\nabla f_{i} (y) - \nabla f_{i} (x))$ . The local update is $d_{k} = T_{i} (y_{i, k - 1}) - x - η_{l} g - η_{l} ξ_{k}$ . By [F2] and the stepsize condition, $∥ T_{i} (y_{i, k - 1}) - x ∥_{2} \leq ∥ d_{k - 1} ∥_{2}$ . Conditional centering of $ξ_{k}$ therefore gives $q_{k} : = E ∥ d_{k} ∥_{2}^{2} \leq (\sqrt{q_{k - 1}} + η_{l} ∥ g ∥_{2})^{2} + η_{l}^{2} σ^{2} .$ Induction from $q_{0} = 0$ yields $q_{k} \leq (k η_{l} ∥ g ∥_{2} + \sqrt{k} η_{l} σ)^{2} \leq 2 k^{2} η_{l}^{2} ∥ g ∥_{2}^{2} + 2 k η_{l}^{2} σ^{2}$ : substituting the bound at $k - 1$ into the recurrence gives $(k η_{l} ∥ g ∥_{2} + \sqrt{k - 1} η_{l} σ)^{2} + η_{l}^{2} σ^{2}$ , which is at most the claimed square.

2.1F5step 1.1givenalgebra

Average the step 1.1 bound for $d_{k - 1}$ over $k = 1, \dots, K$ and [given] clients. Since $K^{- 1} \sum_{k = 1}^{K} 2 (k - 1)^{2} \leq 2 K^{2} / 3$ and $K^{- 1} \sum_{k = 1}^{K} 2 (k - 1) = K - 1 \leq K$ , this gives $E \leq \frac{2}{3} K^{2} η_{l}^{2} \frac{1}{N} \sum_{i} ∥ \nabla f_{i} (x) ∥_{2}^{2} + K η_{l}^{2} σ^{2} \leq \frac{2}{3} K^{2} η_{l}^{2} (G^{2} + 2 β B^{2} (f (x) - f^{⋆})) + K η_{l}^{2} σ^{2} .$ Uniform sampling makes the expected average over selected clients the population average, and the hypothetical local paths have the same per-client law.

3.1F5step 2.1givenalgebra∎

Multiply step 2.1 by $3 β \tilde{η}$ and use $η_{l} = \tilde{η} / (K η_{g})$ . The three resulting coefficients are $2 β {\tilde{η}}^{3} / η_{g}^{2}$ for $G^{2}$ , $4 β^{2} B^{2} {\tilde{η}}^{3} / η_{g}^{2}$ for the function gap, and $3 β {\tilde{η}}^{3} / (K η_{g}^{2})$ for the variance. Since $η_{g} \geq 1$ and $β \tilde{η} \leq 1 / [8 (B^{2} + 1)]$ , these are at most $18 β {\tilde{η}}^{3}$ , $2 \tilde{η} / 3$ , and ${\tilde{η}}^{2} / (2 K η_{g}^{2})$ , respectively. This proves the claim.

Depends on

Used by

Strongly convex FedAvg under bounded gradient dissimilarity Theorem

Dependency tree · two levels

51 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sai Praneeth Karimireddy et al., SCAFFOLD, Appendix D.3, Lemma 8 (standard reference, not scraped)