TheoremStatement: 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.

SCAFFOLD rates for strongly convex, convex and nonconvex objectives

Statement

Assume the Axiom of Choice. Let $N, d, K, R \geq 1$ be positive integers, let $1 \leq S \leq N$ , and let $f_{i} : R^{d} \to R$ have $β$ -Lipschitz gradients, with $β > 0$ . Put $f = N^{- 1} \sum_{i = 1}^{N} f_{i}$ , and suppose $f$ is bounded below by $f^{⋆}$ . Run Option II SCAFFOLD with a fresh uniform size- $S$ client sample in every round, independent of the preceding history and the fresh local oracle randomness, fresh conditionally unbiased local stochastic gradients whose variance on each client is at most $σ^{2}$ , and gradient-consistent initialization $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ . Set $F = f (x_{0}) - f^{⋆}$ , and put $D = ∥ x_{0} - x^{⋆} ∥_{2}$ when a minimizer $x^{⋆}$ exists. In both convex cases below, assume $f^{⋆} = f (x^{⋆})$ .

Strongly convex case. Suppose every $f_{i}$ is $μ$ -strongly convex for $0 < μ \leq β$ and $f$ attains its minimum at $x^{⋆}$ . Set $η_{g} = \sqrt{S}$ and choose $0 < η_{l} \leq \min {\frac{1}{81 β K η_{g}}, \frac{S}{15 μ N K η_{g}}}, \tilde{η} = K η_{l} η_{g} .$ For $R \geq 1$ , independently of the optimization randomness choose $J \in {0, \dots, R - 1}$ with probabilities proportional to $(1 - μ \tilde{η} / 2)^{- (J + 1)}$ and return ${\overset{ˉ}{x}}_{R} = x_{J}$ . Then $E [f ({\overset{ˉ}{x}}_{R}) - f^{⋆}] \leq \frac{V_{0}}{\tilde{η} W_{R}} + \frac{19 \tilde{η} σ^{2}}{K S}, V_{0} = D^{2} + \frac{14 N {\tilde{η}}^{2}}{S} C_{0}, W_{R} = \sum_{r = 1}^{R} (1 - μ \tilde{η} / 2)^{- r},$ where $C_{0} = N^{- 1} \sum_{i} ∥ \nabla f_{i} (x_{0}) - \nabla f_{i} (x^{⋆}) ∥_{2}^{2}$ . Consequently, a suitable $\tilde{η}$ and $R = \tilde{O} (\frac{σ^{2}}{μ K S ϵ} + \frac{β}{μ} + \frac{N}{S})$ communication rounds suffice for expected objective error at most $ϵ > 0$ .
General convex case. Suppose every $f_{i}$ is convex and differentiable, and $f$ attains its minimum at $x^{⋆}$ . Set $η_{g} = \sqrt{S}$ and choose $0 < \tilde{η} = K η_{l} η_{g} \leq 1 / (81 β)$ . For independent uniform $J \in {0, \dots, R - 1}$ and ${\overset{ˉ}{x}}_{R} = x_{J}$ , $\frac{1}{R} \sum_{r = 0}^{R - 1} E [f (x_{r}) - f^{⋆}] \leq \frac{D^{2} + 28 β N {\tilde{η}}^{2} F / S}{\tilde{η} R} + \frac{19 \tilde{η} σ^{2}}{K S} .$ For $D > 0$ and $ϵ > 0$ , set $A = 28 β N F / S$ and choose $\tilde{η} = \min {\frac{1}{81 β}, \frac{D}{\sqrt{A}}, \frac{ϵ K S}{57 σ^{2}}},$ omitting a restriction whose denominator is zero. Taking an integer $R \geq \max {1, 6 D^{2} / (\tilde{η} ϵ)}$ ensures expected objective error at most $ϵ$ . Consequently the sufficient round bound is $R = O (1 + \frac{σ^{2} D^{2}}{K S ϵ^{2}} + \frac{β D^{2}}{ϵ} + \frac{D \sqrt{β N F / S}}{ϵ}) .$ If $D = 0$ , return $x_{0}$ , which already minimizes $f$ .
Nonconvex case. Suppose only that $f$ is $β$ -smooth and bounded below by $f^{⋆}$ . Set $η_{g} = \sqrt{S}$ and choose $0 < \tilde{η} = K η_{l} η_{g} \leq \frac{1}{100 β} {(\frac{S}{N})}^{2 / 3} .$ For independent uniform $J \in {0, \dots, R - 1}$ and ${\overset{ˉ}{x}}_{R} = x_{J}$ , $E ∥ \nabla f ({\overset{ˉ}{x}}_{R}) ∥_{2}^{2} \leq \frac{3 F}{\tilde{η} R} + \frac{60 β \tilde{η} σ^{2}}{K S} .$ Thus a choice of $\tilde{η}$ and $R = O (1 + \frac{β σ^{2} F}{K S ϵ^{2}} + {(\frac{N}{S})}^{2 / 3} \frac{β F}{ϵ})$ rounds suffice to make the expected squared gradient norm at the returned iterate at most $ϵ > 0$ . If $F = 0$ , return $x_{0}$ , whose gradient vanishes.

