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.

Summably biased SPSA has convergent objective values and zero gradient liminf

Statement

Assume AC. Let $f : R^{d} \to R$ be $C^{1}$ , bounded below by a finite $f_{\inf}$ , and have an $L$ -Lipschitz gradient. Let $(F_{k})$ be a filtration, let $x_{k}$ be $F_{k}$ -measurable, and let $G_{k}$ be the output of the SPSA estimator in Two-evaluation simultaneous-perturbation gradient estimator, measurable with respect to $F_{k + 1}$ . At each iteration, draw $Δ_{k}$ and the simulator random inputs freshly and independently of $F_{k}$ ; the two paired calls may share their random input. Suppose $Δ_{k}$ has a fixed perturbation law, the calls satisfy $E [Y_{k}^{\pm} ∣ F_{k}, Δ_{k}] = f (x_{k} \pm c_{k} Δ_{k})$ , and their conditional bias and weighted second moments give, almost surely, $∥ E [G_{k} ∣ F_{k}] - \nabla f (x_{k}) ∥_{2} \leq B c_{k}^{2}, Var (G_{k} ∣ F_{k}) \leq V c_{k}^{- 2}, ∥ \nabla f (x_{k}) ∥_{2} \leq G,$ with deterministic $B, V, G < \infty$ , and deterministic $c_{k} \in (0, 1]$ . The bias and variance hypotheses are supplied, for example, by the bounds of Symmetric simultaneous perturbations have second-order gradient bias and Weighted simulator moments give an inverse-step SPSA variance bound when their smoothness and weighted-moment conditions hold at each history.

For deterministic $α_{k} > 0$ , update $x_{k + 1} = x_{k} - α_{k} G_{k}$ . Assume $X_{k} : = f (x_{k}) - f_{\inf}$ is nonnegative, adapted, and integrable at each $k$ , and $\sum_{k} α_{k} = \infty, c_{k} ⟶ 0, \sum_{k} α_{k} c_{k}^{2} < \infty, \sum_{k} \frac{α_{k}^{2}}{c_{k}^{2}} < \infty .$ Then $X_{k}$ converges almost surely, $\sum_{k} α_{k} ∥ \nabla f (x_{k}) ∥_{2}^{2} < \infty almost surely, {lim inf}_{k \to \infty} ∥ \nabla f (x_{k}) ∥_{2} = 0 almost surely .$ Thus the gradient norm has zero liminf almost surely. Without a compactness condition ensuring an iterate accumulation point, this does not guarantee a stationary iterate limit point, convergence to a minimizer, or convergence of the full gradient sequence.

Facts & Assumptions

Given: AC; the filtration-adapted SPSA update, conditional bias and variance bounds, gradient boundedness along the iterates, the integrable Lyapunov process $X_{k}$ , the deterministic perturbation radii $c_{k}$ , and the four deterministic step-size conditions.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function. AC is required by the conditional-expectation and Doob interfaces in [F5].

[F1]

Filtration-adapted stochastic-gradient oracles and Robbins–Monro updates: $x_{k}$ is $F_{k}$ -measurable, $G_{k}$ is $F_{k + 1}$ -measurable, and the conditional vector second moment is the squared conditional mean plus the sum of coordinate conditional variances.

[F2]

Symmetric simultaneous perturbations have second-order gradient bias: under its perturbation, differentiability, conditional-unbiased-call, and reciprocal-moment assumptions, the conditional SPSA bias is bounded by a deterministic constant times $c_{k}^{2}$ .

[F3]

Weighted simulator moments give an inverse-step SPSA variance bound: under its weighted conditional second-moment assumption, the conditional SPSA variance is bounded by a deterministic constant times $c_{k}^{- 2}$ .

[F4]

Descent inequality for a Lipschitz gradient: if $\nabla f$ is $L$ -Lipschitz, then $f (y) \leq f (x) + ⟨ \nabla f (x), y - x ⟩ + (L / 2) ∥ y - x ∥_{2}^{2}$ .

