Minimax Error for Network Interference

Fix an interaction order $\beta\in\mathbb N$ and an assignment probability $p\in\mathbb R$. Assume:

• (Order.) $1\le \beta$.
• (Design probability.) $0<p<1$.

Then there exist constants $c_{\beta,p},C_{\beta,p}\in\mathbb R$ such that $$0<c_{\beta,p}\le C_{\beta,p}.$$ For every $n,d\in\mathbb N$ and $B\in\mathbb R$ satisfying $1\le n$, $d\le n$, and $0\le B$, with $k_\star(d,\beta,p)$ as in Definition P-1 and $R_n^\star(d,\beta,p,B)$ as in Definition P-8, the following hold: $$c_{\beta,p}B^2 \min\!\left\{1,\frac{d\binom{d}{k_\star(d,\beta,p)}}{n}\right\} \le R_n^\star(d,\beta,p,B).$$ Moreover, $$R_n^\star(d,\beta,p,B) \le \sup_{(G,c)\in\mathcal M_{n,d,\beta}(B)} \mathbb E_Z\!\left[ \left(\widehat\tau_n^{\mathrm{up}}-\tau_n\right)^2 \right] \le C_{\beta,p}B^2 \min\!\left\{1,\frac{d\binom{d}{k_\star(d,\beta,p)}}{n}\right\},$$ where $\mathcal M_{n,d,\beta}(B)$ is the model class in Definition P-5 and $\widehat\tau_n^{\mathrm{up}}$ is SNIPE projected to $[-B,B]$. The unprojected SNIPE estimator also satisfies $$\sup_{(G,c)\in\mathcal M_{n,d,\beta}(B)} \mathbb E_Z\!\left[ \left(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n\right)^2 \right] \le C_{\beta,p}B^2 \frac{d\binom{d}{k_\star(d,\beta,p)}}{n}.$$ For every $(G,c)\in\mathcal M_{n,d,\beta}(B)$ and unit $i$, writing $N_i=\{j:(j,i)\in G\}$, $$\sum_{r=1}^{\min\{\beta,|N_i|\}} \binom{|N_i|}{r} \frac{\Delta_r(p)^2}{\{p(1-p)\}^r} \le A_d,$$ where $$A_d = \sum_{r=1}^{\min\{\beta,d\}} \binom{d}{r} \frac{\Delta_r(p)^2}{\{p(1-p)\}^r}.$$ For every $(G,c)\in\mathcal M_{n,d,\beta}(B)$, every $r\in\mathbb N$, and every unit $i$, if $1\le r$, then $$\sum_{\ell\in V_n} \binom{|N_i\cap N_\ell|}{r} = \sum_{\substack{S\subseteq N_i\\ |S|=r}} \#\{\ell\in V_n:S\subseteq N_\ell\} \le d\binom{|N_i|}{r} \le d\binom{d}{r}.$$ Finally, if $0<B$ and $1\le d$, let $$m=\left\lfloor\frac{n}{d}\right\rfloor, \qquad \rho=\frac{md}{n}, \qquad \delta=\delta(n,d,\beta,B,p).$$ For every $U:\{1,\ldots,m\}\to\mathbb R$ satisfying $|U_b|\le B/2$ for all $b$, there are models $M_+$ and $M_-$ in $\mathcal M_{n,d,\beta}(B)$ whose graph is the complete $d$-block graph, whose coefficient schedules are the corresponding block schedules with signs $+1$ and $-1$, and whose total treatment effects obey $$\tau_n(M_+)=\rho\delta, \qquad \tau_n(M_-)=-\rho\delta.$$ The two block-prior densities with signs $+1$ and $-1$, relative to the block dominating measure, satisfy $$H^2(\Pi_+,\Pi_-) \le \frac{4\pi^2m\delta^2}{B^2A_d}.$$ The active fraction and block energy satisfy $$\frac12\le \rho\le 1, \qquad \frac{A_d}{m} = \frac{dA_d/n}{\rho}.$$

Fix an interaction order $\beta\ge 1$ and a treatment probability $p\in(0,1)$. Then there are constants $c_{\beta,p}$ and $C_{\beta,p}$ such that $0<c_{\beta,p}\le C_{\beta,p}$ and the following statements hold for every $n,d\in\mathbb N$, every $B\in\mathbb R$, and every finite design $D$ on $\{0,1\}^{V_n}$ satisfying the itemized conditions:

