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.

Nonconvex SCAFFOLD server-update moments

Statement

Assume the Axiom of Choice. Let $f_{i} : R^{d} \to R$ be differentiable with $β$ -Lipschitz gradients and let $f = N^{- 1} \sum_{i} f_{i}$ . Run Option II SCAFFOLD with $1 \leq S \leq N$ uniformly sampled clients, $K \geq 1$ local steps, and conditionally unbiased local stochastic gradients of variance at most $σ^{2}$ . Initialize $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ , and set $\tilde{η} = K η_{l} η_{g}$ . Let $E_{r}$ and $Ξ_{r - 1}$ be the drift and tracking errors in the SCAFFOLD analysis-trajectory definition, and let $F_{r - 1}$ be the history before the fresh round- $r$ client sample. All outer expectations below include that history and the current round. Then $E {∥ E [x_{r} ∣ F_{r - 1}] - x_{r - 1} ∥}_{2}^{2} \leq 2 {\tilde{η}}^{2} β^{2} E_{r} + 2 {\tilde{η}}^{2} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2},$ and $E ∥ x_{r} - x_{r - 1} ∥_{2}^{2} \leq 6 {\tilde{η}}^{2} β^{2} E_{r} + 12 {\tilde{η}}^{2} β^{2} Ξ_{r - 1} + 3 {\tilde{η}}^{2} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + \frac{18 {\tilde{η}}^{2} σ^{2}}{K S} .$

Statement references

Karimireddy et al., SCAFFOLD, Appendix E.2, Lemma 14 and its proof

Facts & Assumptions

Given: The SCAFFOLD server and client updates, smooth client gradients, and stochastic-gradient hypotheses in the Statement.

[F1]

SCAFFOLD with client and server control variates: the server displacement is the scaled selected mean of corrected client gradients, and $c = N^{- 1} \sum_{i} c_{i}$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $E_{r}$ averages squared displacements of the gradient-query points from $x_{r - 1}$ , while $Ξ_{r - 1}$ averages squared distances of stored anchors from $x_{r - 1}$ .

[F3]

Option II controls track gradients at stored client anchors: each control equals the mean full gradient at its stored anchors plus a residual; the client controls average to the server control; the average residual second moment per client is at most $σ^{2} / K$ .

[F4]

Second moment bound for a finite martingale-difference sum: a finite sum of predictable conditional means plus centered local errors has second moment at most twice the mean-sum second moment plus twice the total conditional variance bound.

[F5]

Moments of a uniformly sampled fixed-size client set: conditional on the history, the fresh uniform sample is unbiased and its centered mean variance is at most twice $(1 - S / N) / S$ times the population second moment.

[F6]

Gradient of a finite sum is the finite sum of gradients: the population mean of client gradients at $x$ is $\nabla f (x)$ .

[F7]

Relaxed inequalities for squared Euclidean norms and The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : for three vectors, $∥ u + v + w ∥_{2}^{2} \leq 3 (∥ u ∥_{2}^{2} + ∥ v ∥_{2}^{2} + ∥ w ∥_{2}^{2})$ ; squared norms expand as inner products.

[F8]

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 are linear and preserve the integrable bounds.

[A1]

Current-round client sampling is independent of the preceding history, and each local error is conditionally centered with second moment 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 [F8].

Proof

1.1F1F2F6F7F8A1A2givenalgebra

Write $x = x_{r - 1}$ and [given] $d_{i, k} = \nabla f_{i} (y_{i, k - 1}^{r}) - \nabla f_{i} (x)$ . Conditional on the round-start history, client sampling is unbiased, local stochastic-gradient errors are centered, and the client-control terms cancel because $c = N^{- 1} \sum_{i} c_{i}$ . Thus $E [x_{r} - x ∣ F_{r - 1}] = - \tilde{η} (\nabla f (x) + \frac{1}{K N} \sum_{i, k} E [d_{i, k} ∣ F_{r - 1}]) .$ Conditional Jensen, Lipschitzness, and the two-vector relaxed-square bound imply, after averaging the history, $E {∥ E [x_{r} ∣ F_{r - 1}] - x ∥}_{2}^{2} \leq 2 {\tilde{η}}^{2} E ∥ \nabla f (x) ∥_{2}^{2} + 2 {\tilde{η}}^{2} β^{2} E_{r} .$

1.2F2F3F4F5F6F8A1A2givenalgebra

Let $m_{i} = K^{- 1} \sum_{k} \nabla f_{i} (α_{i, k}^{r - 1})$ , [given] $a_{i} = m_{i} - \nabla f_{i} (x)$ , and $e_{i} = c_{i} - m_{i}$ . Define $\overset{ˉ}{a} = N^{- 1} \sum_{i} a_{i}$ and ${\overset{ˉ}{a}}_{S} = S^{- 1} \sum_{i \in S} a_{i}$ , with analogous notation for $e_{i}$ . The corrected server direction has the decomposition $\frac{1}{K S} \sum_{i \in S, k} (g_{i} (y_{i, k - 1}) - c_{i} + c) = A + \nabla f (x) + Q,$ where $A = \frac{1}{K S} \sum_{i \in S, k} (g_{i} (y_{i, k - 1}) - \nabla f_{i} (x)), Q = \overset{ˉ}{a} - {\overset{ˉ}{a}}_{S} + \overset{ˉ}{e} - {\overset{ˉ}{e}}_{S} .$ Apply [F4] to the current-query terms in $A$ ; Jensen and Lipschitzness give $E ∥ A ∥_{2}^{2} \leq 2 β^{2} E_{r} + 2 σ^{2} / (K S)$ . For the anchor vectors, [F2], Jensen and Lipschitzness give $N^{- 1} \sum_{i} E ∥ a_{i} ∥_{2}^{2} \leq β^{2} Ξ_{r - 1}$ . Apply [F5] conditionally to $a_{i}$ and $e_{i}$ , then [F3] to their residual average. This yields $E ∥ Q ∥_{2}^{2} \leq \frac{4 (1 - S / N)}{S} (β^{2} Ξ_{r - 1} + \frac{σ^{2}}{K}) \leq 4 β^{2} Ξ_{r - 1} + \frac{4 σ^{2}}{K S} .$

2.1F1F2F7step 1.2givenalgebra∎

Apply [F7] to the three-term decomposition in step 1.2 and multiply by ${\tilde{η}}^{2}$ . Substitute the bounds from that step. The local-drift, anchor-tracking, gradient and noise coefficients are $6 β^{2}$ , $12 β^{2}$ , $3$ and $18 σ^{2} / (K S)$ , respectively. This is the second inequality in the Statement.

Depends on

Used by

Dependency tree · two levels

56 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 E.2, Lemma 14 (standard reference, not scraped)