Memory Constrained Adversarial Hypothesis Testing

Resumen Técnico: Prueba de Hipótesis Adversaria con Restricciones de Memoria

Enunciado del Problema
Este trabajo investiga la prueba de hipótesis binaria bajo dos restricciones simultáneas: limitaciones de memoria y generación de muestras adversarias. El detector se modela como una máquina de estados finitos (FSM) aleatorizada e invariante en el tiempo con un espacio de estados finito $S$. A diferencia de los escenarios clásicos donde las muestras son independientes e idénticamente distribuidas (i.i.d.) de una distribución fija, este problema considera un escenario de hipótesis compuesta donde las distribuciones subyacentes pertenecen a conjuntos convexos cerrados $\mathcal{P}_0$ y $\mathcal{P}_1$.

Crucialmente, el escenario es adversario. Un adversario, conociendo la hipótesis verdadera ($H=0$ o $H=1$), selecciona la distribución para cada muestra $X_n$ desde el conjunto correspondiente ($\mathcal{P}_0$ o $\mathcal{P}_1$). La elección del adversario es dinámica, dependiendo del historial de muestras pasadas y de todo el historial de los estados internos del detector. El objetivo es minimizar la probabilidad asintótica promedio de error, definida como el error en el peor caso sobre todas las estrategias adversarias posibles, como función del número de estados $S$.

Metodología y Enfoque
Los autores se basan en el trabajo fundacional de Hellman y Cover, quienes estudiaron la prueba de hipótesis con restricciones de memoria para hipótesis simples (distribuciones únicas). Mientras que Hellman y Cover utilizaron una FSM de "contador saturable" que transita basándose en letras específicas que maximizan la relación de verosimilitud, este artículo generaliza el enfoque para manejar escenarios compuestos y adversarios.

1. Diseño Generalizado de FSM: En lugar de depender de letras fijas $x^+$ y $x^-$ que proporcionan la evidencia más fuerte para una hipótesis sobre la otra (lo cual puede no existir o ser consistente en un escenario adversario), la FSM propuesta utiliza funciones no negativas $f_+$ y $f_-$ definidas sobre el alfabeto $\mathcal{X}$. Las probabilidades de transición desde el estado $s$ a $s+1$ o $s-1$ están determinadas por $f_+(x)$ y $f_-(x)$ respectivamente, sujetas a $f_+(x) + f_-(x) \leq 1$.
2. Análisis de Martingalas: El análisis estándar de FSMs a menudo se basa en distribuciones estacionarias. Sin embargo, la presencia de un adversario adaptativo puede romper la ergodicidad, haciendo inválido el análisis de distribuciones estacionarias. Para superar esto, los autores emplean un análisis basado en martingalas. Construyen submartingalas y supermartingalas específicas (ajustando los conteos brutos de estados con una función potencial $V(s)$) para acotar el tiempo que la FSM pasa en estados de frontera (que determinan la decisión) versus estados internos.
3. Optimización Minimax: Los límites de rendimiento se derivan optimizando sobre la elección de las funciones $f_+$ y $f_-$. Los autores definen un exponente generalizado $\gamma$ que involucra un supremo sobre estas funciones y un mínimo sobre las distribuciones adversarias.

Contribuciones y Resultados Clave
El artículo establece límites superiores e inferiores ajustados para la probabilidad asintótica minimax de error $P^*_e(S)$ para un número dado de estados $S$.

• Límites de Error: Los autores prueban que:
  $$P^*_e(S) \geq \frac{1}{1 + \sqrt{\gamma}^{S-1}}$$
  $$P^*_e(S) \leq \frac{1}{1 + \sqrt{C\gamma^{S-2}}}$$
  donde $\gamma$ y $C$ son constantes derivadas de los conjuntos $\mathcal{P}_0$ y $\mathcal{P}_1$ mediante una optimización minimax sobre las funciones $f_+, f_-$.
• Comportamiento Exponencial: Ambos límites exhiben el mismo comportamiento exponencial en $S$. En consecuencia, el exponente de error $\Gamma$ se caracteriza exactamente como:
  $$\Gamma = \frac{1}{2} \log \gamma$$
• Distribuciones Menos Favorables Débiles (LFD): El artículo introduce el concepto de un "par LFD débil" $(p^*, q^*)$. Si tal par existe, el exponente de error se simplifica al exponente de Hellman-Cover calculado sobre estas distribuciones específicas: $\gamma = \gamma_{HC}(p^*, q^*)$. Esto generaliza el resultado clásico de que el error en el peor caso en la prueba compuesta está determinado por las distribuciones "menos favorables".
• Optimalidad de Funciones No Indicadoras: A través de un ejemplo específico, los autores demuestran que las funciones óptimas $f_+$ y $f_-$ no son necesariamente funciones indicadoras (lo cual correspondería a seleccionar letras específicas). En algunos casos, combinaciones lineales de letras (representadas por funciones no binarias) producen un exponente de error estrictamente mejor que cualquier estrategia restringida a subconjuntos fijos del alfabeto.
• Aplicación del Teorema Minimax: Una contribución técnica significativa es la prueba de que el orden de minimización (sobre distribuciones) y maximización (sobre funciones) puede intercambiarse en la definición de $\gamma$, a pesar de que la función no sea conjuntamente cuasi-convexa/concava en el sentido estándar. Esto se logra descomponiendo el problema y aplicando iterativamente el teorema minimax de Sion.

Significado
El artículo proporciona una caracterización rigurosa de los límites fundamentales de la inferencia estadística cuando tanto la memoria está restringida como la fuente de datos es activamente adversaria. Extiende el marco clásico de Hellman-Cover a un escenario más robusto y realista donde las distribuciones son desconocidas y potencialmente manipuladas. El trabajo destaca que en entornos adversarios, las decisiones "duras" simples basadas en símbolos individuales son subóptimas; en su lugar, son necesarias transiciones aleatorizadas basadas en combinaciones ponderadas de observaciones para lograr el exponente de error óptimo. Los resultados ofrecen una comprensión precisa de cómo el número de estados de memoria $S$ escala con la dificultad del problema de prueba de hipótesis bajo condiciones de peor caso.