📊 statistics

A Design-Based Minimax Theory for Network Experiments

This paper establishes a design-based minimax theory for network experiments under arbitrary interference, demonstrating that the fundamental limits of statistical estimation are determined by the connectivity properties of a conflict graph that captures inherent unobservability, and applying these bounds to analyze direct and global average treatment effects.

Original authors: Vardis Kandiros, Christopher Harshaw, Fredrik Sävje

Published 2026-08-06

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Vardis Kandiros, Christopher Harshaw, Fredrik Sävje

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out why your friends are acting a certain way. Maybe you want to know if a new video game makes people more energetic. In a perfect world, you could just give the game to one friend and not the other, then compare their energy levels. But real life isn't a perfect world; people hang out in groups. If you give the game to one friend, their energy might change just because they are talking to the friend who also got the game. This is called "interference": your friend's outcome depends not just on their own treatment, but on what their neighbors are doing.

Scientists call this a "network experiment." They want to measure the true effect of a treatment (like a medicine or a policy) while accounting for these messy social ripple effects. The big question has always been: "How good can our measurements actually get?" If the social network is a tangled web of connections, is there a fundamental limit to how precisely we can calculate the truth, no matter how clever our math is? Until now, we didn't really know the speed limit of these experiments. We had tools to drive, but no idea how fast the car could theoretically go before the engine blew up.

This paper, titled "A Design-Based Minimax Theory for Network Experiments," acts like a mechanic's manual for that theoretical speed limit. The authors, Vardis Kandiros, Christopher Harshaw, and Fredrik Sävje, developed a new way to calculate the absolute best possible precision for any network experiment. They call this the "minimax risk." Think of it as finding the "worst-case scenario" for your experiment. If you have a messy network and a tricky question to answer, what is the smallest error you could possibly make, even if you use the smartest design and the best calculator in the universe?

The authors discovered that the answer depends entirely on a hidden structure they call a "conflict graph." Imagine you are trying to take photos of your friends, but you can only take pictures of people who aren't arguing with each other. If two friends are fighting (in conflict), you can't photograph them both at the same time. The "conflict graph" is a map of all these arguments. The paper proves that the difficulty of your experiment is directly tied to how many people you can photograph at once without them fighting (the "independent set") and how many arguments exist in the group (the "degree" of the graph).

The researchers found that for some types of questions, like measuring the direct effect of a treatment on a single person, the math is relatively straightforward. But for broader questions, like measuring the effect of treating everyone versus no one, the conflict graph becomes much denser and messier, making the experiment much harder to run precisely. They provided mathematical formulas that set a "floor" and a "ceiling" for how accurate any experiment can be. Interestingly, they also showed that for some specific, highly connected networks, figuring out the exact best speed limit is so computationally difficult that it might be impossible for a computer to solve quickly—like trying to find the perfect seating arrangement for a wedding where everyone hates someone else.

In short, this paper doesn't just give you a better ruler; it tells you exactly how short the ruler can possibly be before it breaks. It shows that the structure of the social network itself dictates the limits of what we can learn, and it gives scientists a new way to check if their experiments are as good as they can possibly be.

Technical Summary: A Design-Based Minimax Theory for Network Experiments

Problem Statement

Network experiments are widely used in social and medical sciences to estimate causal effects in the presence of interference, where a unit's outcome depends on the treatments of its neighbors. While significant literature has developed improved statistical procedures (e.g., cluster randomization, independent set designs), the fundamental statistical limits of estimation in these settings remain poorly understood. Specifically, there is a lack of a theoretical benchmark defining the statistically optimal rates of estimation for network experiments. Existing works often fix the estimator and consider restricted classes of designs, or vice versa, failing to provide a universal notion of optimality that accounts for the simultaneous choice of experimental design and estimator.

This paper addresses the question: What are the fundamental minimax rates for estimating causal effects under arbitrary neighborhood interference (ANI), considering all possible experimental designs and estimators?

Methodology

The authors develop a design-based minimax theory for network experiments under the arbitrary neighborhood interference model. The core methodology involves:

Design-Based Minimax Framework: Unlike superpopulation frameworks where the data-generating process is fixed, this approach treats the potential outcome function as the nuisance parameter and the experimental design as a choice variable. The minimax risk is defined as the infimum over all designs and estimators of the supremum of the mean squared error (MSE) over a class of potential outcome functions with bounded moments.
Conflict Graph ( $H$ ): Central to the analysis is the conflict graph, where vertices represent estimand-relevant exposures (treatment configurations) and edges connect exposures that cannot be observed simultaneously under any intervention. The authors prove that the minimax risk is a function solely of this conflict graph, abstracting away the specific network structure and estimand details.
Lower Bounds via Le Cam's Method: The paper adapts Le Cam's method to the design-based setting. This involves constructing mixture distributions over potential outcome functions to establish statistical lower bounds. A key innovation is the development of design-adaptive mixture constructions, necessary because the experimenter controls the design. Two types of lower bounds are derived:
- Global Information: Based on the size of the largest independent set in the conflict graph ( $I(H)$ ).
- Local Information: Based on the degrees of the conflict graph, specifically utilizing a "critical degree" ( $d^*$ ) that captures the connectivity of the densest subgraphs.
Upper Bounds via Bias-Variance Tradeoff: The authors construct unbiased statistical procedures (extensions of the Conflict Graph Design) and derive upper bounds involving the largest eigenvalue ( $\lambda(H)$ ) and average degree ( $d_{avg}(H)$ ) of the conflict graph. They further improve these bounds by introducing a bias-variance tradeoff, where ignoring a subset of "high-degree" exposures (vertices in $H$ ) reduces variance at the cost of introducing bias, leading to a regularized induced subgraph optimization problem.

