Résumé Technique : Apprentissage à partir de Sources de Données Biaisées et Coûteuses

Formulation du Problème

Ce travail traite du défi de la collecte de données multi-sources sous un budget fixe pour estimer des statistiques de population. Dans de nombreux scénarios pratiques (par exemple, les essais cliniques, les sondages politiques), les données doivent être recueillies auprès de $M$ sources hétérogènes, chacune présentant des compositions de groupes et des coûts d'échantillonnage distincts.

La difficulté fondamentale provient de trois facteurs :

1. Coûts Hétérogènes : L'échantillonnage auprès d'une source $m$ entraîne un coût $c_m$.
2. Décalage Distributionnel : La distribution des groupes dans chaque source ($p_m$) diffère de la distribution de la population cible ($q$) et des autres sources.
3. Identité de Groupe Inobservable lors du Recrutement : Bien que les identités de groupe soient connues pour les sources et la cible, les individus ne peuvent pas être pré-sélectionnés en fonction de leur identité de groupe sans engendrer le coût de mesure.

L'objectif est de concevoir un plan d'échantillonnage $\mathbf{n} = (n_1, \dots, n_M)$ (où $n_m$ est le nombre d'échantillons de la source $m$) et un estimateur $\hat{\theta}$ pour minimiser le risque minimax (perte quadratique espérée) pour l'estimation de l'un ou l'autre de :

• La moyenne de la population $\theta_{PM}(Q) = \mathbb{E}_{Y \sim Q}[Y]$.
• Le vecteur des moyennes conditionnelles par groupe $\theta_{GM}(Q) = \{\mathbb{E}[Y|Z=z]\}_{z \in [K]}$.

Le problème est contraint par un budget $B$, tel que $\mathbf{c}^\top \mathbf{n} \le B$. Les auteurs supposent que la distribution conditionnelle $P_{Y|Z}$ est inconnue mais appartient à une classe avec des moyennes bornées ($| \mathbb{E}[Y|Z] | \le R$) et une variance bornée ($\text{Var}(Y|Z) \le \sigma^2$).

Méthodologie

1. Taille d'Échantillon Effective et Discrépance

Les auteurs introduisent la taille d'échantillon effective ($n_{\text{eff}}$) comme la métrique centrale pour évaluer un plan d'échantillonnage. Pour un plan $\mathbf{n}$, soit $p_{\mathbf{n}}$ la distribution de mélange des groupes induite par le plan d'échantillonnage. La taille d'échantillon effective par rapport à une distribution cible $q$ est définie par :
$$n_{\text{eff}}(\mathbf{n}, q) := \frac{\mathbf{1}^\top \mathbf{n}}{d(q || p_{\mathbf{n}})}$$
où $d(a || b) = \sum_{z} \frac{a(z)^2}{b(z)}$ est une mesure de discrépance liée à la divergence $\chi^2$ ($d(a||b) = D_{\chi^2}(a||b) + 1$). Cette métrique quantifie la capacité des données collectées à approximer la distribution cible, en pénalisant les plans qui entraînent une divergence élevée.

2. Plan d'Échantillonnage Optimal

Les auteurs proposent un plan d'échantillonnage $\mathbf{n}^\star_T$ qui maximise la taille d'échantillon effective sous la contrainte de budget :
$$\mathbf{n}^\star_T \in \arg\max_{\mathbf{n}} n_{\text{eff}}(\mathbf{n}, q) \quad \text{sous réserve de} \quad \mathbf{c}^\top \mathbf{n} \le B$$
Pour l'estimation des moyennes conditionnelles par groupe, $q$ est remplacé par la distribution uniforme $u_K$. Le problème d'optimisation est convexe, ce qui le rend efficacement soluble par calcul.

3. Conception de l'Estimateur

L'article associe le plan d'échantillonnage optimal à des estimateurs spécifiques :

• Pour la Moyenne de la Population : Un estimateur de post-stratification ($\hat{\theta}_{PS}$), qui estime la moyenne au sein de chaque groupe et les repondère par la distribution cible $q$.
  $$\hat{\theta}_{PS} = \sum_{z \in [K]} q(z) \bar{Y}_z$$
• Pour les Moyennes Conditionnelles par Groupe : Le vecteur des moyennes observées par groupe ($\hat{\theta}_{VM}$).
• Pour la Prédiction : Une procédure de Minimisation du Risque Empirique Pondéré par l'Importance (IWERM).

Contributions Clés et Résultats

1. Bornes Inférieures Minimax

Les auteurs établissent des bornes inférieures sur le risque minimax pour toute politique. Une contribution technique clé est la technique de preuve, qui utilise un a priori uniforme sur les moyennes bornées et analyse la variance d'un a posteriori normal tronqué. Cela est nécessaire car les a priori conjugués standards (normale-normale) sont invalides lorsque les moyennes sont bornées.

La borne inférieure pour l'estimation de la moyenne de la population est :
$$R^\star_{PM}(B, P_{Y|Z}) \ge \frac{\sigma^2}{n_{\text{eff}}(\mathbf{n}^\star_T, q)} - o\left(\frac{1}{B}\right)$$
Ceci démontre que le risque est fondamentalement limité par la taille d'échantillon effective du plan d'échantillonnage optimal.

2. Bornes Supérieures Minimax et Optimalité

Les auteurs prouvent que la politique $(\mathbf{n}^\star_T, \hat{\theta}_{PS})$ atteint une borne supérieure qui correspond à la borne inférieure dans le terme principal :
$$R_{PM}((\mathbf{n}^\star_T, \hat{\theta}_{PS}), P_{Y|Z}) \le \frac{\sigma^2}{n_{\text{eff}}(\mathbf{n}^\star_T, q)} + o\left(\frac{1}{B}\right)$$
Cela établit que l'approche proposée est minimax optimale. L'analyse montre que les stratégies naïves (par exemple, faire correspondre exactement la distribution cible ou maximiser le nombre brut d'échantillons) sont sous-optimales car elles ne parviennent pas à prendre en compte l'interaction entre le coût, la composition de la source et la capacité de l'estimateur à corriger le biais.

3. Extension aux Problèmes de Prédiction

Le cadre est étendu aux tâches de prédiction (minimisation du risque excessif).

• Borne Supérieure : La politique $(\mathbf{n}^\star_T, \hat{h}_{IWERM})$ atteint une borne de risque excessif évoluant selon $\sqrt{\frac{P_{\text{dim}}(H) K d(q || p_{\mathbf{n}^\star_T})}{B}}$.
• Borne Inférieure : Un nouveau lemme de réduction à un test est développé pour gérer le décalage entre les distributions sources et cibles. Cela produit une borne inférieure évoluant selon $\sqrt{\frac{VC_{\text{dim}}(H) q_{\min} d(q || p_{\mathbf{n}^\star_T})}{B}}$.
  Bien qu'il existe un écart de $\sqrt{K/q_{\min}}$ entre les bornes supérieure et inférieure, la dépendance vis-à-vis de la taille d'échantillon effective et de la mesure de discrépance est identique, suggérant que le principe s'applique également à la prédiction.

4. Résultat d'Impossibilité

L'article prouve que sans l'hypothèse de moyennes bornées ($| \mathbb{E}[Y|Z] | \le R$), le problème est sans issue (risque infini), justifiant ainsi l'hypothèse de bornage utilisée dans le cadre théorique.

Signification et Revendications

L'article affirme fournir la première stratégie de collecte de données minimax-optimale pour les contextes multi-sources avec des coûts et des distributions hétérogènes. Sa signification réside dans :

1. Redéfinition de l'Efficacité : Aller au-delà de la simple "correspondance avec la distribution cible" pour maximiser la taille d'échantillon effective, qui équilibre coût, biais et variance.
2. Rigueur Théorique : Fournir des bornes supérieures et inférieures correspondantes pour l'estimation de la moyenne, établissant les limites fondamentales de l'apprentissage à partir de sources biaisées et coûteuses.
3. Techniques Nouvelles : Introduire un nouveau cadre de réduction à un test pour les problèmes de prédiction où les distributions sources et cibles diffèrent, et utiliser l'analyse de la normale tronquée pour les bornes inférieures sous contraintes de bornage.
4. Praticité : Démontrer par des simulations que la politique proposée surpasse significativement les bases naïves (Uniforme, Coût Inverse, Proche, et Hybride) à travers diverses distributions cibles et contraintes de budget.

Les auteurs notent que bien que les résultats soient établis pour l'estimation de la moyenne et des contextes de prédiction spécifiques, le principe de maximisation de la taille d'échantillon effective offre une approche structurée pour l'apprentissage multi-source en présence de données coûteuses et hétérogènes.