분산 최적화·Local Drift와 통신

통신이 기울기를 평가하는 점을 바꾼다

두 worker의 목적을 F₁(w)=(w+1)²/2, F₂(w)=κ(w−1)²/2로 두자. 전역 목적은 같은 가중치의 평균이다. 전역 최적점은 (κ−1)/(κ+1)이며, 곡률이 다르면 지역 최소점 두 개의 단순 평균과 다르다.

각 round는 두 worker를 같은 broadcast 점에서 시작시킨다. 각각 정확한 지역 기울기로 E번 갱신한 뒤 끝점을 평균한다. 비교하는 중앙 알고리즘은 round당 전체 GD를 E번 수행한다. 성분 기울기 평가 수는 같지만 중간 평가점이 다르다. 비동기 지연·압축·확률 batch·불균등 가중치는 모형화하지 않는 동기식 결정론 예제다.

한 번만 갱신하면 같은 이유

E=1이면 w−η∇Fᵢ(w)의 평균이 w−η∇F(w)다. 같은 초기점에서는 중앙과 지역 궤적이 정확히 일치한다. 모든 기울기를 같은 점에서 평가하고 목적함수 가중치도 맞춘다는 조건이 중요하다.

E>1이면 worker가 통신 사이에 서로 다른 목적을 따라간다. 끝점을 한 번 평균하는 것과 매 중간 단계에서 기울기를 평균하는 것은 일반적으로 다르다. 이를 local drift라고 부르며 평균 연산의 수치 오류가 원인은 아니다.

Round map과 고정점 유도

지역 곡률 hᵢ, 최소점 aᵢ인 이차함수에서

Aᵢ=(1−ηhᵢ)ᴱ, mᵢ=1−Aᵢ로 쓰고 a₁=−1,a₂=1을 넣으면

마지막 식은 분모가 0이 아닐 때만 유효하다. η=0이면 항등 map이라 모든 점이 고정점이고 유일한 고정점은 없다. 대수적 고정점이 존재해도 거기로 수렴하려면 |A|<1이어야 한다. 불안정 고정점을 궤적의 예측값으로 읽지 말자.

수렴해 보여도 남는 편향

κ=4,η=0.1에서 E=1의 고정점은 전역 최적점 0.6이다. E=4이면 m₁=1−0.9⁴=0.3439, m₂=1−0.6⁴=0.8704이므로 고정점은 약 0.433583이다. A≈0.39285라 round map은 수축하지만 극한의 전역 기울기는 0이 아니다.

통신 round 수열의 수렴이 의도한 전역 목적의 최적화를 뜻하지 않는 실제 반례다. 같은 곡률에서는 이 고정점 편향이 사라진다. 따라서 지역 계산을 늘리는 것이 언제나 좋거나 언제나 나쁘다고 일반화할 수 없다.

직접 풀기와 풀이

w₀=0,κ=4,η=0.1,E=4로 여덟 round를 수행하자. 지역 평균은 약 0.433337, 중앙 GD는 약 0.599940에 이른다. 지역 평균에서 전역 기울기는 약 −0.416657이다. 뒤쪽 round의 점 변화가 작다는 종료 기준만으로 왜 충분하지 않은지 설명하자.

E=1과 E=4를 같은 총 기울기 계산량에서 비교하도록 round 수를 조절하고 통신 예산과 계산 예산을 함께 기록하자. 분산 학습 연구에서는 이질성·동기화·집계 가중치·어느 목적의 정상성을 측정하는지를 명시해야 한다.

더 읽기: Bottou, Curtis와 Nocedal.