The convex rates concern the equal-client objective and their stated server-iterate outputs. They do not assert a rate for the count-weighted deployment objective. No gradient-dissimilarity condition is used for SCAFFOLD, and the quadratic-only Hessian-dissimilarity improvement is not claimed for general smooth losses.

Statement references

Karimireddy et al., SCAFFOLD, Theorem III and complete Appendix E

Facts & Assumptions

Given: The equal-client objective, SCAFFOLD algorithm and case-specific convexity, smoothness and stochastic-gradient hypotheses in the Statement, including $f^{⋆} = f (x^{⋆})$ in both convex cases.

[F1]

Strongly convex SCAFFOLD progress in one communication round: in convex cases the distance and control potential contracts and pays for the objective gap and variance.

[F2]

Nonconvex SCAFFOLD progress in one communication round: with $\tilde{η} \leq (S / N)^{2 / 3} / (100 β)$ , the nonnegative potential $P_{r} = E [f (x_{r}) - f^{⋆}] + 24 β^{3} {\tilde{η}}^{2} (N / S) Ξ_{r}$ decreases by at least $\tilde{η} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} / 3$ apart from $10 β {\tilde{η}}^{2} σ^{2} (1 + S / η_{g}^{2}) / (K S)$ .

[F3]

Geometric and sublinear averaging for descent recursions: summing a convex descent recurrence gives a uniform-index average; geometrically weighted summation gives the strongly convex output bound.

[F4]

Smooth convex gradient differences around a minimizer and Gradient of a finite sum is the finite sum of gradients: for convex clients, $C_{0} \leq 2 β F$ and the average client gradient equals $\nabla f$ .

[F5]

Federated objectives and client sampling and SCAFFOLD with client and server control variates: the objective is $N^{- 1} \sum_{i} f_{i}$ ; each round samples clients uniformly without replacement and updates the server model and control by the SCAFFOLD rules.

[F6]

SCAFFOLD trajectories, client drift, control lag and tracking error: $C_{r}$ and $Ξ_{r}$ are the convex control-lag and nonconvex anchor-tracking errors used in the one-round bounds.

