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.

Symmetric simultaneous perturbations have second-order gradient bias

Statement

Gradients are Euclidean column vectors, and vector expectations are taken coordinatewise.

Assume AC for the conditional-expectation interface. Let $Θ \subseteq R^{d}$ be open, $θ \in Θ$ , and $f : Θ \to R$ be $C^{3}$ . Let $Δ_{1}, \dots, Δ_{d}$ be independent, symmetric about zero, and nonzero almost surely, with $E ∣ Δ_{j} ∣ < \infty, E ∣ Δ_{i} ∣^{- 1} < \infty, q_{i} : = E ⁣ [\frac{∥ Δ ∥_{2}^{3}}{∣ Δ_{i} ∣}] < \infty .$ For each $0 < c \leq c_{0}$ , assume ${θ + t Δ : ∣ t ∣ \leq c} \subseteq Θ$ almost surely and, for almost every realized $Δ$ , this segment lies in an open set $V_{c, Δ} \subseteq Θ$ on which $∥ D^{3} f (y) ∥_{o p} \leq M_{3}$ , where the operator norm is the supremum of $∣ D^{3} f [u, v, w] ∣$ over unit vectors $u, v, w$ . Assume the two oracle outputs in Two-evaluation simultaneous-perturbation gradient estimator satisfy $E [Y^{\pm} ∣ Δ] = f (θ \pm c Δ)$ and $E ⁣ [\frac{∣ Y^{+} - f (θ + c Δ) ∣ + ∣ Y^{-} - f (θ - c Δ) ∣}{∣ Δ_{i} ∣}] < \infty$ for every $i$ . Then $∣ E [{\hat{G}}_{i} (θ)] - \partial_{i} f (θ) ∣ \leq \frac{M_{3} c^{2}}{6} q_{i}, {∥ E [\hat{G} (θ)] - \nabla f (θ) ∥}_{2} \leq \frac{M_{3} c^{2}}{6} {(\sum_{i = 1}^{d} q_{i}^{2})}^{1 / 2} .$

Facts & Assumptions

Given: AC; the objective, parameter and smoothness hypotheses; the independent symmetric nonzero perturbation coordinates and moment bounds; and the conditional unbiasedness and weighted integrability of the two oracle outputs.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function. AC is used for the conditional-expectation classes below.

[F1]

Two-evaluation simultaneous-perturbation gradient estimator: ${\hat{G}}_{i} = (Y^{+} - Y^{-}) / (2 c Δ_{i})$ , using the same two outputs for all coordinates.

[F2]

Forward and central differences have first- and second-order error bounds: if $g \in C^{3}$ on a neighborhood of $[- c, c]$ and $∣ g^{'''} ∣ \leq M$ , then $∣ (g (c) - g (- c)) / (2 c) - g^{'} (0) ∣ \leq M c^{2} / 6$ .

[F3]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : derivatives of a composition obey $D (g \circ f) = D g (f) \circ D f$ . Gradients are column vectors represented using the Euclidean inner product of The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , so $D f (θ) [v] = ⟨ \nabla f (θ), v ⟩$ .

[F4]

Expectations factor over finite products of independent random variables: expectations of products of independent integrable random variables factor; the nonnegative case also holds with extended expectations.

[F5]

Conditional expectation as an ae class: under AC, conditional expectations exist as almost-sure classes.

[F6]

Taking out what is known: an integrable measurable factor can be taken outside a conditional expectation when the products are integrable.

[F7]

Linearity, monotonicity, and the modulus bound for expectation: expectation is linear on integrable real random variables.

[F8]

Basic algebra and order properties of conditional expectation: conditional expectation is linear and satisfies the tower property.

[F9]

Random elements and real random variables and Change of variables for expectation: expectation of an integrable function of a real random variable depends only on its law.

[F10]

Conditional expectation given a sigma algebra and Conditional expectation as an ae class: an integrable $σ (Δ)$ -measurable variable is a version of its own conditional expectation, and the version class is unique almost surely.

Proof

1.1givenF2F3

Fix a perturbation vector $Δ$ for which the hypotheses hold and set $g (t) = f (θ + t Δ)$ . By [F3], $g^{'} (0) = ⟨ \nabla f (θ), Δ ⟩$ and $∣ g^{'''} (t) ∣ = ∣ D^{3} f (θ + t Δ) [Δ, Δ, Δ] ∣ \leq M_{3} ∥ Δ ∥_{2}^{3}$ . Applying [F2] with step $c$ gives $∣ \frac{f (θ + c Δ) - f (θ - c Δ)}{2 c} - ⟨ \nabla f (θ), Δ ⟩ ∣ \leq \frac{M_{3} c^{2}}{6} ∥ Δ ∥_{2}^{3} .$

2.1F1step 1.1algebra

Write $ϵ^{\pm} = Y^{\pm} - f (θ \pm c Δ)$ . By [F1], ${\hat{G}}_{i} = \sum_{j = 1}^{d} \partial_{j} f (θ) \frac{Δ_{j}}{Δ_{i}} + R_{i} + \frac{ϵ^{+} - ϵ^{-}}{2 c Δ_{i}}, ∣ R_{i} ∣ \leq \frac{M_{3} c^{2}}{6} \frac{∥ Δ ∥_{2}^{3}}{∣ Δ_{i} ∣},$ using step 1.1 and $Δ_{i} \neq 0$ .

3.1A1F4F5F6F7F8F9F10step 2.1given

Since $f (θ \pm c Δ)$ is integrable and $σ (Δ)$ -measurable, [F10] makes it its own conditional expectation. Conditional linearity [F8] and the hypothesis therefore give $E [ϵ^{\pm} ∣ σ (Δ)] = 0$ . The weighted integrability assumption makes $ϵ^{\pm} / Δ_{i}$ integrable; [F6] takes the finite measurable factor $1 / Δ_{i}$ out of the conditional expectation, and the tower property [F8] gives $E [ϵ^{\pm} / Δ_{i}] = 0$ . For $j = i$ , $Δ_{j} / Δ_{i} = 1$ . For $j \neq i$ , symmetry means $Δ_{j}$ and $- Δ_{j}$ have the same law, so [F9] gives $E [Δ_{j}] = E [- Δ_{j}]$ ; linearity [F7] then gives $E [Δ_{j}] = 0$ . Independence and the finite reciprocal moment give $E [Δ_{j} / Δ_{i}] = E [Δ_{j}] E [1 / Δ_{i}] = 0$ by [F4]. Therefore the expectation of the linear sum in step 2.1 is $\partial_{i} f (θ)$ .

4.1step 2.1step 3.1givenalgebra∎

Taking expectations of the remainder bound in step 2.1 yields $∣ E [{\hat{G}}_{i}] - \partial_{i} f (θ) ∣ \leq E ∣ R_{i} ∣ \leq \frac{M_{3} c^{2}}{6} q_{i} .$ Squaring these coordinate bounds, summing over $i$ , and taking square roots gives the stated vector bound.

Depends on

Used by

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

Dependency tree · two levels

68 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, pp. 484–491 (standard reference, not scraped)
Michael C. Fu, Stochastic Gradient Estimation, preprint of Handbook of Simulation Optimization, §3.2 (standard reference, not scraped)