Wasserstein Distributionally Robust Regret Optimization

기술 요약: 와서스타인 분포 강건 후회 최적화 (Wasserstein Distributionally Robust Regret Optimization)

문제 정의
불확실성 하에서의 의사결정은 대개 경험적 위험 최소화(Empirical Risk Minimization, ERM)에 의존하며, 이는 경험적 분포가 배포 환경을 대표한다는 가정을 전제로 한다. ERM은 매끄러움(smoothness)과 독립 동일 분포(i.i.d.) 가정 하에서 강력한 표본 외(out-of-sample) 보장을 제공하지만, 훈련 분포와 배포 분포가 괴리될 경우 실패할 수 있다. 분포 강건 최적화(Distributionally Robust Optimization, DRO)는 모호성 집합(일반적으로 와서스타인 볼)에 대해 최악의 기대 손실을 최소화함으로써 이 문제를 해결한다. 그러나 DRO의 적대적 초점은 최악의 손실에 맞춰져 있어, 지나치게 보수적인 정책을 초래할 수 있다. 특히 비대칭적 상방 잠재력(예: 저비용, 고마진 재고 상황)이 존재하는 환경에서는 유리한 결과를 억제하는 것이 부적절할 수 있다.

이러한 과도한 보수성을 완화하기 위해, 본 논문은 **사전적(ex-ante) 분포 강건 후회 최적화(DRRO)**를 연구한다. 사후적(ex-post) 후회(각 불확실성 실현에 대해 최적의 결정과 비교하는 것)나 표준 DRO(최악의 손실을 최소화하는 것)와 달리, 사전적 DRRO는 모호성 집합에 대해 최악의 *후회(regret)*를 최소화한다. 여기서 후회는 특정 정책의 기대 손실과 해당 특정 분포에 대한 최적 정책의 기대 손실 간의 차이로 정의된다. 본 논문은 경험적 참조 분포를 중심으로 하는 타입-$p$ 와서스타인 모호성 집합을 활용하는 **와서스타인 DRRO (WDRRO)**에 집중한다.

방법론 및 이론적 프레임워크
본 논문은 "일반적인" 레짐(ERM이 충분한 경우)과 "복잡한" 레짐(WDRRO가 뚜렷한 이점을 제공하는 경우) 사이의 이분법을 중심으로 WDRRO의 구조적 및 계산적 이론을 전개한다.

1. 민감도 이론 및 ERM 선택:

   • 유일한 ERM 최적해: 매끄러움 및 정규성 조건 하에 유일한 ERM 최적해가 존재할 때, 본 논문은 WDRRO가 와서스타인 반경 $\delta$에 대해 **0차 1차 민감도(zero first-order sensitivity)**를 가짐을 증명한다. 즉, 근사 최적 WDRRO 결정은 $\theta_\delta = \theta_{ERM} + o(\delta)$를 만족한다. 이는 일반적으로 ERM에서 $O(\delta)$ 차수로 벗어나는 표준 와서스타인 DRO와 대조된다.
   • 비유일한 ERM 최적해: ERM 해 집합이 유일하지 않을 때, WDRRO는 정규화 도구로서 작용하여 다른 ERM 해들과의 최악의 그래디언트 불일치를 최소화하는 ERM 최적해를 선택한다(미니맥스 그래디언트 불일치 게임).
   • 이차 손실: 엄격하게 볼록한 이차 손실(strictly convex quadratic losses)에 대해 와서스타인 차수가 $p \ge 2$인 경우, 본 논문은 ERM 정책이 임의의 반경 $\delta$에 대해 정확히 WDRRO-최적임을 입증한다.

2. 계산적 레짐 및 난해성:

   • 본 논문은 가정이 깨질 때(예: 비매끄러운 손실, 큰 반경) WDRRO가 계산적으로 취약해짐을 식별한다.
   • NP-난해성: 저자들은 단순한 max-affine 손실(쌍선형 항이 없는 경우)에 대해 타입-1 와서스타인 거리와 $\ell_1$ 그라운드 노름을 사용할 때 WDRRO를 평가하는 것이 **NP-난해(NP-hard)**함을 증명한다. 이러한 난해성은 내부 와서스타인 리스크가 계산 가능한 경우에도 지속되며, 이는 WDRRO를 WDRO, 강건 최적화(RO), 강건 후회 최적화(RRO)와 구별 짓는 특징이다(위 모델들은 동일한 손실 클래스에 대해 계산 가능하다).

