Abstract

Federated learning (FL)은 machine learning setting 방법 중 하나로, 그 목적은 좋은 성능의 centralized model을 학습시키는 것이다. 이때, 학습 데이터는 각각 불안정하고 상대적으로 느린 네트워크 연결을 가진 많은 clients에 걸쳐 분포되어 있어야 한다.

논문에서 생각한 learning 알고리즘은 위의 setting 하에서, 각 client가 round마다 독립적으로 local data를 이용하여 현재 모델에 대한 update를 계산하고 이를 central server에 전송하는 방식으로, 이렇게 모인 update들은 새로운 global model을 계산하기 위해 합쳐져 사용된다. 여기서 일반적으로 clients는 mobile phone을 의미하고, 통신의 효율성이 가장 중요하게 고려된다.

본 논문에서는 uplink communication costs를 줄이기 위한 두 가지 방법을 제시한다.

1. Structured updates
   적은 수의 변수를 사용하여 parameterized된 제한된 space로부터 직접 update를 학습하는 방식.
   e.g. low-rank 혹은 random mask

2. Sketched updates
   Full model update를 학습하여 서버에 전송하기 전에 quantization, random rotations, subsampling 등의 기법들을 함께 사용해 압축하는 방식.

실험은 convolutional, recurrent networks에 대해 모두 진행되었는데, 이를 통해 제안한 방식이 communication cost를 거의 100배 수준으로 줄일 수 있다는 것을 보였다.

Introduction

Dataset이 점차 커지고 model은 점점 복잡해짐에 따라, 다양한 machine들에 걸쳐 model parameter를 최적화하는 것이 machine learning (ML) model의 학습에 요구되고 있다. 이미 존재하는 ML 알고리즘은 data가 여러 장치들에 대해 balanced, i.i.d.의 방식으로 분배되어 있는 highly controlled 환경에 맞춰 설계되어 있는데, 최근 federated learning(과 그와 관련된 탈중앙화 접근 방식)은 이를 대체하는 setting으로 제안되고 있다.

FL에는 보통 매우 많은 수의 devices(clients)가 참여하고, 느리고 불안정한 internet 연결을 가진다. FL은 공유하고 있는 예측 model에 대해 mobile device들이 함께 학습 할 수 있게 해주고, cloud에 data를 저장할 필요 없이 ML을 할 수 있게 만들어준다. 이는 기존에 사용하던 distributed ML(논문 참조)과 다른데, 매우 많은 client들의 존재와 각각이 지닌 data가 매우 unbalanced, non-i.i.d.한, 또한 상대적으로 나쁜 network 연결 환경을 가정하고 있기 때문이다.

본 논문에서는 마지막 constraint에 초점을 맞추고 있는데, 이러한 unreliable하고 asymmetric한 연결은 현실적인 FL에 대해 특히 까다롭기 때문이다.

간단하게, 우리는 일반적인 round가 다음과 같이 구성되는 FL의 동기화 된 알고리즘을 고려한다.

1. 존재하는 clients들에 대해, 현재 model을 다운받는 subset이 선택된다.
2. Subset에 속한 각 client는 자신이 가진 local data를 바탕으로 updated model을 계산한다.
3. Model의 update는 선택된 clients로부터 server에 전송된다.
4. Server는 이러한 model들을 (보통 평균내) 취합하여 개선된 global model을 만들어낸다.

위의 framework의 단순한 구현은 각 clients가 full model(or update)를 round마다 server로 돌려보내는 것을 필요로한다. 이 단계는 다양한 요인들로 인하여 large model에 대해서는 FL의 bottleneck이 될 수 있는데, 그러한 요인 중 하나는 internet 연결 속도의 asymmetric한 특성이다.

일반적으로 uplink는 downlink에 비해 훨씬 느리다. 미국의 평균 broadband speed를 보면 download는 $55.0\textrm{M}bps$, upload는 $18.9\textrm{M}bps$ 이다. (일부 service에서는 더 불균형이 심함)

게다가 기존에 존재하는 model 압축 방식은 현재 model을 다운 받기 위해 필요한 bandwidth를 줄일 수 있으며, 개별 client의 update가 다른 수백 혹은 수천개의 update들을 평균내기 전에 감시될 수 없도록 만들기 위해 적용된 암호화 protocol은 upload에 필요한 bit의 양을 훨씬 증가시킨다.

위와 같은 이유로 uplink communication cost를 줄일 수 있는 method를 찾는 것이 중요한데, 본 논문에서 저자는 다음의 두 가지 일반적인 접근 방식에 대해 연구했다.

