ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

SCAFFOLD controls cancel shifted local gradients at the server model

Example

Let two clients have objectives $f_{1} (w) = \frac{1}{2} (w - 1)^{2}$ and $f_{2} (w) = \frac{1}{2} (w + 1)^{2}$ . At server model $x = 0$ , initialize $c_{i} = \nabla f_{i} (0)$ and $c = (c_{1} + c_{2}) / 2$ . Under SCAFFOLD's corrected local gradient $\nabla f_{i} (y) - c_{i} + c$ , every local step starting from $0$ remains at $0$ , for every positive local step size and every finite local-step count.

Example references

Karimireddy et al., SCAFFOLD, §4 and Algorithm 1

Facts & Assumptions

Given: The two client objectives, server model and control initialization in the Example.

[F1]

SCAFFOLD with client and server control variates: the server control is initialized to the average of the client controls, as specified in the Example.

[F2]

SCAFFOLD with client and server control variates: a local step uses $y \leftarrow y - η_{l} (g_{i} (y) - c_{i} + c)$ . For the exact-gradient corrected direction specified in the Example, take the deterministic oracle $g_{i} (y) = \nabla f_{i} (y)$ .

Proof technique: direct.

Proof

1.1F1givenalgebra

The client gradients are $\nabla f_{1} (w) = w - 1$ and $\nabla f_{2} (w) = w + 1$ . Thus at $x = 0$ the initialized controls are $c_{1} = - 1$ , $c_{2} = 1$ , and $c = 0$ by [F1].

2.1F2step 1.1giveninduction∎

If a client's local point is $y = 0$ , then $\nabla f_{1} (0) - c_{1} + c = - 1 - (- 1) + 0 = 0$ and $\nabla f_{2} (0) - c_{2} + c = 1 - 1 + 0 = 0$ . Hence its next local point is still zero by [F2]. Induction on the local-step index proves every local point is zero.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

2 results within one dependency step 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: Stochastic Controlled Averaging for Federated Learning, §4 (standard reference, not scraped)