• (Population and degree.) The population has size $n\ge1$, $V_n=\{1,\ldots,n\}$, and the degree index satisfies $d\le n$.
• (Radius.) The radius satisfies $B\ge0$.
• (Design.) The design $D$ is the product Bernoulli design with common treatment probability $p$, as in Assumption A-1.

Let $$A_d = \sum_{r=1}^{\bar\beta_d} \binom{d}{r} \frac{\Delta_r(p)^2}{\{p(1-p)\}^r},$$ with $\bar\beta_d$ and $k_\star(d,\beta,p)$ as in Definition P-1. The coefficient-mass model $\mathcal M_{n,d,\beta}(B)$ of Definition P-5 is contained in the uniformly bounded-outcome model $\mathcal M_{n,d,\beta}^{\infty}(B)$ of Definition P-17. If $B>0$ and $d\ge1$, this inclusion is strict: some graph and bounded-outcome coefficient schedule in $\mathcal M_{n,d,\beta}^{\infty}(B)$ has no realization with the same graph and coefficient schedule in $\mathcal M_{n,d,\beta}(B)$. The minimax risks of Definition P-8 satisfy $$c_{\beta,p} B^2 \min\!\left\{1,\frac{dA_d}{n}\right\} \le R_{n,\ell_1}^{\star}(d,\beta,p,B) = R_n^{\star}(d,\beta,p,B) \le R_{n,\infty}^{\star}(d,\beta,p,B).$$ For the bounded-outcome clipped SNIPE estimator $\widehat\tau_{n,\infty}^{\mathrm{up}}$ of Definition P-19, $$R_{n,\infty}^{\star}(d,\beta,p,B) \le \sup_{(G,c)\in\mathcal M_{n,d,\beta}^{\infty}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_{n,\infty}^{\mathrm{up}}-\tau_n(G,c)\bigr)^2 \right] \le C_{\beta,p} B^2 \min\!\left\{1,\frac{dA_d}{n}\right\}.$$ The coefficient-class clipped SNIPE estimator $\widehat\tau_n^{\mathrm{up}}$ also satisfies $$\sup_{(G,c)\in\mathcal M_{n,d,\beta}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{up}}-\tau_n(G,c)\bigr)^2 \right] \le C_{\beta,p} B^2 \min\!\left\{1,\frac{dA_d}{n}\right\}.$$ For every $(G,c)\in\mathcal M_{n,d,\beta}(B)$, the unprojected SNIPE estimator $\widehat\tau_n^{\mathrm{SNIPE}}$ is $D$-unbiased for $\tau_n(G,c)$. The same $D$-unbiasedness holds for every $(G,c)\in\mathcal M_{n,d,\beta}^{\infty}(B)$. Its worst-case mean squared error obeys $$\sup_{(G,c)\in\mathcal M_{n,d,\beta}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n(G,c)\bigr)^2 \right] \le \frac{B^2 d A_d}{n},$$ and $$\sup_{(G,c)\in\mathcal M_{n,d,\beta}^{\infty}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n(G,c)\bigr)^2 \right] \le \frac{B^2 d A_d}{n}.$$ For every unit $i$, on both $\mathcal M_{n,d,\beta}(B)$ and $\mathcal M_{n,d,\beta}^{\infty}(B)$, the local score energy is at most $A_d$. The complete-block energy is comparable to the exposed binomial term: $$c_{\beta,p}\, d\binom{d}{k_\star(d,\beta,p)} \le dA_d \le C_{\beta,p}\, d\binom{d}{k_\star(d,\beta,p)}.$$ If $d\ge1$ and $d\mid n$, let $m=n/d$ and let the graph be the disjoint union of $m$ complete directed $d$-blocks, including loops. Then canonical unprojected SNIPE has exact worst-case risk on the fixed block graph and globally on both classes: $$\sup_{\mathcal M_{n,d,\beta}(B)\text{ on the fixed block graph}} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n\bigr)^2 \right] = \frac{B^2A_d}{m},$$ $$\sup_{\mathcal M_{n,d,\beta}^{\infty}(B)\text{ on the fixed block graph}} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n\bigr)^2 \right] = \frac{B^2A_d}{m},$$ and $$\sup_{(G,c)\in\mathcal M_{n,d,\beta}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n(G,c)\bigr)^2 \right] = \sup_{(G,c)\in\mathcal M_{n,d,\beta}^{\infty}(B)} \mathbb E_D\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n(G,c)\bigr)^2 \right] = \frac{B^2A_d}{m} = \frac{B^2dA_d}{n}.$$ If $B>0$ and $d\ge1$, put $$m=\bigl\lfloor n/d\bigr\rfloor, \qquad \rho=\frac{md}{n}, \qquad \delta=\delta(n,d,\beta,B,p)\ \text{ as in \text{def:block-family}}.$$ For every vector $U=(U_b)_{b=1}^m$ with $|U_b|\le B/2$ for all $b$, there are two coefficient-mass models on the block graph, with signs $+1$ and $-1$, whose coefficient schedules are the corresponding block schedules and whose total treatment effects are $$\tau_n^{+}=\rho\delta, \qquad \tau_n^{-}=-\rho\delta.$$ For the two associated block priors $\Pi_+$ and $\Pi_-$, $$H^2(\Pi_+,\Pi_-) \le \frac{4\pi^2 m\delta^2}{B^2A_d},$$ and the active share satisfies $$\frac12\le \rho\le 1, \qquad \frac{A_d}{m} = \frac{dA_d/n}{\rho}.$$

