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 client-drift bound

Statement

Let $f_{i} : R^{d} \to R$ be convex, differentiable and $β$ -smooth, with $f = N^{- 1} \sum_{i} f_{i}$ minimized at $x^{⋆}$ . Run Option II SCAFFOLD for $K \geq 1$ local steps with server scale $η_{g} \geq 1$ , local step $η_{l}$ , and fresh conditionally unbiased local stochastic gradients of variance at most $σ^{2}$ . Use controls satisfying $c = N^{- 1} \sum_{i} c_{i}$ , initialized by $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ . Let $E_{r}, C_{r - 1}$ be the local-drift and convex control-lag quantities in the SCAFFOLD analysis-trajectory definition. For $\tilde{η} = K η_{l} η_{g} \leq 1 / (81 β)$ , $3 β \tilde{η} E_{r} \leq \frac{2 {\tilde{η}}^{2}}{3} C_{r - 1} + \frac{\tilde{η}}{25 η_{g}^{2}} E [f (x_{r - 1}) - f^{⋆}] + \frac{{\tilde{η}}^{2} σ^{2}}{K η_{g}^{2}} .$

Statement references

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

Facts & Assumptions

Given: The SCAFFOLD local updates, controls, error quantities and stochastic-gradient assumptions in the Statement.

[F1]

SCAFFOLD with client and server control variates: a local update subtracts $η_{l} (g_{i} (y) - c_{i} + c)$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $E_{r}$ averages squared displacements at the query points $y_{i, k - 1}^{r}$ ; $C_{r - 1}$ is the average expected squared error of the mean full gradient at each client's stored anchors from $\nabla f_{i} (x^{⋆})$ .

[F3]

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$ .

[F4]

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

[F5]

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^{⋆})$ .

[F6]

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 current local oracle error has conditional mean zero and conditional second moment at most $σ^{2}$ ; the needed conditional expectations and finite sums obey the stated tower and linearity rules.

[F7]

Option II controls track gradients at stored client anchors: for every client the current control equals the mean full gradient at its stored anchors plus a residual with second moment at most $σ^{2} / K$ .

[A1]

The stochastic-gradient assumptions and gradient-consistent initialization in the Statement hold at every round and local query.

[A2]

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

Proof

1.1F1F3F4F6F7A1A2givenalgebra

If $K = 1$ , every query is the round-start point, so $E_{r} = 0$ and the claim [given] follows. Suppose $K \geq 2$ . Put $m_{i} = K^{- 1} \sum_{k} \nabla f_{i} (α_{i, k}^{r - 1})$ , $e_{i} = c_{i}^{r - 1} - m_{i}$ , $a_{i} = m_{i} - \nabla f_{i} (x^{⋆})$ , $\overset{ˉ}{a} = N^{- 1} \sum_{i} a_{i}$ , and $\overset{ˉ}{e} = N^{- 1} \sum_{i} e_{i}$ . Since $c = N^{- 1} \sum_{i} c_{i}$ and $N^{- 1} \sum_{i} \nabla f_{i} (x^{⋆}) = 0$ , the residual vector in client $i$ 's update is $v_{i} = c - c_{i} + \nabla f_{i} (x_{r - 1}) = \overset{ˉ}{a} - a_{i} + \overset{ˉ}{e} - e_{i} + (\nabla f_{i} (x_{r - 1}) - \nabla f_{i} (x^{⋆})) .$ For each realization, $N^{- 1} \sum_{i} ∥ \overset{ˉ}{a} - a_{i} ∥_{2}^{2} \leq N^{- 1} \sum_{i} ∥ a_{i} ∥_{2}^{2}$ ; the same identity applies to $e_{i}$ . Thus [F2], [F5], and [F7], followed by the three-term squared-norm bound, give $\frac{1}{N} \sum_{i} E ∥ v_{i} ∥_{2}^{2} \leq 3 C_{r - 1} + 3 \frac{σ^{2}}{K} + 6 β E [f (x_{r - 1}) - f^{⋆}] \leq 6 (C_{r - 1} + β E [f (x_{r - 1}) - f^{⋆}] + \frac{σ^{2}}{K}) .$ For $d_{i, k} = y_{i, k}^{r} - x_{r - 1}$ , write the update as $d_{i, k} = T_{i} (y_{i, k - 1}^{r}) - x_{r - 1} - η_{l} v_{i} - η_{l} ξ_{i, k}$ , where $T_{i} (y) = y - η_{l} (\nabla f_{i} (y) - \nabla f_{i} (x_{r - 1}))$ and $ξ_{i, k} = g_{i} (y_{i, k - 1}^{r}) - \nabla f_{i} (y_{i, k - 1}^{r})$ . The vector before $ξ_{i, k}$ is measurable before that draw, so conditional centering removes the cross term and adds at most $η_{l}^{2} σ^{2}$ . Apply [F3] and [F4] with $a = 1 / (K - 1)$ ; since $η_{l} \leq 1 / (81 β K η_{g}) \leq 2 / β$ , $E ∥ d_{i, k} ∥_{2}^{2} \leq (1 + \frac{1}{K - 1}) E ∥ d_{i, k - 1} ∥_{2}^{2} + K η_{l}^{2} E ∥ v_{i} ∥_{2}^{2} + η_{l}^{2} σ^{2} .$

1.2F2step 1.1givenalgebra

Since $d_{i, 0} = 0$ and [given] $\sum_{j = 0}^{k - 1} (1 + 1 / (K - 1))^{j} \leq 3 K$ for $1 \leq k \leq K$ , the recurrence in step 1.1 bounds each query-point second moment by $3 K (K η_{l}^{2} E ∥ v_{i} ∥_{2}^{2} + η_{l}^{2} σ^{2})$ . Average over clients and query indices and use the bound on $v_{i}$ from step 1.1. The result is $E_{r} \leq 18 K^{2} η_{l}^{2} (C_{r - 1} + β E [f (x_{r - 1}) - f^{⋆}]) + 21 K η_{l}^{2} σ^{2} .$

2.1F2step 1.2givenalgebra∎

Multiply step 1.2 by $3 β \tilde{η}$ and substitute $η_{l} = \tilde{η} / (K η_{g})$ . The coefficients of $C_{r - 1}$ , the function gap, and $σ^{2}$ are respectively $54 β {\tilde{η}}^{3} / η_{g}^{2}$ , $54 β^{2} {\tilde{η}}^{3} / η_{g}^{2}$ , and $63 β {\tilde{η}}^{3} / (K η_{g}^{2})$ . Since $η_{g} \geq 1$ and $β \tilde{η} \leq 1 / 81$ , these are at most $2 {\tilde{η}}^{2} / 3$ , $\tilde{η} / (25 η_{g}^{2})$ , and ${\tilde{η}}^{2} / (K η_{g}^{2})$ , respectively. This proves the claim.

Depends on

Used by

Strongly convex SCAFFOLD progress in one communication round Lemma

Dependency tree · two levels

57 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 12 (standard reference, not scraped)