Communication-Efficient Federated Online Decision-Making with Stateful Costs

기술 요약: 상태 의존적 비용을 갖는 통신 효율적 페더레이션 온라인 의사결정

문제 정의
본 논문은 의사결정이 진화하는 운영 상태를 유발하고, 비용이 결과적인 상태 궤적에 따라 발생하는 시스템에서 페더레이션 온라인 의사결정의 과제를 다룬다. 점별 목적 함수를 최적화하는 표준 페더레이션 학습이나 완전 정보를 가정하는 전통적인 온라인 제어와 달리, 이 설정은 중앙 서버와 $N$ 개의 클라이언트가 희소 블록 기반 동기화 및 부분 클라이언트 참여 하에 운영되는 것을 포함한다.

핵심 어려움은 통신 제약과 시스템 동역학 간의 상호작용에서 비롯된다:

1. 상태 의존적 비용: 시간 $t$ 의 비용 $c_t(\chi_t, u_t)$ 는 시스템 상태 $\chi_t$ 에 의존하며, 이 상태는 선형 동역학 $\chi_{t+1} = A\chi_t + Bu_t + Ed_t$ 에 따라 진화한다.
2. 희소 통신: 의사결정은 블록 경계 (매 $K$ 라운드) 에서만 업데이트된다. 블록 내에서는 의사결정 $u_t$ 가 고정된 채 유지된다 ($u_t = \bar{u}_b$).
3. 궤적 불일치: 운영 시스템은 연속적으로 진화하는 반면, 블록 내에서는 의사결정이 정적 상태로 유지되므로, 부패한 (stale) 의사결정은 라운드별 최적 의사결정이 이끌었을 궤적과 다른 상태 궤적을 시스템에 유발한다. 이는 누적된 비용 발생을 변화시킨다.
4. 동적 후회 (Dynamic Regret): 성능은 총 변동 예산 $V_T$ 내에서 매 라운드 변할 수 있지만 희소 통신 프로토콜에 의해 제약받지 않는 경로 길이 제한 비교자 시퀀스 $u^\star_{1:T}$ 에 대해 측정된다.

본 논문은 동적 후회를 온라인 알고리즘의 실현된 궤적이 발생시킨 누적 비용과 사후에 고려할 때 모든 허용 가능한 비교자 시퀀스로 달성 가능한 최소 누적 비용 간의 차이로 정의한다.

방법론: BLADE
저자들은 BLADE(Dynamic Execution 을 위한 블록별 국소 근사) 를 제안한다. 이는 투영된 블록별 페더레이션 온라인 의사결정 방법이다. 알고리즘은 다음과 같이 작동한다:

• 블록 기반 업데이트: 시간 범위는 길이 $K$ 의 블록으로 나뉜다. 서버는 해당 블록의 모든 라운드에 배포되는 블록 반복자 $\bar{u}_b$ 를 유지한다.
• 유한 메모리 대리 모델: 전체 기록 없이 비용의 상태 의존적 특성을 처리하기 위해, BLADE 는 상태의 유한 메모리 근사를 활용한다. 이는 메모리 창 $H$ 내의 모든 동작이 현재 후보 의사결정 $u$ 라고 가정하는 "대각선 대리 상태" $\bar{\chi}_t(u)$ 를 정의한다.
• 국소 분해: 대각선 대리 비용은 국소적으로 분해 가능한 형태, $c_t(\bar{\chi}_t(u), u) = \frac{1}{N}\sum c_{i,t}(u)$ 를 가진다고 가정하여, 클라이언트들이 국소 기울기를 계산할 수 있게 한다.
• 부분 참여: 각 블록의 끝에서 $m$ 개의 클라이언트 부분집합이 샘플링되어 블록 전체에 걸친 기울기 합을 계산하여 반환한다. 서버는 투영된 기울기 단계를 통해 다음 블록 반복자를 업데이트한다:
  $$\bar{u}_{b+1} = \Pi_Z \left( \bar{u}_b - \eta_B \frac{1}{m} \sum_{i \in S_b} \sum_{t \in I_b} \nabla c_{i,t}(\bar{u}_b) \right)$$

주요 기여

1. 문제 정의: 본 논문은 희소 통신이 최적화 오차뿐만 아니라 실현된 상태 궤적과 그 결과로 발생하는 비용에도 영향을 미치는 새로운 페더레이션 온라인 의사결정 문제를 공식화한다.
2. 알고리즘 설계: BLADE 를 도입하여 블록별 동기화, 유한 메모리 상태 근사, 그리고 부분 클라이언트 참여를 상태 의존적 비용을 위한 통합 프레임워크로 통합한다.
3. 이론적 분석: 저자들은 발생한 비용(대리 손실이 아님) 에 대한 동적 후회 상한을 유도한다. 이 상한은 오차 원천을 명시적으로 분리한다:
   • 투영된 온라인 하강에서 비롯된 최적화 오차.
   • 부분 참여에서 비롯된 샘플링 오차.
   • 블록 내에서 의사결정을 고정함으로써 발생하는 궤적 불일치 오차.
   • 유한 메모리 절단 오차.
4. 후회 보장: $K = \lceil \sqrt{T} \rceil$ 설정 하에서, 비교자 변동 $V_T = o(T^{1/4})$ 일 때 기대 동적 후회가 $T$ 에 대해 부분 선형임을 논문은 증명한다. 통신 복잡도는 $O(\sqrt{T})$ 임이 보인다.

결과 및 검증
이론적 상한은 제어된 합성 안정 선형 시스템에 대한 실험을 통해 검증된다. 실험은 이론이 예측한 메커니즘을 분리한다:

• 통신 - 후회 트레이드오프: 블록 길이 $K$ 를 증가시키면 통신 스칼라는 감소하지만 동적 후회는 증가하여, 이론적 트레이드오프를 확인한다.
• 메모리 길이: 메모리 창 $H$ 를 증가시키면 시스템 동역학의 기하학적 감쇠와 일치하게 절단 오차가 무시할 수 있을 때까지 후회가 감소한다.
• 부분 참여: 낮은 참여 비율 ($m/N$) 은 더 높은 샘플링 노이즈로 인해 후회를 증가시킨다.
• 외란 변동: 외부 외란의 변동이 클수록 동적 벤치마크의 특성상 예상대로 발생된 후회가 커진다.
• 시간 범위 스케일링: $K = \lceil \sqrt{T} \rceil$ 일 때 통신 비용은 $O(\sqrt{T})$ 로 스케일링되어 이론적 예측과 일치한다.

의의 및 주장
본 논문은 기존 통신 효율적 페더레이션 학습 연구가 주로 점별 목적 함수에 초점을 맞추는 반면, 동적 후회 문헌은 종종 통신 제약이나 상태 의존적 비용 생성을 무시한다고 주장한다. BLADE 는 희소 통신이 시스템의 상태 궤적을 근본적으로 변화시키는 간극을 다룬다.

저자들은 어려움이 단순히 기존 문제들의 결합이 아님을 강조한다. "블록 고정"된 의사결정은 궤적 수준의 비용 왜곡과 동적 비교자에 대한 블록 정렬 격차를 생성한다. 이러한 효과를 분리함으로써 BLADE 는 시스템 수준의 동적 후회를 제어하기 위한 실용적인 대리 모델 (대각선 대리 모델) 을 제공한다. 이 연구는 온라인 학습자가 희소 통신에 제약받고 메모리가 있는 시스템에서 행동해야 하더라도, 환경의 드리프트 ($V_T$) 가 너무 빠르지 않다면 부분 선형 동적 후회를 달성할 수 있음을 보여준다.