기술 요약: 최대 상대적 개선(Maximin Relative Improvement)으로서의 협상 문제

1. 문제 정식화

본 논문은 여러 하위 집단(그룹)에 걸쳐 단일 통합 예측기를 배포할 때 발생하는 도전 과제를 다룹ุ니다. 즉, 한 그룹을 최적화하면 다른 그룹의 성능이 저하되는 문제를 다룹니다. 그룹 DRO(Group DRO)나 최소 후회(Minimax Regret)와 같은 기존 방식들은 리스크나 후회의 절대적 비교에 의존합니다.

저자들은 그룹 간에 고유한 예측 가능성(베이스라인으로부터 최적의 예측기까지 도달 가능한 '잠재적 개선 폭')이 다를 때 절대적 기준이 실패한다고 주장합니다. 만약 그룹 A는 개선 잠재력이 크고 그룹 B는 작다면, 절대적 최소 후회(minimax regret) 방식은 그룹 A의 절대적 후회를 최소화하기 위해 모델 용량의 거의 전부를 그룹 A에 할당할 수 있으며, 이로 인해 그룹 B의 성능이 베이스라인보다 더 나빠질 수 있습니다. 이는 신호 대 잡음비(signal-to-noise ratio)가 서로 다른 그룹 간에 단위당 절대적 리스크 감소가 동일한 의미를 갖지 않기 때문에 발생합니다.

2. 방법론: 협상 문제로서의 공정 학습

협상 프레임워크

저자들은 그룹 공정성을 하위 집단 간의 **협력적 협상 문제(cooperative bargaining problem)**로 재구성합니다.

• 플레이어: 하위 집단(그룹).
• 불일치 지점($d$): 베이스라인 예측기 $f_0$(예: 회귀에서의 무조건적 평균 또는 분류에서의 다수 클래스)에 의해 발생하는 리스크. 이는 그룹들이 협력에 실패했을 때의 결과를 나타냅니다.
• 이상적 지점($u^{max}$): 각 그룹에 대한 그룹별 최적 예측기 $f^*_g$에 의해 발생하는 리스크.
• 가용 집합(Feasible Set): 함수 클래스 $\mathcal{F}$에 의해 유도되는 달성 가능한 리스크 벡터의 집합 $\mathcal{R}(\mathcal{F})$.

최적화는 각 그룹이 자신의 개별 최적값으로부터 일부 성능을 희생하여 상호 수용 가능한 해결책에 도달하는 타협점을 찾습니다.

상대적 개선 기준

본 논문은 **상대적 개선($\rho_g$)**을 공정성 지표로 제안합니다. 그룹 $g$에 대해, 이는 예측기 $f$에 의해 달성된 실제 리스크 감소량을 최대 가능한 리스크 감소량(베이스라인과 그룹별 최적 예측기 사이의 격차)으로 나눈 비율로 정의됩니다:

$$\rho_g(f) = \frac{R_g(f_0) - R_g(f)}{R_g(f_0) - R_g(f^*_g)}$$

제안된 학습 목적 함수는 **최대 상대적 개선(Maximin Relative Improvement, MMRI)**입니다:
$$f_{RI} = \arg \max_{f \in \mathcal{F}} \min_{g \in \mathcal{G}} \rho_g(f)$$

이론적 연결: 칼라이-스모로딘스키(Kalai–Smorodinsky) 해법

저자들은 MMRI 기준이 정확히 칼라이-스모로딘스키(KS) 협상 해법(Kalai & Smorodinsky, 1975)에 해당함을 입증합니다.

• 기하학적 해석: 효용 공간(효용은 음의 리스크임)에서 KS 해법은 모든 플레이어에 대해 불일치 지점으로부터의 상대적 이득을 동일하게 만드는 파레토 최전선(Pareto frontier) 상의 유일한 점입니다.
• 공리적 정당화: KS 해법은 다음 네 가지 공리에 의해 고유하게 특징지어집니다:
  1. 파레토 최적성 (Pareto Optimality, PO): 다른 그룹을 해치지 않고는 어떤 그룹도 개선할 수 없음.
  2. 대칭성 (Symmetry, SYM): 동일한 가용 집합과 불일치 지점을 가진 그룹은 동등하게 취급됨.
  3. 척도 불변성 (Scale Invariance, SI): 효용 척도의 아핀 변환(affine transformation)에 대해 불변함 (서로 다른 예측 가능성을 가진 그룹 간의 비교 시 매우 중요).
  4. 개별 단조성 (Individual Monotonicity, IM): 다른 그룹의 최적값이 고정된 상태에서 가용 집합이 확장되면, 어떤 그룹도 해를 입지 않음.

논문은 $m=2$인 경우 MMRI가 네 가지 공리를 모두 만족함을 증명합니다. $m > 2$인 경우, 유일성과 파레토 최적성을 보장하기 위해 렉시민(leximin) 정교화(사전식 최대값 방식)를 활용하여 수정된 버전의 공리들을 만족합니다.

기존 방법론과의 비교

본 논문은 기존의 강건 최적화(robust optimization) 방법들을 다른 고전적 협상 해법들과 매핑합니다:

• Group DRO (Minimax Risk): 로스(Rawlsian) 해법(최소 절대 효용을 최대화)에 해당합니다.
• Maximin Explained Variance: 에갈리테리언(Egalitarian) 해법(불일치 지점으로부터의 절대적 이득을 동일하게 함)에 해당합니다합니다.
• Minimax Regret: 동일 손실(Equal Loss) 해법(이상적 지점으로부터의 절대적 편차를 동일하게 함)에 해당합니다.

