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

Federated averaging, local SGD, and SCAFFOLD — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Local updates and periodic synchronization give different averages

Example

Let $f_{1} (x) = x^{2} / 2$ and $f_{2} (x) = x^{2}$ on $R$ , let the two local-SGD workers start at $x_{0}^{1} = x_{0}^{2} = 1$ , and use step size $η = 1 / 2$ with one uniform component draw per worker and step from ${f_{1}, f_{2}}$ . Couple two executions by choosing the positive-probability draw sequence in which worker 1 draws $f_{1}$ twice and worker 2 draws $f_{2}$ twice. After two steps without intermediate synchronization their mean is $1 / 8$ . If they instead synchronize after the first step and again after the second, their final mean is $1 / 16$ .

Example references

Stich, Local SGD Converges Fast and Communicates Little, Definition 2.1

Facts & Assumptions

Given: The two differentiable component functions and the common starting point in the Example.

[F1]

Local SGD with periodic synchronization: each step samples a component uniformly and updates $x \leftarrow x - η \nabla f_{j} (x)$ ; a synchronization replaces all worker states by their arithmetic mean.

[A1]

The two workers' component draws are independent and uniform at each step, as in [F1]. The displayed coupled draw sequence therefore has probability $(1 / 2)^{4} > 0$ in either schedule.

Proof technique: direct.

Proof

1.1F1givenalgebra

The gradients are $\nabla f_{1} (x) = x$ and $\nabla f_{2} (x) = 2 x$ . Without an intermediate synchronization, worker 1 follows $1 \mapsto 1 / 2 \mapsto 1 / 4$ and worker 2 follows $1 \mapsto 0 \mapsto 0$ . Their arithmetic mean is $(1 / 4 + 0) / 2 = 1 / 8$ .

2.1F1step 1.1givenalgebra

With synchronization after the first step, the worker states are first $1 / 2$ and $0$ , so their common synchronized value is $1 / 4$ . On the second step, the same coupled draws give worker states $1 / 4 - (1 / 2) (1 / 4) = 1 / 8$ and $1 / 4 - (1 / 2) (2) (1 / 4) = 0$ . Their mean is $(1 / 8 + 0) / 2 = 1 / 16$ .

3.1A1step 1.1step 2.1∎

Since $1 / 8 \neq 1 / 16$ and the draw sequence in [A1] has positive probability under the algorithm, the two schedules can produce different final worker means.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Keeping records on clients does not imply differential privacy

Example

Let the database be a finite record set, use add/remove adjacency, and let a distributed system release the exact number of records after each client has kept its own record locally. This deterministic count release is not $(ε, δ)$ -differentially private for any finite $ε \geq 0$ and any $0 \leq δ < 1$ .

Example references

Add/remove differential privacy

Facts & Assumptions

Given: The database domain and exact count mechanism in the Example.

[F1]

Differential privacy, databases, and add/remove adjacency: differential privacy requires the event inequality for every ordered neighboring database pair and every measurable output event.

[F2]

Measurable spaces and measurable sets, Probability measures and probability spaces, and Measure kernel and probability kernel: a deterministic count release is a probability kernel into the countable output space $N_{0}$ equipped with its power-set sigma algebra.

Proof technique: direct.

Proof

1.1F1F2givenconstruct

Let $D = \emptyset$ , $D^{'} = {r}$ , and let $M (E) = ∣ E ∣$ . These databases are add/remove neighbors. For the measurable event $A = {1}$ , $\Pr [M (D) \in A] = 0$ and $\Pr [M (D^{'}) \in A] = 1$ .

2.1F1step 1.1givenalgebra∎

The required privacy inequality in the order $(D^{'}, D)$ would read $1 \leq e^{ε} \cdot 0 + δ = δ$ , which is false whenever $δ < 1$ . Therefore the exact count mechanism is not $(ε, δ)$ -differentially private for the stated parameters.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Two clients with shifted least-squares optima

Example

Consider two one-observation scalar least-squares clients with data $(a_{1}, y_{1}) = (1, 1)$ and $(a_{2}, y_{2}) = (2, - 2)$ , using loss $\frac{1}{2} (y_{i} - a_{i} w)^{2}$ . Their objectives are $f_{1} (w) = \frac{1}{2} (w - 1)^{2}$ and $f_{2} (w) = 2 (w + 1)^{2}$ , with local minimizers $1$ and $- 1$ . The equal-client objective has minimizer $- 3 / 5$ . Starting FedAvg from $w_{0} = 0$ , using both clients, two full-gradient local steps of size $1 / 4$ , and server scale $1$ , gives the server model $- 9 / 32$ after one round.

Example references

Fixed-design least-squares objective

Facts & Assumptions

Given: The two client data points and FedAvg parameters in the Example.

[F1]

Fixed-design least-squares, ridge, lasso, group, and fused objectives: a one-observation scalar least-squares loss is $\frac{1}{2} (y - a w)^{2}$ .

[F2]

Federated objectives and client sampling: the equal-client objective is the arithmetic mean of client objectives.

[F3]

Federated averaging (FedAvg): with all clients selected, the server adds the mean of their local model differences when $η_{g} = 1$ .

Verification

technique · direct

1.1F1F2givenalgebra

By [F1], client 1 has derivative $w - 1$ and minimizer $1$ ; client 2 has derivative $4 (w + 1)$ and minimizer $- 1$ . The equal-client derivative is $(w - 1 + 4 (w + 1)) / 2 = (5 w + 3) / 2$ , so its unique zero and minimizer is $- 3 / 5$ .

1.2F1F3givenalgebra

From $w_{0} = 0$ , the two local trajectories are $0 \mapsto 1 / 4 \mapsto 7 / 16$ and $0 \mapsto - 1 \mapsto - 1$ . Averaging the two final local models gives $(7 / 16 - 1) / 2 = - 9 / 32$ .

2.1step 1.1step 1.2algebra∎

Since $- 9 / 32 \neq - 3 / 5$ , this one-round FedAvg output is not the minimizer of the equal-client objective, although the clients' optima are shifted in opposite directions.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

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.

Federated averaging, local SGD, and SCAFFOLD — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Local updates and periodic synchronization give different averages

Example

Example references

Facts & Assumptions

Proof

Keeping records on clients does not imply differential privacy

Example

Example references

Facts & Assumptions

Proof

Two clients with shifted least-squares optima

Example

Example references

Facts & Assumptions

Verification

SCAFFOLD controls cancel shifted local gradients at the server model

Example

Example references

Facts & Assumptions

Proof

Sources