Adversarial Estimation of Assortment Probabilities under Independence Structure

1. Problématique et Contexte

L'article s'intéresse au problème de l'estimation des probabilités d'assortiment (la probabilité conjointe qu'un ensemble d'items soit choisi ou observé). Ce problème est central dans de nombreux domaines tels que la gestion des opérations (bundling de produits, publicité), les essais cliniques (combinaisons de traitements) et l'inférence causale (estimation des scores de propension généralisés pour des traitements multiples).

Le défi principal :
Lorsqu'on a $M$ items binaires, la distribution conjointe est définie par $2^M - 1$ paramètres. Les méthodes existantes (comme les modèles logit multinomiaux) traitent chaque assortiment comme une catégorie distincte. Cela devient statistiquement inefficace et computationnellement prohibitif lorsque $M$ est grand, car le nombre de paramètres croît exponentiellement. De plus, ces méthodes ignorent souvent les structures d'indépendance sous-jacentes (par exemple, l'achat de produits dans des catégories différentes peut être indépendant).

L'objectif est d'exploiter la sparsité dans la structure de dépendance (c'est-à-dire que de nombreuses interactions d'ordre supérieur sont nulles) pour obtenir des estimateurs plus efficaces, même lorsque le nombre de paramètres potentiels ($p \approx 2^M$) dépasse la taille de l'échantillon $N$.

2. Méthodologie

Les auteurs proposent une approche basée sur la représentation de Bahadur (1959), qui décompose la distribution conjointe d'un vecteur binaire en termes de probabilités marginales et de coefficients de corrélation généralisés.

A. Formulation du Modèle

Soit $Y_i \in \{0, 1\}^M$ le vecteur d'observations. La probabilité conditionnelle est modélisée comme :
$$P(Y_i = y | X_i = x) = f(y, \alpha_0(x), r_0(x)) \prod_{j=1}^M \alpha_{0j}(x)^{y_j}(1-\alpha_{0j}(x))^{1-y_j}$$
où :

• $\alpha_0(x)$ : vecteur de probabilités marginales (paramètres de nuisance, de dimension $M$).
• $r_0(x)$ : vecteur de coefficients de corrélation généralisés (paramètres d'intérêt, de dimension $p = 2^M - M - 1$).
• La fonction $f$ est affine par rapport à $r_0(x)$.

L'hypothèse clé est que $r_0(x)$ est parcimonieux (sparse) : la plupart des coefficients de corrélation sont nuls, reflétant une structure d'indépendance partielle entre les composants binaires.

B. Limites des Estimateurs Classiques

• Maximum de Vraisemblance (MLE) : La fonction de vraisemblance est non-concave par rapport aux probabilités marginales $\alpha$, rendant l'optimisation difficile. De plus, le MLE ne s'adapte pas à la parcimonie et surajuste lorsque $2^M \gg N$.
• Estimateur "Plug-in" : Une approche naïve consiste à estimer d'abord $\alpha_0$ (par des moyennes empiriques), puis à fixer $\alpha$ pour estimer $r_0$ via une régression Lasso ($\ell_1$-pénalisée). Cependant, les auteurs montrent que cette approche induit un biais de spécification dans la fonction de score, conduisant à un taux de convergence sous-optimal ($O(\sqrt{sM^2/N})$).

C. La Solution : Estimateurs Adversaires Régularisés

Pour surmonter ces limites, les auteurs développent deux estimateurs adversaires :

1. Estimateur Adversaire ($\hat{r}_A$) :
   Il maximise la vraisemblance en considérant le pire cas sur l'ensemble des probabilités marginales possibles $\alpha$ dans un ensemble d'adversité $A(\hat{\alpha})$.
   $$\hat{r}_A \in \arg\max_r \min_{\alpha \in A(\hat{\alpha})} \left[ \frac{1}{N}\sum \log(1 + W(\alpha, Y_i)'r) - \lambda \|r\|_1 \right]$$
   Avantage : Meilleure performance théorique.
   Inconvénient : Intraitable computationnellement car la minimisation interne sur $\alpha$ est non-concave et complexe.

2. Estimateur du Premier Ordre ($\hat{r}_{FO}$) - Contribution Majeure :
   Pour rendre le problème computationnellement faisable, les auteurs approximent la fonction $W(\alpha, Y_i)$ par un développement de Taylor du premier ordre autour de l'estimateur initial $\hat{\alpha}$.
   $$W^{FO}(\alpha, Y_i) \approx W(\hat{\alpha}, Y_i) + \nabla_\alpha W(\hat{\alpha}, Y_i)(\alpha - \hat{\alpha})$$
   L'objectif devient bilinéaire et concave par rapport à $\alpha$. Si l'ensemble d'adversité $A(\hat{\alpha})$ est choisi comme un hyper-rectangle, le minimum interne est atteint aux sommets (requérant seulement $p$ évaluations).
   $$\hat{r}_{FO} \in \arg\max_r \min_{\alpha \in A(\hat{\alpha})} \left[ \frac{1}{N}\sum \log(1 + W^{FO}(\alpha, Y_i)'r) - \lambda \|r\|_1 \right]$$

D. Extension aux Covariables

Le cadre est étendu au cas avec covariables $X_i$ en utilisant des estimateurs localisés (régression locale linéaire) pour les fonctions de nuisance $\alpha_0(x)$ et $r_0(x)$, permettant une estimation non-paramétrique des effets hétérogènes.

3. Résultats Théoriques Principaux

Sous des conditions de régularité standard (hypothèses de parcimonie, bornes sur les moments, condition de valeur propre restreinte) :

• Taux de Convergence Optimal : L'estimateur du premier ordre $\hat{r}_{FO}$ atteint le taux de convergence optimal (oracle) de l'ordre de $O(\sqrt{sM/N})$, où $s$ est le nombre de coefficients non nuls.
  • Comparaison : L'estimateur "plug-in" classique a un taux plus lent de $O(\sqrt{sM^2/N})$.
  • Condition d'optimalité : L'estimateur $\hat{r}_{FO}$ est optimal lorsque $s \gtrsim \log M$.
• Robustesse : La méthode s'adapte à la structure d'indépendance intrinsèque sans nécessiter de connaître a priori quels coefficients sont nuls (support inconnu).
• Inférence Causale : Dans le contexte de l'estimation des effets moyens de traitement (ATE) avec de multiples traitements binaires, l'utilisation de ces estimateurs pour les scores de propension généralisés permet d'obtenir une convergence en $\sqrt{N}$ et une efficacité semi-paramétrique, même lorsque le nombre de combinaisons de traitements est exponentiellement grand.

4. Contributions Clés

1. Nouvelle Méthodologie d'Estimation : Introduction d'une approche adversaire régularisée pour les paramètres de haute dimension avec des paramètres de nuisance de faible/moyenne dimension, inversant la logique habituelle de l'apprentissage machine (où le paramètre cible est de basse dimension et les nuisances de haute dimension).
2. Estimateur du Premier Ordre Faisable : Développement d'un estimateur $\hat{r}_{FO}$ qui combine la robustesse théorique de l'approche adversaire avec la faisabilité computationnelle grâce à une approximation linéaire et une structure d'ensemble d'adversité simple (hyper-rectangle).
3. Théorie de Convergence : Preuve que l'approche adversaire corrige le biais induit par l'estimation des paramètres de nuisance, permettant d'atteindre le taux de convergence de l'oracle (où les marginales sont connues).
4. Application à l'Inférence Causale : Démonstration que l'exploitation de la parcimonie dans les scores de propension généralisés améliore considérablement l'estimation des effets de traitement dans des scénarios à multiples traitements.

5. Signification et Impact

Ce travail est significatif car il résout le dilemme classique entre la complexité computationnelle et l'efficacité statistique dans les modèles de choix discrets à haute dimension.

• Efficacité Statistique : En exploitant la parcimonie des corrélations (plutôt que de supposer une indépendance totale ou une structure factorielle rigide), la méthode évite le surajustement et fournit des estimations plus précises en échantillons finis.
• Faisabilité : Contrairement aux méthodes d'optimisation non-convexe ou aux approches bayésiennes complexes pour les modèles graphiques, l'estimateur proposé repose sur des programmes convexes (Lasso) et des minimisations simples sur des sommets, rendant l'approche applicable à des problèmes réels.
• Généralité : La méthode ne nécessite pas de connaître la structure de dépendance (le support de $r_0$), ce qui la rend robuste face à des structures de dépendance complexes et inconnues, contrairement aux modèles Ising ou aux graphes conditionnels qui imposent des contraintes structurelles fortes.

Les études de simulation et les applications aux effets de traitement confirment que l'estimateur proposé surpasse les modèles logit multinomiaux et les estimateurs de noyau classiques, offrant des gains substantiels en termes d'erreur quadratique moyenne (RMSE) et de couverture des intervalles de confiance.