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.

Strongly convex SCAFFOLD progress in one communication round

Statement

Assume the Axiom of Choice. Let $f_{i} : R^{d} \to R$ be differentiable, $μ$ -strongly convex and $β$ -smooth, with $0 \leq μ \leq β$ , and let $f = N^{- 1} \sum_{i} f_{i}$ attain $f^{⋆} = f (x^{⋆})$ . Run Option II SCAFFOLD with $1 \leq S \leq N$ clients sampled uniformly without replacement, $K \geq 1$ local steps, local step $η_{l}$ , server scale $η_{g} \geq 1$ , and fresh conditionally unbiased local stochastic gradients with variance at most $σ^{2}$ . Assume $c = N^{- 1} \sum_{i} c_{i}$ , initialize $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ , and define $\tilde{η} = K η_{l} η_{g}$ . If $\tilde{η} \leq \frac{1}{81 β}, and, when μ > 0, \tilde{η} \leq \frac{S}{15 μ N},$ then, with $E_{r}, C_{r}$ as in the SCAFFOLD analysis-trajectory definition and $ρ = (2 + 34 β \tilde{η}) / 3$ , $\begin{aligned} E ∥ x_{r} - x^{⋆} ∥_{2}^{2} + \frac{14 N {\tilde{η}}^{2}}{S} C_{r} & \leq (1 - \frac{μ \tilde{η}}{2}) (E ∥ x_{r - 1} - x^{⋆} ∥_{2}^{2} + \frac{14 N {\tilde{η}}^{2}}{S} C_{r - 1}) \\ - \tilde{η} E [f (x_{r - 1}) - f^{⋆}] + (\frac{18}{K S} + \frac{ρ}{K η_{g}^{2}}) {\tilde{η}}^{2} σ^{2} . \end{aligned}$ For $μ = 0$ this is a general-convex descent inequality; for $μ > 0$ it also contracts the distance-and-control potential.

Statement references

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

Facts & Assumptions

Given: The Option II SCAFFOLD round, objective and stepsize assumptions in the Statement.

[F1]

SCAFFOLD with client and server control variates: the server update is the mean corrected local update, and $c = N^{- 1} \sum_{i} c_{i}$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: $E_{r}$ averages query-point displacement, and $C_{r}$ is the expected squared error of the mean full gradient at the stored anchors from $\nabla f_{i} (x^{⋆})$ .

[F3]

Convex SCAFFOLD server-update second moment: the displacement second moment is at most $6 β^{2} {\tilde{η}}^{2} E_{r} + 12 {\tilde{η}}^{2} C_{r - 1} + 6 β {\tilde{η}}^{2} E [f (x_{r - 1}) - f^{⋆}] + 18 {\tilde{η}}^{2} σ^{2} / (K S)$ .

[F4]

Convex SCAFFOLD control-lag recursion: the next control lag is at most $(1 - S / N) C_{r - 1} + (S / N) (4 β E [f (x_{r - 1}) - f^{⋆}] + 2 β^{2} E_{r})$ .

[F5]

Convex SCAFFOLD client-drift bound: the local drift satisfies $3 β \tilde{η} E_{r} \leq (2 / 3) {\tilde{η}}^{2} C_{r - 1} + \tilde{η} E [f (x_{r - 1}) - f^{⋆}] / (25 η_{g}^{2}) + {\tilde{η}}^{2} σ^{2} / (K η_{g}^{2})$ .

[F6]

Strong-convexity inequality for a perturbed gradient point: each client gradient at a local point paired with $x_{r - 1} - x^{⋆}$ is bounded below by its objective gap, a strong-convexity distance term and the local-point displacement term.

[F7]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : squared distance expands as a norm square plus its inner-product term.

[F8]

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: roundwise conditional expectations are linear and preserve the integrable bounds.

[A1]

The local stochastic-gradient assumptions and gradient-consistent initialization in the Statement hold at all queries; the current client sample is independent of the preceding history.

