Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

기술 요약: 클러스터형 연합 학습을 위한 안정적이고 예산 실행 가능한 연합 형성

문제 정의
연합 학습(Federated Learning, FL) 시스템은 종종 통계적 이질성 문제로 인해 발생하며, 모든 참여자가 하나의 "거대 연합(grand coalition)"을 구성할 경우 최적이 아닌 모델을 생성하게 됩니다. 클러스터형 연방 학습(Clustered FL)은 호환 가능한 참여자들을 그룹화함으로써 통계적 측면을 해결하지만, 경제적 측면은 여전히 미개척 분야로 남아 있습니다. 구체적으로, 다음을 동시에 보장하는 프레임워크가 부족합니다:

1. 안정성(Stability): 참여자가 할당된 연합을 떠나 다른 연합으로 이동할 유인이 없거나(내쉬 안정성, Nash stability), 목적지 연합에 의해 거부되지 않아야 함(개별 안정성, Individual stability).
2. 예산 실행 가능성(Budget Feasibility): 조정자(coordinator)가 참여자들에게 보상하기 위해 필요한 이전을 재정적으로 지원할 때 적자를 발생시키지 않아야 함.
3. 효율성(Efficiency): 결과적으로 도출된 안정적인 분할(partition)이 전역 사회적 후생(global social welfare) 최적값에 근접해야 함.

기존의 접근 방식들은 안정성과 예산 제약을 별개로 취급하거나, 초과 합산성(superadditivity)을 가정하는 경우가 많으나, 이는 이질적이고 비볼록(non-convex)한 FL 환경에서는 성립하지 않습니다.

방법론
본 논문은 이 문제를 **이전 가능한 잉여(transferable surplus)를 가진 헤도닉 연합 형성 게임(hedonic coalition-formation game)**으로 모델링합니다.

• 시스템 모델: 참여자 $N$은 연합들로 분할됩니다. 각 연합 $S$는 가중치가 부여된 로컬 목적 함수를 사용하여 연합별 모델 $\theta_S$를 학습합니다. 이 모델은 통신 실패(업데이트 누락)를 안전한 집계 규칙(safe-aggregation rule)을 통해 처리하며, 업데이트가 도착하지 않으면 모델을 변경하지 않은 상태로 유지합니다.
• 경제 모델:
  • 잉여(Surplus): 총 이전 가능한 잉여 $W(S)$는 기대 학습 이득 $B(S)$에서 조정자 비용 $C_0(S)$와 참여자 비용 $d_i(S)$를 뺀 값으로 정의됩니다.
  • 이전(Transfers): 조정자는 참여자에게 이전 금액 $t_i(S)$를 지급합니다. 참여자의 효용은 $U_i(S) = t_i(S) - d_i(S)$입니다.
  • 예산 실행 가능성: 할당 규칙이 모든 형성된 연합에서 조정자가 비음의 잉여($R_0(S) \ge 0$)를 보유한다면 *약한 예산 실행 가능성(weakly budget feasible)*을 갖는다고 합니다.
• 헤도닉 선호도: 선호도는 잉여를 효용으로 변환하는 할당 규칙에 의해 유도됩니다. 본 논문은 참여자의 효용이 연합 내 다른 모든 구성원 $j \in S$와의 쌍별 가치(pairwise values) $v_{ij}$의 합인 **대칭적 쌍별 잉여 할당(symmetric pairwise surplus allocations)**에 초점을 맞춥니다.
• 게임 이론적 분석:
  • 저자들은 대칭적 쌍별 할당이 **정확한 포텐셜 게임(exact potential game)**을 유도함을 증명합니다. 여기서 포텐셜 함수는 연합 내 쌍별 가치의 합입니다.
  • 이러한 구조는 **내쉬 안정적 분할(Nash-stable partition)**의 존재를 보장하며, 엄격한 최적 응답(strict better-response) 이동 시퀀스가 유한한 단계 내에 종료됨을 보장합니다.
  • 진입자가 목적지 구성원의 동의를 얻어야 하는 개별 안정성(Individual Stability) 또한 분석되었으며, 쌍별 가치가 비음수일 경우 내쉬 안정성이 개별 안정성을 함의함을 보여줍니다.
• 후생 및 효율성:
  • 사회적 후생는 참여자 효용(포텐셜 함수와 연결됨)과 조정자가 보유하는 여유분(slack)으로 분해됩니다.
  • 논문은 정확한 예산 균형(exact budget balance)(보유 여유분이 0인 상태)이 잉여가 정확히 쌍별로 표현 가능한 경우에만 후생 최적의 내쉬 안정적 분할을 생성함을 밝힙니다.
  • 정확한 표현이 불가능할 경우, 예산 실행 가능성만으로는 후생 손실이 무제한이 될 수 있습니다. 그러나 보유 여유분이 최적값에 비해 유계(bounded)인 경우, 곱셈적 효율성 보장(Price of Stability)이 도출됩니다.
  • 전역 포텐셜 극대화는 **가중 최대 일치 상관 클러스터링(weighted maximum-agreement correlation clustering)**과 동일함을 보여줍니다. 논문은 다음과 같은 파이프라인을 제안합니다: 클러스터링을 근사하고, 그 다음 엄격한 최적 응답 안정화를 적용하여 근사 보장을 유지하면서 안정적인 분할에 도달합니다.
