Résumé technique : Une théorie minimax basée sur la conception pour les expériences de réseau

Énoncé du problème

Les expériences de réseau sont largement utilisées dans les sciences sociales et médicales pour estimer les effets causaux en présence d'interférence, où le résultat d'une unité dépend des traitements de ses voisins. Bien qu'une littérature importante se soit développée autour de procédures statistiques améliorées (par exemple, la randomisation par grappes, les plans d'ensembles indépendants), les limites statistiques fondamentales de l'estimation dans ces contextes restent mal comprises. Plus précisément, il manque un benchmark théorique définissant les taux d'estimation statistiquement optimaux pour les expériences de réseau. Les travaux existants fixent souvent l'estimateur et considèrent des classes de conceptions restreintes, ou vice versa, échouant ainsi à fournir une notion universelle d'optimalité qui tienne compte du choix simultané de la conception expérimentale et de l'estimateur.

Ce document répond à la question suivante : Quels sont les taux minimax fondamentaux pour estimer les effets causaux sous interférence de voisinage arbitraire (ANI), en considérant toutes les conceptions expérimentales et tous les estimateurs possibles ?

Méthodologie

Les auteurs développent une théorie minimax basée sur la conception pour les expériences de réseau sous le modèle d'interférence de voisinage arbitraire (ANI). La méthodologie centrale comprend :

1. Cadre minimax basé sur la conception : Contraتيجة aux cadres de superpopulation où le processus générateur de données est fixé, cette approche traite la fonction de résultat potentiel comme le paramètre de nuisance et la conception expérimentale comme une variable de choix. Le risque minimax est défini comme l'infimum sur toutes les conceptions et tous les estimateurs du supremum de l'erreur quadratique moyenne (MSE) sur une classe de fonctions de résultats potentiels avec des moments bornés.
2. Graphe de conflit ($H$) : Central à l'analyse, le graphe de conflit présente des sommets représentant les expositions pertinentes pour l'estimand (configurations de traitement) et des arêtes reliant les expositions qui ne peuvent être observées simultanément sous aucune intervention. Les auteurs prouvent que le risque minimax est une fonction uniquement de ce graphe de conflit, faisant abstraction de la structure spécifique du réseau et des détails de l'estimand.
3. Bornes inférieures via la méthode de Le Cam : Le papier adapte la méthode de Le Cam au cadre basé sur la conception. Cela implique la construction de distributions de mélange sur les fonctions de résultats potentiels pour établir des bornes statistiques inférieures. Une innovation clé est le développement de constructions de mélanges adaptées à la conception, nécessaires car l'expérimentateur contrôle la conception. Deux types de bornes inférieures sont dérivés :
   • Information globale : Basée sur la taille du plus grand ensemble indépendant dans le graphe de conflit ($I(H)$).
   • Information locale : Basée sur les degrés du graphe de conflit, utilisant spécifiquement un « degré critique » ($d^*$) qui capture la connectivité des sous-graphes les plus denses.
4. Bornes supérieures via le compromis biais-variance : Les auteurs construisent des procédures statistiques non biaisées (extensions de la conception du graphe de conflit) et dérivent des bornes supérieures impliquant la plus grande valeur propre ($\lambda(H)$) et le degré moyen ($d_{avg}(H)$) du graphe de conflit. Ils améliorent ensuite ces bornes en introduisant un compromis biais-variance, où ignorer un sous-ensemble d'expositions à « haut degré » (sommets dans $H$) réduit la variance au prix d'une introduction de biais, menant à un problème d'optimisation de sous-graphe induit régularisé.

Contributions clés

1. Caractérisation du risque minimax via les graphes de conflit

Le papier établit que le risque minimax pour une expérience de réseau est une fonction du graphe de conflit $H$. Cela fournit un cadre unifié où la complexité statistique est déterminée par les propriétés structurelles de $H$ (spécifiquement ses ensembles indépendants et sa connectivité) plutôt que par la simple structure du réseau d'interférence $G$.

2. Bornes de taux minimax

Les auteurs fournissent une série de bornes supérieures et inférieures sur le taux minimax en termes de quantités de la théorie des graphes :

• Bornes inférieures : Le risque est borné inférieurement par des fonctions de l'ensemble indépendant maximal $I(H)$ et du degré critique $d^*(H)$. Plus précisément, le taux est au moins de l'ordre de $\max(1/|I(H)|, \sqrt{d^*(H)}/n)$.
• Bornes supérieures : Le risque est borné supérieurement par une quantité impliquant la plus grande valeur propre $\lambda(H)$ et le degré moyen $d_{avg}(H)$, affinée par un terme de compromis biais-variance $Q(S, H)$ qui minimise sur des sous-ensembles $S$ de sommets à supprimer.
• Interaction entre les moments et l'hétérogénéité : L'analyse révèle une interaction entre la force des restrictions de moments ($q$) et l'hétérogénéité des degrés. Des restrictions de moments plus fortes (un $q$ plus élevé) permettent de meilleurs taux en présence de degrés hétérogènes.

