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.

Strong-convexity inequality for a perturbed gradient point

Statement

Let $h : R^{d} \to R$ be continuously differentiable, let $\nabla h$ be $β$ -Lipschitz, and suppose $h$ is $μ$ -strongly convex with $0 \leq μ \leq β$ . Then for every $x, y, z \in R^{d}$ , $⟨ \nabla h (x), z - y ⟩ \geq h (z) - h (y) + \frac{μ}{4} ∥ y - z ∥_{2}^{2} - β ∥ z - x ∥_{2}^{2} .$

Statement references

Karimireddy et al., SCAFFOLD, Appendix C, Lemma 5

Facts & Assumptions

Given: The smoothness and strong-convexity hypotheses in the Statement.

[F1]

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

[F2]

Strong convexity means $h (y) \geq h (x) + ⟨ \nabla h (x), y - x ⟩ + (μ / 2) ∥ y - x ∥_{2}^{2}$ for all $x, y$ .

[F3]

Relaxed inequalities for squared Euclidean norms: $∥ y - x ∥_{2}^{2} \geq \frac{1}{2} ∥ y - z ∥_{2}^{2} - ∥ x - z ∥_{2}^{2}$ .

Proof

1.1F1F2F3givenalgebra

Rearranging [F1] and applying [F2] at the same point $x$ give [given] $⟨ \nabla h (x), z - x ⟩ \geq h (z) - h (x) - \frac{β}{2} ∥ z - x ∥_{2}^{2},$ $⟨ \nabla h (x), x - y ⟩ \geq h (x) - h (y) + \frac{μ}{2} ∥ x - y ∥_{2}^{2} .$ Add the inequalities and use [F3]. This yields $⟨ \nabla h (x), z - y ⟩ \geq h (z) - h (y) + \frac{μ}{4} ∥ y - z ∥_{2}^{2} - \frac{β + μ}{2} ∥ z - x ∥_{2}^{2} .$

2.1step 1.1givenalgebra∎

Since $μ \leq β$ , $(β + μ) / 2 \leq β$ . Replacing the last coefficient by the weaker $- β$ proves the claimed bound.

Depends on

Used by

Dependency tree · two levels

22 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 C, Lemma 5 (standard reference, not scraped)