Fix an integer $\beta$, a common Bernoulli treatment probability $p$, and a radius $B$. Suppose that:

• (Smoothness order.) $\beta\ge 1$.
• (Assignment probability.) $p\in(0,1)$.
• (Radius.) $B>0$.
• (Block sequence.) For each index $t$, $n_t$ and $d_t$ are positive integers with $d_t\mid n_t$, and $$m_t:=\frac{n_t}{d_t}.$$
• (Complete-block graph.) For each $t$, $G_t$ is the directed graph on $V_{n_t}$ in which $j\to i$ exactly when $j$ and $i$ are active units in the same quotient class after division by $d_t$; equivalently, the active units form complete directed blocks with self-loops and inactive units are isolated.
• (Assignment design.) The assignment design $D_t$ is the product Bernoulli design with common probability $p$, as in Assumption A-1.

Define the complete-block score energy by $$A_d := \sum_{r=1}^{\bar\beta_d} \binom{d}{r}\frac{\Delta_r(p)^2}{\{p(1-p)\}^r}.$$ Then, for every $t$, $$R_t^{\mathrm{loc,lin}} = \frac{B^2A_{d_t}}{m_t} = \frac{B^2d_tA_{d_t}}{n_t}.$$ For local linear weights $w\in\mathcal E_t^{\mathrm{loc,lin}}$, put $Z_S:=\prod_{j\in S}Z_j$. For each active block $V_b$, define $$\Psi_{b,t}(w) := \max_{\substack{(\varepsilon_i,S_i)_{i\in V_b}\\ \varepsilon_i\in\{-1,1\},\ S_i\subseteq V_b,\ |S_i|\le \bar\beta_{d_t}}} \mathbb E_Z\!\left[ \left( \sum_{i\in V_b} \varepsilon_i \left\{ w_{i,t}(Z_{b(i)})Z_{S_i} - \mathbf 1\{S_i\ne\varnothing\} \right\} \right)^2 \right].$$ For every $t$ and every $w\in\mathcal E_t^{\mathrm{loc,lin}}$, $$\sup_{c\in\mathcal M_t(G_t)} \mathbb E_Z\!\left[(\widehat\tau_{w,t}-\tau_{n_t})^2\right] = \frac{B^2}{n_t^2}\sum_{b=1}^{m_t}\Psi_{b,t}(w),$$ and, for every active block $V_b$, $$d_t^2A_{d_t}\le \Psi_{b,t}(w).$$ For any sequence $w_t\in\mathcal E_t^{\mathrm{loc,lin}}$, $$\frac{ \sup_{c\in\mathcal M_t(G_t)} \mathbb E_Z\!\left[(\widehat\tau_{w_t,t}-\tau_{n_t})^2\right] }{ B^2A_{d_t}/m_t } \longrightarrow 1$$ if and only if $$\frac{1}{m_td_t^2A_{d_t}} \sum_{b=1}^{m_t} \left\{\Psi_{b,t}(w_t)-d_t^2A_{d_t}\right\} \longrightarrow 0.$$ Moreover, the representer condition $$\frac{1}{n_tA_{d_t}} \sum_{i\in V_{n_t}} \mathbb E_Z\!\left[ \left\{ w_{i,t}(Z_{b(i)})-g_{d_t}(Z_{b(i)}) \right\}^2 \right] \longrightarrow 0$$ implies $$\frac{ \sup_{c\in\mathcal M_t(G_t)} \mathbb E_Z\!\left[(\widehat\tau_{w_t,t}-\tau_{n_t})^2\right] }{ B^2A_{d_t}/m_t } \longrightarrow 1.$$ If $d_t\to\infty$, then there exists a sequence $w_t\in\mathcal E_t^{\mathrm{loc,lin}}$ such that $$\frac{ \sup_{c\in\mathcal M_t(G_t)} \mathbb E_Z\!\left[(\widehat\tau_{w_t,t}-\tau_{n_t})^2\right] }{ B^2A_{d_t}/m_t } \longrightarrow 1,$$ and, for all sufficiently large $t$, $$\frac{1}{n_tA_{d_t}} \sum_{i\in V_{n_t}} \mathbb E_Z\!\left[ \left\{ w_{i,t}(Z_{b(i)})-g_{d_t}(Z_{b(i)}) \right\}^2 \right] =2.$$ For every permutation $\pi:V_{n_t}\to V_{n_t}$ that preserves block membership, meaning $b(\pi(i))=b(i)$ for every $i$, the corresponding relabeled normalized average squared distance from the complete-block SNIPE score is also equal to $2$ for all sufficiently large $t$.