• 검증: 보유 여유분 함수가 서브모듈(submodular)인 경우, 다수의 예산 제약을 다항 시간 오라클로 검증할 수 있음을 제공합니다.

주요 기여

1. 모델링: 업데이트가 정의되지 않은 집계를 생성하지 않고 성공적인 통신 라운드를 처리하며, 초과 합산성을 가정하지 않는 연합별 FL 모델을 도입했습니다.
2. 경제적 분리: 학습 이득, 비용, 이전, 그리고 조정자가 보유하는 잉여를 명시적으로 분리하여 예산 실행 가능성과 개인적 합리성에 대한 조건을 도출했습니다.
3. 안정성 보장: 대칭적 쌍별 할당이 정확한 포텐셜 게임을 생성함을 증명하여, 내쉬 안정적 및 개별 안정적 분할의 존재와 유한한 수렴을 보장합니다.
4. 효율성 경계: 조정자가 보유하는 여유분과 후생 효율성 사이의 관계를 규명했습니다. 정확한 균형이 특정 클래스의 잉여에서만 최적 안정성을 제공함을 입증하고, 상대적으로 유계된 여유분이 타이트한 곱셈적 효율성 경계를 제공함을 보여줍니다.
5. 계산 복잡도: 전역 포텐셜 극대화를 상관 클러스터링(NP-난해)과 연결하고, 근사 및 안정화 파이프라인을 통한 엔드 투 엔드 후생 보장을 도출했습니다.
6. 검증: 보유 여유분이 서브모듈인 경우 지수적으로 많은 예산 제약을 다항 시간 오라클 시간 내에 검증할 수 있음을 보여줍니다.
7. 실험적 검증: $n=4$인 CIFAR-10 데이터셋에 대해 사전 등록된 연구를 수행했습니다.

실험 결과
본 연구는 이질적인 분포를 가진 CIFAR-10 데이터의 5개 시드에 대해 메커니즘을 평가합니다:

• 후생 최적성: "양호한(benign)" 캘리브레이션에서, 분산형 메커니즘은 5개 시드 모두에서 **인증된 추정 테이블 후생 최적값(certified estimated-table welfare optimum)**에 도달했습니다. 실험적 안정성 가격(Price of Stability)은 정확히 1이었습니다.
• 베이스라인 대비 안정성: 반면, "동등 잉여 공유(equal-surplus sharing)" 베이스라인은 5개 시드 중 3개에서 내쉬 안정적 결과를 생성하는 데 실패했습니다(내쉬 안정적 집합이 존재하지 않았고 역학 관계가 순환함).
• 수렴: 분산형 최적 응답 과정은 다양한 초기화 상태로부터 빠르게 수렴했습니다(평균 1.53 회의 이동).
• 민감도: "빈약한(lean, 비용 민감)" 캘리브레이션에서는 안정성 비용이 증가하였고(Price of Stability 최대 1.29), 최적 분할이 추정 오류에 민감해졌으며, 이는 예산 타이트함과 안정성 사이의 트레이드오프를 강조합니다.
• 추정: 쌍별 검증 이득(PVG) 추정치는 그레디언트 정렬(gradient alignment)보다 훨씬 더 신뢰할 수 있는 쌍의 부호를 제공했습니다(그레디언트 정렬은 위양성 발생에 취약함).

의의 및 주장
본 논문은 국소적 평형, 전역적 최적성, 그리고 계산적 용이성을 혼동하지 않으면서 학습 가치, 화폐 이전, 안정성, 그리고 경제적 효율성을 연결한다고 주장합니다.

• 이론적 측면: 내쉬 평형을 국소 포텐셜 최적값으로 올바르게 해석하고 초과 합산성을 가정하지 않음으로써 기존 연구의 한계를 바로잡습니다. 또한 안정성과 효율성이 조정자의 보유 여유분에 의해 연결된 별개의 개념임을 확립합니다.
• 실무적 측면: 제안된 메커니즘은 이질적인 FL 참여자들을 조직하기 위한 증명 가능한 안정적이고 예산 실행 가능한 방법을 제공합니다. 실험 결과는 단순한 잉여 분할 규칙은 안정화에 실패할 수 있지만, 제안된 쌍별 포텐셜 접근 방식은 후생 최적값과 일치할 수 있는 안정적인 상태로의 수렴을 보장한다는 것을 보여줍니다.
• 한계점: 저자들은 현재 모델이 비용과 이득을 알고 있거나 추정한다고 가정하고 있음(인센티브 할당이지 진실한 메커니즘 설계가 아님)을 언급합니다. 실험적 검증은 정확한 열거 및 인증을 위해 $n=4$로 제한되었으며, 결과는 실험의 추정된 가치 테이블에 특화되어 있습니다.

본 연구는 정확한 예산 균형이 일반적으로 후생 최적성을 보장하지는 않지만, 제안된 프레임워크가 클러스터형 연합 학습에서 안정적이고 예산 실행 가능한 연합 형성을 위한 견고한 이론적 토대와 실용적인 메커니즘을 제공한다는 결론을 내립니다.