Résumé technique : Sous-échantillonnage actif pour l'estimation M avec contraintes de mesure de seuils individualisés pour les données de haute dimension

1. Formulation du problème

Le document traite du problème de l'estimation d'un seuil individualisé optimal dans des contextients de haute dimension sous contraintes de mesure. Ce scénario survient fréquemment dans des applications modernes, telles que les études sur les dossiers de santé électroniques (EHR), où les covariables $(X, Z)$ sont disponibles pour une large population, mais où la variable de réponse $Y$ (par exemple, un résultat clinique nécessitant une revue manuelle des dossiers) est coûteuse ou chronophage à obtenir. Par conséquent, seul un petit sous-ensemble de taille $N$ (le budget de marquage) peut être étiqueté à partir d'un grand ensemble de données non étiquetées de taille $n$ ($N \ll n$).

L'objectif spécifique est d'estimer un paramètre de haute dimension $\theta^* \in \mathbb{R}^d$ définissant un seuil linéaire $c(Z) = \theta^{*T}Z$ pour une variable continue $X$. Le seuil optimal minimise la divergence entre l'événement $\{X > \theta^T Z\}$ et une réponse binaire $Y \in \{-1, +1\}$. Formellement, cela est formulé comme un problème d'estimation M :
$$\theta^* = \arg\min_{\theta} R(\theta), \quad \text{où} \quad R(\theta) = \mathbb{E}\left[\gamma(Y) L_{01}\{Y(X - \theta^T Z)\}\right]$$
Ici, $L_{01}$ est la perte 0-1, et $\gamma(\cdot)$ est une fonction de pondération. Le problème est caractérisé par :

• Non-régularité : La perte 0-1 conduit à des distributions limites et des taux de convergence non standards (typiquement plus lents que le taux paramétrique $N^{-1/2}$).
• Haute dimensionnalité : La dimension $d$ peut excéder la taille de l'échantillon, nécessitant des hypothèses de parcimonie ($s$-parcimonce de $\theta^*$).
• Contraintes de mesure : Le processus d'estimation doit sélectionner activement quels points de données doivent être étiquetés pour maximiser l'efficacité, plutôt que de s'appuyer sur un échantillonnage aléatoire.

2. Méthodologie

Les auteurs proposent un algorithme de sous-échantillonnage actif en K étapes qui affine itérativement l'estimateur en concentrant les efforts de marquage sur les points de données les plus informatifs.

Mécanisme central

