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.

Geometric and sublinear averaging for descent recursions

Statement

Let $R \geq 1$ and let $d_{0}, \dots, d_{R} \geq 0$ , $q_{0}, \dots, q_{R - 1} \geq 0$ .

If $a, η > 0$ , $b, c \geq 0$ , and $d_{r} + a η q_{r - 1} \leq d_{r - 1} + b η^{2} + c η^{3} (1 \leq r \leq R),$ then $\frac{1}{R} \sum_{r = 1}^{R} q_{r - 1} \leq \frac{d_{0}}{a η R} + \frac{b η + c η^{2}}{a} .$
If $0 < ρ η < 1$ , $a > 0$ , $b, c \geq 0$ , and $d_{r} \leq (1 - ρ η) d_{r - 1} - a η q_{r - 1} + b η^{2} + c η^{3},$ then for $w_{r} = (1 - ρ η)^{- r}$ and $W_{R} = \sum_{r = 1}^{R} w_{r}$ , $\frac{1}{W_{R}} \sum_{r = 1}^{R} w_{r} q_{r - 1} \leq \frac{d_{0}}{a η W_{R}} + \frac{b η + c η^{2}}{a} .$ The left side in part 2 is the expectation of $q_{r - 1}$ when an index $r \in {1, \dots, R}$ is selected with probability $w_{r} / W_{R}$ .

Facts & Assumptions

Given: The nonnegative sequences, positive step size, and recurrences in the Statement.

[A1]

All weights $w_{r}$ in part 2 are positive because $0 < 1 - ρ η < 1$ .

Proof

1.1givenA1algebra

Rearrange the part 1 inequality as $a η q_{r - 1} \leq d_{r - 1} - d_{r} + b η^{2} + c η^{3}$ and sum over $r = 1, \dots, R$ . The distance terms telescope to $d_{0} - d_{R} \leq d_{0}$ . Divide by $a η R$ to get the first bound.

1.2givenA1algebra

For part 2, multiply the recurrence by $w_{r}$ . Since [given] $w_{r} (1 - ρ η) = w_{r - 1}$ when $w_{0} = 1$ , summing gives $a η \sum_{r = 1}^{R} w_{r} q_{r - 1} \leq d_{0} - w_{R} d_{R} + (b η^{2} + c η^{3}) W_{R} \leq d_{0} + (b η^{2} + c η^{3}) W_{R} .$ Divide by $a η W_{R}$ to obtain the second bound.

2.1A1algebra∎

The probabilities $w_{r} / W_{R}$ are nonnegative and sum to one, so the expected selected value is exactly the weighted average in part 2.

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Sai Praneeth Karimireddy et al., SCAFFOLD, Appendix B, Lemmas 1 and 2 (standard reference, not scraped)