MMRI와 달리, 이러한 방법들은 일반적으로 척도 불변성이 결여되어 있어, 그룹 간 예측 가능성이 이질적일 때 발생하는 실패 모드(failure modes)를 초래합니다.

적정성(Well-Posedness) 및 수렴성

저자들은 가용 리스크 집합 $\mathcal{R}(\mathcal{F})$가 컴팩트(compact)하고 그 볼록 껍질(convex hull)이 비실현 가능한 파레토 최적점을 포함하지 않는다는 조건을 확립함으로써, 학습 문제가 잘 정의된(well-posed) 협상 문제를 유도함을 검증합니다. 이러한 조건은 다음의 경우에 성립합니다:

• 파라미터 설정(볼록 컴팩트 파라미터 공간, 볼록 연속 손실 함수).
• 비파라미터 RKHS 설정(볼록 컴팩트 함수 클래스, 연속 평가 맵).

또한, 본 논문은 표준적인 정칙성 조건(Lipschitz 손실, 엔트로피 조건) 하에서 경험적 최대 상대적 개선 추정량의 유한 샘플 수렴 속도가 $O(1/\sqrt{n})$임을 입증하여, 후회 기반 방법들과 일치함을 보여줍니다.

3. 주요 기여

1. 공정성 기준으로서의 상대적 개선: 그룹 특유의 예측 가능성에 의해 리스크 감소량을 정규화하여, 서로 다른 고유 예측성을 가진 그룹 간의 비교 가능성을 보장하는 지표를 제안합니다.
2. 통합 협상 프레임워크: 기존의 강건한 공정 학습 방법들(Group DRO, Minimax Regret 등)이 특정 고전적 협상 해법과 동일함을 보여줌으로써, 이들의 규범적 약속에 대한 공리적 비교를 가능하게 합니다.
3. 공리적 특징 규명: MMRI가 파레토 최적성, 대칭성, 척도 불변성, 그리고 개별 단조성(또는 $m>2$를 위한 렉시민 정교화)을 만족하는 유일한 해임을 증명합니다.
4. 해악 방지 보장(No-Harm Guarantee): 베이스라인 예측기가 함수 클래스 내에 존재할 경우($f_0 \in \mathcal{F}$), MMRI 솔루션은 어떤 그룹도 베이스라인보다 성능이 나빠지지 않음을 보장하며(개별 합리성), 이는 Minimax Regret가 위반하는 성질입니다.
5. 유한 샘플 보장: 경험적 추정량의 수렴 속도를 제공합니다.

4. 실험 결과

저자들은 2018년 미국 지역사회 조사(ACS) 데이터를 사용하여, 50개 주를 대상으로 로그 변환된 소득을 예측하며 다양한 파티션(성별, 인종) 및 기능(연령, 교육, 혼인 상태, 가구 형태)을 평가했습니다.

• 비대칭성 관찰: 연구는 차등적 예측성이 널리 퍼져 있음을 발견했습니다. "격차 비율"(잠재적 개선 폭 사이의 비율)은 0.04에서 3.48 사이의 범위를 가집니다. 73%의 구성에서 비대칭성은 중등도에서 극심한 수준이었으며, 인종 파티션의 경우 가구 형태에 대해 86%의 주가 극심한 비대칭성을 보였습니다.
• 성능 비교:
  • Minimax Regret (MMR): 높은 비대칭성이 있는 경우(예: 노스다코타, 인종 파티션, 연령 기능), MMR은 높은 잠재적 개선을 가진 그룹에 거의 모든 모델 용량을 할당하여, 다른 그룹의 성능이 베이스라인보다 더 나쁘게 나타납니다(예: -74% 상대적 개선).
  • Maxism Relative Improvement (MMRI): 일관되게 그룹 간 상대적 개선을 균등하게 맞춥니다(예: 노스다코타 예시에서 두 그룹 모두 57%를 달성). 이는 덜 예측 가능한 그룹에 대한 "해악"을 방지합니다.
  • 기타 방법들: Group DRO와 Maximin Explained Variance 역시 비대칭적인 설정에서는 동일한 상대적 개선 선에서 벗어나는 모습을 보입니다.

5. 의의 및 주장

본 논문은 공정성을 협상 문제로 해석하는 것이 공정성 기준을 선택하는 데 있어 원칙적이고 공리적인 토대를 제공한다고 주장합니다.

• 척도 불변성의 중요성: 저자들은 그룹 간 고유 예측성이 다를 때, 추출되는 신호의 분량을 불평등하게 가져가는 것을 피하기 위해 척도 불변 기준(KS/상대적 개선과 같은)이 필수적이라고 주장합니다.
• 의사결정 가이드: 이 프레임워크는 특정 기준이 보편적으로 우월하다고 주장하지 않습니다. 대신, 이는 의사결정 가이드 역할을 합니다. 실무자는 어떤 공리(예: 척도 불변성 vs. 강한 단조성)가 자신의 맥락에 가장 적합한지 식별해야 합니다. 그룹 간 예측성이 이질적이라면, MMRI의 공리적 특성이 자연스러운 선택이 됩니다.
• 이론적 가교: 이 연구는 협력 게임 이론과 공정 학습을 연결하며, 표준적인 학습 가정(컴팩트성, 볼록성)이 ad-hoc적인 페널티 선택 없이도 고전적 협상 해법을 머신러닝에 도입하기에 충분함을 증명합니다.

저자들은 많은 그룹에 대한 렉시민 솔루션을 찾는 계산 복잡도와, 엄격한 볼록성이 깨지거나 표준적인 복잡도 제어가 실패할 수 있는 과잉 매개변수화(overparameterized) 영역으로의 확장 문제를 한계점으로 언급했습니다.