Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, §3.3, p. 11 (corrected: factor ½) — the first-order approximation's error is ½(a − p)ᵀH^a(p′)(a − p)

Proved
DiffNeighbors.Bias.taylor_remainder

by mikedeng1 · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

differences-in-neighborsmultilinear-extensionp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1taylor-approximation

Let h:{0,1}N→Rh : \{0,1\}^N \to \mathbb Rh:{0,1}N→R with multilinear extension FFF, let a∈{0,1}a \in \{0,1\}a∈{0,1} and p∈Rp \in \mathbb Rp∈R, and write a=(a,…,a)\mathbf a = (a, \dots, a)a=(a,…,a) and p=(p,…,p)\mathbf p = (p, \dots, p)p=(p,…,p). Let H(w)H(w)H(w) be the Hessian of FFF at www; by the second-partial identity its entries are Hjk(w)=Ew[Δjkh(Z)]H_{jk}(w) = \mathbb E_w[\Delta_{jk} h(Z)]Hjk​(w)=Ew​[Δjk​h(Z)] for j≠kj \neq kj=k and Hjj(w)=0H_{jj}(w) = 0Hjj​(w)=0. Then there is a point p′=(s,…,s)p' = (s, \dots, s)p′=(s,…,s) on the segment from p\mathbf pp to a\mathbf aa (that is, sss between ppp and aaa) such that the error of the first-order approximation of F(a)F(\mathbf a)F(a) around p\mathbf pp is

F(a)−(F(p)+∑j(a−p)∂F∂wj(p))=12(a−p)⊤H(p′)(a−p)=12∑j∑k≠j(a−p)2 Ep′[Δjkh(Z)].F(\mathbf a) - \Bigl(F(\mathbf p) + \sum_j (a - p)\frac{\partial F}{\partial w_j}(\mathbf p)\Bigr) = \frac12 (\mathbf a - \mathbf p)^\top H(p')(\mathbf a - \mathbf p) = \frac12 \sum_j \sum_{k \neq j} (a - p)^2\, \mathbb E_{p'}[\Delta_{jk} h(Z)].F(a)−(F(p)+j∑​(a−p)∂wj​∂F​(p))=21​(a−p)⊤H(p′)(a−p)=21​j∑​k=j∑​(a−p)2Ep′​[Δjk​h(Z)].

Applied to h=fiah = f^a_ih=fia​, this is the error of the DN estimator's first-order approximation to Fia(a)F^a_i(a)Fia​(a), which Theorem 1's proof then bounds by 12d2ϵ\tfrac12 d^2 \epsilon21​d2ϵ for each treatment.

The page states the error as (a−p)⊤Ha(p′)(a−p)(a - p)^\top H^a(p')(a - p)(a−p)⊤Ha(p′)(a−p) without the factor 12\frac1221​; that is the Lagrange form of Taylor's theorem with the 12\frac1221​ dropped, and it is false (see below). With the 12\frac1221​ restored, the two errors for a=1a = 1a=1 and a=0a = 0a=0 add up to at most d2ϵd^2\epsilond2ϵ, which is Theorem 1's bound.

Formalization Note ∂F/∂wj(p)\partial F/\partial w_j(\mathbf p)∂F/∂wj​(p) is written as Ep[h∣Zj=1]−Ep[h∣Zj=0]\mathbb E_{\mathbf p}[h \mid Z_j = 1] - \mathbb E_{\mathbf p}[h \mid Z_j = 0]Ep​[h∣Zj​=1]−Ep​[h∣Zj​=0] (the first-partial identity), and the Hessian through its entries as above; Set.uIcc p (ind a) is the closed interval between ppp and aaa.

Differences from the source:

  • correction: the error is (a − p)ᵀH^a(p′)(a − p) → the error is ½(a − p)ᵀH^a(p′)(a − p); reason: the printed form is false: a node with two neighbours and f¹(z) = z₁z₂ (1-smooth, satisfies Assumption 1), a = 1, p = ½ gives F¹(w) = w₁w₂, H ≡ [[0,1],[1,0]], error 1 − (¼ + ½(½ + ½)) = ¼, while (a − p)ᵀH(p′)(a − p) = ½ for every p′; the Lagrange remainder carries ½
  • reading: there exists some p′ → p′ = (s, …, s) with s in the closed interval between p and a; reason: p′ is the intermediate point of Taylor's theorem on the segment from (p,…,p) to (a,…,a); an unrestricted p′ would leave the subsequent bound without content
  • encoding: H^a(p′) and (a − p)ᵀ∇F^a(p) → Σ_j Σ_{k≠j} (a − p)² mlExt (secondDiff h j k) (s,…,s), and Σ_j (a − p)(E_p[h|Z_j=1] − E_p[h|Z_j=0]); reason: the Hessian entries and the gradient as identified by the second- and first-partial identities
  • generalization: F^a of node i, p ∈ (0,1), a sum over N_i → the multilinear extension of any h : {0,1}^ι → ℝ, any real p, sums over all coordinates; reason: specializes with h = condOutcome f i a, whose partial derivatives in coordinates outside N_i vanish under Assumption 1
  • encoding: units [N] = {1,…,N}, treatment vectors z ∈ {0,1}^N, an undirected graph without self-loops, d = max_i |N_i| → a finite type ι with N = card ι, z : ι → Bool with 1/0 read through ind, G : SimpleGraph ι, N_i = G.neighborFinset i, d = G.maxDegree; reason: a simple graph is exactly an undirected graph without self-loops; same instances
Preamble
import Mathlib
import Definitions.Def_DiffNeighbors_Bias_Model
Formal statement
namespace DiffNeighbors.Bias

open Finset

/-- **Taylor remainder of the first-order approximation** (corrected: factor `½`), §3.3, p. 11.
For `a ∈ {0, 1}` there is a point `p′ = (s, …, s)` on the segment from `(p, …, p)` to `(a, …, a)` with
`F(a) − [F(p) + (a − p)ᵀ∇F(p)] = ½ (a − p)ᵀ H(p′) (a − p)`,
where the Hessian `H(p′)` has entries `E_{p′}[Δ_jk h(Z)]` off the diagonal and `0` on it. -/
theorem taylor_remainder {ι : Type*} [Fintype ι] [DecidableEq ι] (h : (ι → Bool) → ℝ) (a : Bool)
    (p : ℝ) :
    ∃ s ∈ Set.uIcc p (ind a),
      mlExt h (fun _ => ind a) - mlExt h (fun _ => p)
        - ∑ j, (ind a - p) * (mlExt (fun z => h (Function.update z j true)) (fun _ => p)
            - mlExt (fun z => h (Function.update z j false)) (fun _ => p))
      = (1 / 2) * ∑ j, ∑ k ∈ Finset.univ.erase j,
          (ind a - p) ^ 2 * mlExt (fun z => secondDiff h j k z) (fun _ => s) := by sorry

end DiffNeighbors.Bias
Source
Peng, Ye, Zheng, Differences-in-Neighbors for Network Interference in Experiments, arXiv:2503.02271v1, p. 11, §3.3 (proof of Theorem 1), 'There exists some p′ such that the error of the DN estimator's first-order approximation to F^a(a) is (a − p)^⊤ H^a(p′)(a − p).'
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me