L'algorithme repose sur l'idée que les observations où le résidu $X - \theta^T Z$ est proche de zéro (c'est-à-dire les points « proches du seuil ») fournissent l'information la plus pertinente pour estimer $\theta^*$. La procédure est la suivante :

1. Initialisation : Échantillonner uniformément un petit sous-ensemble des données non étiquetées pour obtenir un premier estimateur $\hat{\theta}_1$ à l'aide d'un estimateur M régularisé avec une perte de substitution lissée.
2. Construction de l'ensemble actif : Pour les étapes suivantes $k=2, \dots, K$, définir un « ensemble actif » $S_k$ contenant les points de données $(X, Z)$ où le résidu estimé est faible :
   $$S_k = \left\{ (X, Z) : -b_{k-1} \leq \frac{X - \hat{\theta}_{k-1}^T Z}{\sqrt{1 + \|\hat{\theta}_{k-1}\|_2^2}} \leq b_{k-1} \right\}$$
   où $b_{k-1}$ est un paramètre de réglage contrôlant la largeur de l'intervalle.
3. Échantillonnage actif : Échantillonner des points parmi les données non étiquetées restantes qui tombent dans $S_k$ avec une probabilité proportionnelle au budget alloué à cette étape. Les points en dehors de $S_k$ ne sont pas étiquetés.
4. Estimation : Résoudre un estimateur M régularisé sur les nouvelles données étiquetées pour mettre à jour l'estimateur $\hat{\theta}_k$.
5. Itération : Répéter jusqu'à ce que $K$ étapes soient complétées.

Composantes techniques

• Perte de substitution lissée (Smoothed Surrogate Loss) : Pour traiter l'intraitabilité computationnelle de la perte 0-1 et la non-régularité du problème, les auteurs utilisent une fonction de perte lissée par noyau $L_\delta(u) = \int_{u/\delta}^\infty K(t) dt$, où $K$ est une fonction de noyau et $\delta$ une largeur de bande (bandwidth).
• Régularisation : Une pénalité $\ell_1$ est appliquée pour gérer la haute dimension ($d \gg N$).
• Algorithme de suivi de chemin (Path-Following Algorithm) : Pour résoudre efficacement le problème d'optimisation non convexe, les auteurs emploient un algorithme de suivi de chemin (Feng et al., 2022) qui calcule des solutions locales approximatives.

3. Principales contributions théoriques

Le papier établit une transition de phase nette dans les taux de convergence de l'estimateur proposé en fonction du paramètre de l smoothnes $\beta$ de la densité conditionnelle de $X$ étant donné $Y$ et $Z$.

Taux de convergence

Soit $N$ le budget total de marquage, $s$ la parcimonie et $d$ la dimension. Le taux de convergence dans la norme $\ell_2$ dépend de $\beta$ :

1. Cas $\beta > (1+\sqrt{3})/2 \approx 1,37$ :

   • Un algorithme en deux étapes ($K=2$) suffit pour atteindre le taux paramétrique :
     $$\|\hat{\theta}_K - \theta^*\|_2 = O_p\left(\sqrt{\frac{s \log d}{N}}\right)$$
   • Ce taux est strictement plus rapide que le taux optimal minimax $O_p((s \log d / N)^{\beta/(2\beta+1)})$ atteignable avec $N$ échantillons i.i.d. de la population, démontrant le bénéfice du sous-échantillonnage actif.

2. Cas $1 < \beta \leq (1+\sqrt{3})/2$ :

   • L'algorithme en deux étapes est sous-optimal.
   • Pour récupérer le taux paramétrique, le nombre d'étapes $K$ doit être augmenté pour atteindre une valeur finie fixe : $K = \lceil \log_{\frac{\beta}{2\beta+1}}(1 - \frac{\beta+1}{2\beta^2}) \rceil + 1$.

3. Cas $0 < \beta \leq 1$ :

   • L'estimateur ne peut pas atteindre le taux paramétrique avec un nombre fixe d'étapes.
   • Un taux super-paramétrique est atteint : $O_p((s/N)^{1/(2\beta)})$ (à un facteur logarithmique près).
   • Cela nécessite que le nombre d'étapes $K$ croisse lentement avec $N$ : $K = \lceil \log_{2\beta+1}(\log N) \rceil$.

Optimalité Minimax

Les auteurs formulent un cadre minimax avec budget $N$ où la distribution d'échantillonnage $Q$ est choisie pour minimiser le risque dans le pire des cas. Ils prouvent que la borne inférieure pour le risque minimax est :
$$\inf_{Q} \inf_{\hat{\theta}} \sup_{P} \mathbb{E}_{P,Q} \|\hat{\theta} - \theta^*(P)\|_2 \gtrsim \left(\frac{s \log(d/s)}{N}\right)^{\frac{1}{2(\beta \wedge 1)}}$$
L'estimateur de sous-échantillonnage actif proposé atteint ce taux (à un facteur logarithmique près), prouvant qu'il est optimal au sens de la théorie minimax dans le cadre de la mesure contrainte.

Adaptation

Le papier développe les méthodes de Lepski pour s'adapter à la lissure $\beta$ et à la parcimonie $s$ inconnues, permettant à l'algorithme de sélectionner les paramètres de réglage sans connaissance préalable de ces quantités.

4. Résultats empiriques

• Simulations : La méthode a été testée sur des données synthétiques sous trois modèles : régression logistique, modèles de moyenne conditionnelle et modèles de réponse binaire générale. La méthode de « sous-échantillonnage actif en deux étapes avec suivi de chemin » a systématiquement surpassé le sous-échantillonnage passif (échantillonnage aléatoire uniforme) et la régression logistique standard avec pénalité $\ell_1$, particulièrement en termes d'erreurs d'estimation $\ell_1$ et $\ell_2$.
• Application sur des données réelles : La méthode a été appliquée à un ensemble de données sur le diabète provenant de 130 hôpitaux américains (répertoire UCI) pour prédire la réadmission précoce basée sur les niveaux d'HbA1c. L'approche de sous-échantillonnage actif a identifié des covariables importantes (ex: « temps passé à l'hôpital », « changement de médication ») et a obtenu des erreurs d'estimation plus faibles par rapport à l'échantillonnage passif sous divers budgets de marquage ($N=3000, 4000, 5000$).

5. Signification et revendications

Le papier affirme fournir une solution statistiquement et computationnellement efficace pour estimer des seuils individualisés lorsque le marquage des données est coûteux. Sa principale importance réside dans :

1. Accélération de la convergence : Démontrer que l'échantillonnage actif peut briser la barrière de convergence non-régulière, atteignant des taux paramétriques (ou super-paramétriques) qui sont inaccessibles avec l'échantillonnage passif sous le même budget.
2. Précision théorique : Caractériser les conditions exactes (via le paramètre de lissage $\beta$) sous lesquelles une procédure simple en deux étapes est suffisante par rapport aux schémas itératifs plus complexes requis.
3. Faisabilité pratique : Proposer un algorithme de suivi de chemin basé sur le gradient, qui est calculable pour les données de haute dimension, contrairement à de nombreuses méthodes d'apprentissage actif qui nécessitent de minimiser directement la perte non convexe 0-1.
4. Optimalité : Établir que la méthode proposée est optimale au sens de la théorie minimax, ce qui signifie qu'aucune autre stratégie d'échantillonnage ne peut atteindre un taux de convergence plus rapide dans le pire des scénarios.

Les auteurs soulignent que leur travail comble le fossé entre l'estimation statistique non-régulière et l'apprentissage actif, offrant un cadre rigoureux pour les problèmes de mesure contrainte en haute dimension.