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

이 논문은 도구변수 (Instrumental Variable, IV) 모델에서 **평균 치료 효과 (Average Treatment Effect, ATE)**에 대한 **최적의 해석적 (analytical) 경계 (sharp bounds)**와 **검증 가능한 함의 (testable implications)**를 도출하는 데 있어 근본적인 계산 복잡도 한계와 이를 극복하는 최적 방법을 제시합니다.

저자들은 기존에 "최적의 해석적 경계는 단순한 부등식이나 확률 법칙을 이용해 다항식 시간 내에 도출될 수 있다"는 주장이나 추측이 **환상 (illusory)**임을 증명하고, 오히려 이러한 경계와 부등식의 수가 결과 변수의 지지집합 (support) 크기에 대해 지수적으로 증가해야 함을 수학적으로 입증했습니다.

다음은 논문의 상세한 기술적 요약입니다.

1. 연구 문제 (Problem Statement)

• 배경: 도구변수 (IV) 모델을 사용하여 인과 효과를 추정할 때, 점 식별 (point identification) 이 불가능한 경우 (예: 비완전 준수, unobserved confounding) **부분 식별 (partial identification)**을 통해 참값이 존재할 수 있는 구간 (bounds) 을 구하는 것이 중요합니다.
• 기존 접근법의 한계:
  1. 최적화 기반 (Balke-Pearl 프레임워크): 전체 데이터 분포 공간에서 선형 프로그래밍 (LP) 을 풀어 최적의 경계를 구합니다. 이 방법은 'sharp(최적)'한 결과를 보장하지만, 변수의 범주 수가 증가함에 따라 계산 복잡도가 급격히 증가하여 실용적으로 사용하기 어렵습니다.
  2. 휴리스틱/대수적 접근: 확률 법칙과 일반적 부등식 (예: Fréchet 부등식) 을 이용해 경계를 유도합니다. 계산은 빠르지만, 항상 'sharp'한 결과를 보장하지는 않으며, 최근 일부 연구에서는 이 방법이 최적의 해석적 경계를 효율적으로 줄 수 있다는 추측이 있었습니다.
• 핵심 질문: "최적의 해석적 경계 (sharp analytical bounds) 를 다항식 시간 (polynomial time) 내에 도출할 수 있는가?"

2. 방법론 (Methodology)

저자들은 이산형 (discrete) 도구변수 모델을 가정하고, 문제를 **선형 프로그래밍 (Linear Programming, LP)**의 쌍대 문제 (Dual Problem) 관점에서 재해석했습니다.

• 선형 프로그래밍 공식화:
  • 관측된 데이터 분포 $P$와 일관된 전체 데이터 분포 $Q$의 집합을 선형 제약 조건 ($M^\top q = p, q \ge 0$) 으로 정의합니다.
  • ATE 의 상한/하한은 이 집합 위에서 선형 목적 함수를 최적화하는 문제로 변환됩니다.
• 쌍대 문제 (Dual Problem) 분석:
  • 원문제 (Primal) 는 전체 데이터 공간 (차원 $2^\ell n^2$) 에서 정의되지만, 쌍대 문제 (Dual) 는 관측된 데이터 공간 (차원 $2^\ell n$) 에서 정의됩니다.
  • Sharp Bounds: 쌍대 문제의 **최적해 (Vertex)**를 모두 탐색하여 구합니다.
  • Testable Implications: 쌍대 문제의 **극단선 (Extreme Rays)**을 모두 탐색하여 관측 데이터가 IV 모델과 일치하는지 검증하는 부등식을 도출합니다.
• 구조적 특성화 (Structural Characterization):
  • 저자들은 쌍대 문제의 feasible region (허용 영역) 의 **꼭짓점 (Vertices)**과 **극단선 (Extreme Rays)**의 구조를 명시적으로 분석했습니다.
  • 이를 통해 각 꼭짓점과 극단선이 대응하는 이진 시그니처 (Binary Signature) 벡터들을 정의하고, 이들의 수를 세는 조합론적 분석을 수행했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. 해석적 ATE 경계의 근본적 복잡도 (Fundamental Limits on ATE Bounds)

