Resumen Técnico: Vecinos Más Cercanos de Dos Lados para la Completación de Matrices

Planteamiento del Problema

El artículo aborda el problema de la completación de matrices en el contexto de modelos de factores latentes, centrándose específicamente en entornos donde la matriz de verdad subyacente $\Theta$ es generada por una función latente no lineal $f$ que actúa sobre factores latentes de filas y columnas desconocidos. El modelo se define como:
$$\theta_{i,j} = f(u_i, v_j)$$
donde $u_i \in \mathbb{R}^{d_1}$ y $v_j \in \mathbb{R}^{d_2}$ son factores latentes, y $f$ pertenece a una clase de funciones Hölder con un parámetro de suavidad $\lambda \in (0, 1]$. Este entorno generaliza los modelos bilineales estándar (donde $f(u,v) = \langle u, v \rangle$) a funciones no paramétricas, potencialmente no suaves (menos suaves que Lipschitz).

Un desafío crítico abordado es el régimen de Datos Faltantes No Aleatorios (MNAR, por sus siglas en inglés). A diferencia del régimen de Datos Faltantes Completamente al Azar (MCAR), donde la ausencia de datos es independiente de los datos mismos, el MNAR asume que la probabilidad de que una entrada sea observada depende de los factores latentes no observados. Además, los autores consideran escenarios donde las entradas pueden ser determinísticamente faltantes (es decir, faltan con probabilidad 0 para configuraciones específicas), un fenómeno común en sistemas del mundo real como los motores de recomendación donde las preferencias del usuario dictan la visibilidad.

El objetivo es estimar la verdad subyacente $\theta_{i,j}$ tanto para las entradas observadas como para las faltantes sin conocimiento previo de los factores latentes $U$ y $V$ o de la función $f$, logrando tasas de convergencia minimax óptimas.

Metodología: Vecinos Más Cercanos de Dos Lados (TS-NN)

Los autores proponen el algoritmo de Vecinos Más Cercanos de Dos Lados (TS-NN). La intuición central es aproximar las distancias latentes entre filas y columnas utilizando datos observados, y luego promediar los resultados sobre los vecindarios resultantes.

1. Estimación de Distancias: Dado que la función latente $f$ es desconocida, el algoritmo construye proxies basados en datos para las distancias cuadráticas $L_2$ entre las filas y las columnas.

   • El algoritmo estima la distancia entre la fila $i$ y la $i'$ promediando las diferencias al cuadrado de sus entradas observadas a través de columnas comunes, corregido por la varianza del ruido ($2\sigma^2$).
   • De manera similar, las distancias de las columnas se estiman utilizando filas comunes.
   • Formalmente, la distancia de fila estimada es:
     $$\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$$
     (Se aplica una fórmula simétrica para las columnas).

2. Construcción de Vecindarios: Utilizando parámetros de ajuste $\eta_{row}$ y $\eta_{col}$, el algoritmo define vecindarios:

   • $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
   • $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$

3. Estimación: La estimación $\hat{\theta}_{i,j}$ es el promedio de todas las entradas observadas $X_{i',j'}$ donde $i' \in N_{row}(i)$ y $j' \in N_{col}(j)$.

Contribuciones Clave y Resultados Teóricos

1. Adaptabilidad a la Suavidad y Optimalidad Minimax

El principal hallazgo teórico es que TS-NN se adapta a la suavidad $\lambda$ de la función latente $f$.

• Régimen MCAR: Bajo los supuestos estándar de MCAR, los autores demuestran que, con un ajuste apropiado ($\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$), el Error Cuadrático Medio (MSE) alcanza la tasa minimax óptima no paramétrica:
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  Esta tasa coincide con la de un algoritmo "oráculo" que tiene acceso a los verdaderos factores latentes $U$ y $V$.
• Régimen MNAR: El artículo establece que esta optimalidad se mantiene incluso bajo condiciones MNAR, siempre que se cumpla una condición de regularidad (Supuesto 6). Esta condición requiere esencialmente que el número de entradas observadas en la intersección de los vecindarios de fila y columna sea lo suficientemente grande en relación con el producto de los tamaños de los vecindarios, incluso si algunas entradas faltan de forma determinística.

