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

Nonconvex SCAFFOLD progress in one communication round

Statement

Assume the Axiom of Choice. Let $f_{i} : R^{d} \to R$ have $β$ -Lipschitz gradients with $β > 0$ , and let $f = N^{- 1} \sum_{i} f_{i}$ be bounded below by $f^{⋆}$ . Run Option II SCAFFOLD with $1 \leq S \leq N$ uniformly sampled clients, $K \geq 1$ local steps, server scale $η_{g} \geq 1$ , and fresh conditionally unbiased local stochastic gradients of within-client variance at most $σ^{2}$ . Initialize $c_{i}^{0} = \nabla f_{i} (x_{0})$ and $c^{0} = N^{- 1} \sum_{i} c_{i}^{0}$ . Client samples are fresh and independent of prior history and counterfactual oracle draws. Let $p = S / N$ , $t = \tilde{η} = K η_{l} η_{g}$ , and let $Ξ_{r}$ be the control-anchor tracking error. If $0 < t \leq \frac{p^{2 / 3}}{100 β},$ then the potential $P_{r} = E [f (x_{r}) - f^{⋆}] + \frac{24 β^{3} t^{2}}{p} Ξ_{r}$ satisfies $P_{r} \leq P_{r - 1} - \frac{t}{3} E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + \frac{10 β t^{2} σ^{2}}{K S} (1 + \frac{S}{η_{g}^{2}}) .$

Statement references

Karimireddy et al., SCAFFOLD, Appendix E.2, Lemma 17 and its proof

Facts & Assumptions

Given: The nonconvex SCAFFOLD update, smoothness and stochastic-gradient assumptions in the Statement.

[F1]

SCAFFOLD with client and server control variates: the server update is the average of selected corrected local updates with global scale $η_{g}$ .

[F2]

SCAFFOLD trajectories, client drift, control lag and tracking error: counterfactual client paths use fresh oracle randomness independent of participation, and oracle moments are conditional on the full prequery history.

[F3]

Nonconvex SCAFFOLD server-update moments: the conditional-mean displacement and the server displacement have the squared-norm bounds stated there.

[F9]

Gradient of a finite sum is the finite sum of gradients: $N^{- 1} \sum_{i} \nabla f_{i} (x) = \nabla f (x)$ .

[F4]

Nonconvex SCAFFOLD control-anchor tracking recursion: the exact tracking recursion has coefficients $1 - p / 2 + 72 β^{2} t^{2}$ , $2 p + (36 + 8 / p) β^{2} t^{2}$ , $(18 + 8 / p) t^{2}$ , and $108 t^{2}$ for the previous tracking error, drift, squared gradient and $σ^{2} / (K S)$ .

[F5]

Nonconvex SCAFFOLD query-point drift bound: $E_{r} \leq 72 t^{2} (E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2} + β^{2} Ξ_{r - 1}) / η_{g}^{2} + 96 t^{2} σ^{2} / (K η_{g}^{2})$ .

[F6]

Descent inequality for a Lipschitz gradient: $β$ -Lipschitz gradients give $f (x + u) \leq f (x) + ⟨ \nabla f (x), u ⟩ + (β / 2) ∥ u ∥_{2}^{2}$ .

[F7]

Relaxed inequalities for squared Euclidean norms and The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : squared norms and inner products expand by the Euclidean algebra used in the two moment lemmas.

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

[A1]

The smoothness and stochastic-oracle assumptions in the Statement hold at every query.

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

