Realizable Bayes-Consistency for General Metric Losses

Resumen Técnico: Consistencia Bayesiana Realizable para Pérdidas Métricas Generales

1. Planteamiento del Problema

Este artículo aborda el problema de la consistencia bayesiana universal fuerte en el escenario realizable para el aprendizaje con pérdidas métricas generales. El escenario implica:

• Un espacio de instancias $(X, \rho)$ y un espacio de etiquetas $(Y, \ell)$, donde $\ell$ es una métrica que puede ser no acotada.
• Una clase de hipótesis $\mathcal{H} \subseteq Y^X$.
• Una distribución generadora de datos $\bar{\mu}$ sobre $X \times Y$ que es realizable por $\mathcal{H}$, lo que significa que el riesgo óptimo es cero ($\inf_{h \in \mathcal{H}} R_{\bar{\mu}}(h) = 0$).

El objetivo es determinar las condiciones necesarias y suficientes sobre $\mathcal{H}$ tales que exista una regla de aprendizaje libre de distribuciones cuyo riesgo converja a cero casi seguramente para cada distribución realizable $\bar{\mu}$.

Los autores destacan una distinción crítica entre pérdidas acotadas y no acotadas. En entornos acotados, controlar la probabilidad de error es sinónimo de controlar el riesgo. En entornos métricos no acotados, un aprendiz puede cometer errores en eventos con probabilidad decreciente, sin embargo, la magnitud de estos errores puede crecer tan rápidamente que el riesgo esperado permanece infinito o falla en converger a cero. El artículo busca caracterizar cuándo tales "fallos catastróficos por eventos raros" son evitables.

2. Metodología y Marco Teórico

El artículo emplea un enfoque combinatorio arraigado en la teoría de juegos infinitos y obstrucciones de árboles, extendiendo marcos previamente desarrollados para la clasificación 0-1 y la regresión acotada.

Definiciones Clave:

• Árbol de Littlestone $(\gamma_k)$ Infinito No Decreciente: Un árbol binario completo donde los nodos internos en la profundidad $k$ son instancias $x_{k,i}$, y las aristas salientes están etiquetadas con $y_{k,i,1}, y_{k,i,2} \in Y$ tales que la distancia métrica $\ell(y_{k,i,1}, y_{k,i,2}) \ge \gamma_k$. La secuencia $(\gamma_k)$ es no decreciente y diverge hacia infinito ($\gamma_k \to \infty$). El árbol es "realizable" si cada camino finito de raíz a hoja es consistente con alguna hipótesis en $\mathcal{H}$.
• Supuesto de Realizabilidad: Los autores asumen una condición de "parametrización compacta" (Lema 4.3): $\mathcal{H}$ está parametrizado por un espacio compacto $\Theta$ con un mapa de evaluación continuo. Bajo este supuesto leve, la realizabilidad de prefijos finitos implica que cada camino infinito es realizado por una única hipótesis.

Arquitectura de la Prueba:
El resultado principal se establece mediante una cota inferior (necesidad) y una cota superior (suficiencia).

• Cota Inferior (Imposibilidad): Si $\mathcal{H}$ contiene un árbol de Littlestone $(\gamma_k)$ infinito no decreciente, los autores construyen una distribución realizable donde el adversario oculta una secuencia de elecciones de etiquetas cada vez más separadas detrás de masas de probabilidad que decaen rápidamente. Utilizando un argumento de Borel-Cantelli, muestran que para cualquier algoritmo de aprendizaje, el riesgo esperado es infinito para cada tamaño de muestra $n$. El aprendiz se ve forzado a adivinar entre etiquetas separadas por $\gamma_k$ en nodos no vistos, lo que conduce a un riesgo divergente.
• Cota Superior (Algoritmo Constructivo): Si no existe tal árbol, los autores construyen una regla de aprendizaje libre de distribuciones. La prueba procede en cuatro pasos:
  1. Codificación Teórico-Jueguera: La ausencia de la obstrucción del árbol implica que el aprendiz tiene una estrategia ganadora en un juego infinito específico de Gale-Stewart contra un adversario.
  2. Estabilización: Al simular este juego en una muestra i.i.d., el proceso se estabiliza casi seguramente después de un número finito de rondas. Esto produce, para cada $x$, un conjunto de etiquetas "admisibles" $H_K(x)$ con diámetro acotado.
  3. Particionamiento: El espacio de instancias $X$ se particiona en celdas numerables basadas en un subconjunto denso de $Y$. Dentro de cada celda, el conjunto de etiquetas admisibles tiene un diámetro acotado.
  4. Reducción: El problema se reduce a un número numerable de subproblemas con pérdidas acotadas. Los autores aplican el algoritmo existente MedNet (Tsir Cohen & Kontorovich, 2022), que es fuertemente universalmente consistente de Bayes para pérdidas métricas acotadas, a cada celda y agregan los resultados.

3. Contribuciones Clave

1. Caracterización Precisa: El artículo proporciona una condición necesaria y suficiente para la consistencia bayesiana universal fuerte realizable bajo pérdidas métricas generales (posiblemente no acotadas). La condición es la no existencia de un árbol de Littlestone $(\gamma_k)$ infinito no decreciente en la clase de hipótesis.
2. Resolución de un Problema Abierto: Este trabajo resuelve el caso realizable de un problema abierto planteado por Tsir Cohen & Kontorovich (2022). Demuestra que condiciones naturales de tipo finitud, como la finitud del riesgo de Bayes ($R^* < \infty$) o la condición "acotada-en-expectativa" (BIE) en el espacio de etiquetas, son insuficientes para garantizar la consistencia en el escenario no acotado.
3. Regla de Aprendizaje Constructiva: En ausencia de la obstrucción del árbol, el artículo presenta una regla de aprendizaje explícita (basada en el algoritmo MedNet y la estabilización teórico-jueguera) que logra la consistencia bayesiana universal fuerte.
4. Construcción de Contraejemplo: Los autores proporcionan un contraejemplo concreto (Sección 3) que muestra que incluso cuando $R^* < \infty$, no existe un aprendiz consistente libre de distribuciones si la clase de hipótesis admite la estructura específica de árbol con brecha no acotada.

4. Resultados y Significado

El teorema central (Teorema 4.5) establece que para espacios de Polish $(X, \rho)$ y $(Y, \ell)$ y una clase de hipótesis $\mathcal{H}$ que satisface condiciones leves de medibilidad y compacidad, son equivalentes:

1. Existe una regla de aprendizaje libre de distribuciones que es fuertemente universalmente consistente de Bayes para cada distribución realizable.
2. $\mathcal{H}$ no contiene un árbol de Littlestone $(\gamma_k)$ infinito no decreciente con $\gamma_k \to \infty$.

Significado:
El artículo aclara que la dificultad del aprendizaje con pérdidas métricas no acotadas no es meramente una cuestión de integrabilidad o condiciones de momentos sobre la distribución. En cambio, la obstrucción es combinatoria e intrínseca a la clase de hipótesis. La escala de la ambigüedad (la brecha entre etiquetas) puede crecer sin límite a lo largo de la profundidad de un árbol, creando un escenario donde eventos raros dominan el riesgo. Esto extiende el marco clásico del árbol de Littlestone (utilizado para pérdida 0-1) y los árboles de Littlestone escalados (utilizados para regresión acotada) al escenario métrico general no acotado, señalando la interacción precisa entre las magnitudes de pérdida no acotadas y la realizabilidad.

Los autores señalan que extender esta caracterización al escenario agnóstico (donde la distribución no es necesariamente realizable) sigue siendo una dirección abierta, citando las barreras discutidas en su Apéndice.