Finite-Sample Inference for Sparsely Permuted Linear Regression

Resumen Técnico: Inferencia de Muestra Finita para la Regresión Lineal Permutada de Forma Dispersa

Planteamiento del Problema
El artículo aborda el problema de la inferencia estadística en la regresión lineal donde la correspondencia entre las covariables y las respuestas se ve alterada por una permutación desconocida. Específicamente, los autores consideran el modelo:
$$Y_{\text{obs}} = \Pi_0 X \beta_0 + \sigma_0 u_{\text{rel}}$$
donde $Y_{\text{obs}} \in \mathbb{R}^n$ es el vector de respuesta observado, $X \in \mathbb{R}^{n \times p}$ es una matriz de diseño determinista, $\beta_0 \in \mathbb{R}^p$ es el vector de coeficientes desconocido, y $\Pi_0$ es una matriz de permutación desconocida de $n \times n$. El ruido $u_{\text{rel}}$ sigue una distribución normal estándar.

El enfoque se centra en el régimen de permutación dispersa (sparsely permuted), donde el número de desajustes (la distancia de Hamming entre $\Pi_0$ e la matriz identidad $I_n$) está acotado por un entero pequeño $k$ (es decir, $d(\Pi_0, I_n) \leq k$). El artículo tiene como objetivo resolver dos objetivos inferenciales primarios en un entorno de muestra finita:

1. Prueba de Hipótesis: Determinar si existe algún desajuste (probar $H_0: \Pi_0 \in \mathcal{P}_{n, k_0}$ frente a $H_1: \Pi_0 \in \mathcal{P}_{n, k} \setminus \mathcal{P}_{n, k_0}$).
2. Conjuntos de Confianza: Construir conjuntos de confianza válidos para los coeficientes de regresión $\beta_0$ que den cuenta de la incertidumbre en la estimación de $\Pi_0$.

Metodología
El marco propuesto se basa en el método de muestras de repro (repro samples method) combinado con un paso de localización para manejar la complejidad combinatoria del espacio de permutaciones $\mathcal{P}_{n,k}$, el cual crece factorialmente con $n$.

1. Localización mediante Muestras de Repro:
   En lugar de buscar en todo el espacio de permutaciones, los autores generan un conjunto de candidatos dependiente de los datos $\mathcal{C}(L) \subset \mathcal{P}_{n,k}$. Esto se logra generando $L$ vectores de ruido artificial $u^*_1, \dots, u^*_L \sim N(0, I_n)$ y resolviendo un problema de optimización para cada uno:
   $$\hat{\Pi}_\ell = \arg\min_{\Pi \in \mathcal{P}_{n,k}} \|(I_n - M(\Pi X, u^*_\ell))Y_{\text{obs}}\|_2^2$$
   donde $M(\cdot)$ denota la matriz de proyección ortogonal. El conjunto de candidatos se define como $\mathcal{C}(L) = \{\hat{\Pi}_1, \dots, \hat{\Pi}_L\}$. Los resultados teóricos muestran que, si $L$ es suficientemente grande, $\mathcal{C}(L)$ contiene a la verdadera $\Pi_0$ con alta probabilidad, y la probabilidad de exclusión decae polinómicamente con $L$.

2. Sustituto Computacional (LAP ponderado por puntuación):
   Resolver el objetivo de mínimos cuadrados sobre permutaciones es computacionalmente intratable. Los autores proponen un Problema de Asignación Lineal (LAP) ponderado por puntuación como un sustituto. La matriz de costos $\Omega$ se construye para penalizar las asignaciones fuera de la diagonal y recompensar las coincidencias en la diagonal, incorporando un término que induce dispersión. Este problema sustituto se resuelve exactamente en tiempo $O(n^3)$ utilizando el algoritmo húngaro. El artículo demuestra que, bajo condiciones específicas de muestra finita, la solución de este LAP coincide con el minimizador global del objetivo original de mínimos cuadrados con alta probabilidad.