• 결과: 결과 변수 $Y$가 $n$개의 서로 다른 값을 가질 때, ATE 에 대한 **최적의 해석적 경계 (Sharp Analytical Bound)**는 $n$에 대해 지수적으로 증가하는 선형 항들의 최대 (또는 최소) 로 표현되어야 합니다.
• 증명:
  • 이진 도구변수 ($\ell=2$) 의 경우, 쌍대 문제의 꼭짓점 (Vertices) 의 수는 정확히 $5 \times 4^{n-1} - 2^{n+2} + 4$개이며, 이는 $O(4^n)$ 수준입니다.
  • 다중 값 도구변수 ($\ell > 2$) 의 경우에도 꼭짓점의 수는 $\ell((\ell-1)^{n-1} - (\ell-1))$로 지수적으로 증가합니다.
• 의미: 따라서 **다항식 크기 (polynomial-size)**의 선형 표현식 집합으로는 일반적인 경우 최적의 경계를 도출할 수 없습니다. 기존에 제안된 휴리스틱 방법들이 최적의 경계를 줄 수 있다는 주장은 불가능합니다.

3.2. 검증 가능한 함의 (Sharp Testable Implications)

• 결과: IV 모델이 관측 데이터와 일치하기 위해 만족해야 하는 **필요충분조건 (Necessary and Sufficient Conditions)**인 IV 부등식의 수도 $n$에 대해 지수적으로 증가합니다.
• 구체적 결과:
  • 이진 도구변수 ($\ell=2$) 의 경우, 불필요한 중복이 없는 최적의 IV 부등식 집합의 크기는 $2^{n+1} - 4$개입니다.
  • 이는 기존 연구 (Bonet 2001, Kédagni & Mourifié 2020 등) 에서 제시된 부등식들이 불필요하게 많거나 (redundant), 혹은 충분하지 않았음을 보완한 것입니다.
• 의미: IV 모델의 검증 가능성 (Testability) 을 완전히 설명하기 위해서는 지수적으로 많은 부등식이 필요합니다.

3.3. 계산적으로 최적화된 알고리즘 및 소프트웨어

• 접근법: 선형 프로그래밍 솔버를 사용하여 모든 꼭짓점을 나열하는 기존 방식 (지수 시간 이상의 복잡도) 대신, 논문에서 유도한 **명시적인 구조적 특성 (Explicit Structural Characterization)**을 활용했습니다.
• 성능:
  • 최적의 경계와 부등식을 출력 민감도 (Output-sensitive) 방식으로 계산합니다. 즉, 계산 시간은 도출된 항 (또는 부등식) 의 수에 비례하여 선형 ($O(\text{number of terms})$) 입니다.
  • 이는 이론적으로 증명된 하한 (Lower Bound) 과 일치하는 최적의 시간 복잡도입니다.
• 시뮬레이션 결과:
  • $n=6$ 정도의 작은 크기에서도 기존 패키지 (causaloptim 등) 는 계산이 불가능해지는 반면, 저자들의 방법은 밀리초 (milliseconds) 단위로 모든 최적 경계와 부등식을 계산했습니다.
  • Python 및 R 코드는 오픈 소스로 제공됩니다.

4. 의의 및 결론 (Significance & Conclusion)

1. 이론적 명확성: 도구변수 모델에서 최적의 인과적 경계를 도출하는 데 있어 지수적 복잡도는 알고리즘의 한계가 아니라 모델 자체의 내재적 조합론적 특성임을 증명했습니다. 이는 "더 좋은 알고리즘"을 기다리는 것이 아니라, 문제의 본질적인 복잡도를 인정해야 함을 시사합니다.
2. 실용적 기여: 이론적으로 복잡도가 높음에도 불구하고, 저자들의 구조 기반 알고리즘은 중간 크기의 이산형 IV 모델에서도 실용적으로 최적의 경계와 검증 부등식을 즉시 계산할 수 있게 합니다.
3. 향후 연구: 이 연구는 이진 도구변수 ($\ell=2$) 에 대한 완전한 특성을 제공하며, 다중 값 도구변수 ($\ell > 2$) 에 대한 최적의 해석적 표현은 향후 과제로 남겼습니다.

요약하자면, 이 논문은 "최적의 해석적 경계를 효율적으로 구할 수 있다"는 환상을 깨뜨리고, 그 복잡도가 지수적임을 수학적으로 엄밀히 증명함과 동시에, 그 지수적 복잡도를 피하지 않고 **가장 효율적인 방식 (선형 시간)**으로 이를 계산하는 방법을 제시하여 인과 추론 분야에서 중요한 이정표를 세웠습니다.