§3.3, p. 11 — |Σ_{j,k∈N_i, j≠k} (a − p)² E_{p′}[Δ_jk f^a_i(Z)]| ≤ d²ϵ for ϵ-smooth f^a_i
ProvedDiffNeighbors.Bias.remainder_bounddifferences-in-neighborsestimator-biasp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1second-order-difference
Let be the interference graph with maximum degree , let be a unit, , , and let be any vector of treatment probabilities, with the expectation under independent . If the conditional outcome function is -smooth, then
By the second-partial identity the sum is , so with the corrected Taylor remainder this bounds the error of each first-order approximation by , and Theorem 1 follows.
Differences from the source:
- reading: |(a − p)ᵀH^a(p′)(a − p)| = Σ_{j,k∈N_i: j≠k} (a − p)² E[Δ_jk f^a(Z)] ≤ d²ϵ → |Σ_{j,k∈N_i, j≠k} (a − p)² E_{p′}[Δ_jk f^a_i(Z)]| ≤ d²ϵ; reason: the absolute value printed on the left applies to the sum, and E is the expectation at p′ (the Hessian is evaluated at p′)
- generalization: p′ the Taylor point between (p,…,p) and (a,…,a), with ϵ-smoothness of f¹_i, f⁰_i for all nodes, under Assumption 1 → any p′ ∈ [0,1]^ι, ϵ-smoothness of the single function f^a_i, any outcome functions; reason: the bound holds for every product Bernoulli law; the Taylor point is one such vector, and the paper's hypotheses imply these
- encoding: p a treatment probability, p′ a vector of probabilities → hypotheses p ∈ [0,1] and p′l ∈ [0,1] for all l; reason: outside [0,1] E{p′} is not an expectation; these are the values the proof uses
- encoding: f^a_i as a function of z_{N_i}; E[f^a(Z) | Z_j = b] and E[f^a(Z) | Z_j = b, Z_k = c] → condOutcome f i a z = f_i(z with z_i := a), a function on all of {0,1}^N; conditional expectations are bernExp of the function with the conditioned coordinates overwritten by Function.update; reason: under Assumption 1 condOutcome f i a depends only on z_{N_i}; by independence of the coordinates, conditioning on Z_j = b is the same as setting z_j := b
- 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
/-- **Bound on the second-order term**, §3.3, p. 11: for `a ∈ {0, 1}`, `p ∈ [0, 1]`, any vector of
treatment probabilities `p′ ∈ [0, 1]^N` and an `ε`-smooth conditional outcome function `f^a_i`,
`|∑_{j,k ∈ N_i, j ≠ k} (a − p)² E_{p′}[Δ_jk f^a_i(Z)]| ≤ d²ε`, with `d` the maximum degree and `E_{p′}`
the expectation under independent Bernoulli(`p′_l`) coordinates. -/
theorem remainder_bound {ι : Type*} [Fintype ι] [DecidableEq ι] (G : SimpleGraph ι)
[DecidableRel G.Adj] (f : ι → (ι → Bool) → ℝ) (i : ι) (a : Bool) (ε p : ℝ) (w : ι → ℝ)
(hp : p ∈ Set.Icc (0 : ℝ) 1) (hw : ∀ l, w l ∈ Set.Icc (0 : ℝ) 1)
(hε : IsSmooth ε (condOutcome f i a)) :
|∑ j ∈ G.neighborFinset i, ∑ k ∈ (G.neighborFinset i).erase j,
(ind a - p) ^ 2 * mlExt (fun z => secondDiff (condOutcome f i a) j k z) w|
≤ (G.maxDegree : ℝ) ^ 2 * ε := 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), display '|(a − p)^⊤ H^a(p′)(a − p)| = Σ_{j,k∈N_i: j≠k} (a − p)² E[Δ_jk f^a(Z)] ≤ d²ϵ'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.