2. Robustez ante la Ausencia Determinística

Una contribución significativa es la demostración de que TS-NN produce tasas de error no triviales incluso cuando una parte significativa de la matriz es determinísticamente faltante (por ejemplo, el 50% de las entradas faltan para pares usuario-ítem específicos). Los límites teóricos muestran que, mientras la probabilidad de ausencia "efectiva" dentro de los vecindarios permanezca acotada lejos de cero, la tasa minimax se preserva.

3. Garantías Puntuales y Normalidad Asintótica

• Límites Puntuales: El artículo proporciona límites de error puntuales no asintóticos para entradas individuales $\hat{\theta}_{i,j}$. Estos límites exhiben una "maldición de la dimensionalidad" con respecto a los parámetros de ajuste y las dimensiones de la matriz, la cual desaparece al promediarse a nivel de población (MSE).
• Normalidad Asintótica: Bajo condiciones específicas sobre el tamaño del vecindario, los autores demuestran que el estimador puntual es asintóticamente normal:
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  Este resultado permite la construcción de intervalos de confianza válidos para las estimaciones contrafácticas.

Resultados Empíricos

Los autores validan sus hallazgos teóricos a través de:

1. Simulaciones Sintéticas:

   • Los experimentos comparan TS-NN contra líneas base que incluyen Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT) y SoftImpute.
   • Resultados: TS-NN logra consistentemente las mejores tasas de decaimiento de MSE, igualando al Oracle-TS-NN (que conoce los factores latentes) en entornos MCAR. Crucialmente, TS-mente mantiene un rendimiento robusto en entornos MNAR donde otros métodos (como DR-NN) se degradan significativamente.
   • Adaptabilidad de la Suavidad: Las tasas de decaimiento empíricas de TS-NN se alinean con las predicciones teóricas a medida que varía el parámetro de suavidad $\lambda$.
   • Intervalos de Confianza: Los intervalos de confianza construidos alcanzan una cobertura casi nominal (95%) para tamaños de muestra moderados, validando el resultado de normalidad asintótica.

2. Caso de Estudio del Mundo Real (HeartSteps):

   • El método se aplica al conjunto de datos de salud móvil HeartSteps, un ensayo micro-aleatorizado que involucra a 37 usuarios y puntos de decisión durante 6 semanas.
   • El conjunto de datos exhibe características MNAR (los usuarios no están disponibles aproximadamente el 20% del tiempo, y las notificaciones solo se envían si están disponibles).
   • Resultados: En un entorno de validación cruzada de 5 pliegues, TS-NN supera a las variantes de NN de un solo lado (Row-NN, Col-NN) y a líneas base como "All-Row-NN" en la estimación de conteos de pasos contrafácticos, demostrando la utilidad práctica del enfoque de dos lados para manejar la ausencia determinística.

Significado y Reivindicaciones

El artículo afirma que unifica dos dominios de investigación distintos: la completación de matrices no paramétrica y el análisis de datos faltantes MNAR.

• Análisis Pionero: Los autores afirman que este es el primer análisis teórico de un método que maneja simultáneamente factores latentes de fila y columna desconocidos, una función Hölder-continua no lineal (con $\lambda < 1$) y la ausencia de datos MNAR.
• Equivalencia con el Oráculo: El trabajo demuestra que la falta de conocimiento sobre los factores latentes no penaliza la tasa de convergencia; TS-NN se desempeña tan bien como un oráculo con conocimiento total de $U$ y $V$ en el régimen intermedio.
• Robustez: Se demuestra que la metodología es robusta a los patrones de ausencia determinística, una característica que suele ignorarse en la literatura estándar de completación de matrices pero que es crítica para aplicaciones del mundo real como los sistemas de recomendación.

Los autores concluyen que TS-NN proporciona una solución teóricamente fundamentada, adaptativa y robusta para la completación de matrices en entornos complejos, no suaves y de ausencia no aleatoria.