Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models

Aquí presento un resumen técnico detallado del artículo "Fundamental Limits and Optimal Methods for Sharp Analytical Causal Bounds in Instrumental Variable Models" (Límites Fundamentales y Métodos Óptimos para Cotas Analíticas Agudas en Modelos de Variables Instrumentales), escrito por Arefe Boushehrian, Mohammad Reza Badri, Sina Akbari y Negar Kiyavash.

1. Introducción y Planteamiento del Problema

El objetivo central del trabajo es abordar el problema de la identificación parcial de efectos causales en modelos de Variables Instrumentales (VI) con variables categóricas (discretas). Específicamente, se busca derivar cotas analíticas agudas (sharp bounds) para el Efecto Promedio del Tratamiento (ATE) y caracterizar las implicaciones testables (desigualdades instrumentales) del modelo.

• Contexto: Cuando la identificación puntual falla (debido a la falta de supuestos fuertes como la monotonicidad), las cotas agudas proporcionan el intervalo más estrecho posible para el efecto causal, consistente con los datos observados y los supuestos del modelo.
• El Dilema: Existen dos enfoques principales:
  1. Optimización basada en programación lineal (LP): Métodos como el marco de Balke-Pearl garantizan cotas agudas pero tienen una complejidad computacional que crece rápidamente, haciéndolos intratables para soportes de salida grandes.
  2. Derivación heurística analítica: Métodos que usan leyes de probabilidad e inecuaciones genéricas (como Fréchet) para obtener expresiones cerradas. Se ha conjeturado que estos métodos podrían ofrecer cotas agudas con menor complejidad computacional.
• La Pregunta Clave: ¿Es posible obtener cotas analíticas agudas para el ATE y un conjunto completo de desigualdades instrumentales testables con una complejidad polinómica en el tamaño del soporte de la variable de resultado ($n$), evitando la explosión combinatoria de los métodos de optimización?

2. Metodología y Enfoque Teórico

Los autores utilizan una formulación unificada basada en Programación Lineal (LP) y su dualidad para demostrar que la complejidad exponencial es una característica intrínseca del modelo, no un artefacto algorítmico.

A. Formulación Primal y Dual

• Primal: El problema de encontrar las cotas del ATE se formula como la optimización de un funcional lineal sobre el poliedro de distribuciones de datos completos ($Q$) consistentes con las distribuciones observadas ($P$) y los supuestos de exclusión e independencia.
  • $L(P) = \min c^T q$ sujeto a $M^T q = p, q \geq 0$.
• Dual: Mediante el teorema de dualidad fuerte, el problema se transforma en maximizar $v^T p$ sujeto a $Mv \leq c$.
  • Las cotas agudas corresponden a los vértices del poliedro dual factible $H$.
  • Las implicaciones testables (desigualdades instrumentales) corresponden a los rayos extremos del cono dual $K$ definido por $Mr \leq 0$.

B. Análisis de Complejidad

El núcleo de la metodología es el análisis combinatorio de la estructura de los vértices de $H$ y los rayos extremos de $K$.

• Los autores demuestran que el número de vértices $M$-distintos (únicos módulo el núcleo de la matriz de restricciones) y el número de rayos extremos crecen exponencialmente con el tamaño del soporte de la variable de resultado ($n$).
• Se define una correspondencia biyectiva entre estos elementos geométricos y ciertas "firmas" binarias (vectores de admissibilidad), permitiendo contarlos y caracterizarlos explícitamente.

3. Contribuciones Clave

El artículo presenta tres contribuciones fundamentales:

1. Límites Inferiores Fundamentales de Complejidad:

   • Se demuestra que cualquier representación analítica aguda de las cotas del ATE en un modelo VI discreto debe involucrar un número de términos lineales que crece exponencialmente con $n$.
   • Específicamente, para un instrumento binario ($\ell=2$), el número de términos necesarios es $5 \times 4^{n-1} - 2^{n+2} + 4$.
   • Para instrumentos multivaluados ($\ell > 2$), el crecimiento es $\Omega(\ell (\ell-1)^{n-1})$.
   • Conclusión: No existe ninguna familia de expresiones analíticas lineales de tamaño polinómico que pueda generar cotas agudas en general. La complejidad exponencial es inevitable.