For the fair-coin design $p=1/2$, the following two conclusions hold.

• (Exact fair-coin contrasts.) For every $n,d,\beta\in\mathbb N$ and $B\in\mathbb R$ with $n\ge 1$, $d\ge 1$, $d\le n$, $\beta\ge 1$, and $B\ge 0$, the Bernoulli contrast coefficients satisfy, for every $r\ge 1$, $$\Delta_r(1/2) = \begin{cases} 2^{1-r}, & r \text{ odd},\\ 0, & r \text{ even}. \end{cases}$$ Consequently the complete-block score energy at interaction order $\beta$ is $$A_d = 4\sum_{\substack{1\le r\le \bar\beta_d\\ r\ \mathrm{odd}}}\binom dr, \qquad \bar\beta_d=\min\{\beta,d\},$$ and the exposed order $k_\star(d,\beta,1/2)$ from Definition P-1 is the largest odd integer at most $\bar\beta_d$, with value $0$ when no such odd integer exists.
• (First-order frontier.) There exist constants $c_{\mathrm{lower}},c_{\mathrm{upper}}\in\mathbb R$ with $$0<c_{\mathrm{lower}}\le c_{\mathrm{upper}}$$ such that, for every $n,d\in\mathbb N$ and $B\in\mathbb R$ with $n\ge 1$, $d\ge 1$, $d\le n$, and $B\ge 0$, the order-one energy is $$A_d=4d,$$ and the minimax risks of Definition P-8 satisfy $$c_{\mathrm{lower}}B^2\min\!\left\{1,\frac{d^2}{n}\right\} \le R_n^\star(d,1,1/2,B),$$ $$R_n^\star(d,1,1/2,B) = R_{n,\ell_1}^\star(d,1,1/2,B) \le R_{n,\infty}^\star(d,1,1/2,B) \le c_{\mathrm{upper}}B^2\min\!\left\{1,\frac{d^2}{n}\right\}.$$ If additionally $d\mid n$, then the unprojected SNIPE estimator $\widehat\tau_n^{\mathrm{SNIPE}}$ has exact worst-case mean squared error $$\sup_{M\in\mathcal M_{n,d,1}(B)} \mathbb E_{1/2,M}\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n\bigr)^2 \right] = \frac{4B^2d^2}{n},$$ and, over the uniformly bounded-outcome class, $$\sup_{M\in\mathcal M_{n,d,1}^{\infty}(B)} \mathbb E_{1/2,M}\!\left[ \bigl(\widehat\tau_n^{\mathrm{SNIPE}}-\tau_n\bigr)^2 \right] = \frac{4B^2d^2}{n}.$$