The Stability of Online Algorithms in Performative Prediction

이 논문은 제한 조건 없이 배치된 무회수 (no-regret) 온라인 알고리즘이 데이터 분포를 변화시키더라도 결국 예측이 사후적으로 최적인 '성능적 안정 균형'으로 수렴함을 증명하고, 이를 통해 경사 하강법과 같은 일반적인 알고리즘이 왜 피드백 루프를 안정화시키는지 설명합니다.

핵심

이 논문은 **"예측이 현실을 바꿀 때, 어떻게 혼란을 멈추고 안정을 찾을 수 있을까?"**라는 질문에 대한 해답을 제시합니다.

간단히 말해, 이 연구는 **"예측 알고리즘이 사람들의 행동을 바꾸고, 그 바뀐 행동이 다시 알고리즘을 학습시키는 악순환 (피드백 루프) 을 어떻게 자연스럽게 해결할 수 있는지"**를 수학적으로 증명했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제 상황: "예측이 현실을 만들어내는 함정"

상상해 보세요. 어떤 은행이 "이 사람은 신용이 나빠서 대출을 거절해야 한다"는 AI 모델을 만들었다고 칩시다.

• 예측: AI 는 "신용 불량"이라고 예측합니다.
• 현실 변화: 사람들은 대출을 못 받자, "어차피 대출 안 해주면 뭐 해?"라며 신용카드를 쓰지 않거나, 반대로 "AI 가 나를 나쁘게 보게 하려고" 일부러 신용 점수를 조작합니다.
• 결과: 은행은 다음 달에 데이터를 다시 수집하면, "오, 사람들이 정말 신용이 나빠졌네!"라고 생각합니다. 그래서 AI 를 다시 학습시키고, 더 가혹한 모델을 만듭니다.

이렇게 예측이 현실을 바꾸고, 바뀐 현실이 다시 예측을 왜곡하는 악순환을 '수행적 예측 (Performative Prediction)'이라고 합니다. 기존 연구들은 이 악순환이 멈추려면 "사람들의 반응이 아주 부드럽고 예측 가능해야 한다"는 매우 까다로운 조건이 필요하다고 했습니다. 하지만 현실은 그렇지 않죠. (예: 0.1 점 차이로 대출이 거절되면 사람들은 갑자기 화를 내거나 행동을 완전히 바꿉니다.)

2. 이 논문의 핵심 발견: "혼합된 예측 (Mixing)"의 마법

이 논문의 저자들은 **"단 하나의 완벽한 모델을 찾으려 하지 말고, 여러 모델을 섞어서 사용하라"**는 놀라운 해결책을 제시했습니다.

🍲 비유: "요리사의 스프 시식"

• 기존 방식 (단일 모델): 요리사 (AI) 가 한 번에 큰 냄비 (전체 데이터) 를 다 끓여보고, "이 맛을 더 짜게 해야겠다"라고 생각하면 소금 한 숟가락을 넣고 다시 끓입니다. 하지만 손님이 그 소금 양에 따라 식성을 바꾸면, 요리사는 끝없이 소금을 넣고 뺐다를 반복하며 냄비가 터질 수도 있습니다.
• 이 논문의 방식 (혼합 모델): 요리사가 "오늘은 A, B, C 세 가지 레시피를 각각 33% 씩 섞어서 스프를 만들어보자"라고 생각합니다.
  • A 레시피를 쓴 손님은 약간 짜게 느끼고, B 는 적당히, C 는 싱겁게 느낍니다.
  • 중요한 점은 전체 스프의 평균 맛은 매우 안정적이라는 것입니다.
  • 손님들의 반응이 예측을 바꾼다 해도, "어떤 레시피를 썼든 전체 평균 맛은 최적"이라는 상태에 도달하게 됩니다.

이 논문의 결론은 **"어떤 알고리즘 (예: 경사 하강법) 을 쓰든, 그 알고리즘이 만들어낸 여러 단계의 모델들을 '섞어서' 사용하면, 그 혼합된 상태는 자연스럽게 안정된다"**는 것입니다.

3. 왜 이것이 중요한가요?

1. 조건이 필요 없습니다: 기존에는 "사람들의 반응이 아주 부드럽게 변해야 한다"는 가정이 필수였는데, 이 연구는 그런 가정이 전혀 없어도 안정된다는 것을 증명했습니다. 현실처럼 반응이 급격하게 변하는 상황 (예: 합격/불합격 기준선) 에서도 작동합니다.
2. 복잡한 수학 없이 해결: "이 모델이 최적이다"라는 단일 정답을 찾기 위해 복잡한 계산을 할 필요 없이, 그냥 알고리즘이 돌아가는 동안 나온 여러 모델들을 모아서 섞기만 하면 됩니다.
3. 악순환 방지: 이 방식은 AI 가 계속 변덕을 부리며 사회를 혼란스럽게 만드는 '달리는 루프 (Runaway Feedback Loop)'를 자연스럽게 멈추게 합니다.