• Structured updates
  Directly learn an update from a restricted space that can be parametrized using a smaller number of variables
• Sketched updates
  Learn a full model update, then compress it before sending to the server

이들은 이후 더 자세히 설명할 것이고, 둘을 결합하여 사용할수도 있다. 예를 들어 먼저 structured update를 배우고, sketching을 진행하는 것이다. (논문에서 이를 실험해보지는 않음)

이제 논문에서 다루는 problem을 더 자세히 알아보자. FL의 목적은 많은 client들에 나뉘어 저장되어 있는 data를 통해 얻은 parameter들이 포함된 real matrix $\mathbf{W}\in\mathbb{R}^{d_1 \times d_2}$를 이용, model을 학습하는 것이다.

먼저 FL의 communication-naive version을 보자. Round $t\geq 0$에서 server는 current model $\mathbf{W}_t$ 를 $n_t$ 명의 clients 로 구성된 subset $S_t$에게 분배한다. 이 client들은 local data를 바탕으로 model을 독립적으로 update 하게 되는데, update된 local model을 각각 $\mathbf{W}_t^1, \mathbf{W}_t^2, \cdots, \mathbf{W}_t^{n_t}$ 라 두면, client $i$ 의 update는 다음과 같다.

이러한 update는 한 client에 대해 계산된 single gradient가 될 수 있지만, 일반적으로는 보다 더 복잡한 연산을 사용한다. (예를 들면, client의 local dataset에 대한 multiple steps of SGD)

어떤 경우에 대해서도 선택된 각 client는 update를 server에게 다시 전송하고, global update는 client 측의 update를 모두 종합하여 계산하는 방식으로 이루어진다.

Learning rate $\eta_t$는 server가 선택하는 것인데 여기서는 편의를 위해 $\eta_t = 1$ 로 둔다.

이후의 section에서는 neural network (NN)을 위한 FL을 다루는데, 이때 우리는 각 layer의 parameter들을 표현하기 위해 분리된 2D matrix $\mathbf{W}$를 사용하고 $d_1$과 $d_2$는 각각 output, input 차원을 나타낸다. 참고로, FC layer의 parameter들은 자연스럽게 2D 행렬들로 표현된다. 하지만 convolutional layer의 kernel은 $\# \textrm{ of input} \times \textrm{width} \times \textrm{height} \times \# \textrm{ of output}$ 모양의 4D tensor이다. 이러한 경우 $\mathbf{W}$는 기존 kernel의 형태에서 $\left( \# \textrm{ of input} \times \textrm{width} \times \textrm{height} \right) \times \# \textrm{ of output}$ 의 모양으로 reshape 된다.

Outline and summary

FL에서 communication efficiency를 증대시키기 위한 목표는, 제한된 internet 연결과 계산 가능성 환경 아래서 많은 client들에 나뉘어 저장되어 있는 data로 학습하는 한편 $\mathbf{H}_t^i$ 를 서버로 전송하는 것에 대한 cost를 줄이는 것이다. 이에 논문에서는 2가지 general approach를 제안하고, 실험을 통해 deep neural network를 학습시키는 과정에서 이 방법들이 미치는 효과를 검증해본다.

저자는 이러한 기법들이 FedAvg 알고리즘의 수렴에 미치는 영향을 CIFAR data를 이용한 실험을 통해 조사했고, 그 결과 약간의 수렴 속도 감소와 함께 통신에 필요한 data 양을 100배 단위로 감소시킬 수 있었다.

이는 기존의 CIFAR data size 보다 작은 양의 정보를 주고 받음에도 모든 convolutional model에 대해 좋은 prediction 정확도를 얻을 수 있도록 한다.

User-partitioned text data를 기반으로 진행한 보다 더 현실적인 실험에서는 모든 사용자가 가지고 있는 data를 한번 사용하기도 전에, 다음 단어의 예측을 위한 RNN을 효과적으로 학습시킬 수 있다는 것을 보였다.

마지막으로 주목할만한 점은 저자가 structured random rotation을 통한 update의 전처리 과정을 포함하여 가장 좋은 결과를 얻었다는 것이다. 이 단계의 실용성은 우리의 setting에 유일하다. 왜냐하면 random rotation을 적용시키는 것에 대한 cost가 SGD를 병렬 구현하는 보통의 경우에는 dominant 할 수 있지만, FL에서의 local training과 비교했을 때는 무시할 수 있는 수준이기 때문이다.

Reference

Konečný, Jakub, et al. "Federated learning: Strategies for improving communication efficiency." arXiv preprint arXiv:1610.05492 (2016).