Improved Distribution Estimation in $\ell_\infty$

Resumen Técnico: Mejora en la Estimación de Distribuciones en $\ell_\infty$

Planteamiento del Problema
El artículo aborda el problema clásico de estimar una distribución de probabilidad discreta desconocida $p$ sobre un alfabeto contable a partir de $n$ muestras independientes e idénticamente distribuidas (i.i.d.). Mientras que existe una extensa teoría para las pérdidas $\ell_1$ y $\ell_2$, los autores se centran en la pérdida $\ell_\infty$ (norma infinito), definida como $\|\hat{p} - p\|_\infty = \sup_{i \ge 1} |\hat{p}_i - p_i|$. Esta métrica es crítica en aplicaciones modernas como la calibración uniforme, la detección de anomalías y las pruebas de bondad de ajuste, donde la mayor discrepancia coordenada a coordenada desencadena una respuesta.

El desafío central es que, si bien una decaimiento de riesgo uniforme de $O(1/\sqrt{n})$ se mantiene para todas las distribuciones discretas, obtener tasas dependientes de la distribución que sean agudas y límites totalmente empíricos (aquellos que no requieren el conocimiento de funcionales desconocidos de $p$) sigue siendo difícil. La dificultad está gobernada no meramente por el tamaño del soporte, sino por el perfil de cola desconocido de $p$. Este trabajo construye sobre y extiende el estudio no asintótico iniciado por Kontorovich y Painsky (2025), abordando específicamente preguntas abiertas relativas a los límites de confianza totalmente empíricos y la identificación de la distribución de peor caso (la menos favorable).

Metodología y Marco de Trabajo
Los autores analizan el Estimador de Máxima Verosimilitud (MLE), denotado como $\hat{p}$, donde $\hat{p}_i$ es la frecuencia empírica del símbolo $i$. El análisis se apoya en dos marcos teóricos primarios:

1. Proxies de Complejidad: El trabajo utiliza medidas de complejidad dependientes de la distribución introducidas por Kontorovich y Painsky (2025), específicamente $v^*(p) = \sup_i p_i(1-p_i)$ y $V^*(p) = \sup_i p^\downarrow_i(1-p^\downarrow_i)\log(i+1)$, donde $p^\downarrow$ es la permutación no creciente de $p$.
2. Teoría de Glivenko–Cantelli Local (LGC): Para refinar la comprensión del comportamiento dependiente de la distribución, el artículo incorpora límites de Glivenko–Cantelli locales agudos. Esto implica el análisis de dos nuevos funcionales, $S(p)$ y $M(p)$, que capturan diferentes aspectos del comportamiento de la cola y la estructura de la varianza.
3. Desacoplamiento y Reducción: Para el análisis minimax, los autores reducen el modelo de muestreo multinomial dependiente a un modelo Bernoulli independiente utilizando desigualdades de desacoplamiento, lo que permite la aplicación de caracterizaciones agudas disponibles para variables independientes (Blanchard y Voráček, 2024).
4. Plug-ins Empíricos: Para lograr límites de confianza totalmente empíricos, los autores reemplazan los funcionales poblacionales desconocidos con sus contrapartes empíricas (por ejemplo, $\hat{v}^*$ y $\hat{V}^*$) y utilizan desigualdades de concentración para acotar la desviación entre el funcional empírico y el verdadero.

Contribuciones Clave y Resultados

• Tasa Minimax y Distribución Menos Favorable:
  El artículo resuelve la estructura del riesgo esperado de $\ell_\infty$ en el peor de los casos. Establece que la tasa minimax escala como $\Theta(n^{-1/2})$. Crucialmente, identifica una distribución simple y fija, la menos favorable, $p^\star = (1/2, 1/2, 0, \dots)$, que alcanza este riesgo de peor caso salvo por constantes universales. Este resultado responde a una pregunta abierta al demostrar que el caso más difícil para la estimación $\ell_\infty$ existe en un alfabeto de dos puntos y no requiere un tamaño de soporte efectivo dependiente de $n$.

• Límite de Alta Probabilidad Totalmente Empírico:
  Los autores derivan una desigualdad de desviación de alta probabilidad para $\|\hat{p} - p\|_\infty$ que es totalmente empírica. El límite depende únicamente de estadísticas de plug-in observables ($\hat{v}^*$ y $\hat{V}^*$) y no requiere el conocimiento de los funcionales desconocidos $v^*(p)$ o $V^*(p)$. El límite se adapta automáticamente al perfil de cola desconocido de $p$ mientras retiene el comportamiento $\sqrt{\log(1/\delta)/n}$ en el peor de los casos.

• Régimen Refinado Dependiente de la Distribución:
  Utilizando funcionales LGC, el artículo proporciona una visión más granular del error de estimación. Introduce $S(p) = \sup_j p^\downarrow_j \log(j+1)$ y $M(p) = \sup_j \frac{\log(j+1)}{\log(2 + \frac{\log(j+1)}{n p^\downarrow_j})}$.

  • $S(p)$ representa la parte "sub-Gaussiana" del error, que domina cuando un bloque de coordenadas posee suficiente masa para que las fluctuaciones de la varianza sean la fuente principal de error.
  • $M(p)$ representa la parte "sub-Gamma" o de Poisson, capturando el impacto de muchos símbolos de baja probabilidad visibles al tamaño de muestra $n$.
    El artículo demuestra que el error de estimación está gobernado por el máximo de estos dos términos (escalados por $1/n$), ilustrando tres regímenes cualitativamente diferentes: dominación de la varianza, dominación de la cola y perfiles altamente dispersos donde ambos mecanismos producen errores pequeños.

• Límites Inferiores:
  El artículo proporciona un límite inferior minimax bajo una restricción en $V^*(p)$, mostrando que para cualquier estimador, existe una distribución con $V^*(p) \le V'$ tal que el error esperado es al menos $c\sqrt{V'/n}$.

Significación y Reivindicaciones
El artículo afirma refinar y extender la teoría existente de la estimación de distribuciones en $\ell_\infty$ en tres direcciones específicas:

1. Resolución Teórica: Resuelve la cuestión de la distribución menos favorable, demostrando que es una distribución de dos puntos simple, independiente de $n$, en lugar de una estructura compleja dependiente de $n$.
2. Aplicabilidad Práctica: Al proporcionar un límite de confianza totalmente empírico, el trabajo permite la construcción de garantías dependientes de los datos sin requerir conocimiento previo del perfil de cola de la distribución.
3. Comprensión Matizada: La introducción de los funcionales $S(p)$ y $M(p)$ ofrece una "imagen de regímenes" que explica cuándo y por qué diferentes comportamientos de cola dominan el error de estimación, yendo más allá de las tasas minimax globales para capturar la interacción entre la varianza y el decaimiento de la cola.

Los autores reportan resultados empíricos alentadores que demuestran que estos límites son informativos en muestras finitas, aunque la contribución principal sigue siendo el refinamiento teórico de los límites y la identificación de las distribuciones extremas.