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.

Variance reduction across independent local-SGD workers

Statement

At a fixed time $t$ , suppose the worker points $x_{t}^{1}, \dots, x_{t}^{K}$ are determined by the earlier sampled indices. Define $g_{t} = \frac{1}{K} \sum_{k = 1}^{K} g_{t}^{k} (x_{t}^{k}), {\overset{ˉ}{g}}_{t} = \frac{1}{K} \sum_{k = 1}^{K} \nabla f (x_{t}^{k}),$ where each $g_{t}^{k}$ is the average of $b \geq 1$ independent uniform component gradients from ${f_{1}, \dots, f_{n}}$ . If, for every worker point $x_{t}^{k}$ , $\frac{1}{n} \sum_{j = 1}^{n} ∥ \nabla f_{j} (x_{t}^{k}) - \nabla f (x_{t}^{k}) ∥_{2}^{2} \leq σ^{2},$ then $E ∥ g_{t} - {\overset{ˉ}{g}}_{t} ∥_{2}^{2} \leq \frac{σ^{2}}{b K} .$

Statement references

Stich, Local SGD Converges Fast and Communicates Little, Lemma 3.2, Remark 2.4 and Appendix A

Facts & Assumptions

Given: The finite-sum objective, worker iterates, and mutually independent uniform indices in the Statement.

[F1]

Local SGD with periodic synchronization: each worker averages $b$ independent component gradients at its current point.

[F2]

Independent random elements: independence means independence of the sigma-algebras generated by the random indices.

[F3]

Expectation of a nonnegative or integrable random variable: expectation is the integral against the index law; on this finite law it is a finite weighted sum by Expectation agrees with the published finite weighted sum.

[F4]

Linearity, monotonicity, and the modulus bound for expectation: expectation is linear on integrable variables.

[F5]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the squared norm expands as the inner product of a finite sum with itself.

Proof

1.1F1F2F3F4F5givenalgebra

Fix the earlier indices, so each $x_{t}^{k}$ is fixed. For worker $k$ and within-batch draw $q$ , put $ϵ_{k q} = \nabla f_{i_{t, q}^{k}} (x_{t}^{k}) - \nabla f (x_{t}^{k})$ . Uniform sampling gives a zero finite mean for every $ϵ_{k q}$ and $E ∥ ϵ_{k q} ∥_{2}^{2} \leq σ^{2}$ . Distinct draws are independent by [F1]–[F2], so every cross inner product between distinct centered draws has mean zero by [F3]–[F5]. Expanding $g_{t} - {\overset{ˉ}{g}}_{t} = (b K)^{- 1} \sum_{k, q} ϵ_{k q}$ therefore leaves only $b K$ diagonal terms.

2.1step 1.1givenalgebra∎

Each diagonal term is at most $σ^{2}$ by the hypothesis, so the expansion in step 1.1 is at most $(b K)^{- 2} (b K) σ^{2} = σ^{2} / (b K)$ . Averaging over the earlier finite index history proves the unconditional inequality.

Depends on

Used by

Strongly convex local-SGD round complexity Theorem

Dependency tree · two levels

34 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

Sebastian U. Stich, Local SGD Converges Fast and Communicates Little, Lemma 3.2 and Appendix A (standard reference, not scraped)