3. Application à des estimands spécifiques

Les résultats généraux sont appliqués à deux estimands causaux standards :

• Effet de traitement direct (DTE) : Le taux minimax est montré comme étant borné par des quantités liées au réseau d'interférence original $G$ (par exemple, $\sqrt{d_{avg}(G)}/n$ et $\lambda(G)/n$).
• Effet de traitement moyen global (GATE) : Le taux minimax est borné par des quantités liées au réseau à deux sauts $G^2$ (par exemple, $\sqrt{d_{avg}(G^2)}/n$ et $\lambda(G^2)/n$). Cela soutient formellement l'intuition selon laquelle le GATE est plus difficile à estimer que le DTE en raison de la connectivité plus dense du graphe à deux sauts.

4. Étroitesse (Tightness) et dureté computationnelle

• Étroitesse : Les bornes sont montrées comme étant étroites pour les graphes $d$-réguliers. Pour les graphes $d$-réguliers aléatoires, les bornes correspondent à un facteur logarithmique près, caractérisant le taux minimax dans un sens de cas moyen.
• Dureté computationnelle : Le papier conjecture que calculer le taux minimax exact (ou même l'approcher avec certains facteurs) est NP-difficile, car cela est intimement lié au problème de la recherche de l'ensemble indépendant maximal dans les graphes. Cela suggère que bien que les limites théoriques soient bien définies, trouver la procédure optimale pour un réseau arbitraire peut être computationnellement intraitable.

Résultats

• Résultat principal (informel) : Le risque minimax $R(G, \tau)$ pour estimer un effet causal $\tau$ sur un réseau $G$ est borné par :
  $$\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}$$
  où $H$ est le graphe de conflit, $I(H)$ est l'ensemble indépendant maximal, $d^*(H)$ est le degré critique, et $Q(S, H)$ implique les propriétés spectrales du sous-graphe induit $H \setminus S$.
• DTE vs. GATE : Pour les graphes $d$-réguliers aléatoires, le taux minimax pour le DTE est borné par $O(d/n)$ en haut, mais la borne inférieure est $\Omega((d \log d)/n)$, indiquant un écart logarithmique. En revanche, le taux minimax pour le GATE est borné entre $\Omega(d/n)$ et $O(d^2/n)$. Cela confirme que le GATE est statistiquement plus difficile à estimer que le DTE, et que les bornes pour le DTE sur les graphes aléatoires ne sont pas étroites jusqu'à des facteurs constants.
• Amélioration par le compromis biais-variance : La stratégie de compromis biais-variance proposée améliore considérablement la borne supérieure pour les graphes présentant une forte hétérogénéité de degré (par exemple, les graphes en étoile), réduisant le taux de $O(1/\sqrt{n})$ à $O(1/n)$ en ignorant le nœud central.

Signification et affirmations

Le papier affirme combler une lacune critique dans la littérature de l'inférence causale basée sur la conception en fournissant les premières analyses minimax qui tiennent compte simultanément de la conception expérimentale et du choix de l'estimateur sans restrictions.

• Benchmark théorique : Il fournit une limite statistique fondamentale pour les expériences de réseau, permettant aux chercheurs d'évaluer la proximité des procédures existantes par rapport à l'optimalité.
• Aperçu structurel : En liant le risque minimax au graphe de conflit, le papier offre une nouvelle perspective sur le « problème fondamental de l'inférence causale » dans les contextes de réseau, le formulant comme un problème d'inobservabilité encodé dans la topologie du graphe.
• Orientation pratique : Les résultats suggèrent que pour les réseaux présentant une forte hétérogénéité de degré, ignorer les nœuds à haut degré (introduisant un biais) peut être une stratégie statistiquement optimale pour réduire la variance, une découverte contre-intuitive qui défie les approches classiques d'estimation non biaisée.
• Limites computationnelles : La conjecture concernant la dureté computationnelle de dériver le taux minimax exact souligne un obstacle potentiel à la mise en œuvre pratique, suggérant que les travaux futurs pourraient devoir se concentrer sur des approximations efficaces en termes de calcul ou sur l'optimalité du taux au sein de familles de graphes spécifiques.

Les auteurs maintiennent une position modeste, reconnaissant que bien que leurs bornes caractérisent le risque minimax pour les graphes réguliers et aléatoires, une caractérisation simple sous forme fermée pour des graphes arbitraires peut ne pas exister en raison de la complexité computationnelle sous-jacente. Le travail est présenté comme une étape fondamentale vers la compréhension des limites statistiques des expériences de réseau.