3. Procedimientos de Inferencia de Muestra Finita:

   • Prueba de Permutación: Se desarrolla una prueba de Monte Carlo condicional para probar la dispersión de la permutación. El estadístico de prueba $D(Y)$ mide la distancia de Hamming entre la mejor permutación ajustada en $\mathcal{C}(L)$ y la identidad. El valor crítico se calibra uniformemente sobre el conjunto nulo localizado $\hat{\mathcal{P}}_{n, k_0} = \mathcal{C}(L) \cap \mathcal{P}_{n, k_0}$ utilizando distribuciones condicionales que eliminan los parámetros molestos ($\beta, \sigma$).
   • Inferencia de Coeficientes: Los conjuntos de confianza para $\beta_0$ se construyen tomando la unión de las regiones de confianza basadas en el estadístico $F$ sobre todas las $\Pi \in \mathcal{C}(L)$. Este enfoque de "simultaneidad local" asegura una cobertura válida incluso cuando la alineación verdadera es incierta, siempre que la verdadera $\Pi_0$ se encuentre dentro de $\mathcal{C}(L)$.

Contribuciones Clave

• Garantías Teóricas: El artículo proporciona garantías no asintóticas para todos los componentes del marco.
  • Teorema 4.1: Establece que la probabilidad de falta de cobertura del conjunto de candidatos $\mathcal{C}(L)$ decae polinómicamente con el número de muestras de repro $L$.
  • Teorema 4.3: Demuestra que la prueba propuesta controla el error de Tipo I al nivel $\alpha$ en muestras finitas, condicionado al evento de localización.
  • Teorema 4.4: Demuestra que el conjunto de confianza basado en la unión para $\beta_0$ logra la cobertura nominal hasta un término de error evanescente relacionado con la probabilidad de localización.
  • Teorema 4.5: Proporciona una equivalencia de alta probabilidad entre el LAP ponderado por puntuación, computacionalmente eficiente, y el problema original de mínimos cuadrados combinatorios.
• Eficiencia Computacional: Al reducir la búsqueda a un conjunto localizado y utilizar el algoritmo húngaro, el método evita la complejidad factorial de la búsqueda exhaustiva, escalando polinómicamente ($O(n^3)$) con el tamaño de la muestra.
• Extensiones: La metodología se extiende para manejar diseños parcialmente permutados (donde solo un subconjunto de las covariables está desajustado) y regresión permutada con regularización Ridge.

Resultados

• Simulaciones: Simulaciones extensas variando tamaños de muestra ($n$), conteos de desajuste ($k$) y niveles de ruido ($\sigma_0$) confirman las propiedades teóricas.
  • El tamaño del conjunto de candidatos permanece manejable, y la verdadera permutación se incluye con alta frecuencia.
  • La prueba de permutación mantiene un control válido del error de Tipo I (tasas de rechazo $\leq 0.05$ cuando $k=0$) y exhibe un poder creciente a medida que crecen los desajustes.
  • Los conjuntos de confianza para $\beta_0$ logran una cobertura empírica cercana al nivel nominal (por ejemplo, 95%) en todos los regímenes, con volúmenes que no exhiben un conservadurismo excesivo.
• Aplicación a Datos Reales: El método se aplicó a los datos de calidad del aire de Beijing (concentraciones de PM2.5 frente a covariables meteorológicas).
  • En un escenario con desajustes locales introducidos artificialmente (el 8% de las filas mezcladas dentro de una ventana de 3 horas), el método rechazó con éxito la hipótesis nula de ausencia de desajuste.
  • En el escenario sin perturbaciones, el conjunto de candidatos colapsó a la matriz identidad, y la hipótesis nula no fue rechazada, confirmando el control del error de Tipo I en la práctica.

Significancia
El artículo afirma ofrecer una base general y computacionalmente factible para la validez exacta de muestra finita en modelos estadísticos que involucran parámetros discretos y combinatorios como las permutaciones. A diferencia de los enfoques asintóticos tradicionales o los métodos de inferencia selectiva que tienen dificultades con la naturaleza no poliédrica de la selección de permutaciones, este marco:

1. Evita la dependencia de la asintótica local o de expansiones de verosimilitud suaves.
2. Proporciona un control riguroso del error de muestra finita tanto para la prueba de hipótesis como para la estimación de parámetros.
3. Cierra la brecha entre la teoría estadística y la tractabilidad computacional en presencia de incertidumbre de alineación.

Los autores posicionan este trabajo como una solución al desafío de realizar inferencia cuando los emparejamientos de datos están parcialmente desconocidos o corrompidos, un problema común en la integración de datos para la preservación de la privacidad y el enlace de registros.