Key Contributions

1. Characterization of Minimax Risk via Conflict Graphs

The paper establishes that the minimax risk for a network experiment is a function of the conflict graph $H$ . This provides a unified framework where the statistical complexity is determined by the structural properties of $H$ (specifically its independent sets and connectivity) rather than just the underlying interference network $G$ .

2. Minimax Rate Bounds

The authors provide a series of upper and lower bounds on the minimax rate in terms of graph-theoretic quantities:

Lower Bounds: The risk is bounded below by functions of the largest independent set $I(H)$ and the critical degree $d^*(H)$ . Specifically, the rate is at least on the order of $\max(1/|I(H)|, \sqrt{d^*(H)}/n)$ .
Upper Bounds: The risk is bounded above by a quantity involving the largest eigenvalue $\lambda(H)$ and average degree $d_{avg}(H)$ , refined by a bias-variance tradeoff term $Q(S, H)$ which minimizes over subsets $S$ of vertices to remove.
Interplay of Moments and Heterogeneity: The analysis reveals an interplay between the strength of moment restrictions ( $q$ ) and degree heterogeneity. Stronger moment restrictions (higher $q$ ) allow for better rates in the presence of heterogeneous degrees.

3. Application to Specific Estimands

The general results are applied to two standard causal estimands:

Direct Treatment Effect (DTE): The minimax rate is shown to be bounded by quantities related to the original interference network $G$ (e.g., $\sqrt{d_{avg}(G)}/n$ and $\lambda(G)/n$ ).
Global Average Treatment Effect (GATE): The minimax rate is bounded by quantities related to the two-hop network $G^2$ (e.g., $\sqrt{d_{avg}(G^2)}/n$ and $\lambda(G^2)/n$ ). This formally supports the intuition that GATE is harder to estimate than DTE due to the denser connectivity of the two-hop graph.

4. Tightness and Computational Hardness

Tightness: The bounds are shown to be tight for $d$ -regular graphs. For random $d$ -regular graphs, the bounds match up to logarithmic factors, characterizing the minimax rate in an average-case sense.
Computational Hardness: The paper conjectures that computing the exact minimax rate (or even approximating it within certain factors) is NP-Hard, as it is intimately linked to the problem of finding maximum independent sets in graphs. This suggests that while the theoretical limits are well-defined, finding the optimal procedure for an arbitrary network may be computationally intractable.

Results

Main Result (Informal): The minimax risk $R(G, \tau)$ for estimating a causal effect $\tau$ on network $G$ is bounded by:
$\max\left(\frac{1}{|I(H)|}, \frac{\sqrt{d^*(H)}}{n}\right) \lesssim \inf_{D, \hat{\tau}} \sup_{y} \mathbb{E}[(\hat{\tau} - \tau)^2] \lesssim \min_{S} \frac{Q(S, H)}{n}$
where $H$ is the conflict graph, $I(H)$ is the maximum independent set, $d^*(H)$ is the critical degree, and $Q(S, H)$ involves the spectral properties of the induced subgraph $H \setminus S$ .
DTE vs. GATE: For random $d$ -regular graphs, the minimax rate for DTE is bounded by $O(d/n)$ from above, but the lower bound is $\Omega((d \log d)/n)$ , indicating a logarithmic gap. In contrast, the minimax rate for GATE is bounded between $\Omega(d/n)$ and $O(d^2/n)$ . This confirms that GATE is statistically more difficult to estimate than DTE, and that the bounds for DTE on random graphs are not tight up to constant factors.
Bias-Variance Improvement: The proposed bias-variance tradeoff strategy significantly improves the upper bound for graphs with high degree heterogeneity (e.g., star graphs), reducing the rate from $O(1/\sqrt{n})$ to $O(1/n)$ by ignoring the central node.

Significance and Claims

The paper claims to fill a critical gap in the design-based causal inference literature by providing the first minimax analyses that simultaneously account for experimental design and estimator choice without restrictions.

Theoretical Benchmark: It provides a fundamental statistical limit for network experiments, allowing researchers to assess how close existing procedures are to optimality.
Structural Insight: By linking minimax risk to the conflict graph, the paper offers a new perspective on the "fundamental problem of causal inference" in network settings, framing it as a problem of unobservability encoded in graph topology.
Practical Guidance: The results suggest that for networks with high degree heterogeneity, ignoring high-degree nodes (introducing bias) can be a statistically optimal strategy to reduce variance, a counter-intuitive finding that challenges standard unbiased estimation approaches.
Computational Limits: The conjecture regarding the computational hardness of deriving the exact minimax rate highlights a potential barrier in practical implementation, suggesting that future work may need to focus on computationally efficient approximations or rate optimality within specific graph families.

The authors maintain a modest stance, acknowledging that while their bounds characterize the minimax risk for regular graphs and random graphs, a simple, closed-form characterization for arbitrary graphs may not exist due to the underlying computational complexity. The work is presented as a foundational step toward understanding the statistical limits of network experiments.