False statementConstruction: AI-adaptedVerification: AI-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 general-convex round headline with a uniform server-iterate output

Statement

There is a universal constant $C > 0$ with the following property. Let $N, d, K \geq 1$ , $1 \leq S \leq N$ , and $β > 0$ . Let each $f_{i} : R^{d} \to R$ be convex and differentiable with $β$ -Lipschitz gradient, and suppose $f = N^{- 1} \sum_{i = 1}^{N} f_{i}$ attains its minimum $f^{⋆} = f (x^{⋆})$ . Set $D = ∥ x_{0} - x^{⋆} ∥_{2}$ and $F = f (x_{0}) - f^{⋆}$ . Run Option II SCAFFOLD with independent uniform size- $S$ client samples, fresh conditionally unbiased local stochastic gradients of conditional variance at most $σ^{2}$ , and gradient-consistent initial controls $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ . Set $η_{g} = \sqrt{S}$ . For every $ϵ > 0$ there are an integer $R \geq 1$ and a single constant local stepsize $η_{l} > 0$ , used in all rounds, such that $0 < \tilde{η} = K η_{l} η_{g} \leq \min {\frac{1}{81 β}, \frac{ϵ K S}{57 σ^{2}}}, R \leq C (1 + \frac{σ^{2} D^{2}}{K S ϵ^{2}} + \frac{β D^{2}}{ϵ} + \frac{N F}{S}),$ where the variance restriction is omitted when $σ = 0$ , and the uniform server-iterate output ${\overset{ˉ}{x}}_{R} = x_{J}$ , with $J$ independent and uniform on ${0, \dots, R - 1}$ , satisfies $E [f ({\overset{ˉ}{x}}_{R}) - f^{⋆}] \leq ϵ$ .

Statement references

SCAFFOLD local, control and server updates

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

Facts & Assumptions

Given: The claim in the Statement, interpreted with a universal constant independent of the objective scale, client count and target accuracy.

[F1]

SCAFFOLD with client and server control variates: with $K = S = 1$ and $η_{g} = 1$ , a selected client's Option II control becomes the gradient queried at the round-start server iterate; all other client controls persist, and the server control is their population mean.

Refutation

1.1givenconstructalgebra

Fix $N \geq 2$ and $β > 0$ . Take $d = K = S = 1$ , $η_{g} = 1$ , $x_{0} = 1$ , $f_{i} (x) = β x^{2} / 2$ for every client, and the exact oracle $g_{i} (x) = β x$ . Every client is convex and $β$ -smooth, the equal-client objective has minimizer $x^{⋆} = 0$ and minimum zero, and $D = 1$ , $F = β / 2$ , $σ = 0$ . Initialize $c_{i}^{0} = β$ and $c^{0} = β$ , as required. Sample one independent uniform client in every round. These deterministic exact oracles satisfy every conditional unbiasedness and variance hypothesis; all moments at a finite time are finite because there are finitely many sample histories.

2.1F1step 1.1algebra

Let $t = β η_{l} \in (0, 1 / 81]$ , put $a_{i}^{r} = c_{i}^{r} / β$ and $m_{r} = N^{- 1} \sum_{i} a_{i}^{r}$ , and let $I_{r}$ be the client sampled to pass from time $r$ to time $r + 1$ . The updates [F1] become $x_{r + 1} = (1 - t) x_{r} + t (a_{I_{r}}^{r} - m_{r}), a_{I_{r}}^{r + 1} = x_{r}, a_{j}^{r + 1} = a_{j}^{r} (j \neq I_{r}), a_{i}^{0} = 1.$ Conditioning on the history through time $r$ , the sampled difference has mean zero. Therefore, for $z_{r} = E x_{r}^{2}$ and $V_{r} = E [N^{- 1} \sum_{i} (a_{i}^{r} - m_{r})^{2}]$ , $E x_{r} = (1 - t)^{r}, z_{r + 1} = (1 - t)^{2} z_{r} + t^{2} V_{r}, z_{r} \geq (1 - t)^{2 r} .$ The claimed uniform output has expected objective gap $F R^{- 1} \sum_{r = 0}^{R - 1} z_{r}$ .

