Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features

Resumen Técnico: Compromiso Computacional-Estadístico en la Prueba de Dos Muestras con Núcleos y Características de Fourier Aleatorias

Planteamiento del Problema
El artículo aborda las limitaciones computacionales de la prueba de Discrepancia de la Media Máxima (MMD), un método no paramétrico prominente para la prueba de dos muestras. Si bien la prueba MMD estándar ofrece garantías teóricas sólidas y flexibilidad para datos complejos y de alta dimensión, su dependencia de una complejidad cuadrática en el tiempo ($O(N^2)$) obstaculiza su escalabilidad. Se han propuesto diversos métodos de aproximación, como las Características de Fourier Aleatorias (RFF), para reducir los costos computacionales a un tiempo subcuadrático o lineal. Sin embargo, persiste una brecha crítica en la comprensión teórica del compromiso entre la eficiencia computacional y el poder estadístico en las pruebas MMD basadas en RFF. Específicamente, no está claro si una prueba RFF-MMD puede alcanzar las mismas tasas de separación minimax que la prueba MMD completa de tiempo cuadrático sin incurrir en costos computacionales cuadráticos, y bajo qué condiciones el número de características aleatorias ($R$) debe escalar con el tamaño de la muestra ($N$).

Metodología
Los autores investigan la prueba RFF-MMD dentro de un marco de prueba de permutación. La metodología implica:

1. Análisis Teórico de la Consistencia: El artículo analiza primero la consistencia puntual de la prueba RFF-MMD cuando el número de características aleatorias $R$ es fijo. Al examinar la distribución límite de la estadística de prueba y su contraparte de permutación, los autores derivan las condiciones bajo las cuales la prueba falla en distinguir entre distribuciones distintas.
2. Marco Minimax: Para evaluar rigurosamente el compromiso tiempo-poder, los autores adoptan un marco de prueba minimax no asintótico. Analizan las tasas de separación uniforme de la prueba RFF-MMD frente a dos clases específicas de alternativas:
   • Métrica $L_2$: Distribuciones dentro de una bola de Sobolev (densidades suaves).
   • Métrica MMD: Pares de distribuciones generales separadas por la distancia MMD.
3. Descomposición de la Aleatoriedad: Un aspecto técnico clave del análisis es la descomposición sistemática de tres fuentes distintas de aleatoriedad: las muestras de datos, las características de Fourier aleatorias y las permutaciones utilizadas para determinar los valores críticos. Los autores gestionan la interacción de estas fuentes para derivar límites precisos sobre el poder estadístico y la complejidad computacional.
4. Suposiciones Distributivas Específicas: El artículo explora subclases específicas de distribuciones, particularmente distribuciones gaussianas con una covarianza común, para determinar si es posible obtener límites más ajustados sobre el número de características.

Contribuciones y Resultados Clave

• Inconsistencia con Características Fijas: El artículo establece un resultado negativo: una prueba RFF-MMD con un número fijo de características aleatorias $R$ no es puntualmente consistente. Los autores demuestran que existen infinitas parejas de distribuciones distintas para las cuales el poder de la prueba converge al nivel de significancia $\alpha$ (es decir, falla en detectar la alternativa) incluso cuando el tamaño de la muestra $N \to \infty$. Esto ocurre porque un conjunto finito de frecuencias aleatorias puede no capturar las diferencias entre funciones características específicas.
• Suficiencia de Caracteridades Divergentes: Por el contrario, el artículo demuestra que la consistencia puntual se logra si el número de características aleatorias $R$ tiende a infinito a medida que aumenta el tamaño de la muestra, independientemente de la tasa de divergencia.
• Compromiso Óptimo para Alternativas $L_2$: Bajo la suposición de que las distribuciones subyacentes pertenecen a una bola de Sobolev de suavidad $s$ en dimensión $d$, los autores derivan la elección óptima para $R$. Demuestran que si $R \gtrsim n^{2d/(4s+d)}$ (donde $n = \min\{n_1, n_2\}$), la prueba RFF-MMD alcanza la tasa de separación minimax de $n^{-2s/(4s+d)}$. Crucialmente, cuando las distribuciones son suficientemente suaves ($s > d/4$), esta tasa óptima es alcanzable en tiempo subcuadrático.
• Compromiso Óptimo para Alternativas MMD: Para probar frente a alternativas separadas por la métrica MMD, el requisito estándar para igualar la tasa minimax ($n^{-1/2}$) es $R \asymp N$, lo que resulta en un costo computacional de $O(N^2)$ (tiempo cuadrático). Sin embargo, los autores identifican una subclase específica de distribuciones —pares de distribuciones gaussianas con una covarianza fija común— donde la relación entre la estadística de prueba esperada y el MMD poblacional permite un límite más ajustado. Para esta clase, la tasa de separación minimax puede alcanzarse con un número fijo de características aleatorias ($R = O(1)$), resultando en complejidad de tiempo lineal ($O(Nd)$).

Significado y Afirmaciones
El artículo afirma llenar una brecha teórica sobre el compromiso computacional-estadístico en la prueba de dos muestras con núcleos. Su significado principal radica en proporcionar condiciones rigurosas bajo las cuales las pruebas RFF-MMD pueden igualar el poder estadístico de la prueba MMD completa de tiempo cuadrático mientras operan en tiempo subcuadrático o incluso lineal.

Los autores enfatizan que sus hallazgos no son meramente asintóticos, sino que proporcionan garantías no asintóticas dentro de un marco minimax. Demuestran que el "costo" de utilizar características aleatorias no es una pérdida universal de poder, sino más bien una dependencia de la suavidad de las distribuciones subyacentes y de la métrica específica de interés. Los resultados sugieren que para distribuciones suficientemente suaves o clases paramétricas específicas (como las gaussianas), se puede evitar el cuello de botella cuadrático de las pruebas MMD estándar sin sacrificar la optimalidad estadística.

Los hallazgos teóricos se corroboran mediante estudios de simulación en diversos escenarios, incluyendo gaussianas univariadas y de alta dimensión, distribuciones uniformes perturbadas y datos de imágenes MNIST. Estos experimentos confirman que el poder empírico de la prueba RFF-MMD converge al de la prueba MMD estándar a medida que $R$ aumenta, y que el $R$ requerido para lograr un poder comparable depende de la complejidad de la distribución subyacente.

El artículo concluye señalando que, si bien los resultados para distribuciones gaussianas son técnicamente manejables, la evidencia empírica sugiere que podrían existir ganancias similares para clases más amplias, dejando la exploración de estas clases como una dirección para trabajos futuros. Los autores también destacan el desafío de extender estos resultados a distribuciones con soportes no acotados.