기술 요약: 부분적 수행적 예측 (Partially Performative Prediction)

문제 정의

본 논문은 분포 변화를 오로지 내생적(endogenous, 모델 $\theta$에 의해 유도됨)인 것으로 모델링하는 기존의 수행적 예측(performative prediction) 프레임워크의 한계를 다룹니다. 고전적인 수행적 예측에서 데이터 분포 $D(\theta)$는 학습자의 행동에 의해서만 변화합니다. 그러나 저자들은 금융, 의료, 정책과 같은 실제적인 결과적 도메인(consequential domains)에서 분포 변화가 순수하게 내생적이지는 않다는 점에 주목합니다. 이러한 변화는 학습자의 영향과 더불어, 학습자와 독립적으로 진화하는 외생적(exogenous) 요인(예: 계절적 효과, 시장 동력, 정책 변화)이 혼합되어 발생합니다.

이러한 상호작용을 포착하기 위해, 본 논문은 부분적 수행적 예측을 도입합니다. 이 설정에서 $t$ 시점의 데이터 분포는 다음과 같이 시간에 따라 변하는 혼합물입니다:
$$D_t(\theta) = (1 - \alpha_t)D(\theta) + \alpha_t P_t$$
여기서:

• $D(\theta)$는 모델 $\theta$에 의존하는 수행적 성분입니다.
• $P_t$는 $\theta$와 독립적으로 시간에 따라 진화하는 외생적 분포입니다.
• $\alpha_t \in [0, 1]$는 외생적 변화의 상대적 강도를 조절합니다.

이 프레임워크는 고전적인 수행적 예측($\alpha_t = 0$일 때 회복됨)을 일반화하며, 순수하게 외생적인 변화 설정($\alpha_t = 1$일 때)에 접근합니다. 핵심 과제는 "타겟"(최적 또는 안정적인 모델)이 더 이상 정적이지 않다는 것입니다. 타겟은 학습자의 행동과 $P_t$의 외부 진화 모두로 인해 표류(drift)하게 됩니다.

방법론 및 프레임워크

1. 목적 함수의 재정의: 동적 후회 (Dynamic Regret)

환경이 비정상성(non-stationary)을 띠기 때문에, 단일 고정 모델로 수렴하는 것(수행적 안정성이나 최적성과 같이)은 불충분합니다. 저자들은 시간에 따라 변하는 벤치마크 시퀀스에 대한 **동적 후회(dynamic regret)**를 통해 성능을 측정할 것을 제안합니다.

• 수행적 안정성 후회 ($Reg^{PS}_T$): 학습자의 시퀀스 $\{\theta_t\}$를, $\theta^{PS}_t$에 의해 유도된 분포에 대해 디커플링된 리스크를 최소화하는 수행적 안정 지점들의 시퀀스 $\{\theta^{PS}_t\}$와 비교합니다.
• 수행적 최적성 후회 ($Reg^{PO}_T$): 학습자를 수행적 리스크 $PR_t(\theta) = \mathbb{E}_{Z \sim D_t(\theta)}[\ell(Z, \theta)]$를 최소화하는 수행적 최적 지점들의 시퀀스 $\{\theta^{PO}_t\}$와 비교합니다.

2. 핵심 분석 도구: 경로 길이 (Path Length)

이론적 경계(theoretical bounds)의 중심이 되는 양은 벤치마크 시퀀스의 누적 이동량으로 정의되는 경로 길이입니다:
$$\sum_{t=1}^{T-1} \Delta^{PS}_t \quad \text{단, } \Delta^{PS}_t = \|\theta^{PS}_t - \theta^{PS}_{t+1}\|$$
본 논문은 후회 경계가 외생적 분포 $P_t$의 변화율과 혼합 계수 $\alpha_t$에 의해 구동되는 이 경로 길이에 명시적으로 의존함을 입증합니다.

3. 분석된 알고리즘

본 논문은 이 설정에 적응된 여러 표준 학습 휴리스틱을 분석합니다:

• 반복 리스크 최소화 (RRM): $\theta_{t+1} = \arg\min_\theta \mathbb{E}_{Z \sim D_t(\theta_t)}[\ell(Z, \theta)]$를 업데이트합니다.
• 반복 경사 하강법 (RGD): 전체 기대 경사(full expected gradients)를 사용합니다.
• 확률적 경사 하강법 (SGD): "탐욕적(greedy)" 방식(배포당 하나의 샘플)과 "게으른(lazy)" 방식(배포당 여러 샘플/업데이트) 변형을 포함합니다.
• 제로 차수 알고리즘 (Zeroth-Order Algorithms): 수행적 리스크의 경사를 구하기 어려운 수행적 최적성을 위해 사용됩니다. 여기에는 모델을 섭동(perturb)시켜 경사를 추정하는 Two-Deployment (ZGD2) 및 Single-Deployment (ZGD) 방법이 포함됩니다.