Put $x = x_{r - 1}$ and $Δ = x_{r} - x$ . The smooth-descent bound [F6] and conditional expectation give $E [f (x_{r}) - f (x_{r - 1})] \leq E ⟨ \nabla f (x), E [Δ ∣ F_{r - 1}] ⟩ + \frac{β}{2} E ∥ Δ ∥_{2}^{2} .$ By [F1], $Δ = - t (K S)^{- 1} \sum_{i \in S_{r}, k} (g_{i} (y_{i, k - 1}^{r}) - c_{i} + c)$ . Conditional centering at each query and then averaging gives the same conditional mean with $g_{i}$ replaced by $\nabla f_{i}$ . By [F2], the full hypothetical paths are independent of the fresh sample given the round-start history, so each participation indicator in this conditional mean can be replaced by its mean $S / N$ . The control terms cancel because $c = N^{- 1} \sum_{i} c_{i}$ . Adding and subtracting the round-start gradients and using [F9] now yields $E [Δ ∣ F_{r - 1}] = - t v$ , where $v = \nabla f (x) + (K N)^{- 1} \sum_{i, k} E [\nabla f_{i} (y_{i, k - 1}^{r}) - \nabla f_{i} (x) ∣ F_{r - 1}]$ . Write $δ = v - \nabla f (x)$ for the mean local-gradient displacement. Conditional Jensen and Lipschitzness give $E ∥ δ ∥_{2}^{2} \leq β^{2} E_{r}$ . In the descent cross term, use $- ⟨ u, δ ⟩ \leq (∥ u ∥_{2}^{2} + ∥ δ ∥_{2}^{2}) / 2$ with $u = \nabla f (x)$ ; thus $- ⟨ u, u + δ ⟩ \leq - ∥ u ∥_{2}^{2} / 2 + ∥ δ ∥_{2}^{2} / 2$ . Substituting the second-moment bound in [F3] gives $\begin{aligned} E [f (x_{r}) - f (x_{r - 1})] \leq & - (\frac{\tilde{η}}{2} - \frac{3 β {\tilde{η}}^{2}}{2}) E ∥ \nabla f (x) ∥_{2}^{2} \\ + (\frac{β^{2} \tilde{η}}{2} + 3 β^{3} {\tilde{η}}^{2}) E_{r} + 6 β^{3} {\tilde{η}}^{2} Ξ_{r - 1} + \frac{9 β {\tilde{η}}^{2} σ^{2}}{K S} . \end{aligned}$

2.1F4step 1.1givenalgebra

Write $h = β t$ , $G = E ∥ \nabla f (x_{r - 1}) ∥_{2}^{2}$ , $X = Ξ_{r - 1}$ , and $q = σ^{2} / (K S)$ . Add $24 β^{3} t^{2} / p$ times the tracking increment from [F4] to the inequality in step 1.1. The resulting coefficients of $E_{r}$ , $X$ , $G$ and noise are, respectively, $β^{2} t d$ , $β^{3} t^{2} (- 6 + 1728 h^{2} / p)$ , $- t (1 / 2 - 3 h / 2) + 24 β^{3} t^{4} (18 / p + 8 / p^{2})$ , and $9 β t^{2} q + 2592 β^{3} t^{4} q / p$ , where $d = \frac{1}{2} + 51 h + \frac{864 h^{3}}{p} + \frac{192 h^{3}}{p^{2}} .$ Since $h \leq p^{2 / 3} / 100$ and $0 < p \leq 1$ , we have $h \leq 1 / 100$ , $h^{2} / p \leq 1 / 10000$ , $h^{3} / p \leq 1 / 1000000$ , and $h^{3} / p^{2} \leq 1 / 1000000$ . Consequently $d \leq 1.011056 < 11 / 10$ .

3.1F5step 2.1givenalgebra∎

Substitute [F5] into the drift term in step 2.1, using $d \leq 11 / 10$ and $η_{g} \geq 1$ . The total coefficient of $X$ , divided by $β^{3} t^{2}$ , is at most $- 6 + 1728 / 10000 + (396 / 5) / 100 = - 5.0352 < 0$ . The coefficient of $G$ , divided by $t$ , is at most $- 1 / 2 + 3 / 200 + 624 / 1000000 + (396 / 5) / 10000 = - 0.476456 \leq - 1 / 3$ . Finally the variance contribution, divided by $β t^{2} q$ when $q > 0$ , is at most $9 + 2592 / 10000 + (528 / 5) S / (100 η_{g}^{2}) = 9.2592 + 1.056 S / η_{g}^{2} \leq 10 (1 + S / η_{g}^{2})$ ; when $q = 0$ all these variance terms vanish. Drop the nonpositive $X$ term. The resulting inequality is exactly the claimed potential recursion.

Remarks

The source states a sufficient step bound with absolute constant $1 / 24$ . The locally proved result uses $1 / 100$ because it retains the dependence between the participation indicators, adaptive local queries, and the server displacement. This changes only absolute constants in the resulting nonconvex communication rate.

Depends on

Used by

SCAFFOLD rates for strongly convex, convex and nonconvex objectives Theorem

Dependency tree · two levels

64 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.2, Lemma 17 (standard reference, not scraped)