2. Caracterización Completa de Implicaciones Testables:

   • Se proporciona una caracterización completa y aguda de las desigualdades instrumentales (implicaciones testables) para instrumentos binarios.
   • Se demuestra que el número de desigualdades necesarias y suficientes también crece exponencialmente ($2^{n+1} - 4$ para $\ell=2$).
   • Esto refuta la idea de que se pueden obtener todas las implicaciones testables mediante un número polinómico de desigualdades simples.

3. Algoritmos y Software Óptimos:

   • A pesar de la complejidad exponencial, los autores desarrollan un paquete de software (en Python y R) que calcula estas cotas y desigualdades con complejidad óptima sensible a la salida.
   • El tiempo de ejecución es lineal en el número de términos de la cotas (es decir, $O(\text{términos})$), evitando la sobrecarga combinatoria de los métodos de enumeración de vértices genéricos (como causaloptim).
   • El método explota la estructura explícita de los vértices y rayos derivada en el papel para generar las soluciones directamente, sin necesidad de resolver el LP numérico completo para cada instancia.

4. Resultados Principales

• Teorema de Imposibilidad Computacional: Se prueba que la separación computacional esperada entre métodos de optimización (lentos) y métodos analíticos heurísticos (rápidos) es ilusoria. Si se requiere agudeza (sharpness), la complejidad exponencial es intrínseca al modelo de VI discreto.
• Fórmulas Cerradas para Instrumento Binario:
  • Se derivan explícitamente las cotas superiores e inferiores del ATE como el máximo/mínimo sobre un conjunto de $O(4^n)$ expresiones lineales de las probabilidades observadas.
  • Se listan las $2^{n+1}-4$ desigualdades instrumentales necesarias y suficientes.
• Validación Empírica:
  • Los experimentos muestran que, mientras que los métodos existentes (basados en enumeración de poliedros) se vuelven intratables incluso para tamaños de soporte moderados ($n=6$), el método propuesto calcula todas las cotas y desigualdades en milisegundos.
  • La ventaja computacional es de más de 1000 veces para $n=6$ en comparación con enfoques anteriores.

5. Significado e Impacto

Este trabajo es fundamental para la inferencia causal en modelos de variables instrumentales por varias razones:

1. Claridad Teórica: Cierra el debate sobre si es posible obtener cotas analíticas agudas de manera eficiente. Establece un límite inferior teórico: la complejidad exponencial es inevitable para la agudeza en modelos discretos.
2. Eficiencia Práctica: Proporciona la primera herramienta capaz de calcular cotas agudas y desigualdades instrumentales completas para soportes de salida grandes, algo que antes se consideraba computacionalmente prohibido. Esto permite aplicar métodos de identificación parcial en escenarios más realistas y complejos.
3. Rigor en la Testabilidad: Al caracterizar completamente el conjunto de desigualdades instrumentales, permite a los investigadores verificar si un conjunto de datos observado es compatible con un modelo de VI, identificando violaciones que métodos aproximados podrían pasar por alto.
4. Herramienta de Investigación: El código abierto y las fórmulas derivadas sirven como un estándar de referencia para futuros trabajos en identificación parcial, estableciendo la base para extensiones a instrumentos multivaluados y otros modelos estructurales.

En resumen, el paper demuestra que la "magia" de obtener soluciones analíticas simples y agudas para modelos de VI complejos no existe; la complejidad es inherente. Sin embargo, al entender y explotar la estructura geométrica subyacente, es posible calcular estas soluciones complejas de manera eficiente, superando las limitaciones de los métodos de optimización tradicionales.