4. 한 줄 요약

"완벽한 한 가지 정답을 찾으려 애쓰지 말고, 여러 가지 시도를 섞어서 사용하면, 그 '혼합된 상태'가 자연스럽게 사회와 가장 잘 어울리는 안정적인 균형점에 도달하게 됩니다."

이 연구는 인공지능이 사회와 상호작용할 때, 우리가 흔히 쓰는 학습 방법들 (경사 하강법 등) 이 사실은 이미 이 '안정화'를 위해 설계되어 있었다는 것을 밝혀냈습니다. 즉, 우리가 이미 알고 있는 도구들을 조금만 다르게 (모델들을 섞어서) 사용하면, 예측과 현실 사이의 혼란을 해결할 수 있다는 희망을 줍니다.

기술 요약

1. 문제 정의 (Problem Statement)

예측 수행성 (Performativity) 의 역설:
기존의 기계 학습은 데이터가 고정된 분포에서 독립적으로 동일하게 (i.i.d.) 추출된다고 가정합니다. 그러나 예측 수행성 (Performative Prediction) 프레임워크 (Perdomo et al., 2020) 에서는 배포된 예측 모델이 미래 데이터의 분포 자체를 변화시킵니다.

• 피드백 루프: 모델 $\theta$가 배포되면 데이터 분포 $D(\theta)$가 형성되고, 이 데이터로 다시 모델을 재학습 (Retraining) 하는 과정이 반복됩니다.
• 불안정성: 이러한 피드백 루프가 통제되지 않으면 모델이 계속 업데이트되어 "런어웨이 (runaway)" 현상이 발생할 수 있습니다.
• 기존 한계: 기존 연구들은 모델이 분포에 미치는 영향이 작고 매끄럽게 변한다는 강한 가정 (분포 맵 $D(\cdot)$의 Lipschitz 연속성, 손실 함수의 강한 볼록성 등) 하에서만 수렴을 증명했습니다. 특히 분포가 불연속적으로 변하거나 (예: 임계값 기반 의사결정), 손실 함수가 비볼록/비매끄러운 경우 안정성을 보장할 수 없었습니다. 최근 연구 (Anagnostides et al., 2026) 는 단일 안정 모델을 찾는 문제가 PPAD-완전 (PPAD-complete) 문제임을 보여주어, 일반적인 조건에서 단일 모델의 존재성이나 계산 가능성이 보장되지 않음을 시사했습니다.

2. 방법론 (Methodology)

이 논문은 온라인 최적화 (Online Optimization) 와 예측 수행성 사이의 깊은 연결을 규명합니다.

• 핵심 아이디어: 단일 결정론적 모델 대신 모델의 혼합 (Mixture of models) 을 고려합니다. 즉, 학습자가 매번 하나의 모델만 배포하는 것이 아니라, 학습 과정에서 생성된 모델 시퀀스 $\theta_1, \dots, \theta_T$에 대한 균일 분포 (Uniform distribution) 를 배포하는 것으로 접근합니다.
• 무회복 (No-Regret) 알고리즘 활용:
  • 온라인 학습 알고리즘 (예: Gradient Descent, Follow-the-Leader) 은 시간에 따라 손실 함수가 변하는 환경에서도 누적 손실이 최적의 고정 전략 대비 "회복 (Regret)"이 서브리니어 (sublinear, $o(T)$) 로 증가하도록 보장합니다.
  • 본 논문은 이러한 무회복 알고리즘의 시퀀스를 균일하게 혼합한 분포 $\mu$ 가 예측 수행적 안정성 (Performatively Stable) 을 만족함을 증명합니다.
• 증명 기법 (Martingale Argument):
  • 표준적인 "온라인 - 배치 (Online-to-Batch)" 변환 기법을 확장하여 사용합니다.
  • 핵심은 각 시간 단계 $t$에서 데이터 $z_t$가 고정된 분포가 아니라, 현재 모델 $\theta_t$에 의해 유도된 분포 $D(\theta_t)$에서 샘플링된다는 점입니다.
  • 마팅게일 (Martingale) 차이 시퀀스를 구성하여, 기대값 내에서 실제 손실과 기대 손실 간의 오차가 상쇄됨을 보여줍니다. 이를 통해 $D(\cdot)$의 연속성이나 Lipschitz 조건 없이도 수렴을 증명합니다.

3. 주요 기여 (Key Contributions)