3. 알고리즘 솔루션:

   • 정확한 알고리즘: 중간 규모의 인스턴스에 대해, 와서스타인 쌍대성(duality)을 사용하여 후회의 유한 비볼록(nonconvex) 정식화를 도출한다. 이는 그라운드 트루스 벤치마크 역할을 한다.
   • 볼록 완화(Convex Relaxations): 더 큰 규모의 문제를 처리하기 위해, 저자들은 다루기 쉬운 볼록 완화 기법을 개발한다.
     • 쌍선형 항이 없는 손실($d_k=0$)의 경우, 사후적 후회를 상한하는 단일 볼록 프로그램을 도출한다. 이 완화는 $\delta=0$일 때와 지지 집합의 직경보다 큰 반경에서 정확하며, 근사 오차는 $O(\delta)$이다.
     • 쌍선형 항이 있는 손실($d_k \neq 0$)의 경우, 벤치마크 중심점으로 결정 공간을 덮는 **로컬 커버 확장(local-cover extension)**을 제안한다. 이를 통해 교차 항을 근사하며, 커버링 반경 $\rho$에 의존하는 추가 오차 항($O(\rho \delta)$)을 도입한다.

주요 결과 및 실험
본 논문은 뉴스벤더 문제와 평균-CVaR 포트폴리오 배분 실험을 통해 이론과 알고리즘을 검증한다.

• 뉴스벤더 문제:

  • 저비용, 고마진 설정에서, DRRO 정책은 불확실성 반경이 증가함에 따라 더 공격적으로 변하는 반면, DRO는 더 보수적으로 변한다. 이는 DRO가 억제하는 "상방" 잠재력을 포착한다.
  • 고비용 설정에서는 DRRO가 더 보수적으로 변하며, 이는 DRRO의 반응 방향이 페이오프의 비대칭성에 따라 달라짐을 보여준다.
  • 제안된 볼록 완화는 정확한 WDRRO 솔루션을 매우 밀접하게 추적하며, 주문량과 후회 측면에서 무시할 만한 격차를 보인다.
  • 계산 측면에서, 제안된 완화 방식은 대규모 샘플 크기로 효율적으로 확장되는 반면, 경쟁 완화 방식(Cho and Yang [14])은 샘플 크기가 증가함에 따라 계산 불가능(NP-hard)해진다.

• 포트폴리오 최적화 (Mean-CVaR):

  • 단일 자산 설정에서, DRO는 반경이 증가함에 따라 불연속적인 "전부 아니면 전무(all-or-nothing)" 행동(전액 투자에서 제로 투자로 급격히 변화)을 보인다. 반면, DRRO 정책은 불리한 분포에 맞서 후회와 노출 사이의 균형을 맞추며 점진적으로 조정되는 비단조적(non-monotone) 행동을 보인다.
  • 다중 자산 설정에서, DRRO 완화는 DRO가 결국 무위험 자산으로 완전히 이동하는 것과 달리, 더 넓은 범위의 반경에 대해 위험 자산에 대한 양(+)의 노출을 유지한다.
  • 이론적 분석에 따르면, 매우 큰 반경에 대해 후회-최적 정책은 (무한한 상방 잠재력으로 인해) 위험 자산에 전액 투자하는 방향으로 수렴하는 반면, DRO는 무위험 자산으로 수렴한다.

의의 및 주장
본 논문은 와서스타인 DRRO에 대한 최초의 종합적인 이론 및 계산 프레임워크를 제공한다고 주장한다. 주요 기여는 다음과 같다:

1. 이론적 통찰: 정규 레짐(매끄러운 손실, 유일한 ERM)에서는 후회 기반의 강건화가 불필요하며, 이미 ERM이 1차적으로 최적임을 확립한다. WDRRO의 가치는 주로 비매끄럽거나 큰 반경의 레짐에서 드러난다.
2. 복잡도 분리: max-affine 손실에 대해 벤치마크 결정에 대한 외부 극대화 과정 때문에 WDRRO가 표준 강건 정식화(WDRO, RO, RRO)보다 계산적으로 더 어렵다는 것을 입증한다.
3. 실용적 알고리즘: WDRRO 평가를 위한 최초의 정확한 알고리즘과, 계산 가능하고 확장 가능하며 유한 반경 보장을 제공하는 새로운 클래스의 볼록 완화 기법을 제공한다.
4. 행동적 미묘함: DRRO가 최악의 손실을 고려하는 DRO가 놓치는, 비대칭 페이오프 환경에서의 손실 의존적 공격적 또는 보수적 행동을 포착할 수 있음을 보여준다.

저자들은 결론적으로, 온건한 레짐에서는 ERM이 충분하지만, 복잡하고 비매끄럽거나 이해관계가 걸린 시나리오에서 분포 오설정(distributional misspecification)을 다루기 위해서는 WDRRO가 필수적인 도구이며, 계산 복잡성을 관리하기 위해 개발된 완화 기법을 활용해야 한다고 밝힌다.