FEDERATED OPTIMIZATION IN HETEROGENEOUS NETWORKS

원문 : https://arxiv.org/pdf/1812.06127.pdf 

 

연합 학습(FL)은 기존의 분산 최적화 및 훈련과 차별화되는 크게 두 가지 주요 특징이 있는 분산 학습 패러다임입니다. 

이는 System 이질성과 non-IID Issue 입니다.

이 페이퍼에서는 FedProx라는 프레임워크를 도입하여 연합 네트워크의 이질성을 해결하고자 합니다.

 

FedProx는 연합 학습의 SOTA인 FedAvg의 다양성에 의한 일반화 및 재매개변수화로 볼 수 있습니다.

 

이 재매개변수화는 기존의 AVG scheme 방법 자체를 약간 수정하지만 이 수정은 이론과 실제 모두에서 중요한 영향을 미칩니다.

 

이론적으로 우리는 동일하지 않은 분포(통계적 이질성)에서 데이터를 학습할 때 그리고 각 참여 장치가 가변적인 작업량(시스템 이질성)을 수행하도록 허용함으로써 장치 수준에서의 시스템 제약 조건을 가진 채로 프레임워크에 대한 수렴 보장을 제공합니다.

 

실질적으로 FedProx가 현실적인 연합 데이터 세트 전체에서 FedAvg보다 더 유연한 수렴을 수행한다고 저자들은 주장합니다. 특히 매우 이질적인 환경에서 FedProx는 FedAvg에 비해 훨씬 더 안정적이고 정확한 수렴 동작을 보입니다.

 

목적함수

Proximal Term

 

 

client 훈련과정에서 local function 대신 Proximal term을 추가한 목적함수를 제안 합니다.

그리고 이 근사 항을 최소화 하는 과정에서 local model의 가중치가 global model의 최종 수렴을 위한 방향에서 크게 멀어지는 것을 방지합니다. 

 

Algorithm

FedProx(알고리즘 2)는 각 라운드에서 장치의 하위 집합이 선택되고 로컬 업데이트가 수행된 다음 이러한 업데이트의 평균을 구해 글로벌 업데이트를 형성한다는 점에서 FedAvg와 유사합니다. 그러나 FedProx는 알고리즘에서와 같이 간단한 수정을 통해 상당한 실질적 개선을 가져오고 global model에 대한 수렴 보장을 제공합니다.

먼저 FedProx는 Partial local update를 용인합니다. 이전에 논의한 다른 post에서와 같이 연합 네트워크의 서로 다른 Edge 장치는 종종 컴퓨팅 하드웨어, 네트워크 연결 및 배터리 수준 측면에서 서로 다른 리소스 제약 조건을 갖습니다.

 

따라서 FedAvg에서와 같이 각 장치가 균일한 양의 작업(즉, 동일한 수의 로컬 에포크 E를 실행)을 수행하도록 하는 것은 비현실적입니다.

FedProx에서는 사용 가능한 시스템 리소스를 기반으로 여러 장치에서 로컬로 수행되는 다양한 작업량을 허용하여 FedAvg를 일반화한 다음 낙오자에서 보낸 부분 솔루션을 집계합니다(이러한 장치를 삭제하는 것과 대비 더 많은 client를 집계 할 수 있음).

 

즉, 훈련 프로세스 전체에 걸쳐 모든 장치에 대해 균일한 γ를 가정하는 대신 FedProx는 다른 장치와 다른 반복에서 변수 γ를 암시적으로 수용합니다.

하지만 장치 간에 수행되는 불균일한 양의 작업을 다수번 허용하면 시스템 이질성의 부정적인 영향 (Partial Aggregation)을 완화하는 데 도움이 될 수 있지만 너무 많은 로컬 업데이트의 이질적인 존재는 여전히 (잠재적으로) 근본적인 방향의 상이로 인해 global model을 다른 방향으로 수렴 시킬 수 있습니다.

 

이에 변수 로컬 업데이트의 영향을 효과적으로 제한하기 위해 로컬 하위 문제에 Proximal term을 위와 같이 삽입해 가중치의 발산을 제한 합니다. 특히 로컬 함수 Fk(·)를 최소화하는 대신 장치 k는 지정된 목적함수를 사용하여 최소화합니다.

 

Experiment Result

 

 

 

실험 결과 FedProx는 이기종 네트워크에서 FedAvg에 비해 상당한 수렴 개선을 가져옵니다. 

 

구체적으로 0%, 50% 및 90% 장치가 낙오자가 되도록 강제하여 다양한 수준의 시스템 이질성을 시뮬레이션했습니다.(FedAvg에 의해 삭제됨).

(1) FedAvg와 FedProx(μ = 0)를 비교할때 다양한 횟수의 local update를 수행하도록 허용하면 시스템 이질성이 존재할 때 수렴에 도움이 될 수 있음을 알 수 있습니다.

 

(2) FedProx(μ = 0)와 FedProx(μ > 0)를 비교하여 추가된 Proximal term의 이점을 보여줍니다.

 

μ > 0인 FedProx는 시스템 이질성이 있는 경우(50% 및 90% 낙오자)와 시스템 이질성이 없는 경우(0% 낙오자) 둘 다에서 보다 안정적인 수렴을 유도합니다.

 

μ = 0이고 시스템 이질성(스트래글러 없음)이 없는 FedProx는 FedAvg에 해당합니다. 

다음은 데이터 이질성이 수렴에 미치는 영향입니다. 

 

실험에서 각 장치가 같은 양의 local update를 실행하도록 강제함으로써 시스템 이질성의 영향을 제거합니다.

 

이 설정에서 μ = 0인 FedProx는 FedAvg로 전환됩니다.

 

(1) 상단: 왼쪽에서 오른쪽으로 통계적 이질성이 증가하는 4개의 합성 데이터 세트에 대한 훈련 손실을 보여줍니다.

 

μ = 0인 방법은 FedAvg에 해당합니다. 이질성이 증가하면 수렴이 악화되지만 μ > 0을 설정하는것으로 수렴저하를 방지하는 데 도움이 될 수 있습니다.

 

(2) 하단 행: 4개의 합성 데이터 세트의 해당 비유사성 측정(그라데이션 분산)을 표시합니다. 

 

결론

 

이 페이퍼는 연합 네트워크에 내재된 시스템 및 통계적 이질성을 해결하는 최적화 프레임워크인 FedProx를 제안합니다.

FedProx는 다양한 양의 작업을 여러 장치에서 로컬로 수행할 수 있도록 하며 proximal term를 사용하여 수렴을 안정화합니다.

 

시스템 이질성 가정 하에 현실적인 연합 설정에서 FedProx에 대한 수렴 보장을 제공하는 동시에 낙오자와 같은 실제 문제도 고려했습니다. 

 

하지만 Straggler의 훈련 데이터에 대한 공정성이나 훈련 과정에서 임의의 client에 bias 될 수 있는 가능성이 열려 있습니다.