1. 무조건적 환원 (Unconditional Reduction):

   • 어떤 무회복 (No-Regret) 알고리즘이든, 그 알고리즘이 생성한 모델 시퀀스의 균일 혼합 (Uniform Mixture) 은 예측 수행적 안정성을 가진다는 것을 증명했습니다.
   • 이는 $D(\cdot)$의 성질 (연속성, Lipschitz 상수 등) 에 대한 어떤 가정도 필요하지 않습니다 (Unconditional).

2. 혼합 모델 (Mixture) 을 통한 복잡성 장벽 우회:

   • Anagnostides et al. (2026) 의 부정적 결과 (단일 안정 모델 찾기가 PPAD-완전) 를 우회합니다.
   • 단일 모델이 아닌 혼합 분포를 안정성 해법으로 정의함으로써, 불연속적인 분포 맵이나 비볼록 손실 함수가 있는 경우에도 안정성을 보장할 수 있습니다.

3. 기존 알고리즘의 안정성 재해석:

   • 경사 하강법 (Gradient Descent), Follow-the-Leader (재학습) 등 널리 사용되는 알고리즘들이 예측 수행적 환경에서도 자연스럽게 안정화됨을 이론적으로 입증했습니다.
   • 특히 약한 볼록성 (Weakly convex) 이나 비매끄러운 (Non-smooth) 손실 함수, 그리고 유한 샘플 (Finite-sample) 환경에서도 안정성 보장을 확장했습니다.

4. 주요 결과 (Key Results)

주요 정리 (Theorem 3 - Informal):
온라인 알고리즘이 손실 시퀀스 $\ell_t(\theta) = \ell(z_t, \theta)$ (여기서 $z_t \sim D(\theta_t)$) 에 대해 서브리니어 회복 (Regret) 을 보장한다면, 생성된 모델 $\theta_1, \dots, \theta_T$의 균일 분포 $\mu$는 다음과 같이 $\text{Regret}(T)/T$-예측 수행적 안정성을 가집니다.

$$\mathbb{E}_{\theta \sim \mu} \mathbb{E}_{z \sim D(\theta)} [\ell(z; \theta)] \le \min_{\theta' \in \Theta} \mathbb{E}_{\theta \sim \mu} \mathbb{E}_{z \sim D(\theta)} [\ell(z; \theta')] + \frac{\text{Regret}(T)}{T}$$

구체적 적용 사례 (Corollaries):

• 재학습 (Retraining): Follow-the-Leader 알고리즘을 사용할 경우, $\tilde{O}(\log T / T)$ 수렴 속도로 안정성을 보장합니다.
• 경사 하강법 (Gradient Descent):
  • 볼록 손실 함수: $O(1/\sqrt{T})$ 수렴.
  • 강한 볼록 손실 함수: $O(\log T / T)$ 수렴.
  • 기존 연구와 달리 $D(\cdot)$의 Lipschitz 조건이나 $\rho < 1$ (수렴 조건) 이 필요하지 않습니다.
• 일반적인 손실 함수 (Log Loss, Squared Loss): Online Newton Step 알고리즘을 적용하여 $\tilde{O}(1/T)$ 속도로 안정성을 달성할 수 있음을 보였습니다.

5. 의의 및 중요성 (Significance)

1. 이론적 확장: 예측 수행성 연구의 적용 범위를 크게 확장했습니다. 기존에 "불가능"하거나 "불연속"으로 간주되었던 영역 (예: 의료/교육에서의 임계값 기반 의사결정, 전략적 분류 등) 에서도 안정적 해법을 찾을 수 있음을 보였습니다.
2. 실천적 통찰: 왜 실제 사회 시스템에서 널리 사용되는 학습 알고리즘 (경사 하강법 등) 이 무한한 피드백 루프를 생성하지 않고 안정화되는지에 대한 이론적 근거를 제공합니다. 이는 알고리즘이 내재적으로 균형을 맞추는 성질을 가짐을 시사합니다.
3. 새로운 연구 방향: 온라인 최적화와 예측 수행성 (Performativity) 간의 연결 고리를 확립하여, 향후 다중 에이전트 (Multi-agent) 환경이나 상태 의존적 (Stateful) 환경에서의 안정성 연구에 대한 토대를 마련했습니다.

결론적으로, 이 논문은 예측 수행적 환경에서 단일 모델의 안정성을 찾는 것이 어렵더라도, 무회복 온라인 알고리즘을 통해 생성된 모델들의 혼합 (Mixture) 을 배포함으로써 어떤 조건에서도 안정성을 보장할 수 있음을 증명함으로써 해당 분야의 패러다임을 바꾸는 중요한 업적입니다.