[F5]

Robbins–Siegmund almost-supermartingale convergence: under AC, nonnegative adapted integrable $X_{k}$ with $E [X_{k + 1} ∣ F_{k}] \leq X_{k} - b_{k} + r_{k}$ , for predictable nonnegative integrable $b_{k}$ and deterministic summable $r_{k} \geq 0$ , satisfies $X_{k}$ convergent almost surely and $\sum_{k} b_{k} < \infty$ almost surely.

[F6]

Basic algebra and order properties of conditional expectation and Taking out what is known: conditional expectation is linear and an integrable $F_{k}$ -measurable factor may be taken outside it when the products are integrable.

Proof

1.1A1givenF1F6algebra

Put $m_{k} = E [G_{k} ∣ F_{k}]$ and $b_{k}^{b i a s} = m_{k} - \nabla f (x_{k})$ . By [F1] and [F6], the $F_{k}$ -measurable iterate and gradient can be taken outside the conditional moment calculations. The second-moment identity then gives, for a deterministic $K < \infty$ , $E [∥ G_{k} ∥_{2}^{2} ∣ F_{k}] = ∥ m_{k} ∥_{2}^{2} + Var (G_{k} ∣ F_{k}) \leq (G + B)^{2} + V c_{k}^{- 2} \leq K (1 + c_{k}^{- 2}),$ where the last inequality uses $c_{k} \leq 1$ .

2.1A1F1F2F3F4F6step 1.1givenalgebra

Apply [F4] to $y = x_{k} - α_{k} G_{k}$ and condition on $F_{k}$ , using [F6] to take the known iterate and gradient outside conditional expectation. Since $m_{k} = \nabla f (x_{k}) + b_{k}^{b i a s}$ and $∥ \nabla f (x_{k}) ∥_{2} \leq G$ , this gives $E [X_{k + 1} ∣ F_{k}] \leq X_{k} - α_{k} ∥ \nabla f (x_{k}) ∥_{2}^{2} + G B α_{k} c_{k}^{2} + \frac{L K}{2} α_{k}^{2} (1 + c_{k}^{- 2}) .$ For $c_{k} \leq 1$ , $1 + c_{k}^{- 2} \leq 2 c_{k}^{- 2}$ ; hence the deterministic error $r_{k} : = G B α_{k} c_{k}^{2} + L K α_{k}^{2} c_{k}^{- 2}$ is summable by the step-size assumptions.

3.1F1F5step 2.1given

The process $b_{k} : = α_{k} ∥ \nabla f (x_{k}) ∥_{2}^{2}$ is nonnegative, $F_{k}$ -measurable, and integrable because $∥ \nabla f (x_{k}) ∥_{2} \leq G$ . Step 2.1 is the Robbins–Siegmund inequality with multiplicative error $a_{k} = 0$ , decrement $b_{k}$ , and deterministic error $r_{k}$ .

4.1A1F5step 3.1givenalgebra∎

By [F5], $X_{k}$ converges almost surely and $\sum_{k} α_{k} ∥ \nabla f (x_{k}) ∥_{2}^{2} < \infty$ almost surely. If ${lim inf}_{k} ∥ \nabla f (x_{k}) ∥_{2} > 0$ on a path, there are $ε > 0$ and an index $k_{0}$ for which $∥ \nabla f (x_{k}) ∥_{2}^{2} \geq ε$ for all $k \geq k_{0}$ on that path. Then the weighted sum is at least $ε \sum_{k \geq k_{0}} α_{k} = \infty$ , contradicting its finiteness. Thus the liminf is zero almost surely.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

66 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

Michael C. Fu, Stochastic Gradient Estimation, preprint of Handbook of Simulation Optimization, §§3–4 (standard reference, not scraped)
J. C. Spall, An Overview of the Simultaneous Perturbation Method for Efficient Optimization, §§SPSA algorithm and gain sequences (standard reference, not scraped)