3.1step 2.1algebra

Put $L = ⌊ 1 / (4 t) ⌋$ . Since $t \leq 1 / 81$ , we have $L \geq 1 / (8 t)$ . For every integer $0 \leq r < L$ , Bernoulli's inequality gives $(1 - t)^{2 r} \geq 1 - 2 r t \geq 1 / 2$ . The bias lower bound in step 2.1 thus implies, for every $R \geq 1$ , $\frac{1}{R} \sum_{r = 0}^{R - 1} z_{r} \geq \frac{\min {R, L}}{2 R} \geq \min {\frac{1}{2}, \frac{1}{16 t R}} .$ This argument uses only the scalar inequality $(1 - t)^{n} \geq 1 - n t$ for integers $n \geq 0$ , which follows by induction.

3.2step 2.1algebra

After $r$ updates, at least $N - r$ table entries are still equal to their initial value 1. If $U$ is their set, the pairwise variance identity gives $\frac{1}{N} \sum_{i} (a_{i}^{r} - m_{r})^{2} = \frac{1}{2 N^{2}} \sum_{i, j} (a_{i}^{r} - a_{j}^{r})^{2} \geq \frac{∣ U ∣}{N^{2}} \sum_{i} (a_{i}^{r} - 1)^{2} \geq (1 - \frac{r}{N}) \frac{1}{N} \sum_{i} (a_{i}^{r} - 1)^{2}$ whenever $r \leq N$ . Indeed, retain in the double sum the pairs with exactly one index in $U$ ; pairs with both indices in $U$ contribute zero, and the two orientations cancel the factor 2.

4.1step 2.1step 3.2algebra

For a fixed client $i$ and $0 \leq s < r$ , the event that its last update before time $r$ occurs at time $s$ has probability $N^{- 1} (1 - 1 / N)^{r - 1 - s}$ . On this event $a_{i}^{r} = x_{s}$ . The event involves only $I_{s}, \dots, I_{r - 1}$ , which are independent of $x_{s}$ ; hence its conditional law of $x_{s}$ is the unconditional law. If the client was never updated, $a_{i}^{r} = 1$ . Consequently, taking expectations in step 3.2 and using $E (x_{s} - 1)^{2} \geq (E x_{s} - 1)^{2}$ , we obtain $V_{r} \geq (1 - \frac{r}{N}) \frac{1}{N} \sum_{s = 0}^{r - 1} {(1 - \frac{1}{N})}^{r - 1 - s} {(1 - (1 - t)^{s})}^{2} .$ The expectation inequality follows by expanding the nonnegative variance $E (x_{s} - E x_{s})^{2}$ .

5.1step 4.1algebra

Suppose $2 ⌈ 1 / t ⌉ \leq r \leq N / 2$ . In step 4.1 restrict to $s \geq ⌈ 1 / t ⌉$ , leaving at least $r / 2$ indices. Since $(1 - t)^{s} \leq e^{- t s} \leq e^{- 1} < 1 / 2$ , each squared factor is at least $1 / 4$ . Bernoulli's inequality gives $(1 - 1 / N)^{r - 1 - s} \geq 1 - r / N \geq 1 / 2$ ; the prefactor $1 - r / N$ is also at least $1 / 2$ . Thus $V_{r} \geq \frac{r}{32 N} .$ Here $1 - t \leq e^{- t}$ follows, for example, because the derivative of $e^{- t} - (1 - t)$ is $1 - e^{- t} \geq 0$ for $t \geq 0$ , and its value at zero is zero.

6.1step 3.1step 5.1algebra

Assume $R \leq N / 2$ and set $q = t R$ . If $q < 16$ , step 3.1 gives $R^{- 1} \sum_{r < R} z_{r} \geq 1 / 256$ . If $q \geq 16$ , then $R \geq 16 / t \geq 1296$ . Consider all integers $r \in [⌈ R / 2 ⌉, ⌊ 3 R / 4 ⌋]$ . There are at least $R / 8$ such integers; each satisfies $2 ⌈ 1 / t ⌉ \leq r \leq N / 2$ , so step 5.1 gives $V_{r} \geq R / (96 N)$ . Also $r + L \leq 3 R / 4 + 1 / (4 t) \leq R - 1$ : the final inequality follows from $R / 4 - 1 / (4 t) \geq 15 / (4 t) > 1$ .