[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 can be iterated and the stated integrable inequalities averaged.

[A1]

Every client stochastic gradient is conditionally unbiased with within-client variance at most $σ^{2}$ at every query; client samples are uniform fixed-size subsets; initialization is gradient-consistent.

[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.1F1F3F5F6F8A1A2givenalgebra

In the strongly convex case, put $\tilde{η} = K η_{l} \sqrt{S}$ and [given] apply [F1]. Since $η_{g}^{2} = S$ , the variance term in [F1] is at most $19 {\tilde{η}}^{2} σ^{2} / (K S)$ . The geometric recurrence lemma [F3] with gap coefficient one and weights $w_{r} = (1 - μ \tilde{η} / 2)^{- r}$ gives $E [f ({\overset{ˉ}{x}}_{R}) - f^{⋆}] \leq \frac{V_{0}}{\tilde{η} W_{R}} + \frac{19 \tilde{η} σ^{2}}{K S}, V_{0} = E ∥ x_{0} - x^{⋆} ∥_{2}^{2} + \frac{14 N {\tilde{η}}^{2}}{S} C_{0} .$ This is the strongly convex bound in the Statement.

1.2F1F3F4F6F8A1A2givenalgebra

In the general convex case, apply [F1] with $μ = 0$ and [given] $η_{g} = \sqrt{S}$ . It gives $V_{r} \leq V_{r - 1} - \tilde{η} E [f (x_{r - 1}) - f^{⋆}] + 19 {\tilde{η}}^{2} σ^{2} / (K S)$ . Sum over $r = 1, \dots, R$ and drop the nonnegative terminal potential. For independent uniform $J$ this yields $\frac{1}{R} \sum_{r = 0}^{R - 1} E [f (x_{r}) - f^{⋆}] \leq \frac{V_{0}}{\tilde{η} R} + \frac{19 \tilde{η} σ^{2}}{K S}, V_{0} = D^{2} + \frac{14 N {\tilde{η}}^{2}}{S} C_{0} .$ Substitution of $C_{0} \leq 2 β F$ proves the exact bound in the Statement.

1.3F2F3F5F6F8A1A2givenalgebra

In the nonconvex case use [F2] with $η_{g}^{2} = S$ . The initialization in [F6] gives $Ξ_{0} = 0$ , so $P_{0} = F$ . Its variance term is at most $20 β {\tilde{η}}^{2} σ^{2} / (K S)$ . Sum over rounds and drop $P_{R} \geq 0$ to obtain $\frac{\tilde{η}}{3} \sum_{r = 1}^{R} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} \leq F + \frac{20 R β {\tilde{η}}^{2} σ^{2}}{K S} .$ Dividing by $R \tilde{η} / 3$ and choosing the uniform independent output index gives precisely the nonconvex finite-round bound.

2.1F3F4step 1.1givenalgebra

In the strongly convex case, by convex smoothness, [F4] gives $C_{0} \leq 2 β F$ , hence [given] $V_{0} \leq D^{2} + 28 β N {\tilde{η}}^{2} F / S$ . Also $W_{R} = \frac{(1 - μ \tilde{η} / 2)^{- R} - 1}{μ \tilde{η} / 2} .$ Thus $V_{0} / (\tilde{η} W_{R}) \leq ϵ / 2$ whenever $R \geq \frac{2}{μ \tilde{η}} \log (1 + \frac{μ V_{0}}{ϵ}),$ and the variance term is at most $ϵ / 2$ if $\tilde{η} \leq ϵ K S / (38 σ^{2})$ . Choose the largest step satisfying these restrictions. Its reciprocal is bounded by a constant times $β + μ N / S + σ^{2} / (K S ϵ)$ ; dividing by $μ$ gives the stated communication rate, up to the displayed logarithmic factor.

2.2F1F4step 1.2givenalgebra

Let $D > 0$ and set $A = 28 β N F / S$ . With the displayed choice of $\tilde{η}$ , one has $A \tilde{η} \leq D^{2} / \tilde{η}$ and $19 \tilde{η} σ^{2} / (K S) \leq ϵ / 3$ . Thus step 1.2 is at most $2 D^{2} / (\tilde{η} R) + ϵ / 3 \leq 2 ϵ / 3$ for the stated integer $R$ . The reciprocal step equals the maximum of $81 β$ , $\sqrt{A} / D$ , and $57 σ^{2} / (ϵ K S)$ , omitting zero-denominator restrictions. Bound this maximum by the sum to obtain the stated communication rate. If $D = 0$ , the initial point is minimizing and requires no round.

3.1F2step 1.1step 2.1step 1.2step 2.2step 1.3givenalgebra∎

For $F > 0$ , choose $\tilde{η} = \min {(S / N)^{2 / 3} / (100 β), ϵ K S / (120 β σ^{2})}$ , omitting the variance restriction if $σ = 0$ , and take $R \geq \max {1, 6 F / (\tilde{η} ϵ)}$ . Each term in the bound of step 1.3 is at most $ϵ / 2$ . Bounding the reciprocal minimum by the sum proves the nonconvex round rate. If $F = 0$ , the finite lower bound is attained at $x_{0}$ , so differentiability implies $\nabla f (x_{0}) = 0$ and returning it suffices. Together with the two convex branches, this proves all branches.

Remarks

The source's general-convex headline prints $N F / S$ . Under the literal constant-step, uniform-server-iterate output specified here, that claimed round term is false; the original claim and a full analytic counterexample are preserved in fs-scaffold-general-convex-uniform-output-round-headline. The corrected bound above optimizes the exact local potential, rather than merely inserting an epsilon in that term. The source's appendix permits other output probabilities; no claim is made here about every possible alternative output interpretation.

The nonconvex proof retains the full communication order with a sufficient absolute step constant $100$ . The source reports $24$ ; the local proof uses the stated smaller step to absorb the conservative adaptive-noise and selection-correlated anchor bounds. The original source-reading and native-authoring evidence remain historical evidence; these are separate later repairs.

Remarks references

SCAFFOLD general-convex round headline with a uniform server-iterate output

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

71 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, Theorem III and Appendix E (standard reference, not scraped)