TheoremStatement: AI-adaptedProof: AI-generatedPipeline-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.

Local Jacobian perturbations give a pathwise bound for graph-gradient error

Statement

For a finite scalar-output graph on one fixed strict branch, associate to each parent-slot edge $e$ the exact local derivative map $A_{e}$ at the exact real-arithmetic primal values. Use induced Euclidean operator norms on all edge spaces. Suppose a reverse recurrence instead uses local maps ${\tilde{A}}_{e}$ from the same branch satisfying $∥ {\tilde{A}}_{e} - A_{e} ∥ \leq η_{e}$ , with exact accumulation arithmetic. For an input block $i$ , let $P (i, o)$ be the finite directed paths from that block to output $o$ , and order the edges of a path $π = (e_{1}, \dots, e_{s})$ from input to output. The exact gradient contribution is the transpose of $A_{e_{s}} \dots A_{e_{1}}$ , and the perturbed recurrence returns the corresponding sum using ${\tilde{A}}_{e}$ . It obeys $∥ {\tilde{g}}_{i} - g_{i} ∥ \leq \sum_{π \in P (i, o)} \sum_{ℓ = 1}^{s} η_{e_{ℓ}} (\prod_{r < ℓ} ∥ A_{e_{r}} ∥) (\prod_{r > ℓ} (∥ A_{e_{r}} ∥ + η_{e_{r}})) .$ The bound covers local Jacobian and derivative-evaluation errors represented by $η_{e}$ . It does not include roundoff in the reverse accumulation additions.

Facts & Assumptions

Given: A finite $C^{1}$ graph on a fixed strict branch, exact edge Jacobians $A_{e}$ , perturbed edge Jacobians ${\tilde{A}}_{e}$ , and exact real accumulation of the perturbed reverse recurrence.

[F1]

Finite straight-line computational programs and real-arithmetic tapes: a graph is finite and acyclic, and each parent slot defines a separate edge with a local derivative map.

[F2]

Reverse mode computes the exact gradient of the real-arithmetic graph: exact reverse accumulation returns the gradient of the graph's scalar output.

[F3]

Composition satisfies |ST|\le|S|,|T|: induced operator norms satisfy $∥ S T ∥ \leq ∥ S ∥ ∥ T ∥$ for composable bounded linear maps.

[F4]

Cauchy–Schwarz: $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥ ∥ y ∥$ , with equality exactly for dependent pairs: Euclidean inner products satisfy $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ .

[A1]

Each edge perturbation satisfies the stated operator-norm bound; all sums and products in this theorem are exact real arithmetic.

Proof

technique · expand reverse accumulation into paths and telescope each matrix product

1.1F1F2givenconstruct

Starting with output cotangent $1$ , the exact reverse recurrence at a node sums one local derivative-transpose contribution from each outgoing parent-slot edge. By induction in reverse topological order, its expansion at input block $i$ has one ordered derivative product for every path from $i$ to the output: the length-zero path at the output node has product $1$ (including when the output itself is an input), and extending a path by one edge multiplies its product by that edge's local derivative. The same finite recurrence with ${\tilde{A}}_{e}$ yields the sum of perturbed path products; the output seed is unchanged. By [F2], the exact path sum is $g_{i}$ .

1.2A1algebra

Fix a path $π = (e_{1}, \dots, e_{s})$ . Insert one factor at a time to write ${\tilde{A}}_{e_{s}} \dots {\tilde{A}}_{e_{1}} - A_{e_{s}} \dots A_{e_{1}} = \sum_{ℓ = 1}^{s} {\tilde{A}}_{e_{s}} \dots {\tilde{A}}_{e_{ℓ + 1}} ({\tilde{A}}_{e_{ℓ}} - A_{e_{ℓ}}) A_{e_{ℓ - 1}} \dots A_{e_{1}} .$ This identity follows by cancellation of consecutive products in the telescoping sum.

2.1A1F3F4step 1.2algebra

Submultiplicativity [F3] and [A1] bound the $ℓ$ th summand by $η_{e_{ℓ}} \prod_{r < ℓ} ∥ A_{e_{r}} ∥ \prod_{r > ℓ} (∥ A_{e_{r}} ∥ + η_{e_{r}})$ . A path product $L$ maps an input block to $R$ ; writing $w = L^{T} 1$ , Cauchy--Schwarz [F4] gives $∣ L x ∣ \leq ∥ w ∥_{2} ∥ x ∥_{2}$ , with equality at $x = w / ∥ w ∥_{2}$ when $w \neq 0$ , and both norms are zero when $w = 0$ . Hence $∥ L ∥ = ∥ L^{T} 1 ∥_{2}$ , so the operator-norm estimate also bounds the path's gradient-contribution error. Summing these bounds over $ℓ$ controls the error on this path.

3.1step 1.1step 2.1algebra∎

The perturbed and exact gradients are finite sums over the same paths by step 1.1. The triangle inequality therefore bounds their difference by the sum of the pathwise errors from step 2.1, which is exactly the displayed bound.

Depends on

Used by

Real-arithmetic graph derivatives and rounded execution are different objects Remark

Dependency tree · two levels

18 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

MIT OpenCourseWare 18.S096, Matrix Calculus for Machine Learning and Beyond, complete lecture notes, Chapter 8 §§8.3–8.4.1 (standard reference, not scraped)
A. Griewank, Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic Differentiation, §1 (standard reference, not scraped)