7.1step 2.1step 3.1step 6.1algebra

Iterating the exact nonnegative recurrence in step 2.1, each $t^{2} V_{r}$ from step 6.1 contributes $t^{2} V_{r} (1 - t)^{2 j}$ to $z_{r + 1 + j}$ for $0 \leq j < L$ . These indices all lie below $R$ by step 6.1. Their weights sum to at least $L / 2 \geq 1 / (16 t)$ , by the Bernoulli estimate in step 3.1. All contributions are nonnegative, so they can be summed, including when their target indices overlap. It follows that $\frac{1}{R} \sum_{r < R} z_{r} \geq \frac{1}{R} t^{2} \frac{R}{8} \frac{R}{96 N} \frac{1}{16 t} = \frac{q}{12288 N} (q \geq 16) .$ Combining this with step 3.1 and using $\max {u, v} \geq \sqrt{u v}$ gives $R^{- 1} \sum_{r < R} z_{r} \geq 1 / \sqrt{196608 N} > 1 / (1024 \sqrt{N})$ . The $q < 16$ bound in step 6.1 gives the same conclusion. Thus, for every admissible constant stepsize and every $1 \leq R \leq N / 2$ , $E [f (x_{J}) - f^{⋆}] \geq \frac{F}{1024 \sqrt{N}} .$

8.1step 1.1step 7.1algebra∎

Now take $β = N^{- 2}$ and $ϵ = F N^{- 3 / 4} = \frac{1}{2} N^{- 11 / 4}$ . On this family the claimed round expression is exactly $1 + \frac{σ^{2} D^{2}}{K S ϵ^{2}} + \frac{β D^{2}}{ϵ} + \frac{N F}{S} = 1 + 2 N^{3 / 4} + \frac{1}{2 N} .$ For any proposed universal constant $C > 0$ , choose an integer $N$ large enough that $C (1 + 2 N^{3 / 4} + 1 / (2 N)) \leq N / 2$ and $N^{1 / 4} > 1024$ . Such integers exist because the displayed expression divided by $N$ tends to zero. Every round count allowed by the claim then satisfies $R \leq N / 2$ , but step 7.1 gives $E [f (x_{J}) - f^{⋆}] \geq F / (1024 \sqrt{N}) > F N^{- 3 / 4} = ϵ$ , for every admissible constant step. This contradicts the asserted accuracy and refutes the Statement.

Remarks

This refutation concerns the literal constant-step, uniform random server-iterate output above. The source's Theorem III prints the round term $N F / S$ , while its Appendix E allows unspecified output weights in equation (22). This item does not refute all those possible weighted outputs, suffix sampling, the last iterate, arithmetic averages of iterates, or time-varying stepsizes. Fixed powers of logarithms do not rescue the uniform-output headline: on the chosen family they multiply $O (N^{3 / 4})$ by a fixed power of $\log N$ , still giving $o (N)$ rounds.

The exact convex finite-round potential estimate is a separate valid claim. Its initial-control contribution is $14 N \tilde{η} C_{0} / (S R)$ with $C_{0} \leq 2 β F$ under gradient-consistent initialization. The refutation does not challenge that estimate; it challenges the claimed round complexity obtained by removing the accuracy dependence from the initialization term.

The exact original native general-convex clause is preserved in the repair packet as cycle2/original-general-convex-clause.md, with the native preimage and the exact substring bound in cycle2/original-clause-record.json. The quantified Statement above makes its uniform-output, fixed-step, universal-constant interpretation explicit.

Depends on

SCAFFOLD with client and server control variates

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

2 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

Karimireddy et al., SCAFFOLD, Theorem III and Appendix E, Theorem VII and output (22) (standard reference, not scraped)