LemmaStatement: AI-adaptedProof: 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 control-anchor tracking recursion

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}$ . 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}$ . Current client samples are independent of the past and of the counterfactual local oracle draws. Write $p = S / N$ , $t = \tilde{η} = K η_{l} η_{g}$ , and let $E_{r}, Ξ_{r}$ be the query-point drift and anchor-tracking errors. Then $Ξ_{r} \leq (1 - \frac{p}{2} + 72 β^{2} t^{2}) Ξ_{r - 1} + (2 p + (36 + \frac{8}{p}) β^{2} t^{2}) E_{r} + (18 + \frac{8}{p}) t^{2} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + \frac{108 t^{2} σ^{2}}{K S} .$

Statement references

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

Facts & Assumptions

Given: The SCAFFOLD anchor update, stochastic-gradient assumptions and tracking errors in the Statement.

[F1]

SCAFFOLD with client and server control variates: selected clients replace controls by Option II local updates; unselected clients keep controls and anchors.

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $Ξ_{r}$ is the mean squared distance of stored anchors from $x_{r}$ , and $E_{r}$ is the mean squared query-point drift from $x_{r - 1}$ .

[F4]

Nonconvex SCAFFOLD server-update moments: the conditional mean and second moment of the server displacement are bounded by local drift, tracking error, objective gradient and within-client variance.

[F5]

Moments of a uniformly sampled fixed-size client set: a client is selected with probability $p$ in a uniform size- $S$ sample.

[F6]

Relaxed inequalities for squared Euclidean norms and The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : squared norms of sums obey the stated relaxed-square and Young inequalities.

[F7]

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: condition on the past and average current round randomness.

[A1]

The gradient and stochastic-oracle hypotheses in the Statement hold at every 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 [F7].

Proof

1.1F1F2F5F6F7A1A2givenalgebra

Put $x = x_{r - 1}$ , $Δ = x_{r} - x$ , $I_{i} = 1_{{i \in S_{r}}}$ , $z_{i, k} = α_{i, k}^{r - 1} - x$ , and $w_{i, k} = y_{i, k - 1}^{r} - x$ . Let $Z = (K N)^{- 1} \sum_{i, k} z_{i, k}$ , $U = (K N)^{- 1} \sum_{i, k} I_{i} w_{i, k}$ , and $V = (K N)^{- 1} \sum_{i, k} I_{i} z_{i, k}$ . The actual anchor update is $α_{i, k}^{r} - x = z_{i, k} + I_{i} (w_{i, k} - z_{i, k})$ . Expand the squared distance after subtracting $Δ$ . Fresh uniform sampling gives the first two terms in $Ξ_{r} = (1 - p) Ξ_{r - 1} + p E_{r} + E ∥ Δ ∥_{2}^{2} - 2 E ⟨ Z, Δ ⟩ - 2 E ⟨ U, Δ ⟩ + 2 E ⟨ V, Δ ⟩ .$ All cross terms retain their actual dependence on the selected sample.

2.1F2F5F6F7step 1.1givenalgebra

Jensen gives $E ∥ Z ∥_{2}^{2} \leq Ξ_{r - 1}$ . Since exactly $S$ clients participate, $∥ U ∥_{2}^{2} \leq p (K N)^{- 1} \sum_{i, k} I_{i} ∥ w_{i, k} ∥_{2}^{2}$ , and the analogous estimate holds for $V$ and $z_{i, k}$ . The counterfactual local paths have the same law independently of the fresh participation sample, so $E ∥ U ∥_{2}^{2} \leq p^{2} E_{r}$ ; old anchors are history-measurable, giving $E ∥ V ∥_{2}^{2} \leq p^{2} Ξ_{r - 1}$ . Set $D_{2} = E ∥ Δ ∥_{2}^{2}$ and $M_{2} = E ∥ E [Δ ∣ F_{r - 1}] ∥_{2}^{2}$ . Because $Z$ is history-measurable, Young's inequality bounds the three cross terms in step 1.1, respectively, by $p Ξ_{r - 1} / 4 + 4 M_{2} / p$ , $p E_{r} + p D_{2}$ , and $p Ξ_{r - 1} / 4 + 4 p D_{2}$ . Hence $Ξ_{r} \leq (1 - p / 2) Ξ_{r - 1} + 2 p E_{r} + (1 + 5 p) D_{2} + 4 M_{2} / p .$ This also holds for $p = 1$ .

3.1F4step 2.1givenalgebra∎

Apply the two server moment bounds [F4] to step 2.1, using $1 + 5 p \leq 6$ . The coefficients of $Ξ_{r - 1}$ , $E_{r}$ , $E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2}$ , and $σ^{2} / (K S)$ are bounded by $1 - p / 2 + 72 β^{2} t^{2}$ , $2 p + (36 + 8 / p) β^{2} t^{2}$ , $(18 + 8 / p) t^{2}$ , and $108 t^{2}$ , respectively. These are the claimed coefficients.

Depends on

Used by

Nonconvex SCAFFOLD progress in one communication round Lemma

Dependency tree · two levels

51 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 15 (standard reference, not scraped)