주요 기여 및 결과

1. 안정성을 위한 이론적 경계

저자들은 내생적 변화와 외생적 변화를 명시적으로 절충하는 RRM 및 RGD에 대한 후회 경계를 도출합니다.

• 정리 3.2 (RRM): 강볼록성(strong convexity) 및 매끄러움(smoothness) 가정 하에, 안정성 후회는 다음과 같이 제한됩니다:
  $$Reg^{PS}_T(ARRM) = O\left(1 + \sum_{t=1}^{T-1} \Delta^{PS}_t\right)$$
  수렴에 필요한 수축 계수(contraction factor)는 고전적인 설정에 비해 완화됩니다: $\epsilon < \frac{\mu}{(1-\alpha_{\min})\beta_z}$.
• 통찰: 변화가 주로 수행적일 때($\alpha_t \approx 0$), 경로 길이는 사라지고 후회는 상수가 됩니다. 변화가 주로 외생적일 때($\alpha_t \approx 1$), 후회는 $P_t$의 비정상성에 의존합니다. $P_t$가 빠르게 변동하면 후회가 커질 수 있고, $P_t$가 거의 일정하다면 후회는 낮게 유지됩니다.

2. 최적성을 위한 이론적 경계

수행적 최적성을 위해, 본 논문은 제로 차수 최적화 기법을 활용합니다.

• 정리 5.2 & 5.3: 저자들은 두 번의 배포(two-deployment) 및 한 번의 배포(single-deployment) 제로 차수 알고리즘에 대한 후회 경계를 제공합니다. 이 경계는 차원 $d$, 시간 지평 $T$, 그리고 최적 시퀀스의 경로 길이 $\sum \Delta^{PO}_t$에 따라 스케일링됩니다.
• 볼록성 트레이드오프: 본 논문은 외생적 성분이 클수록($\alpha_t \approx 1$) 타겟을 추적하기는 어려워지지만(경로 길이 증가), 동시에 수행적 리스크가 볼록해질 가능성이 높아진다는 점(외생적 부분이 볼록하다면)을 언급합니다. 반대로, 강력한 내생적 피드백은 손실 함수가 볼록하더라도 수행적 리스크를 비볼록(non-convex)하게 만들 수 있습니다.

3. 실험적 검증

신용 점수 데이터셋(전략적 반응 모델)과 합성 가우시안 데이터에 대한 실험은 이론적 발견을 검증합니다:

• 무작위 외생적 변화: $\alpha_t$가 더 빠르게 감소할수록(움직이는 외생적 항의 가중치를 줄일수록) 낮은 후회를 보입니다.
• 정적 외생적 변화: $\alpha_t$를 더 크게 유지할수록(고정된, 비수행적 분포에 가깝게 할수록) 낮은 후회를 얻습니다.
• 실험적 후회 곡선은 $\alpha_t$ 스케줄의 순위에 관한 이론적 상한선과 일치합니다.

의의 및 주장

본 논문은 단일 학습 모델 아래에서 내생적 변화와 외생적 변화를 통합하는 최초의 프레임워크를 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

1. 일반화: 본 논문은 고전적인 수행적 예측을 엄격하게 일반화하며, 표준 알고리즘(예: RRM)이 외생적 노이즈가 존재하는 상황에서도 여전히 효과적이지만 수렴 조건의 재평가가 필요함을 보여줍니다.
2. 동적 벤치마킹: 정적 평형에서 동적 후제로 패러다임을 전환하여, 현실 세계의 시스템에서는 "최적의" 모델이 움직이는 타겟임을 인정합니다.
3. 트레이드오프 식별: 움직이는 타겟을 추적하는 어려움(외생적 드리프트)과 비볼록한 지형을 최적화하는 어려움(내생적 피드백) 사이의 트레이드오프를 명시적으로 규명합니다.

저자들은 특히 그리디 SGD(greedy SGD)에 대한 후회율의 하한(lower bound)을 맞추는 문제나 정칙성 가정(볼록성, 민감도)을 완화하는 문제가 여전히 남아 있음을 언급하며, 향-후 연구 분야로 남겨두는 등 겸허한 태도를 유지합니다. 또한 현재의 선형 프로토콜을 넘어 비선형 혼합 모델로 후회 정의가 자연스럽게 확장될 수 있음을 시사합니다.