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 query-point drift bound

Statement

Assume the Axiom of Choice. Let $f_{i} : R^{d} \to R$ have $β$ -Lipschitz gradients with $β > 0$ and let $f = N^{- 1} \sum_{i} f_{i}$ be bounded below. Run Option II SCAFFOLD with $1 \leq S \leq N$ uniformly sampled clients, $K \geq 1$ local steps, server scale $η_{g} \geq 1$ , and fresh conditionally unbiased local stochastic gradients with within-client variance at most $σ^{2}$ . Initialize $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ . Let $\tilde{η} = K η_{l} η_{g}$ and let $E_{r}, Ξ_{r - 1}$ be the query-point drift and anchor-tracking errors in the SCAFFOLD analysis-trajectory definition. If $0 < \tilde{η} \leq \frac{(S / N)^{2 / 3}}{24 β},$ then $E_{r} \leq 72 K^{2} η_{l}^{2} (E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + β^{2} Ξ_{r - 1}) + 96 K η_{l}^{2} σ^{2} .$

Statement references

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

Facts & Assumptions

Given: The Option II local updates, anchor errors and stochastic-gradient assumptions in the Statement.

[F1]

SCAFFOLD with client and server control variates: a local update is $y_{i, k} = y_{i, k - 1} - η_{l} (g_{i} (y_{i, k - 1}) - c_{i} + c)$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $E_{r}$ averages squared displacements of local query points $y_{i, k - 1}^{r}$ from $x_{r - 1}$ ; $Ξ_{r - 1}$ averages squared distances of stored anchors from $x_{r - 1}$ .

[F3]

Option II controls track gradients at stored client anchors: each control $c_{i}$ is the mean full gradient at its stored anchors plus a residual whose second moment is at most $σ^{2} / K$ , and $c = N^{- 1} \sum_{i} c_{i}$ .

[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}$ ; the squared norm of three vectors is at most three times the sum of their squared norms.

[F5]

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 expectation is linear, preserves expectations and inequalities, and permits taking out integrable history-measurable factors. The centering and variance bounds used below are the oracle hypotheses in [A1], not consequences of these interfaces.

[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 [F5].

Proof

1.1F2F3F4F5A1givenalgebra

If $K = 1$ , all query points are at the round start, so $E_{r} = 0$ . Suppose [given] $K \geq 2$ , write $x = x_{r - 1}$ , and define $m_{i} = K^{- 1} \sum_{k} \nabla f_{i} (α_{i, k}^{r - 1})$ , $e_{i} = c_{i} - m_{i}$ , $a_{i} = m_{i} - \nabla f_{i} (x)$ , and their client means $\overset{ˉ}{a} = N^{- 1} \sum_{i} a_{i}$ , $\overset{ˉ}{e} = N^{- 1} \sum_{i} e_{i}$ . The corrected control vector in client $i$ 's local update is $v_{i} = c - c_{i} + \nabla f_{i} (x) = \nabla f (x) + \overset{ˉ}{a} - a_{i} + \overset{ˉ}{e} - e_{i} .$ For each realization, $N^{- 1} \sum_{i} ∥ \overset{ˉ}{a} - a_{i} ∥_{2}^{2} \leq N^{- 1} \sum_{i} ∥ a_{i} ∥_{2}^{2}$ ; the same holds for $e_{i}$ . Lipschitzness and Jensen give $N^{- 1} \sum_{i} E ∥ a_{i} ∥_{2}^{2} \leq β^{2} Ξ_{r - 1}$ , and [F3] gives $N^{- 1} \sum_{i} E ∥ e_{i} ∥_{2}^{2} \leq σ^{2} / K$ . Apply the three-vector bound [F4] to obtain $\frac{1}{N} \sum_{i} E ∥ v_{i} ∥_{2}^{2} \leq 3 (E ∥ \nabla f (x) ∥_{2}^{2} + β^{2} Ξ_{r - 1} + \frac{σ^{2}}{K}) .$

1.2F1F2F4F5step 1.1A1A2givenalgebra

Put $d_{i, k} = y_{i, k}^{r} - x$ . Define [given] $T_{i} (y) = y - η_{l} (\nabla f_{i} (y) - \nabla f_{i} (x))$ and $ξ_{i, k} = g_{i} (y_{i, k - 1}^{r}) - \nabla f_{i} (y_{i, k - 1}^{r})$ . The update is $d_{i, k} = T_{i} (y_{i, k - 1}^{r}) - x - η_{l} v_{i} - η_{l} ξ_{i, k}$ , and $∥ T_{i} (y_{i, k - 1}^{r}) - x ∥_{2} \leq (1 + η_{l} β) ∥ d_{i, k - 1} ∥_{2}$ . Conditional centering of $ξ_{i, k}$ removes its cross term with the pre-draw vector. Use [F4] with $a = 1 / (K - 1)$ to get $E ∥ d_{i, k} ∥_{2}^{2} \leq q E ∥ d_{i, k - 1} ∥_{2}^{2} + K η_{l}^{2} E ∥ v_{i} ∥_{2}^{2} + η_{l}^{2} σ^{2}, q = (1 + \frac{1}{K - 1}) (1 + η_{l} β)^{2} .$ The step bound implies $η_{l} β \leq 1 / (24 K)$ . For $K \geq 2$ , $1 + 1 / (K - 1) \leq 1 + 2 / K$ and $(1 + 1 / (24 K))^{2} \leq 1 + 1 / (10 K)$ , hence $q \leq 1 + 3 / K$ . Therefore $\sum_{j = 0}^{K - 1} q^{j} \leq K (1 + 3 / K)^{K} \leq K e^{3} < 24 K$ . Unrolling from $d_{i, 0} = 0$ and averaging the query points gives $E_{r} \leq 24 K^{2} η_{l}^{2} \frac{1}{N} \sum_{i} E ∥ v_{i} ∥_{2}^{2} + 24 K η_{l}^{2} σ^{2} .$

2.1F2step 1.1step 1.2algebra∎

Substitute the control-vector bound from step 1.1 into step 1.2. [given] Collecting the gradient, anchor-tracking and oracle-variance terms gives $E_{r} \leq 72 K^{2} η_{l}^{2} (E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + β^{2} Ξ_{r - 1}) + 96 K η_{l}^{2} σ^{2},$ which is the Statement.

Depends on

Used by

Nonconvex SCAFFOLD progress in one communication round Lemma

Dependency tree · two levels

46 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 16 (standard reference, not scraped)