Improved Distribution Estimation in $\ell_\infty$

Résumé Technique : Amélioration de l'Estimation de Distribution en $\ell_\infty$

Énoncé du Problème
Le papier traite le problème classique de l'estimation d'une distribution de probabilité discrète inconnue $p$ sur un alphabet dénombrable à partir de $n$ échantillons indépendants et identiquement distribués (i.i.d.). Bien qu'une théorie étendue existe pour les pertes $\ell_1$ et $\ell_2$, les auteurs se concentrent sur la perte $\ell_\infty$ (norme de la supréme) , définie par $\|\hat{p} - p\|_\infty = \sup_{i \ge 1} |\hat{p}_i - p_i|$. Cette métrique est critique dans des applications modernes telles que le calibrage uniforme, la détection d'anomalies et les tests d'adéquation, où la plus grande divergence coordonnée déclenche une réponse.

Le défi central est que, bien qu'une décroissance du risque uniforme en $O(1/\sqrt{n})$ soit valable pour toutes les distributions discrètes, l'obtention de taux dépendants de la distribution qui soient nets et de bornes entièrement empiriques (celles ne nécessitant pas la connaissance de fonctionnels inconnus de $p$) reste difficile. La difficulté est régie non seulement par la taille du support, mais aussi par le profil de queue inconnu de $p$. Ce travail s'appuie sur et étend l'étude non asymptotique initiée par Kontorovich et Painsky (2025), en abordant spécifiquement les questions ouvertes concernant les bornes de confiance entièrement empiriques et l'identification de la distribution la plus défavorable (la moins favorable).

Méthodologie et Cadre
Les auteurs analysent l'Estimateur du Maximum de Vraisemblance (EMV), noté $\hat{p}$, où $\hat{p}_i$ est la fréquence empirique du symbole $i$. L'analyse repose sur deux cadres théoriques principaux :

1. Proxys de Complexité : Le travail utilise des mesures de complexité dépendantes de la distribution introduites par Kontorovich et Painsky (2025), spécifiquement $v^*(p) = \sup_i p_i(1-p_i)$ et $V^*(p) = \sup_i p^\downarrow_i(1-p^\downarrow_i)\log(i+1)$, où $p^\downarrow$ est la permutation décroissante de $p$.
2. Théorie de Glivenko–Cantelli Locale (LGC) : Pour affiner la compréhension du comportement dépendant de la distribution, le papier incorpore des bornes de Glivenko–Cantelli locales plus précises. Cela implique l'analyse de deux nouveaux fonctionnels, $S(p)$ et $M(p)$, qui capturent différents aspects du comportement de la queue et de la structure de la variance.
3. Découplage et Réduction : Pour l'analyse minimax, les auteurs réduisent le modèle d'échantillonnage multinomial dépendant à un modèle de Bernoulli indépendant en utilisant des inégalités de découplage, permettant l'application des caractérisations précises disponibles pour les variables indépendantes (Blanchard et Voráček, 2024).
4. Plug-ins Empiriques : Pour obtenir des bornes entièrement empiriques, les auteurs remplacent les fonctionnels de population inconnus par leurs équivalents empiriques (par exemple, $\hat{v}^*$ et $\hat{V}^*$) et utilisent des inégalités de concentration pour borner l'écart entre les fonctionnels empiriques et réels.

Contributions Clés et Résultats

• Taux Minimax et Distribution la Moins Favorable :
  Le papier résout la structure du risque $\ell_\infty$ attendu dans le pire des cas. Il établit que le taux minimax évolue en $\Theta(n^{-1/2})$. De manière cruciale, il identifie une distribution simple et fixe, la moins favorable, $p^\star = (1/2, 1/2, 0, \dots)$, qui atteint ce risque maximal à des constantes universelles près. Ce résultat répond à une question ouverte en démontrant que l'instance la plus difficile pour l'estimation $\ell_\infty$ existe sur un alphabet à deux points et ne nécessite pas une taille de support effectif dépendant de $n$.

• Borne de Haute Probabilité Entièrement Empirique :
  Les auteurs dérivent une inégalité de déviation à haute probabilité pour $\|\hat{p} - p\|_\infty$ qui est entièrement empirique. La borne dépend uniquement de statistiques de plug-in observables ($\hat{v}^*$ et $\hat{V}^*$) et ne nécessite pas la connaissance des fonctionnels inconnus $v^*(p)$ ou $V^*(p)$. La borne s'adapte automatiquement au profil de queue inconnu de $p$ tout en conservant le comportement $\sqrt{\log(1/\delta)/n}$ dans le pire des cas.

• Régime Affiné Dépendant de la Distribution :
  En utilisant les fonctionnels LGC, le papier fournit une vue plus granulaire de l'erreur d'estimation. Il introduit $S(p) = \sup_j p^\downarrow_j \log(j+1)$ et $M(p) = \sup_j \frac{\log(j+1)}{\log(2 + \frac{\log(j+1)}{n p^\downarrow_j})}$.

  • $S(p)$ représente la partie « sub-gaussienne » de l'erreur, dominant lorsque un bloc de coordonnées porte une masse suffisante pour que les fluctuations de variance soient la source primaire d'erreur.
  • $M(p)$ représente la partie « sub-gamma » ou poissonnienne, capturant l'impact de nombreux symboles à faible probabilité visibles à la taille d'échantillon $n$.
    Le papier prouve que l'erreur d'estimation est gouvernée par le maximum de ces deux termes (mis à l'échelle par $1/n$), illustrant trois régimes qualitativement différents : domination de la variance, domination de la queue, et profils très dispersés où les deux mécanismes produisent de petites erreurs.

• Bornes Inférieures :
  Le papier fournit une borne inférieure minimax sous une contrainte sur $V^*(p)$, montant que pour tout estimateur, il existe une distribution avec $V^*(p) \le V'$ telle que l'erreur attendue est au moins de $c\sqrt{V'/n}$.

Signification et Revendications
Le papier affirme affiner et étendre la théorie existante de l'estimation de distribution en $\ell_\infty$ dans trois directions spécifiques :

1. Résolution Théorique : Il règle la question de la distribution la moins favorable, montrant qu'elle est une simple distribution à deux points indépendante de $n$, plutôt qu'une structure complexe dépendant de $n$.
2. Applicabilité Pratique : En fournissant une borne de confiance entièrement empirique, ce travail permet la construction de garanties dépendantes des données sans nécessiter la connaissance préalable du profil de queue de la distribution.
3. Compréhension Nuancée : L'introduction des fonctionnels $S(p)$ et $M(p)$ offre une « image de régime » qui explique quand et pourquoi différents comportements de queue dominent l'erreur d'estimation, allant au-delà des taux minimax globaux pour capturer l'interaction entre la variance et la décroissance de la queue.

Les auteurs rapportent des résultats empiriques encourageants démontrant que ces bornes sont informatives dans des échantillons finis, bien que la principale contribution demeure le raffinement théorique des bornes et l'identification des distributions extrémales.