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.

Convex SCAFFOLD server-update second moment

Statement

Assume the Axiom of Choice. Let $f_{i} : R^{d} \to R$ be convex, differentiable and $β$ -smooth, with equal-client objective $f = N^{- 1} \sum_{i} f_{i}$ attaining $f^{⋆} = f (x^{⋆})$ . At round $r$ , run Option II SCAFFOLD with $S$ clients sampled uniformly without replacement, $K$ local steps and effective step $\tilde{η} = K η_{l} η_{g}$ . Assume $c = N^{- 1} \sum_{i} c_{i}$ , initialize $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ , and assume local stochastic gradients are conditionally unbiased with within-client variance at most $σ^{2}$ . All expectations are unconditional over the round history, client sample and local stochastic-gradient draws. With $E_{r}$ and $C_{r - 1}$ as in the SCAFFOLD analysis-trajectory definition, $E ∥ x_{r} - x_{r - 1} ∥_{2}^{2} \leq 6 {\tilde{η}}^{2} β^{2} E_{r} + 12 {\tilde{η}}^{2} C_{r - 1} + 6 {\tilde{η}}^{2} β E [f (x_{r - 1}) - f^{⋆}] + \frac{18 {\tilde{η}}^{2} σ^{2}}{K S} .$

Statement references

Karimireddy et al., SCAFFOLD, Appendix E.1, Lemma 10 and its proof

Facts & Assumptions

Given: The Option II SCAFFOLD round, controls, convex equal-client objective and stochastic-gradient assumptions in the Statement.

[F1]

SCAFFOLD with client and server control variates: the server displacement is $- \tilde{η} (K S)^{- 1} \sum_{i \in S, k} (g_{i} (y_{i, k - 1}) - c_{i} + c)$ and $c = N^{- 1} \sum_{i} c_{i}$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $E_{r}$ averages the expected squared displacement of the current gradient-query points from $x_{r - 1}$ ; $C_{r - 1}$ averages the expected squared error of the mean full gradient at each stored anchor from $\nabla f_{i} (x^{⋆})$ .

[F3]

Moments of a uniformly sampled fixed-size client set: conditional on fixed client vectors, the sample mean is unbiased and its centered second moment is at most $2 (1 - S / N) / S$ times their population second moment; this also applies conditionally on the history before the fresh round sample.

[F4]

Smooth convex gradient differences around a minimizer and Gradient of a finite sum is the finite sum of gradients: $\nabla f (x^{⋆}) = 0$ and $N^{- 1} \sum_{i} ∥ \nabla f_{i} (x) - \nabla f_{i} (x^{⋆}) ∥_{2}^{2} \leq 2 β (f (x) - f^{⋆})$ .

[F5]

Option II controls track gradients at stored client anchors: if $m_{i} = K^{- 1} \sum_{k} \nabla f_{i} (α_{i, k}^{r - 1})$ and $e_{i} = c_{i} - m_{i}$ , then $N^{- 1} \sum_{i} E ∥ e_{i} ∥_{2}^{2} \leq σ^{2} / K$ .

[F6]

Second moment bound for a finite martingale-difference sum: for the current chronologically ordered oracle errors $ξ_{j}$ , with predictable conditional means $d_{j}$ , the normalized local-query average obeys $E ∥ (K S)^{- 1} \sum_{j} (d_{j} + ξ_{j}) ∥_{2}^{2} \leq 2 E ∥ (K S)^{- 1} \sum_{j} d_{j} ∥_{2}^{2} + 2 σ^{2} / (K S)$ .

[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})$ .

[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: the local conditional moments, current-round conditioning and integrable inequalities are valid under the stated filtration.

[A1]

The uniform client sample in round $r$ is fresh and independent of the history and oracle draws preceding that sample.

[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.1F1F2F5givenalgebra

Put $x = x_{r - 1}$ and $g_{i}^{⋆} = \nabla f_{i} (x^{⋆})$ . For the stored [given] controls define $m_{i} = K^{- 1} \sum_{k} \nabla f_{i} (α_{i, k}^{r - 1})$ , $a_{i} = m_{i} - g_{i}^{⋆}$ , and $e_{i} = c_{i} - m_{i}$ . Set $b_{i} = c_{i} - g_{i}^{⋆} = a_{i} + e_{i}$ , and denote population and selected means by a bar and a subscript $S$ . Since $N^{- 1} \sum_{i} g_{i}^{⋆} = 0$ and $c = N^{- 1} \sum_{i} c_{i}$ , the corrected server direction has the exact three-term decomposition $\frac{1}{K S} \sum_{i \in S, k} (g_{i} (y_{i, k - 1}) - c_{i} + c) = A + D + Q,$ where $A = \frac{1}{K S} \sum_{i \in S, k} (g_{i} (y_{i, k - 1}) - \nabla f_{i} (x)), D = \frac{1}{S} \sum_{i \in S} (\nabla f_{i} (x) - g_{i}^{⋆}), Q = \overset{ˉ}{b} - b_{S} .$ Indeed, adding the three displayed terms cancels the sampled client gradients at $x$ and $x^{⋆}$ and leaves $c - b_{S}$ in the control terms.

2.1F2F3F5F8A1A2step 1.1algebra

Conditional on the pre-sample history, apply [F3] to the vectors [given] $b_{i}$ . Then use $b_{i} = a_{i} + e_{i}$ , [F2], [F5], and the two-vector relaxed square inequality to obtain $E ∥ Q ∥_{2}^{2} \leq 2 (1 - \frac{S}{N}) \frac{1}{S} \frac{1}{N} \sum_{i} E ∥ b_{i} ∥_{2}^{2} \leq 4 (1 - \frac{S}{N}) \frac{C_{r - 1} + σ^{2} / K}{S} \leq 4 C_{r - 1} + \frac{4 σ^{2}}{K S} .$ This also holds when $N = 1$ or $S = N$ , when $Q = 0$ .

2.2F2F3F4F6F8A1A2step 1.1algebra

Write each summand of $A$ as $d_{i, k} + ξ_{i, k}$ with $d_{i, k} = \nabla f_{i} (y_{i, k - 1}) - \nabla f_{i} (x)$ and $ξ_{i, k} = g_{i} (y_{i, k - 1}) - \nabla f_{i} (y_{i, k - 1})$ . Chronologically order the $K S$ current oracle draws and apply [F6]. Jensen's inequality and $β$ -Lipschitzness give $E ∥ A ∥_{2}^{2} \leq 2 β^{2} E_{r} + 2 σ^{2} / (K S)$ . For $D$ , conditional Jensen over the uniform subset and then [F4] give $E ∥ D ∥_{2}^{2} \leq 2 β E [f (x) - f^{⋆}]$ .

3.1F1F2F7step 2.2step 2.1algebra∎

Apply [F7] to the decomposition in step 1.1, multiply by [given] ${\tilde{η}}^{2}$ , and substitute the bounds from steps 2.2 and 2.1. Collecting terms yields $E ∥ x_{r} - x_{r - 1} ∥_{2}^{2} \leq 6 {\tilde{η}}^{2} β^{2} E_{r} + 12 {\tilde{η}}^{2} C_{r - 1} + 6 {\tilde{η}}^{2} β E [f (x_{r - 1}) - f^{⋆}] + \frac{18 {\tilde{η}}^{2} σ^{2}}{K S},$ which is the Statement.

Depends on

Used by

Strongly convex SCAFFOLD progress in one communication round Lemma

Dependency tree · two levels

59 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.1, Lemma 10 (standard reference, not scraped)