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

Resumo Técnico: Limites Fundamentais e Métodos Ótimos para Limites Analíticos Agudos em Modelos de Variável Instrumental

1. Problema e Contexto

O artigo aborda o problema de identificação parcial de efeitos causais em modelos de Variável Instrumental (IV) com variáveis categóricas. Quando a identificação pontual de um efeito causal (como o Efeito Médio do Tratamento - ATE) falha devido a suposições fracas (sem monotonicidade forte), o objetivo é derivar limites agudos (sharp bounds) que caracterizem o intervalo mais estreito possível para o estimando, consistente com os dados observados e as suposições do modelo.

Existem duas abordagens principais na literatura para obter esses limites:

1. Abordagem de Otimização (Balke-Pearl): Formula o problema como uma programação linear sobre a distribuição de dados completos. Embora garantida como aguda, sua complexidade computacional cresce rapidamente, tornando-a inviável para conjuntos de dados com suporte de resultados grande.
2. Abordagem Analítica/Heurística: Deriva limites fechados usando leis de probabilidade e desigualdades genéricas (ex: Fréchet). Recentemente, conjecturou-se que essa abordagem poderia fornecer limites agudos com complexidade polinomial, evitando a explosão combinatória da otimização.

A tese central do artigo é que essa vantagem percebida da abordagem analítica é ilusória. Os autores provam que, para obter limites analíticos agudos (necessários e suficientes), a complexidade inerente ao modelo IV é exponencial, independentemente do método utilizado.

2. Metodologia

Os autores utilizam uma estrutura baseada em Programação Linear (PL) e sua formulação dual para caracterizar rigorosamente o problema.

• Formulação Primal: O espaço de distribuições de dados completos consistentes com os dados observados e as suposições do IV (exclusão, independência e consistência) é modelado como um poliedro convexo $\Gamma(p)$ definido por restrições lineares $M^\top q = p, q \geq 0$.
• Formulação Dual:
  • Para o ATE, o problema de encontrar limites agudos é equivalente a encontrar os vértices do conjunto viável dual $H = \{v : Mv \leq c\}$. O limite inferior é dado por $\max_{v \in H} v^\top p$.
  • Para as Implicações Testáveis (desigualdades de IV), o problema é caracterizar as raias extremas do cone dual $K = \{r : Mr \leq 0\}$. A viabilidade do modelo exige que $p^\top r \leq 0$ para todas as raias extremas.
• Análise Combinatória: Em vez de enumerar vértices usando algoritmos genéricos de PL (que são ineficientes), os autores exploram a estrutura algébrica específica das matrizes do modelo IV. Eles definem "assinaturas" binárias que mapeiam biunivocamente os vértices e raias extremas, permitindo uma contagem exata e uma construção direta das soluções.

3. Principais Contribuições e Resultados

A. Limites Inferiores Fundamentais de Complexidade
O resultado mais impactante é a prova de que a complexidade exponencial não é um artefato de algoritmos ineficientes, mas uma propriedade intrínseca do modelo IV discreto:

• Para o ATE: Se a variável de resultado $Y$ assume $n$ valores distintos, qualquer representação analítica aguda do limite superior ou inferior do ATE deve ser expressa como o máximo (ou mínimo) de uma coleção de termos lineares cujo cardinal cresce exponencialmente com $n$.
  • Para um instrumento binário ($\ell=2$), o número de termos é aproximadamente $5 \times 4^{n-1}$.
  • Para instrumentos com múltiplos valores ($\ell > 2$), o crescimento é da ordem de $\ell(\ell-1)^{n-1}$.
• Para Implicações Testáveis: O número de desigualdades de IV necessárias e suficientes para caracterizar completamente o modelo também cresce exponencialmente com o suporte do resultado. Para $\ell=2$, o número exato de desigualdades agudas é $2^{n+1} - 4$.

Conclusão Teórica: Nenhuma família de expressões analíticas lineares de tamanho polinomial pode produzir limites agudos gerais para o ATE em modelos IV. A "barreira" computacional é inevitável.

B. Caracterização Analítica Completa (Caso Binário)
Para o caso de instrumento binário ($\ell=2$), os autores fornecem uma caracterização explícita e completa:

• Derivaram fórmulas fechadas para todos os vértices do dual, mapeando-os através de "assinaturas admissíveis" (subconjuntos $S_1, S_2, S_3$ de vetores binários).
• Derivaram o conjunto exato e não redundante de desigualdades de IV (implicações testáveis) que são necessárias e suficientes. Isso refina trabalhos anteriores (como Bonet, 2001; Kédagni e Mourifié, 2020) que forneciam conjuntos maiores e redundantes.

C. Algoritmo e Implementação Ótimos
Como complemento construtivo, os autores desenvolveram um pacote de software (Python e R) que:

• Calcula os limites agudos do ATE e as desigualdades de IV com complexidade de tempo ótima (linear no número de termos da solução).
• Evita a enumeração explícita de vértices de poliedros genéricos, utilizando diretamente as caracterizações estruturais derivadas.
• Desempenho: Enquanto pacotes existentes baseados em enumeração de poliedros tornam-se intratáveis para $n \geq 6$, o método proposto calcula o conjunto completo de limites e desigualdades em milissegundos, mesmo para suportes maiores.

4. Significado e Impacto

• Refutação de Conjecturas: O trabalho refuta a crença de que é possível obter limites agudos analíticos com complexidade polinomial em modelos IV gerais. Ele estabelece que a explosão combinatória é uma característica fundamental da geometria do problema.
• Eficiência Prática: Ao fornecer uma formulação estrutural direta, o artigo torna viável a aplicação de limites agudos em cenários onde métodos anteriores falhavam devido à complexidade computacional.
• Fundamentação Teórica: Fornece limites inferiores rigorosos para o número de termos necessários em qualquer sistema de limites ou desigualdades, fechando a lacuna entre a complexidade observada em métodos de otimização e a complexidade teórica do problema.
• Aplicabilidade: As ferramentas e códigos fornecidos permitem que pesquisadores realizem inferência causal parcial robusta em dados categóricos com múltiplos níveis de resultado, algo que era anteriormente computacionalmente proibitivo.

Em resumo, o artigo demonstra que a "simplicidade" analítica em modelos IV tem um custo exponencial inevitável, mas oferece os meios matemáticos e computacionais para gerenciar essa complexidade de forma ótima.