[A2]

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

Proof

1.1F1F3F6F7F8A1A2givenalgebra

Write $Δ x = x_{r} - x_{r - 1}$ . Conditional on the round-start history, [given] the client-control terms cancel in the mean server update by [F1] and uniform sampling. Expand $∥ x_{r - 1} + Δ x - x^{⋆} ∥_{2}^{2}$ , and apply [F6] to each local gradient at $y_{i, k - 1}^{r}$ with comparison points $x^{⋆}$ and $x_{r - 1}$ . Averaging over clients and query indices gives a cross-term bound $- 2 \tilde{η} E [f (x_{r - 1}) - f^{⋆}] - μ \tilde{η} E ∥ x_{r - 1} - x^{⋆} ∥_{2}^{2} / 2 + 2 β \tilde{η} E_{r}$ . Add the second-moment bound [F3]. The result is $\begin{aligned} E ∥ x_{r} - x^{⋆} ∥_{2}^{2} & \leq (1 - \frac{μ \tilde{η}}{2}) E ∥ x_{r - 1} - x^{⋆} ∥_{2}^{2} + (6 β {\tilde{η}}^{2} - 2 \tilde{η}) E [f (x_{r - 1}) - f^{⋆}] \\ + 12 {\tilde{η}}^{2} C_{r - 1} + (2 β \tilde{η} + 6 β^{2} {\tilde{η}}^{2}) E_{r} + \frac{18 {\tilde{η}}^{2} σ^{2}}{K S} . \end{aligned}$

2.1F2F4step 1.1givenalgebra

Multiply [F4] by $14 {\tilde{η}}^{2} / (S / N)$ and add it to step 1.1. [given] Set $t = β \tilde{η}$ . The objective-gap coefficient becomes $- 2 \tilde{η} + 62 β {\tilde{η}}^{2}$ , the local-drift coefficient is $2 β \tilde{η} + 34 β^{2} {\tilde{η}}^{2} = 3 β \tilde{η} ρ$ , and the extra control-lag coefficient after subtracting the contracted old potential is $(- 2 + 7 μ \tilde{η} / (S / N)) {\tilde{η}}^{2} C_{r - 1}$ . The resulting inequality is $\begin{aligned} V_{r} \leq & (1 - μ \tilde{η} / 2) V_{r - 1} + (- 2 \tilde{η} + 62 β {\tilde{η}}^{2}) E [f (x_{r - 1}) - f^{⋆}] \\ + 3 β \tilde{η} ρ E_{r} + (- 2 + 7 μ \tilde{η} / (S / N)) {\tilde{η}}^{2} C_{r - 1} + \frac{18 {\tilde{η}}^{2} σ^{2}}{K S}, \end{aligned}$ where $V_{r} = E ∥ x_{r} - x^{⋆} ∥_{2}^{2} + 14 {\tilde{η}}^{2} C_{r} / (S / N)$ .

3.1F2F5step 2.1givenalgebra∎

Substitute [F5] into step 2.1. Since $\tilde{η} / (25 η_{g}^{2}) \leq \tilde{η} / 25$ and $ρ \leq 196 / 243$ , the objective-gap coefficient is at most $(- 2 + 62 / 81 + 196 / 6075) \tilde{η} \leq - \tilde{η}$ . Also $μ \tilde{η} / (S / N) \leq 1 / 15$ , so the remaining control-lag coefficient is at most $(- 23 / 15 + 392 / 729) {\tilde{η}}^{2} < 0$ . Finally $ρ \leq 196 / 243 < 1$ , and the drift variance term is at most ${\tilde{η}}^{2} σ^{2} / (K η_{g}^{2})$ . Drop the nonpositive control-lag term and combine the two variance terms. This proves the Statement.

Depends on

Used by

SCAFFOLD rates for strongly convex, convex and nonconvex objectives Theorem

Dependency tree · two levels

56 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 13 (standard reference, not scraped)