[Abstract]

SGD는 병렬처리를 할 수 있어 좋지만, 통신에 cost가 많이 들어간다. 이에 대응하기 위해 양자화된 gradient만 통신하는 방법이 제안되었는데, 이는 항상 수렴하지는 않는다. 이 논문에서 제안된 QSGD는 수렴을 보장하고 좋은 성능을 가진다. 이 방법을 이용하면 통신 대역과 수렴 시간에 대한 trade-off를 마음대로 할 수 있다. 각 노드들은 반복 당 몇 비트를 보낼지 조절할 수 있는데, 그러면 분산과의 trade-off가 있다. 이 방법은 딥러닝 학습에서의 시간을 줄여준다.

[1] Introduction

SGD에서의 gradient를 보내는 작업은 상당한 bottleneck이 되는데, 이를 줄이기 위한 precision을 줄이는 방법과 gradient의 부호만 보내는 방법이 있었는데, 이들은 특정 조건에서만 수렴했다.

[3] Quantized Stochastic Gradient Descent (QSGD)

[3.1] Generalized Stochastic Quantization and Coding

Stochastic Quantization

양자화 함수는 $Q_s(v)$로 나타내며, $s$는 $0$부터 $1$까지를 $s$개로 나눌 것이라는 파라미터이다. 모든 벡터 $v$에 대하여 $Q_s(v)$는 unbiasedness, variance bound, sparsity가 증명되었다.

Efficient Coding of Gradients

$Q_s(v)$는 튜플 로 표현될 수 있다. 그리고 Elias coding을 사용하는데, $k$를 elias coding한다고 하면 우선 $k$를 이진수로 표현하고, length를 그 뒤에 붙인다. 그리고 바로 앞에 있는 것을 반복적으로 encoding하는데, 매우 효율적이다. 양자화 레벨 $s$로 양자화된 를 하나의 string $S$로 encoding한다면, 처음 32비트로 를 encode하고, $\sigma_i$, $\text{Elias}(\zeta_i)$를 반복적으로 붙인다. 이렇게 하면 $Q_s(\tilde{g}(x))$를 encoding하는 데에 필요한 비트수는 를 넘지 않는다. dense한 gradient에 대해서는 $s=\sqrt(n)$으로 encoding하는데, 이 때 필요한 비트수는 최대 $2.8n+32$이다.

[3.2] QSGD Guarantees

QSGD를 $K$개의 프로세서에서 실행한다고 하면, 한 회당 $2.8n+32$번의 통신만을 사용한다. 이것은 매우 효율적이고, non-convex SGD에도 사용할 수 있다.

[3.3] Quantized Variance-Reduced SGD

SVRG를 업데이트할 때 QSGD를 사용해도 같은 수렴 한계를 얻을 수 있다. 적절한 수를 선택하면, 각 epoch당 $O(\kappa(\frac{\log 1}{\epsilon}+n))$의 통신만 사용하면 된다.

[5] Experiments

Communication vs. Computation

먼저, 네트워크들을 communication-intensive(AlexNet, VGG, LSTM)과 computation-intensive(Inception, ResNet)로 나누었는데, 두 부류 다 통신을 줄이자 시간에서의 이득이 보였다.

Accuracy

4bit나 8bit QSGD는 충분히 높은 정확도를 보인다. 최근 발표된 논문에 따르면 gradient에 noise를 추가하는 것이 도움이 되는데, 이 논문의 방법도 zero-mean noise의 일종일 수 있다. 그러나 엄청나게 비트수를 줄이는 것은 정확도에 해가 될 수 있다. 한가지 이슈는, 특정 layer는 양자화에 특히 민감할 수 있다는 것이다. convolution layer의 비트수를 많이 줄이면(2bit QSGD) 정확도 손실을 가져온다.