TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Weighted simulator moments give an inverse-step SPSA variance bound

Statement

Assume AC. At a current history $F$ , let $c > 0$ , let $Δ_{i} \neq 0$ almost surely, and use the two-evaluation estimator from Two-evaluation simultaneous-perturbation gradient estimator. Suppose the weighted conditional second moment is bounded: $E ⁣ [(∣ Y^{+} ∣^{2} + ∣ Y^{-} ∣^{2}) \sum_{i = 1}^{d} ∣ Δ_{i} ∣^{- 2} | F] \leq B$ almost surely, with deterministic $B < \infty$ . Then $E [∥ \hat{G} ∥_{2}^{2} ∣ F] \leq \frac{B}{2 c^{2}}, Var (\hat{G} ∣ F) \leq \frac{B}{2 c^{2}},$ where the vector conditional variance is the sum of coordinate conditional variances as in Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates.

Facts & Assumptions

Given: AC, the current history, step $c$ , nonzero perturbation coordinates, and the weighted conditional second-moment bound.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function; AC is inherited by the conditional-expectation interface in [F2].

[F1]

Two-evaluation simultaneous-perturbation gradient estimator: ${\hat{G}}_{i} = (Y^{+} - Y^{-}) / (2 c Δ_{i})$ .

[F2]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates and Conditional variance: for a vector oracle, conditional variance is the sum of the coordinate conditional variances.

[F3]

Conditional variance is well-defined and has the second-moment formula: for a square-integrable vector oracle, $E [∥ \hat{G} ∥_{2}^{2} ∣ F] = ∥ E [\hat{G} ∣ F] ∥_{2}^{2} + Var (\hat{G} ∣ F)$ .

[F4]

Basic algebra and order properties of conditional expectation: conditional expectation preserves inequalities and satisfies the tower property for integrable variables.

Proof

1.1givenF1F4algebra

For each coordinate, [F1] and $(a - b)^{2} \leq 2 a^{2} + 2 b^{2}$ give $∥ \hat{G} ∥_{2}^{2} = \sum_{i = 1}^{d} \frac{(Y^{+} - Y^{-})^{2}}{4 c^{2} Δ_{i}^{2}} \leq \frac{∣ Y^{+} ∣^{2} + ∣ Y^{-} ∣^{2}}{2 c^{2}} \sum_{i = 1}^{d} ∣ Δ_{i} ∣^{- 2} .$ The weighted conditional bound and the tower property in [F4] make the right side integrable, so each coordinate of $\hat{G}$ is square-integrable.

2.1A1F4step 1.1given

By conditional monotonicity [F4], taking conditional expectations in step 1.1 and applying the weighted bound yields $E [∥ \hat{G} ∥_{2}^{2} ∣ F] \leq B / (2 c^{2})$ .

3.1A1F2F3step 2.1algebra∎

By [F3], $Var (\hat{G} ∣ F) = E [∥ \hat{G} ∥_{2}^{2} ∣ F] - ∥ E [\hat{G} ∣ F] ∥_{2}^{2} \leq E [∥ \hat{G} ∥_{2}^{2} ∣ F]$ . Step 2.1 gives the second bound.

Depends on

Used by

Summably biased SPSA has convergent objective values and zero gradient liminf Theorem

Dependency tree · two levels

23 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

J. C. Spall, An Overview of the Simultaneous Perturbation Method for Efficient Optimization, §§SPSA algorithm and perturbation conditions (standard reference, not scraped)
Michael C. Fu, Stochastic Gradient Estimation, preprint of Handbook of Simulation Optimization, Proposition 3.1 (standard reference, not scraped)